c# - 删除列表中包含另一个的名称

Question

我有一个文件，每一行都有 "Name|Number"，我想删除列表中名称包含另一个名称的行。例如，如果文件中有 "PEDRO|3"、 "PEDROFILHO|5"、 "PEDROPHELIS|1"，我想删除行 "PEDROFILHO|5"、 "PEDROPHELIS|1"。

列表有 180 万行，我是这样写的，但是太慢了:

List<string> names = File.ReadAllLines("firstNames.txt").ToList();
List<string> result = File.ReadAllLines("firstNames.txt").ToList();

foreach (string name in names)
{
    string tempName = name.Split('|')[0];
    List<string> temp = names.Where(t => t.Contains(tempName)).ToList();
    foreach (string str in temp)
    {
        if (str.Equals(name))
        {
            continue;
        }
        result.Remove(str);
    }
}
File.WriteAllLines("result.txt",result);

有谁知道更快的方法吗？或者如何提高速度？

Answer 1

由于您要在单词中到处寻找匹配项，因此您最终会使用 O(n²) 算法。您可以稍微改进实现以避免列表中的字符串删除，这本身就是一个 O(n) 操作:

var toDelete = new HashSet<string>();
var names = File.ReadAllLines("firstNames.txt");
foreach (string name in names) {
    var tempName = name.Split('|')[0];
    toDelete.UnionWith(
        // Length constraint removes self-matches
        names.Where(t => t.Length > name.Length && t.Contains(tempName))
    );
}
File.WriteAllLines("result.txt", names.Where(name => !toDelete.Contains(name)));