Versuchen, eine effizientere Möglichkeit zum Filtern von Dateien zu finden

Question

Angesichts einer Liste von deviceIds, ich versuche, eine effizientere Art der Behandlung von Duplikaten zu finden. Wenn ein Duplikat in der DeviceId-Liste gefunden wird, muss ich nur die letzte Datei behalten und die anderen löschen. Was ich bis jetzt erreicht habe, scheint in Ordnung zu sein, aber ich frage mich, ob es effizienter gemacht werden kann? Meine aktuelle Methode scheint nicht gut zu skalieren, zum Beispiel verarbeitet sie 25.000 Dateien in 5 Sekunden, benötigt aber 70 Sekunden für 100.000 Dateien. Irgendwelche Gedanken?

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:

implementiert ich TacticalCoders Lösung, die wunderbar funktioniert, Verarbeitung 100.000 Dateien in 0,60 Sekunden.

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

Meine aktuelle Methode scheint nicht gut zu skalieren, zum Beispiel, es verarbeitet 25.000 Dateien in 5 Sekunden, aber dauert 70 Sekunden 100.000 Dateien. Irgendwelche Gedanken?

Das ist, weil Sie ein O (n^2) Algorithmus (es möglicherweise zu viel schlimmer ausarten können als O (n^2) wenn Sie meist Duplikate haben passieren, in dem Fall, dass Sie‘ d machen einen O (n log n) Sortieren Sie zusätzlich zu Ihren zwei for-Schleifen, aber ich nehme an, Sie haben nicht 100 000 Dateien im Grunde immer das gleiche Duplikat).

Wenn ich lese das Problem richtig konnte man nur einen ersten Durchgang tun, wo Sie eine Map < String, List < Datei bauen würde >> (wo der Schlüssel würde die (Teil-) Zeichenkette an die Geräte-ID entspricht) .

Nach diesem ersten Durchlauf würde sich jede Datei mit einem Duplikat in einer Liste mit mindestens zwei Einträgen befinden, während jede Datei ohne Duplikat in einer eigenen Liste wäre.

Sie würden dann über Ihre Karte durchlaufen und Sie jedes Mal eine Liste < Datei> mit mehr als einem Eintrag finden, dann sortieren Sie diese Liste nach dem Datum und löschen alle, aber die aktuelle Version der Datei.

Würde das funktionieren?

EDIT Sie müssen vorsichtig mit Ihren Geräte-IDs sein: Ich weiß überhaupt nicht, wie sie aussehen, aber wenn eine ID sein kann, sagen wir "nop100" und eine andere Geräte-ID kann sagen, " nop1000 ", dann, wenn Sie" nop100 "vor" nop1000 "verarbeiten, können Sie Probleme mit Ihrem Aufruf der Methode haben (weil" nop1000 "fälschlicherweise mit der Geräte-ID von" nop100 "Geräten übereinstimmt). Soweit ich das beurteilen kann, existiert dieses Problem auch in dem von Ihnen geposteten Teilcode. Es gibt natürlich Workarounds, aber es ist schwierig, weiter zu gehen, ohne mehr über die Art der zu verarbeitenden Dateinamen zu erfahren.