arrays - 在格上有效地计算邻居的功能

Question

我正在研究 Ising模型，我正在尝试有效地计算函数 H(σ)，其中 σ 是 Lx 的当前状态L 格(即 σ_ij ∈ {+1, -1} for i,j ∈ {1,2,..., L})。要计算特定 σ 的 H，我需要执行以下计算:

其中 ⟨i j⟩ 表示站点 σ_i 和 σ_j 是最近的邻居并且(假设)J 是一个常数。

几个问题:

1. 我应该将状态 σ 存储为 LxL 矩阵还是L² 列表？对于 RAM 中的内存访问，一个比另一个更好吗(我想这取决于我访问元素的方式......)？
2. 无论哪种情况，我怎样才能最好地计算 H？

我真的认为这归结为我如何最有效地访问(和操纵)每个状态的邻居。

一些想法:

1. 我发现，如果我循环遍历列表或矩阵中的每个元素，我将重复计算，那么是否有“最佳”方法返回唯一的邻居？
2. 是否有我没有想到的更好的数据结构？

Answer 1

你的问题有点宽泛，让我有点困惑，所以如果我的答案不是你要找的，请原谅，但我希望它能有所帮助(一点点)。

---

在索引方面，数组比列表更快。矩阵是一个二维数组，例如(其中 N 和 M 对您来说都是 L):

这意味着您首先访问 a[i]，然后访问 a[i][j]。

但是，您可以通过使用一维数组模拟二维数组来避免这种双重访问。在这种情况下，如果您想访问矩阵中的元素 a[i][j]，您现在可以这样做，a[i * L + j]。

这样你加载一次，但你乘以并添加你的变量，但在某些情况下这可能仍然更快。

---

现在关于最近邻问题，您似乎使用的是 square-lattice Ising model ，这意味着您在二维空间中工作。

低维度最近邻搜索的一个非常有效的数据结构是 kd-tree .该树的构造需要 O(nlogn)，其中 n 是数据集的大小。

现在您应该考虑构建这样一个数据结构是否值得。

PS:有很多库实现了 kd-tree，例如 CGAL。