比较数组中其余项的每个项目的最快方法？

问题描述 投票：1回答：4

我有一个项目数组，对于数组中的每个项目，我需要对同一数组中的其余项目进行一些检查。

这是我正在使用的代码：

const myArray = [ ...some stuff ];

let currentItem;
let nextItem;
for (let i = 0; i < myArray.length; i++) {
  currentItem = myArray[i];
  for (let j = i + 1; j < myArray.length; j++) {
    nextItem = myArray[j];
    doSomeComparision(currentItem, nextItem);
  }
}

虽然这有效，但我需要找到一种更有效的算法，因为如果数组非常大，它会显着减慢。

有人可以提供一些关于如何使这个算法更好的建议吗？

Edit 1

我道歉。

我应该提供更多关于我在这里尝试做的事情。我正在使用上面的循环与HalfEdge数据结构，a.k.a。DCEL。

基本上，HalfEdge是一个具有3个属性的对象：

class HalfEdge = {
  head: // some (x,y,z) coords
  tail: // some (x,y,z) coords
  twin: // reference to another HalfEdge
}

给定twin的HalfEdge定义如下：

/**
  * if two Half-Edges are twins:
  * Edge A   TAIL ----> HEAD
  *           =          =
  * Edge B   HEAD <---- TAIL
  */

我的数组包含许多HalfEdges，对于数组中的每个HalfEdge，我想找到它的双胞胎（即满足上述条件的那个）。

基本上，我正在比较两个3D矢量（一个来自currentItem，另一个来自nextItem）。

Edit 2

修复了代码示例中的拼写错误（即从let j = 0到let j = i + 1）

javascript arrays algorithm for-loop
4个回答
1
投票

这是您的问题的线性时间解决方案。我对javascript并不熟悉，所以我会觉得在psuedo-code中正确地给你算法更为舒服。

lookup := hashtable()
for i .. myArray.length
  twin_id := lookup[myArray[i].tail, myArray[i].head]
  if twin_id != null
    myArray[i].twin := twin_id
    myArray[twin_id].twin := i
  else
    lookup[myArray[i].head, myArray[i].tail] = i

我们的想法是构造一个(head, tail)对的哈希表，并检查是否已存在与当前节点匹配的(tail, head)对。如果是这样，它们是双胞胎，并将它们标记为这样，否则用新条目更新哈希表。每个元素只循环一次，并且哈希表的插入/检索是在恒定时间内完成的。

1
投票

我不知道是否有任何类型的特定算法更有效，但我立即想到以下优化：

  • 让j从i + 1开始 - 否则你将所有项目相互比较两次 - 在循环外部用myArray.length初始化变量，因为相同的操作完成两次。
  • 如果比较是任何类型的直接“相等/更大”，那么它可以帮助首先对数组进行排序

编辑1更新 我认为优化取决于预期匹配的数量。也就是说，如果所有的HalfEdge对象都有一个双胞胎，那么我认为你现在采用上述变化的方法已经非常理想了。但是，如果预期双胞胎的百分比相当低，那么我建议如下： - 提取所有头部的列表和所有尾部的列表，对它们进行排序，并相互比较。还记得哪个头发孪生尾巴。然后，你再次原始循环，但只进入发现匹配的头的内循环。不确定这是最佳的，但我希望你能得到我的方法。

1
投票

不知道有关项目类型的更多信息

1）你应该首先对你的数组进行排序，然后只能向前进行比较，它应该给你一个复杂的o（log n）+ n ^ 2，这可能是有用的，这取决于你的项目的类型，并可能导致更多的改进。

2）从i + 1开始内部循环应该进一步减少到o（log n + n）

const myArray = [ ...some stuff ].sort((a,b) => sortingComparison(a,b)); // sorting comparison must return a number

let currentItem;
let nextItem;
for (let i = 0; i < myArray.length; i++) {
  currentItem = myArray[i];
  for (let j = i + 1; j < myArray.length; j++) {
    nextItem = myArray[j];
    doSomeComparision(currentItem, nextItem);
  }
}

奖励：这是一些奇特的功能代码（如果你的目标是原始性能，for循环版本更快）

function compare(value, array) {
  array.forEach((nextValue) => {
    // Do your coparisson here
    // nextValue === value
  }
}

const myArray = [items]
myArray
  .sort((a,b) => (a-b))
  .forEach((v, idx) => compare(v, myArray.slice(idx, myArray.length))
0
投票

由于值是3D坐标，因此构建八叉树（O（N））并在其HEAD值上添加项目。然后，从它们中的每一个，使用已经构建的八叉树（O（Nklog（N）））将它们跟随它们的TAIL值，其节点包含最多k个边缘，这意味着在每个TAIL的最低级别节点处仅进行k次比较。同样找到每个TAIL可能需要从上到下行进至八（8）级的八叉树。

O（N）具有常数的构建八叉树+ O（N * k * log（N）），每个节点具有足够低的k个边缘（以及八叉树的logN水平）。

当您在八叉树中跟随TAIL时，具有相同值的任何HEAD将在具有最大k个元素的相同节点中，或者任何“足够接近”的HEAD值将在该最低级别节点及其最近邻居内。

您是在寻找精确的HEAD == TAIL还是使用了一些公差？宽容可能需要“松散的八叉树”imo。

如果每条边都有一个定义的长度，那么如果边是双对称的，那么你可以用这个值约束搜索半径。

对于高达5k - 10k的边缘，八度树中可能只有5-10个级别，具体取决于每个节点限制的边缘，如果选择此限制大约为2-4，则每个HEAD只需要执行10-40个操作它的双边具有相同的TAIL值。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.