时间戳

首页 > 解决方案 > 点之间唯一距离的一维数组

java - 点之间唯一距离的一维数组

问题描述

我正在用行星（点）编写一个 N 体模拟器。我已经让它工作了，但仍然有很多可能的优化，其中之一是计算点之间的距离一次并将它们存储在一个数组中。我可以使用 2d 数组（需要转换为 1d，因为 GPU 不支持 2d 数组）但是有两个问题：

  1. 模拟将限制为 √2147483647（最大整数值）行星 = 46340 个行星，因为数组的大小为 n^2（n 是行星的数量）
  2. 很多距离会重复（0和1之间的距离与1和0之间的距离相同）

要获得唯一连接的数量，公式是：D = (n*(n-1))/2
但是现在我遇到了一个问题：如何在给定两个行星 id-s (x ,y)。行星 0 和 1 之间的距离指数为 0, 0-2 -> 1, 1-2 -> 2...

标签： javaarrays

解决方案

为了帮助可视化它的样子，这里有一个表格，显示了哪个索引（在 1D 数组中）对应于每对行星 ID。要使用此表，给定一对行星 id，找到对应于两个 id 中较大者的行和对应于两个 id 中较小者的列，这将为您提供带有 where 索引的单元格该距离存储在您的一维数组中。

在此处输入图像描述

所以，现在我们需要一个公式，给定两个行星 ID 并计算一维索引号。为简单起见，我们将假设首先给出较大的行星 id。（如果没有，那么我们可以简单地交换两个行星 ID。）

第一项工作是获取较大的行星 id 并确定其行中的第一个索引。换句话说，我们需要将 1 转换为 0，将 2 转换为 1，将 3 转换为 3，将 4 转换为 6，将 5 转换为 10，将 6 转换为 15，等等。幸运的是，模式 0,1,3,6,10,15 是众所周知 - 它是三角数。第 N 个三角数的常用公式是 (n*(n+1))/2 但在这种情况下，我们实际上想要第 N-1 个三角数，所以我们想要的公式是(n*(n-1))/2。

一旦我们有了行的第一个索引，我们就可以添加较小的行星 id 来获得最终索引。

所以，我们的最终公式是：

 given A (larger planet id) and B (smaller planet id):
 the index of dist(A,B) in the 1D array is ((A * (A-1)) / 2) + B

推荐阅读