Улучшить производительность сортировки файлов по расширению - PullRequest
Новая
       42

Улучшить производительность сортировки файлов по расширению

1 голос
/ 21 мая 2010

С данным массивом имен файлов самый простой способ сортировки по расширению файла выглядит так: 

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

Проблема в том, что в очень длинном списке (~ 800 КБ) сортировка занимает очень много времени, а сортировка по всему имени файла происходит быстрее на пару секунд!

Теоретически, есть способ оптимизировать его: вместо использования Path.GetExtension() и сравнения вновь созданных строк только для расширений, мы можем предоставить Сравнение, чем сравнение существующих строк имени файла, начиная с LastIndexOf('.'), без создания строки.

Теперь предположим, что я нашел LastIndexOf('.'), я хочу повторно использовать нативный StringComparer .NET и применить его только к части строки после LastIndexOf('.'), чтобы сохранить все культурные соображения. Не нашел способа сделать это.

Есть идеи?

Edit:

С идеей tanascius использовать метод char.CompareTo(), я пришел с моим Uber-Fast-File-Extension-Comparer, теперь он сортируется по расширению в 3 раза быстрее! это даже быстрее, чем все методы, которые каким-то образом используют Path.GetExtension(). что ты думаешь?

Редактировать 2:

Я обнаружил, что в этой реализации не учитывается культура, поскольку метод char.CompareTo() не учитывает культуру, поэтому это не идеальное решение.

Есть идеи? 

    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;
        }
    }

Ответы [ 4 ]

1 голос
/ 21 мая 2010

Не самая эффективная память, но самая быстрая по моим тестам: 

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();

Сделал мини-тест на 800k случайно сгенерированных 8.3 имен файлов:

Сортировка предметов с помощью Linq to Objects ... 00: 00: 04.4592595

Сортировка элементов с помощью SortedDictionary ... 00: 00: 02.4405325

Сортировка элементов с помощью Array.Sort ... 00: 00: 06.6464205

1 голос
/ 21 мая 2010

Вы можете написать компаратор, который сравнивает каждый символ расширения. char тоже имеет CompareTo() ( см. Здесь ).

По сути, вы зацикливаетесь, пока у вас не останется больше символов в хотя бы одной строке или одна CompareTo() возвращает значение! = 0.

РЕДАКТИРОВАТЬ: В ответ на правки OP

Производительность вашего метода сравнения может быть значительно улучшена. Смотрите следующий код. Дополнительно я добавил строку 

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

для включения использования CultureInfo и CompareOptions. Однако это замедляет все по сравнению с версией, использующей простой char.CompareTo() (примерно в 2 раза). Но, согласно моему собственному вопросу SO , похоже, это путь. 

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++;
        }
    }
}

Использование: 

fileNames1.Sort( new ExtensionComparer( CultureInfo.GetCultureInfo( "sv-SE" ),
                    CompareOptions.StringSort ) );
1 голос
/ 21 мая 2010

Создайте новый массив, который содержит каждое из имен файлов в формате ext.restofpath (или какой-то формат пары / кортежа, который может по умолчанию сортироваться по расширению без дальнейшего преобразования). Сортируйте это, затем конвертируйте обратно.

Это быстрее, потому что вместо того, чтобы извлекать расширение много раз для каждого элемента (поскольку вы делаете что-то вроде N log N сравнения), вы делаете это только один раз (а затем перемещаете его назад один раз).

0 голосов
/ 21 мая 2010

Основная проблема заключается в том, что вы вызываете Path.GetExtension несколько раз для каждого пути. если это делает быструю сортировку, то можно ожидать, что Path.GetExtension будет вызываться в любом месте от log (n) до n раз, где n - количество элементов в вашем списке для каждого элемента в списке. Итак, вы захотите кэшировать вызовы Path.GetExtension.

если бы вы использовали linq, я бы предложил что-то вроде этого: 

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

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

...