C#最快的2组排序数字的交集

coder 2024-05-28 原文

我在我的应用程序的时间关键部分计算 2 组排序数字的交集。这个计算是整个应用的最大瓶颈，所以我需要加快速度。

我尝试了很多简单的选项，目前正在使用这个:

foreach (var index in firstSet)
{
    if (secondSet.BinarySearch(index) < 0)
        continue;

    //do stuff
}

firstSet 和secondSet 都是List 类型。

我也尝试过使用 LINQ:

var intersection = firstSet.Where(t => secondSet.BinarySearch(t) >= 0).ToList();

然后循环遍历交点。

但是由于这两个集合都已排序，我觉得有更好的方法来做到这一点。请注意，我无法从集合中删除项目以使其更小。两组通常各包含大约 50 个项目。

请帮助我，因为我没有太多时间来完成这件事。谢谢。

注意:我这样做了大约 530 万次。所以每一微秒都很重要。

最佳答案

如果您有两个都已排序的集合，则可以实现比 LINQ 开箱即用的任何东西更快的交集。

基本上，保留两个 IEnumerator<T>游标打开，每组一个。在任何时候，以较小的值(value)为准。如果它们在任何一点匹配，则将它们都推进，依此类推，直到到达任一迭代器的末尾。

这样做的好处是您只需要迭代每个集合一次，并且可以在 O(1) 内存中完成。

这是一个示例实现 - 未经测试，但它确实可以编译:)它假设两个传入序列都是无重复的并且已排序，都根据提供的比较器(传入 Comparer<T>.Default ):

(答案末尾有更多文字!)

static IEnumerable<T> IntersectSorted<T>(this IEnumerable<T> sequence1,
    IEnumerable<T> sequence2,
    IComparer<T> comparer)
{
    using (var cursor1 = sequence1.GetEnumerator())
    using (var cursor2 = sequence2.GetEnumerator())
    {
        if (!cursor1.MoveNext() || !cursor2.MoveNext())
        {
            yield break;
        }
        var value1 = cursor1.Current;
        var value2 = cursor2.Current;

        while (true)
        {
            int comparison = comparer.Compare(value1, value2);
            if (comparison < 0)
            {
                if (!cursor1.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
            }
            else if (comparison > 0)
            {
                if (!cursor2.MoveNext())
                {
                    yield break;
                }
                value2 = cursor2.Current;
            }
            else
            {
                yield return value1;
                if (!cursor1.MoveNext() || !cursor2.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
                value2 = cursor2.Current;
            }
        }
    }
}

编辑:如评论中所述，在某些情况下，您可能有一个输入比另一个输入大得多，在这种情况下，您可以使用二进制搜索从较小的集合中的每个元素中节省大量时间更大的集合。然而，这需要随机访问更大的集合(这只是二进制搜索的先决条件)。您甚至可以通过使用 previous 结果中的匹配来为二分搜索提供下限，从而使其比简单的二分搜索稍微好一点。因此，假设您正在寻找一个集合中的值 1000、2000 和 3000，每个整数都从 0 到 19,999。在第一次迭代中，您需要查看整个集合 - 您的起始下限/上限索引分别为 0 和 19,999。然而，当您在索引 1000 处找到匹配项后，下一步(您正在寻找 2000)可以从较低的索引 2000 开始。随着您的进步，您所处的范围需要搜索逐渐缩小。然而，这是否值得额外的实现成本是另一回事。

关于C#最快的2组排序数字的交集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7164572/

C#最快 cursor code value .net intersection sortedset

有关C#最快的2组排序数字的交集的更多相关文章

ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2
我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s
c# - 如何在 ruby 中调用 C# dll？ - 2
如何在ruby中调用C#dll？最佳答案我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL
C# 到 Ruby sha1 base64 编码 - 2
我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha
区块链之加解密算法&数字证书 - 2
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
基于C#实现简易绘图工具【100010177】 - 2
C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.
ruby - 将n维数组的每个元素乘以Ruby中的数字 - 2
在Ruby中，是否有一种简单的方法可以将n维数组中的每个元素乘以一个数字？这样:[1,2,3,4,5].multiplied_by2==[2,4,6,8,10]和[[1,2,3],[1,2,3]].multiplied_by2==[[2,4,6],[2,4,6]]？(很明显，我编写了multiplied_by函数以区别于*，它似乎连接了数组的多个副本，不幸的是这不是我需要的)。谢谢! 最佳答案它的长格式等价物是:[1,2,3,4,5].collect{|n|n*2}其实并没有那么复杂。你总是可以使你的multiply_by方法:c
ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2
我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night
ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2
我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我
Ruby 的数字方法性能 - 2
我正在使用Ruby解决一些ProjectEuler问题，特别是这里我要讨论的问题25(Fibonacci数列中包含1000位数字的第一项的索引是多少？)。起初，我使用的是Ruby2.2.3，我将问题编码为:number=3a=1b=2whileb.to_s.length但后来我发现2.4.2版本有一个名为digits的方法，这正是我需要的。我转换为代码:whileb.digits.length当我比较这两种方法时，digits慢得多。时间./025/problem025.rb0.13s用户0.02s系统80%cpu0.190总计./025/problem025.rb2.19s用户0.0
ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2
我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

C#最快的2组排序数字的交集

有关C#最快的2组排序数字的交集的更多相关文章

随机推荐