Попытка найти более эффективный способ фильтрации файлов

Question

Учитывая список устройств, я пытаюсь найти более эффективный способ обработки дубликатов. Когда дубликат найден в списке deviceId, мне нужно сохранить только последний файл и удалить остальные. То, что я придумал, похоже, работает нормально, но мне интересно, можно ли сделать его более эффективным? Мой текущий метод, похоже, не очень хорошо масштабируется, например, он обрабатывает 25 000 файлов за 5 секунд, но занимает 70 секунд для 100 000 файлов. Есть предположения?

List<File> filteredList; 
     for(int i = 0; i < deviceIds.size(); i++) { 
      if(i < (deviceIds.size()-1) && deviceIds.get(i).equals(deviceIds.get(i+1))) { 
       filteredList = Lists.newArrayList(Iterables.filter(fileList, new DeviceIdFilter(deviceIds.get(i)))); 
       Collections.sort(filteredList, new OldestFileComparator()); 
       for(int t = 0; t < (filteredList.size()-1); t++) { 
        filteredList.get(t).delete(); 
       } 
      } 
     } 

private static class DeviceIdFilter implements Predicate<File> { 
    private String deviceId; 
    private DeviceIdFilter(final String deviceId) { 
     this.deviceId = deviceId; 
    } 
    @Override 
    public boolean apply(final File file) { 
     return file.getName().contains(deviceId); 
    } 
} 

public class OldestFileComparator implements Comparator<File> { 
    public int compare(File filea, File fileb) { 
     if (filea.lastModified() > fileb.lastModified()) { 
      return +1; 
     } else if (filea.lastModified() < fileb.lastModified()) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

Edit:

Я реализовал TacticalCoders решение, которое работало замечательно, обработку 100000 файлов в 0,60 секунды.

Map<String, List<File>> fileMap = new HashMap<String,List<File>>(); 
    String deviceId; 
    List<File> deviceFileList; 
    for(File file : fileList) { 
     deviceId = getDeviceId(file.getName()); 
     if(fileMap.containsKey(deviceId)) { 
      fileMap.get(deviceId).add(file); 
     } else { 
      deviceFileList = new LinkedList<File>(); 
      deviceFileList.add(file); 
      fileMap.put(deviceId, deviceFileList); 
     } 
    } 

    for (Map.Entry<String, List<File>> mapEntry : fileMap.entrySet()) { 
     deviceFileList = mapEntry.getValue(); 
     if(deviceFileList.size() > 1) { 
      Collections.sort(deviceFileList, new OldestFileComparator()); 
      for(int t = 0; t < (deviceFileList.size()-1); t++) { 
       deviceFileList.get(t).delete(); 
      } 
     } 

Answer 1

Мой текущий метод не кажется, хорошо масштабируется, например, обрабатывает 25000 файлов в 5 секунд, но занимает 70 секунд, 100000 файлов. Есть предположения?

Это потому, что у вас есть (п^2) алгоритм O (потенциально может вылиться в гораздо хуже, чем O (N^2), если вам посчастливилось иметь в основном дубликаты, в этом случае» d делать O (n log n) сортировать в дополнение к вашим двум для циклов, но я полагаю, у вас нет 100 000 файлов, которые в основном всегда одинаковы).

Если я прочитал эту проблему правильно, вы могли бы просто сделать первый проход, где вы бы построить Map < String, List < File >> (где ключ будет (суб) строка, соответствующая идентификатор устройства) ,

После этого сначала передайте каждый файл, который имеет дубликат, в списке с по меньшей мере двумя записями, в то время как каждый файл, который не имеет дубликатов, будет в своем собственном списке.

Вы бы затем перебрать карту и каждый раз, когда вы нашли List < Файл> с более чем одной записи, то вы сортировать этот список в соответствии с датой и удалить все, кроме последнего файла.

Будет ли это работать?

EDIT вы должны быть осторожны с идентификаторами устройств: Я не знаю, на все то, что они похожи, но если один идентификатор может быть, скажем, «nop100» и другое устройство ID может быть, скажем, " nop1000 ", то, если вы обработаете« nop100 »до« nop1000 », у вас могут возникнуть проблемы с вашим содержит вызов метода (поскольку« nop1000 »ошибочно соответствует идентификатору устройства устройств« nop100 »). Насколько я могу судить, эта проблема существует и в частичном коде, который вы опубликовали. Конечно, есть обходные пути, но трудно идти дальше, не зная больше о типах файлов, которые вы обрабатываете.