草庐IT

c# - 高效笛卡尔积算法

coder 2024-05-20 原文

有人可以为我演示一种比我目前使用的算法更有效的笛卡尔积算法(假设有一个)。我环顾四周并用谷歌搜索了一下，但看不到任何明显的东西，所以我可能会遗漏一些东西。

foreach (int i in is) {
   foreach (int j in js) {
      //Pair i and j
   }
}

这是我在代码中所做的高度简化的版本。这两个整数是查找键，用于检索一个/多个对象，并且将来自两个查找的所有对象配对成新对象。

这个小代码块在一个更大更复杂的系统中成为一个主要的性能瓶颈，因为它运行的数据集规模很大。通过改进用于存储对象的数据结构和所涉及的查找，可能会减轻其中一些问题，但我认为主要问题仍然是笛卡尔积本身的计算。

编辑

关于我对算法的具体使用的更多背景，看看是否有任何技巧可以用来回应 Marc 的评论。整个系统是一个 SPARQL 查询引擎，它处理图形数据集上的 SPARQL 查询，SPARQL 是一种基于模式的语言，因此每个查询都包含一系列与图形匹配的模式。在两个后续模式没有公共(public)变量(它们不相交)的情况下，有必要计算两个模式产生的解决方案的笛卡尔积以获得整个查询的可能解决方案集。可能有任意数量的模式，我可能不得不多次计算笛卡尔积，如果查询由一系列不相交的模式组成，这可能导致可能的解决方案呈指数级增长。

不知何故从现有的答案我怀疑是否有任何可以应用的技巧

更新

所以我想我会发布一个关于我实现的更新，以尽量减少做笛卡尔积的需要，从而总体上优化查询引擎。请注意，并不总是可以完全消除对产品的需求，但几乎总是可以进行优化，从而使连接的两个集合的规模小得多。

由于作为一组三重模式的每个 BGP(基本图形模式)都作为一个 block 执行(本质上)，引擎可以自由地在 BGP 中重新排序模式以获得最佳性能。例如考虑以下 BGP:

?a :someProperty ?b .
?c :anotherProperty ?d .
?b a :Class .

按原样执行查询需要笛卡尔积，因为第一个模式的结果与第二个模式不相交，因此前两个模式的结果是它们各自结果的笛卡尔积。这个结果将包含比我们实际需要的更多的结果，因为第三个模式限制了第一个模式的可能结果，但我们直到之后才应用这个限制。但是如果我们像这样重新排序:

?b a :Class .
?a :someProperty ?b .
?c :anotherProperty ?d .

我们仍然需要笛卡尔积来获得最终结果，因为第二个和第三个模式仍然不相交，但是通过重新排序，我们限制了第二个模式结果的大小，这意味着我们的笛卡尔积的大小将小得多.

我们还进行了一些其他优化，但我不打算在这里发布它们，因为它开始进入对 SPARQL 引擎内部结构的相当详细的讨论。如果有人对更多细节感兴趣，请发表评论或发推文给我@RobVesse

最佳答案

笛卡尔积的复杂度是O(n2)，没有捷径。

在特定情况下，迭代两个轴的顺序很重要。例如，如果您的代码正在访问数组中的每个插槽——或图像中的每个像素——那么您应该尝试以自然顺序访问这些插槽。图像通常按“扫描线”布局，因此任何 Y 上的像素都是相邻的。因此，您应该在外循环上迭代 Y 并在内循环上迭代 X。

是否需要笛卡尔积或是否是更有效的算法取决于您要解决的问题。

关于c# - 高效笛卡尔积算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1741364/

c#高效的sectionstrongalgorithmperformancecartesian-product

有关c# - 高效笛卡尔积算法的更多相关文章

  1. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  2. 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

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  5. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

    我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr

  6. c# - C# 中的 Flatten Ruby 方法 - 2

    我如何做Ruby方法"Flatten"RubyMethod在C#中。此方法将锯齿状数组展平为一维数组。例如:s=[1,2,3]#=>[1,2,3]t=[4,5,6,[7,8]]#=>[4,5,6,[7,8]]a=[s,t,9,10]#=>[[1,2,3],[4,5,6,[7,8]],9,10]a.flatten#=>[1,2,3,4,5,6,7,8,9,10 最佳答案 递归解决方案:IEnumerableFlatten(IEnumerablearray){foreach(variteminarray){if(itemisIEnume

  7. ruby - 可以像在 C# 中使用#region 一样在 Ruby 中使用 begin/end 吗？ - 2

    我最近从C#转向了Ruby，我发现自己无法制作可折叠的标记代码区域。我只是想到做这种事情应该没问题:classExamplebegin#agroupofmethodsdefmethod1..enddefmethod2..endenddefmethod3..endend...但是这样做真的可以吗？method1和method2最终与method3是同一种东西吗？还是有一些我还没有见过的用于执行此操作的Ruby惯用语？ 最佳答案 正如其他人所说，这不会改变方法定义。但是，如果要标记方法组，为什么不使用Ruby语义来标记它们呢？您可以使用

  8. c# - Ruby 等效于 C# Linq 聚合方法 - 2

    什么是Linq聚合方法的ruby​​等价物。它的工作原理是这样的varfactorial=new[]{1,2,3,4,5}.Aggregate((acc,i)=>acc*i);每次将数组序列中的值传递给lambda时，变量acc都会累积。 最佳答案 这在数学以及几乎所有编程语言中通常称为折叠。它是更普遍的变形概念的一个实例。Ruby从Smalltalk中继承了这个特性的名称，它被称为inject:into:(像aCollectioninject:aStartValueinto:aBlock一样使用。)所以，在Ruby中，它称为inj

  9. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  10. ruby - 在 Ruby 中实现 Luhn 算法 - 2

    我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s

随机推荐