logo标签列表

比较List<string>是否包含字符串C#

c#listcomparebig-ocontains
3

我有两个包含字符串的列表，每个列表都存储路径信息。 List1 包含每个文件的完整 UNC 路径。 List2 包含每个路径的缩短版本。

我正在尝试使用来自 List2 的部分路径信息构建字典作为键，并将来自 List1 的完整路径信息作为值。

例如：

List1 = { "\\\\some\path111\to\file1.txt", "\\\\some\path222\to\file2.txt", "\\\\some\path333\to\file3.txt" };
List2 = { "\to\file3.txt", "\to\file2.txt", "\to\file1.txt" };

比较的预期结果：

{\to\file1.txt, \\\\some\path111\to\file1.txt}
{\to\file2.txt, \\\\some\path111\to\file2.txt}
{\to\file3.txt, \\\\some\path111\to\file3.txt}

我成功地编写了我需要的功能，但运行速度非常慢（见下文）。我想知道是否有任何方法可以加快速度或在不同的集合中存储信息以获得更快的匹配。这两个列表各包含大约500,000个字符串。
private Dictionary<string, string> FullPathBuilder(List<string> partialPathList, List<string> fullPathList)
{
    Dictionary<string, string> result = new Dictionary<string, string>();
    try
    {
        foreach (string partPath in partialPathList)
        {
            foreach (string matchedFullPath in fullPathList.Where(s => s.Contains(partPath)))
            {
                if (ThirdPartyRepackVariables.cancelQC)
                {
                    break;
                }

                // get the match.  
                if (matchedFullPath != null)
                {
                    if (!result.ContainsKey(partPath))
                    {
                        result.Add(partPath, matchedFullPath);
                        ThirdPartyRepackVariables.pathsUpdated++;
                    }
                }
                else
                {
                    result.Add(partPath, partPath);
                    ThirdPartyRepackVariables.unmatchedPaths.Add(partPath);
                }
            }
        }
    }
    catch (Exception ex)
    {
        MessageBox.Show(ex.Message, "Error building path cross reference");
    }
    return result;
}
你是自己创建这些列表的吗？还是从文件或其他地方读取的？ - Dmytro Shevchenko
这些项目有特定的顺序吗？ - Yar
是的，列表是在之前创建的。部分路径是从我正在处理的数据中获取的，完整路径列表是通过遍历目录来创建的。 - complhex
我的意思是，你能否将List1的第一项与List2的第一项匹配？ - Yar
它们没有特定的顺序。我认为它们不总是一对一的匹配。 - complhex
显示剩余2条评论
5个回答
4

您目前的实现需要循环遍历500,000个项目(您的外部foreach循环)。对于每个项目，您会查看内部集合中的500,000个项目(您的Where语句)以查找匹配项。

假设完整路径总是以部分路径结尾(即部分路径始终包括完整文件名)，则可以通过按照路径的相反顺序对两个列表进行排序来加快速度。

排序后两个列表按照相同的顺序排列，可以使您在第二个列表上进行循环的时间缩短。

1
不需要1对1匹配。只要完整路径大于部分路径（按字符串反向排序），就可以停止搜索。即使没有匹配或多个匹配，仍然可以获得性能提升。 - Tim Copenhaver
这是一个很好的解决方案。如果您反转两个列表中的字符串并对其进行排序，那么您可以执行标准合并以查找匹配项。 - Jim Mischel
@Abbodanza，我不确定我理解你的例子。在你的例子中，这两个值将相互匹配，因此合并逻辑（大于比较）不会发挥作用。 - Tim Copenhaver
1

解决方案

根据Tim Copenhaver的优秀建议对输入列表进行排序，我编写了一个执行所需合并操作的函数：

public static IDictionary<string, string> MergePaths(
    IEnumerable<string> partialPaths, IEnumerable<string> fullPaths)
{
    var sortedPartialPaths = partialPaths
        .Select(p => new { Original = p, Reverse = p.Reverse() })
        .OrderBy(p => p.Reverse)
        .ToList();

    var sortedFullPaths = fullPaths
        .Select(p => new { Original = p, Reverse = p.Reverse() })
        .OrderBy(p => p.Reverse)
        // Capture the index of each full path so we can skip full paths later.
        .Select((p, i) => new { p.Original, p.Reverse, Index = i })
        .ToList();

    var lastFullPathIndex = 0;

    return sortedPartialPaths.ToDictionary(
        pp => pp.Original,
        pp => 
        {
            var matchedFullPath = sortedFullPaths
                // Skip all full paths that have already been matched.
                .Skip(lastFullPathIndex)
                // Skip all full paths that are smaller in terms of string sort order.
                .SkipWhile(fp => fp.Reverse.CompareTo(pp.Reverse) < 0)
                // Only take the full paths that end with the matching partial path. 
                // Should only take one. If there are more the rest will be discarded.
                .TakeWhile(fp => fp.Reverse.StartsWith(pp.Reverse))
                .FirstOrDefault();

            // Update the index of our last match.
            lastFullPathIndex = matchedFullPath?.Index ?? lastFullPathIndex;

            return matchedFullPath?.Original;
        });
}

请注意，它不使用框架版本的Skip()，而是使用这个IList<T>特定的实现：
public static IEnumerable<T> Skip<T>(this IList<T> list, int count)
{
    for (var i = count; i < list.Count; i++)
        yield return list[i];
}

原始版本速度太慢了，因为它实际上没有防止类型的多余枚举。
它还使用以下扩展方法来反转字符串：
public static string Reverse(this string s)
{
    var arr = s.ToCharArray();
    Array.Reverse(arr);
    return new string(arr);
}

性能

我使用了一个简单的1:1映射（如René Vogts answer中所述）作为性能基线。如果我们假设每个部分路径都可以匹配到恰好一个完整路径，则以下代码将表现最佳，即它将随着路径数量的增加而线性扩展（不包括排序）：

public static IDictionary<string, string> MergePathsOneToOne(
    IList<string> partialPaths, IList<string> fullPaths)
{
    var sortedPartialPaths = partialPaths.OrderBy(p => p.Reverse()).ToList();
    var sortedFullPaths = fullPaths.OrderBy(p => p.Reverse()).ToList();

    return Enumerable
        .Range(0, sortedPartialPaths.Count)
        .ToDictionary(
            i => sortedPartialPaths[i], 
            i => sortedFullPaths[i]);
}

在我的机器上，MergePathsOneToOne() 处理 500,000 条路径需要约 6-7 秒的时间。
然而，如果存在没有匹配到完整路径的部分路径，或者收集了根本不应该匹配的完整路径，则此方法将失败。
我的解决方案几乎与 1:1 版本一样快（处理 500,000 条路径需要 7-8 秒）。但更重要的是，它与 1:1 版本具有相同的可扩展性。
查看用于性能测试的代码：https://gist.github.com/bert2/de9ff3b347ac32d5cebecc4d8149a452 在那里，您还将找到 MergePaths() 的两个其他实现。一个是使用 LinkedList<T>，另一个是使用 List<T>.FindIndex(startIndex, predicate)，以跳过完整路径，但它们的性能提升并不明显。
请注意，性能测量结果仅供参考。由于热身不足、GC干扰和缺乏平滑处理，您无法比较绝对值。但它们应该让您了解每个算法在更改路径数量时的扩展能力。
1

我想到了几件事情：

  • contains 是一个非常慢的操作，因为你总是在匹配结尾，所以使用 EndsWith 进行检查。

  • 除非你期望有多个匹配（这是很可能的，但会破坏你的字典），否则你需要从未来的循环中排除匹配结果，还要在第一次匹配时退出当前循环。

  • 如果在比较之前对列表进行排序，则匹配更可能出现在循环的早期。

将其转换为代码，你会得到：

    //Test clocks at 137ms
    public static Dictionary<string, string> FullPathBuilderImproved(IEnumerable<string> partialPathList, IEnumerable<string> fullPathList)
    {
        Dictionary<string, string> result = new Dictionary<string, string>();
        partialPathList = partialPathList.OrderBy(s => string.Concat(s.Reverse()));
        List<string> unmatchedList = fullPathList.OrderBy(s =>string.Concat(s.Reverse())).ToList();

        foreach (string partPath in partialPathList)
        {
            string matchedFullPath = unmatchedList.FirstOrDefault(f => f.EndsWith(partPath));
            if (matchedFullPath != null)
            {
                result.Add(partPath, matchedFullPath);
                unmatchedList.Remove(matchedFullPath);
            }
            else
            {
                result.Add(partPath, partPath);

            }
        }
        return result;
    }

您的代码运行时间为20秒

两个测试都使用此代码生成测试数据

    IEnumerable<string> partial = Enumerable.Range(0, 10000).Select(i => System.IO.Path.GetRandomFileName()).ToList();
    IEnumerable<string> full = partial.Select(i => System.IO.Path.Combine( System.IO.Path.GetTempPath(),i)).ToList();

编辑：在审查中，我认为Abbondanza的反转函数比我使用的反转连接更快。

0

我认为一个好的方式是这样的：

Dictionary<string, string> result = List2.ToDictionary(s => s, 
                       s => List1.FirstOrDefault(f => f.EndsWith(s)) ?? s);

但我不擅长确定执行时间的行为。它会一次迭代修剪路径列表。但是对于每个修剪路径，都会扫描完整路径列表以查找匹配元素。所以我猜它大约是O(n*logn)（尽管我甚至不知道这个符号是否正确）。

要更新ThirdPartyRepackVariables的另外两个属性，您可以像这样更改代码：

Dictionary<string, string> result = List2.ToDictionary(s => s, 
                       s =>
                       {
                           string v =  List1.FirstOrDefault(f => f.EndsWith(s));
                           if (v == null)
                           {
                               ThirdPartyRepackVariables.unmatchedPaths.Add(s);
                               return s;
                           }
                           ThirdPartyRepackVariables.pathsUpdated++;
                           return v;
                       });
如果您有一对一的匹配（即每个修剪路径都有一个完整路径，反之亦然），您可以像Tim Copenhaver建议的那样首先对列表进行排序：
var sortedList1 = list1.OrderBy(s => new string(s.Reverse().ToArray())).ToList();
var sortedList2 = list2.OrderBy(s => new string(s.Reverse().ToArray())).ToList();

然后将它们简单地转换为字典：

Dictionary<string, string> result = Enumerable.Range(0, sortedList1.Count)
                       .ToDictionary(i => sortedList2[i], i => sortedList1[i]);
我会尝试一下，谢谢！我该如何返回这两个值以添加到字典集合中？ - complhex
@complhex 我不明白，字典是由 ToDictionary 创建的，第一个 lambda 返回键（修剪后的路径），第二个返回值（匹配的完整路径或修剪后的路径）。 - René Vogt
抱歉，我误解了。只是在适应LINQ / Lambda - 这些东西总是让我感到困惑 - complhex
@complhex 添加了一个版本，该版本还会更新您的 ThirdPartyRepackVariables 属性。 - René Vogt
0

实现这个的一种方法是使用Aho-Corasick字符串匹配算法。我在https://www.informit.com/guides/content.aspx?g=dotnet&seqNum=869上有一个实现。

以下是如何使用它：

// build the automaton
var matcher = new AhoCorasickStringSearcher();
foreach (var partial in partialList)
{
    matcher.AddItem(partial);
}
matcher.CreateFailureFunction();

// now search each line . . .
foreach (var line in fullPaths)
{
    var matches = matcher.Search(line);
    // here, if matches contains items, you can add them to your dictionary
}

这应该会非常快地执行。

您需要阅读文章以了解如何使用它的更多细节，但这就是要点。

话虽如此，建议先反转字符串并排序，然后运行标准合并算法是一个不错的选择。它易于实现，而且很可能更快。

这个链接只是带我到了informit.com的起始页，找不到指南。 - Mattias
@mattias：不幸的是，该指南已不存在。 - Jim Mischel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接