c# - 在大列表中搜索要删除的项目

Question

我是 c# 的初学者并且有问题 - 有一个超过 100 万行的大列表(文本文件) - 结构是:

698563200209000258
698563200209000316
698563200225000019
698563200232000143
698563200235000199
698563200235000272
698563200240*     
698563200293*     
698563200301000511
698563200304000849
698563200316000696
698563200328000825
698563200240000833
698563200328000841
698563200328000866
698563200328000882
698563200328000916
698563200328000940
698563200239000957
698563200328000965
698563200239000973
698563200328000981

我正在搜索由带星号的行组成的行来制作要删除的项目列表(带星号的除外)在上面的示例中，对于行:;698563200293* 结果应该是:698563200239000957 和 698563200239000973

我得到的代码是:

HashSet<string> fileHash = new HashSet<string>(textFile);
List<string> fileListToRemove = new List<string>();
string lineWithAsterisk;

foreach (string i in fileHash)
{ 
     if (i.Contains("*"))
     { 
         lineWithAsterisk = i.Substring(0, i.IndexOf("*"));
         var result = from singleA in fileHash.AsParallel()
                      where singleA.Substring(0, lineWithAsterisk.Length) == lineWithAsterisk
                      select singleA;
         fileListToRemove.AddRange(result.Skip(1).ToList());
    }
}

大约需要 1 小时才能完成(4 核 i7)- 请帮助我加快速度。

有什么建议吗？

Answer 1

原始代码的问题在于您要为文件中的每一行迭代整个数据集，从而导致复杂度为 O(n 平方)。

以下代码在 O(2*n + n log n) 时间内运行。不要忘记 using System.IO;

var textFile = File.ReadAllLines(); // O(n)

List<string> fileLines = new List<string>(textFile);
List<string> fileListToRemove = new List<string>();

// start with dummy line not in file
string lastLineWithAsterisk="************";
int asteriskLocation;

// Sort the file O(n log n)
fileLines.Sort();

// iterate backwards. The * will sort directly after the numbers it matches. 
// O(n)
for (int i=fileLines.Count()-1; i>=0; i--)
{ 
     asteriskLocation = fileLines[i].IndexOf('*');
     if(asteriskLocation != -1)
         lastLineWithAsterisk =  fileLines[i].SubStr(0,asteriskLocation);
     else
         if(fileLines[i].StartsWith(lastLineWithAsterisk))
             fileListToRemove.Add(fileLines[i]);
}

也可以使用并行 for 循环(每个线程必须有一个单独的 fileListToRemove 并在最后组合它们。)

编辑:解决原question在一分钟内使用以下代码:

var textFile = File.ReadAllLines(); // O(n)
var outFile = File.Create("C:\\outputfile.txt");
List<string> fileLines = new List<string>(textFile);


// start with dummy line not in file
string lastLineWithAsterisk="************";
int asteriskLocation;

// Sort the file O(n log n)
fileLines.Sort();

// iterate backwards. The * will sort directly after the numbers it matches. 
// O(n)
for (int i=fileLines.Count()-1; i>=0; i--)
{ 
     asteriskLocation = fileLines[i].IndexOf('*');
     if(asteriskLocation != -1)
     { 
       lastLineWithAsterisk=fileLines[i].SubStr(0,asteriskLocation);
     // Write the * lines
     outFile.WriteLine(fileLines[i]);
     }
     else
         // exclude matching lines
         if(!fileLines[i].StartsWith(lastLineWithAsterisk))
             outFile.WriteLine(fileLines[i]);

}
outFile.Close();
outFile.Dispose();

在这个版本中不需要并行化，因为限制因素是硬盘速度。

这假设输出顺序无关紧要。只需反转文件的顺序即可获得原始顺序。