1

对于给定的文件名数组，按文件扩展名对其进行排序的最简单方法如下：

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

问题是在很长的列表（~800k）上排序需要很长时间，而按整个文件名排序会更快几秒钟！

理论上，有一种方法可以优化它：Path.GetExtension()我们可以提供一个比较，而不是使用和比较新创建的仅扩展名字符串，而不是比较现有的文件名字符串，LastIndexOf('.')而不创建新的字符串。

现在，假设我找到了LastIndexOf('.')，我想重用本机 .NET 的 StringComparer 并将其仅应用于 之后的字符串部分LastIndexOf('.')，以保留所有文化考虑。没有找到办法做到这一点。

有任何想法吗？

编辑：

有了 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

4 回答 4

1

根据我的测试，不是内存效率最高但速度最快的：

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 对项目进行排序到对象... 00:00:04.4592595

使用 SortedDictionary 对项目进行排序... 00:00:02.4405325

使用 Array.Sort 对项目进行排序... 00:00:06.6464205

于 2010-05-20T21:45:07.133 回答
1

您可以编写一个比较器来比较扩展名的每个字符。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 ) );
于 2010-05-20T21:26:25.610 回答
1

创建一个新数组，其中包含ext.restofpath格式中的每个文件名（或某种可以在扩展名上默认排序而无需进一步转换的某种对/元组格式）。对其进行排序，然后将其转换回来。

这更快，因为不必为每个元素多次检索扩展名（因为您正在执行N log N比较之类的操作），您只需执行一次（然后将其移回一次）。

于 2010-05-20T21:21:47.987 回答
0

这里的主要问题是您为每个路径多次调用 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 只为每个文件名调用一次。

于 2010-05-20T21:26:41.927 回答