Améliorer les performances de tri des fichiers par extension

Question

Avec un tableau donné des noms de fichiers, la plus simple façon de trier par extension de fichier est comme ceci:

Array.Sort(fileNames, 
    (x, y) => Path.GetExtension(x).CompareTo(Path.GetExtension(y))); 

Le problème est que sur très longue liste (~ 800k Il faut beaucoup de temps pour trier, alors que le tri par le nom de fichier entier est plus rapide pour quelques secondes! Théorique, il existe un moyen de l'optimiser: au lieu d'utiliser Path.GetExtension() et de comparer les nouvelles extensions uniquement, nous pouvons fournir une comparaison comparant les chaînes de fichiers existantes à partir du LastIndexOf('.') sans créer de nouvelles chaînes.

Maintenant, supposons que j'ai trouvé le LastIndexOf('.'), je veux réutiliser le StringComparer natif de .NET et l'appliquer seulement à la partie sur la chaîne après le LastIndexOf('.'), pour préserver toute considération de culture. N'a pas trouvé un moyen de le faire.

Des idées?

Edit:

Avec l'idée de tanascius d'utiliser la méthode char.CompareTo(), je suis venu avec mon Uber-Fast-File-Extension-Comparer, maintenant le tri par extension 3x fois plus rapide! il est encore plus rapide que toutes les méthodes qui utilisent Path.GetExtension() d'une certaine manière. Qu'est-ce que tu penses?

Edit 2:

Je trouve que cette mise en œuvre n'envisage la culture depuis la méthode char.CompareTo() ne considérer la culture, donc ce n'est pas une solution parfaite.

Des idées?

public static int CompareExtensions(string filePath1, string filePath2) 
    { 
     if (filePath1 == null && filePath2 == null) 
     { 
      return 0; 
     } 
     else if (filePath1 == null) 
     { 
      return -1; 
     } 
     else if (filePath2 == null) 
     { 
      return 1; 
     } 

     int i = filePath1.LastIndexOf('.'); 
     int j = filePath2.LastIndexOf('.'); 

     if (i == -1) 
     { 
      i = filePath1.Length; 
     } 
     else 
     { 
      i++; 
     } 

     if (j == -1) 
     { 
      j = filePath2.Length; 
     } 
     else 
     { 
      j++; 
     } 

     for (; i < filePath1.Length && j < filePath2.Length; i++, j++) 
     { 
      int compareResults = filePath1[i].CompareTo(filePath2[j]); 

      if (compareResults != 0) 
      { 
       return compareResults; 
      } 
     } 

     if (i >= filePath1.Length && j >= filePath2.Length) 
     { 
      return 0; 
     } 
     else if (i >= filePath1.Length) 
     { 
      return -1; 
     } 
     else 
     { 
      return 1; 
     } 
    } 

Answer 1

Créer un nouveau tableau contenant chacun des noms de fichiers au format ext.restofpath (ou une sorte de forme paire/tuple qui peut par défaut tri sur l'extension sans autre transformation). Triez cela, puis convertissez-le.

Ceci est plus rapide car au lieu d'avoir à récupérer l'extension plusieurs fois pour chaque élément (puisque vous faites quelque chose comme N log N compare), vous le faites seulement une fois (et ensuite le reculer une fois).

Answer 2

Vous pouvez écrire un comparateur qui compare chaque caractère de l'extension. char a aussi un CompareTo() (see here).

Fondamentalement, vous boucle jusqu'à ce que vous n'avez plus à gauche dans les caractères d'au moins une chaîne ou une CompareTo() retourne une valeur = 0.

EDIT: En réponse aux modifications de l'OP

Le les performances de votre méthode de comparaison peuvent être considérablement améliorées. Voir le code suivant. De plus, j'ai ajouté la ligne

string.Compare(filePath1[i].ToString(), filePath2[j].ToString(), 
       m_CultureInfo, m_CompareOptions); 

pour permettre l'utilisation de CultureInfo et CompareOptions. Cependant, cela ralentit tout par rapport à une version en utilisant un char.CompareTo() (à propos du facteur 2). Mais, selon mon own SO question cela semble être le chemin à parcourir.

public sealed class ExtensionComparer : IComparer<string> 
{ 
    private readonly CultureInfo m_CultureInfo; 
    private readonly CompareOptions m_CompareOptions; 

    public ExtensionComparer() : this(CultureInfo.CurrentUICulture, CompareOptions.None) {} 

    public ExtensionComparer(CultureInfo cultureInfo, CompareOptions compareOptions) 
    { 
     m_CultureInfo = cultureInfo; 
     m_CompareOptions = compareOptions; 
    } 

    public int Compare(string filePath1, string filePath2) 
    { 
     if(filePath1 == null || filePath2 == null) 
     { 
      if(filePath1 != null) 
      { 
       return 1; 
      } 
      if(filePath2 != null) 
      { 
       return -1; 
      } 
      return 0; 
     } 

     var i = filePath1.LastIndexOf('.') + 1; 
     var j = filePath2.LastIndexOf('.') + 1; 

     if(i == 0 || j == 0) 
     { 
      if(i != 0) 
      { 
       return 1; 
      } 
      return j != 0 ? -1 : 0; 
     } 

     while(true) 
     { 
      if(i == filePath1.Length || j == filePath2.Length) 
      { 
       if(i != filePath1.Length) 
       { 
        return 1; 
       } 
       return j != filePath2.Length ? -1 : 0; 
      } 
      var compareResults = string.Compare(filePath1[i].ToString(), filePath2[j].ToString(), m_CultureInfo, m_CompareOptions); 
      //var compareResults = filePath1[i].CompareTo(filePath2[j]); 
      if(compareResults != 0) 
      { 
       return compareResults; 
      } 
      i++; 
      j++; 
     } 
    } 
} 

Utilisation:

fileNames1.Sort(new ExtensionComparer(CultureInfo.GetCultureInfo("sv-SE"), 
        CompareOptions.StringSort)); 

Answer 3

le principal problème ici est que vous appelez Path.GetExtension plusieurs fois pour chaque chemin. Si cela fait un quicksort alors vous pouvez vous attendre à ce que Path.GetExtension soit appelé n'importe où de log (n) à n fois où n est le nombre d'éléments dans votre liste pour chaque élément dans la liste. Donc, vous allez vouloir mettre en cache les appels à Path.GetExtension.

si vous utilisez LINQ je suggère quelque chose comme ceci:

filenames.Select(n => new {name=n, ext=Path.GetExtension(n)}) 
     .OrderBy(t => t.ext).ToArray(); 

cela assure que Path.GetExtension est appelée une seule fois pour chaque nom de fichier.

Answer 4

Pas le plus efficace de la mémoire, mais le plus rapide selon mes tests:

SortedDictionary<string, List<string>> dic = new SortedDictionary<string, List<string>>(); 
foreach (string fileName in fileNames) 
{ 
    string extension = Path.GetExtension(fileName); 
    List<string> list; 
    if (!dic.TryGetValue(extension, out list)) 
    { 
     list = new List<string>(); 
     dic.Add(extension, list); 
    } 
    list.Add(fileName); 
} 
string[] arr = dic.Values.SelectMany(v => v).ToArray(); 

Est-ce un mini référence sur 800k générés au hasard 8.3: les noms de fichiers

Tri des éléments avec LINQ to Objects ... 00: 00: 04,4592595

articles de tri avec SortedDictionary ... 00: 00: 02,4405325

articles de tri avec Array.Sort ... 00: 00: 06,6464205