javascript - 数组算法太慢

Question

我编写了一个算法，可以在一个巨大的对象数组结构中找到六边形的每一行。
该数组包含大约 80.000 - 100.000 个元素(从开始到结束的线坐标)。
一个六边形由 6 个线点组成。所以这个数组有大约 15.000 个六边形的信息。
对象的结构(未排序!!!)如下所示:

const stamps = [
  { 
    vertices: [
      {x: 114.5116411118, y: 342.9815785601},
      {x: 115.6663416502, y: 344.9815785601}
    ]
  },
  {
    vertices: [
      {x: 115.6663416502, y: 340.9815785601},
      {x: 114.5116411118, y: 342.9815785601}
    ]
  },
  {
    vertices: [
      {x: 122.6663416502, y: 364.9815785601},
      {x: 147.9757427269, y: 314.9815785601},
    ]
  },
  {
    vertices: [
      {x: 117.9757427269, y: 340.9815785601},
      {x: 115.6663416502, y: 340.9815785601},
    ]
  },
  {
    vertices: [
      {x: 119.1304432653, y: 342.9815785601},
      {x: 117.9757427269, y: 340.9815785601},
    ]
  },
  {
    vertices: [
      {x: 117.9757427269, y: 344.9815785601},
      {x: 119.1304432653, y: 342.9815785601},
    ]
  },
  {
    vertices: [
      {x: 115.6663416502, y: 344.9815785601},
      {x: 117.9757427269, y: 344.9815785601},
    ]
  },
];

为了找到每条线六边形，我的想法是必须有 2 个元素必须具有相同的坐标。如果是这种情况，我将跳转到该元素的索引并重复该过程，直到我拥有六边形的所有 6 行。
它是这样工作的，但它真的，真的很慢。对于具有 80.000 个元素的数组，大约需要 3 分钟。
算法:

function findHexPolyPoints() {
  const hexCoordinates = [];
  let activeArrayPos = 0;
  let position = 0;
  while (1) {
    let foundPair = false;
    if (stamps.length < 6) break;
    for (let k = 0; k < stamps.length; ++k) {
      if (k === position) continue;
      if (stamps[position].vertices[0].x === stamps[k].vertices[1].x && stamps[position].vertices[0].y === stamps[k].vertices[1].y) {
        if (hexCoordinates[activeArrayPos]) {
          hexCoordinates[activeArrayPos].push(stamps[k].vertices[0].x, stamps[k].vertices[0].y);
        } else {
          hexCoordinates.push([stamps[position].vertices[0].x, stamps[position].vertices[0].y, stamps[k].vertices[0].x, stamps[k].vertices[0].y]);
        }
        foundPair = true;
      } else if (stamps[position].vertices[1].x === stamps[k].vertices[0].x && stamps[position].vertices[1].y === stamps[k].vertices[0].y) {
        if (hexCoordinates[activeArrayPos]) {
          hexCoordinates[activeArrayPos].push(stamps[k].vertices[1].x, stamps[k].vertices[1].y);
        } else {
          hexCoordinates.push([stamps[position].vertices[1].x, stamps[position].vertices[1].y, stamps[k].vertices[1].x, stamps[k].vertices[1].y]);
        }
        foundPair = true;
      }
      if (foundPair) {
        stamps.splice(position, 1);
        if (k > position) {
          position = k - 1;
        } else {
          position = k;
        }
        if (hexCoordinates[activeArrayPos].length < 12) break;
      }
      if (hexCoordinates[activeArrayPos] && hexCoordinates[activeArrayPos].length === 12) {
        if (k > position) stamps.splice(k - 1, 1);
        else stamps.splice(k, 1);
        activeArrayPos += 1;
        position = 0;
        break;
      }
      if (k === stamps.length - 1) {
        stamps.splice(position, 1);
        break;
      }
    }
  }
  sortHexagons(hexCoordinates);
}

有什么办法可以加快我的算法？我读过一个简单的 for 循环仍然比一些 js 排序函数更快。 map . filter或类似的。

Answer 1

以下 O(n) 算法假设

两个不同的六边形没有重叠的顶点

数组中相同的顶点不超过两个(意思是，可能有一个不属于任何六边形的孤儿，但其坐标不应等于任何六边形顶点)

坐标中没有浮点不准确(意味着应该相等的两个顶点，=== 完全相等)

假设 6 个连接的顶点形成一个六边形...(没有重心计算和检查以确保它实际上是一个六边形)

(如果点 1. 和 2. 不正确，则算法需要更多工作，以尝试所有可能性(在 overt[x_y] 数组中，见下文)以避免非六边形或重叠坐标，具体取决于期望找到重叠的六边形或孤儿，复杂性可能超过 O(n))
使用 map 的概念(从键中获取对象值)，这被认为是 O(1)。
为了方便使用顶点坐标，我们可以将 x 和 y 连接成一个字符串

x:123.456, y:789.321

给

x_y = "123.456_789.321"

让我们创建 3 个变量 avert = [] , overt = {} , hexas = []

avert是所有顶点的数组，avert[index]是x_y顶点坐标的数组(2)

overt 是一个对象，对于每个 x_y 坐标给出 avert 中的索引数组(大小不应超过 2，如上所述(并且没有 >2 检查))

hexas 是array(6)的数组，找到的六边形列表(每个坐标的格式为x_y)

在第一个 forEach 中，创建了 avert 和 overt。
下一个 forEach 处理所有 avert 顶点 [x_y1, x_y2]

从第一个顶点开始，寻找6个点组成一个六边形

将每个顶点添加到一个六边形数组 hexa ，从下一个(第一个之后)开始

假设坐标没有排序，因此确保我们不会回到之前的顶点

跳过使用的顶点(六边形)

确保找到的最后一个顶点与origin(第一个)具有相同的坐标

初始化

let avert = [], overt = {}, hexas = [];

stamps.forEach(function(e, i){
    let xy1 = e['vertices'][0]['x']+'_'+e['vertices'][0]['y'];
    let xy2 = e['vertices'][1]['x']+'_'+e['vertices'][1]['y'];
    // overt[XY] (array) should have two elements at most (no overlapping),
    // one if orphan
    if ( ! overt[xy1]) overt[xy1] = [];
    overt[xy1].push( i );
    if ( ! overt[xy2]) overt[xy2] = [];
    overt[xy2].push( i );
    avert.push([ xy1, xy2 ]);
});

加工

avert.forEach(function (e){
    let j,coord = e[0];   // first coords x_y
    let origin = coord;
    let hexa = [];
    let lastindex = -1;   // avoid going back!
    // try to find 5 connected vertices + origin
    for(j=0 ; j<6 ; j++) {
        let o = overt[coord];
        if ( o === undefined || o.length < 2 ) {
           break; // not found(already processed), or orphan!
        }
        let index = o[0] == lastindex ? o[1] : o[0];  // no turn back!
        lastindex = index;
        coord = avert[index][0] === coord ? avert[index][1] : avert[index][0];
        hexa.push(coord);
    }
    if (j >= 6) { // found all vertices
        // check that the last coord is the starting point
        if (hexa[5] === origin) { // got it
             hexas.push( hexa );
             hexa.forEach(function(h){ // delete used vertices
                delete overt[h];
             });
        }
    }
});

所有六边形都应该在 hexas