二进制搜索更慢，我做错了什么

本文关键字：错了 什么 搜索 二进制 | 更新日期: 2023-09-27 18:21:50

EDIT：所以看起来这是正常的行为，所以有人能推荐一种更快的方法来完成这些众多的交叉吗？

所以我的问题是这个。我有8000个列表（每个列表中都有字符串）。对于每个列表（大小从50到400），我将其与其他列表进行比较，并根据交叉点编号进行计算。所以我会做

list1（相交）list1=数字

list1（相交）list2=编号

list1（相交）list888=编号

我对每个列表都这样做。以前，我有HashList，我的代码本质上是这样的：（嗯，我实际上是在搜索对象的属性，所以我不得不对代码进行一点修改，但基本上是这样的：

我下面有两个版本，但如果有人知道得更快，请告诉我！

循环浏览AllLists，获取每个列表，从list1开始，然后执行以下操作：

foreach (List list in AllLists)
{
    if (list1_length < list_length) //just a check to so I'm looping through the                  
                                    //smaller list
    {
        foreach (string word in list1)
        {
            if (block.generator_list.Contains(word))
            {
                //simple integer count
            }
        }
    }
// a little more code, but the same, but looping through the other list if it's smaller/bigger

然后，我将列表制作成常规列表，并应用Sort（），这将我的代码更改为

foreach (List list in AllLists)
{
    if (list1_length < list_length) //just a check to so I'm looping through the                  
                                    //smaller list
    {
        for (int i = 0; i < list1_length; i++)
        {
            var test = list.BinarySearch(list1[i]);
            if (test > -1)
            {
                //simple integer count
            }
        }
    }

第一个版本大约需要6秒，另一个版本需要20多秒（我只是停在那里，否则会需要一分钟以上！！）（这是针对数据的一小部分）

我确信某个地方有一个严重的错误，但我找不到。

二进制搜索更慢，我做错了什么

我已经尝试了三种不同的方法来实现这一点（假设我正确理解了这个问题）。请注意，我使用HashSet<int>是为了更容易地生成随机输入。设置：

List<HashSet<int>> allSets = new List<HashSet<int>>();
Random rand = new Random();
for(int i = 0; i < 8000; ++i) {
    HashSet<int> ints = new HashSet<int>();
    for(int j = 0; j < rand.Next(50, 400); ++j) {
        ints.Add(rand.Next(0, 1000));
    }
    allSets.Add(ints);
}

我检查了三种方法（代码在内部循环中运行）：

循环：

请注意，您在代码中得到了重复的结果（将集合A与集合B相交，稍后将集合B与集合A相交）。由于您正在进行列表长度检查，它不会影响您的性能。但以这种方式迭代更清晰。

for(int i = 0; i < allSets.Count; ++i) {
    for(int j = i + 1; j < allSets.Count; ++j) {
    }
}

第一种方法：

使用IEnumerable.Intersect()来获得与其他列表的交集，并检查IEnumerable.Count()来获得交集的大小。

var intersect = allSets[i].Intersect(allSets[j]);
count = intersect.Count();

这是平均177秒中速度最慢的一次

第二种方法：

克隆了我相交的两个集合中的较小集合，然后使用ISet.IntersectWith()并检查生成的集合Count。

HashSet<int> intersect;
HashSet<int> intersectWith;
        if(allSets[i].Count < allSets[j].Count) {
            intersect = new HashSet<int>(allSets[i]);
            intersectWith = allSets[j];
        } else {
            intersect = new HashSet<int>(allSets[j]);
            intersectWith = allSets[i];
        }
        intersect.IntersectWith(intersectWith);
        count = intersect.Count;
    }
}

这一次稍快，平均154秒

第三种方法：

做了一些与您在较短集合上迭代并在较长集合上检查ISet.Contains非常相似的事情。

for(int i = 0; i < allSets.Count; ++i) {
    for(int j = i + 1; j < allSets.Count; ++j) {
        count = 0;
        if(allSets[i].Count < allSets[j].Count) {
            loopingSet = allSets[i];
            containsSet = allSets[j];
        } else {
            loopingSet = allSets[j];
            containsSet = allSets[i];
        }
        foreach(int k in loopingSet) {
            if(containsSet.Contains(k)) {
                ++count;
            }
        }
    }
}

这种方法是迄今为止最快的（正如预期的那样），平均为66秒

结论

你使用的方法是这三种方法中最快的。我当然想不出比这更快的单线程方法了。也许还有更好的并发解决方案。

我发现，在迭代/搜索任何类型的集合时，最重要的考虑因素之一是非常小心地选择集合类型。为了您的目的而遍历一个普通集合并不是最理想的。尝试使用以下内容：

System.Collections.Generic.HashSet<T>

使用Contains（）方法同时迭代较短的两个列表（正如您已经提到的那样）应该会获得接近O（1）的性能，与通用Dictionary类型中的键查找相同。

相关文章：