c# - 处理 list 需要太多时间

Question

这是我的类(class):

public class Record
{
   public string PersonName {get; set;}
   public string RequestID {get; set;}
}

我有一个与此类相关的数据库表，并且我在开始时将其全部拉入内存。我正在尝试使用以下算法找到两个人之间的关系:

1. 我选择两个人(我的意思是该列表中的记录，两个属性可以有多个记录)
2. 我列出了第一个人的 RequestID
3. 对于每个 RequestID，我列出具有相同 RequestID 的用户
4. 对于每个用户，我都会检查该用户是否与第二个用户具有相同的 RequestID。
5. 如果发现，请破坏并执行操作。

这是我对上述算法的实现:

foreach(var elem in listofFirstPerson)
{
  List<Record> listofRelatedPeople = RecordList.Where(r => r. RequestID == elem.RequestID).ToList(); //I actually get distinct records from actual list and the distinct version count is about 100k

  foreach(var relatedPerson in listofRelatedPeople )
  {
    List<Record> listofRecordsforRelatedPerson = RecordList.Where(r => r. PersonName ==  relatedPerson.PersonName).ToList();

    for(int i = 0; i < listofRecordsforRelatedPerson.Count; i++)
    {
      for(int j = 0; j < listofSecondPerson.Count; j++)
      {
       if(listofRecordsforRelatedPerson[i].RequestID ==listofSecondPerson[j].RequestID)
        //break all loops and do stuff
      }
    }
  }
}

这个算法有效。但它的速度慢得令人难以置信。正如我提到的，listofRelatedPeople 大约有 100k，并且它在大约 20 秒内仅迭代了几百条记录。我怎样才能使这个算法更快？有更快的方法吗？提前致谢。

编辑:

在我的列表中有这样的记录:

• 姓名:“Jason”请求 ID:“1”
• 姓名:“Larry”请求 ID:“1”
• 姓名:“Kevin”请求 ID:“7”
• 姓名:“Joshua”请求 ID:“4”
• 姓名:“Tom”请求 ID:“1”
• 姓名:“Tom”请求 ID:“7”
• 姓名:“Ben”请求ID:“7”

假设我选择 Jason 和 Kevin，如您所见，他们的请求 ID 不同，所以我需要找到他们之间的关系。因此，我列出了具有相同 RequestID 的用户，他们是 Larry 和 Tom。然后我获取了 Larry 的所有记录，发现他没有与 Kevin 具有相同 RequestID 的记录。因此我转到 Tom，我发现 Tom 与 Kevin 具有相同的 RequestID，所以我选择 >汤姆就完成了。

Answer 1

据我了解，您当前的算法可以用 LINQ 表示如下:

static Record FirstRelated(List<Record> records, string firstName, string secondName)
{
    var listofFirstPerson = records.Where(r => r.PersonName == firstName).ToList();
    var listofSecondPerson = records.Where(r => r.PersonName == secondName).ToList();
    var result = (
        from r1 in listofFirstPerson // (1)
        from r2 in records //(2)
        where r2.RequestID == r1.RequestID
        from r3 in records // (3)
        where r3.PersonName == r2.PersonName
        from r4 in listofSecondPerson // (4)
        where r4.RequestID == r3.RequestID
        select r2
    ).FirstOrDefault();
    return result;
}

所以基本上你有 4 个嵌套循环。如果我们指定

N = records.Count
M1 = listofFirstPerson.Count
M2 = listofSecondPerson.Count

那么算法的时间复杂度将为O(M1 * N * N * M2)，N较大时通常会导致性能问题。

查看上面的实现，可以注意到，通过将 (1) 与 (2)、(3) 与 (4) 合并并通过 PersonName 关联结果集，可以获得相同的结果>:

var firstRelated =
    from r1 in listofFirstPerson
    from r2 in records
    where r2.RequestID == r1.RequestID
    select r2;
var secondRelated =
    from r4 in listofSecondPerson
    from r3 in records
    where r3.RequestID == r4.RequestID
    select r3;
var result = (
    from r1 in firstRelated
    from r2 in secondRelated
    where r2.PersonName == r1.PersonName
    select r1
).FirstOrDefault();

到目前为止，我们没有改进任何东西 - 算法仍然是相同的二次时间复杂度。但它给了我们这样的想法 - 由于现在 firstRelated 和 secondRelated 是独立的，因此不需要为每个记录执行 secondRelated 的 firstRelated，因此我们可以提前从 secondRelated 准备一个快速哈希查找数据结构(平均查找时间复杂度为 O(1))，并且在迭代一次 firstRelated 时使用它，从而获得更好的 O(M1 * N) 时间复杂度(几乎就像消除代码中导致缓慢的最后两个内部循环的成本)。

另请注意，我们不再需要构建两个初始列表，因为我们将仅处理 firstRelated 和 secondRelated 一次。

所以最终的解决方案将是这样的:

var firstRelated =
    from r1 in records
    where r1.PersonName == firstName
    from r2 in records
    where r2.RequestID == r1.RequestID
    select r2;
var secondRelated =
    from r4 in records
    where r4.PersonName == secondName
    from r3 in records
    where r3.RequestID == r4.RequestID
    select r3;

现在可以使用 LINQ join 运算符为我们进行有效的关联:

var result = (
    from r1 in firstRelated
    from r2 in secondRelated
    where r2.PersonName == r1.PersonName
    select r1
).FirstOrDefault();

或者通过准备并使用 HashSet 以及 secondRelated 中的 PersonName 来手动执行此操作:

var secondRelatedNames = new HashSet<string>(secondRelated.Select(r => r.PersonName));
var result = firstRelated.FirstOrDefault(r => secondRelatedNames.Contains(r.PersonName));