如何理解计算物理中的元胞链接列表（Cell Linked List）算法？

好的，咱们来聊聊计算物理里那点儿“元胞链接列表”（Cell Linked List，简称 CLL）的门道。这玩意儿听着挺技术，其实原理一点儿都不复杂，就像咱们生活中的事儿一样，只是换了个数学的说法。

你想象一下，咱们要处理一个模拟场景，里面有无数个粒子在动。这些粒子之间会有各种各样的相互作用，比如引力、斥力，或者更复杂的力。计算这些粒子之间的力，最直接的办法就是把每一对粒子都算一遍。如果粒子数量是 N，那计算量就是 N 乘以 N1，大概是 O(N^2) 的量级。粒子一多，这个计算量就爆炸了，模拟就卡得动不了。

所以，咱们得想个法子，把这 O(N^2) 的计算降下来。CLL 就是这么一个聪明的主意。它的核心思想是：如果两个粒子离得太远，它们之间的力就可以忽略不计了。 咱们没必要去计算那些基本没影响的力，这样就能省下大量的计算时间。

CLL 到底是怎么做的呢？

你可以把整个模拟空间想象成一个大棋盘，或者一个网格。CLL 算法就是把这个大棋盘切成很多个小方块，就像切蛋糕一样。这些小方块就叫“元胞”（cell）。

1. 划分空间：
首先，咱们需要确定这个“棋盘”有多大，以及要切成多少个小方块。这个大小和数量的设定是很有讲究的。
元胞大小的选取： 一个非常重要的原则是，每个元胞的大小要比你关心的相互作用的最大范围（通常是截断半径，cutoff radius）要大一些，但也不能太大。
如果元胞太小，一个相互作用范围内的粒子可能分布在好几个元胞里，那计算的复杂性又上来了。
如果元胞太大，一个元胞里可能包含太多粒子，那在同一个元胞内找邻居的工作量还是很大。
一个常见的策略是，让元胞的边长等于或略大于相互作用的截断半径。这样，在一个元胞里的粒子，它可能影响到的其他粒子，要么在这个元胞里，要么在它紧邻的元胞里。

2. 粒子入胞：
然后，咱们就把所有的粒子都“放”到这些小方块里。怎么放呢？就是根据每个粒子的坐标，找到它属于哪个元胞，然后把它放到那个元胞里。
每个元胞会有一个清单，记录下属于这个元胞的所有粒子。这个清单，通常就是用“链接列表”（linked list）的形式来表示的。

3. 计算相互作用：
有了这个划分，计算就变得高效了。现在，咱们要计算一个粒子（咱们叫它“目标粒子”）受到的力。
首先，计算目标粒子在它自己元胞里的其他粒子产生的力。 这个很简单，就在同一个清单里找。
接着，计算目标粒子在它周围的元胞里的粒子产生的力。 咱们只需要检查目标粒子所在的元胞的邻居元胞。
对于一个二维的元胞，它有 8 个邻居（上下左右，以及四个对角）。
对于一个三维的元胞，它有 26 个邻居。
关键点来了： 由于咱们设定了元胞大小，一个粒子最远能影响到的其他粒子，一定在它自己所在的元胞或者它的邻居元胞里。所以，我们不需要去检查所有其他的元胞，只需要检查这“一圈”邻居元胞就够了。

4. 链接列表的“链接”在哪里？
你可能会问，链接列表到底是怎么起作用的？
每个元胞都需要一个地方来存储它包含的粒子。最简单的方式是，每个元胞有一个指针，指向它第一个粒子所在的节点。而这个节点，又指向下一个属于这个元胞的粒子节点，直到列表末尾。
所以，当我们要遍历一个元胞里的所有粒子时，就是跟着这个链接列表走。
这样，当一个粒子被分配到某个元胞后，它就被加到了这个元胞的链接列表的末尾。

CLL 的好处在哪里？

显著降低计算复杂度： 把 O(N^2) 的计算降低到接近 O(N) 的量级。这个提升是非常巨大的，尤其是在粒子数量巨大的情况下。
空间局部性： CLL 利用了粒子相互作用的空间局部性。离得近的粒子，它们更可能在同一个或相邻的元胞里，这样查找起来就非常方便。
易于实现： 相对于其他一些更复杂的加速算法（比如 KD Tree），CLL 的实现相对来说是比较直观和容易的。

举个例子（更形象一些）：

想象你住在一个小区里，小区被划分成很多幢楼（元胞）。每个人（粒子）都住在某幢楼里。

传统方法（O(N^2)）： 你想知道你（目标粒子）周围有多少人可能和你打招呼（产生相互作用）。你得认识小区里的每一个人，然后挨个去问：“嘿，我们离得近吗？”
CLL 方法：
你只需要知道你住在哪一幢楼（元胞）。
然后，你只需要关注你自己这一幢楼里的人，以及你隔壁几幢楼里的人。
因为你假设，那些离你太远（比如在小区另一头）的人，跟你打招呼的可能性几乎为零。
这样，你的社交范围就大大缩小了，效率就提高了。

CLL 的一些细节和注意事项：

边界处理： 如果粒子在模拟的边界附近，处理起来会稍微麻烦一些，可能需要进行周期性边界条件的映射，或者在边界处创建一些“镜像”元胞。
动态粒子分布： 如果粒子在模拟过程中分布非常不均匀，某些元胞会非常拥挤，而有些则很稀疏。这可能会影响算法的效率。这时候可能需要考虑一些自适应的元胞划分策略。
粒子移动： 粒子在运动，所以它们所属的元胞也可能发生变化。在每个时间步（或者几个时间步），都需要重新将粒子分配到相应的元胞中。这个重新分配的过程也是 CLL 的一部分。
内存管理： 链接列表需要额外的内存来存储指针。对于非常大的模拟，需要考虑内存的使用效率。

总而言之， 元胞链接列表（CLL）算法就像是在一个庞大而复杂的系统中，用一种“分而治之”的思想，将空间切割成若干个小的、易于管理的部分。通过限制粒子间的相互作用只在相邻的“小区域”内进行，极大地提高了计算的效率，是处理大规模粒子模拟中粒子间相互作用的经典且高效的算法之一。它巧妙地利用了空间划分和链接列表的数据结构，让原本不可能的任务变得可执行。

刚刚学了这块，授课老师讲的非常好，把这块讲明白了。

你的问题是：

1.Head是对应的元胞中序号最大的粒子么？

2.那List是怎么将粒子链接起来的呢？

先回答再解释。

1. HEAD这个数组存的是cell中序号最大粒子的序号，如果这个cell没有粒子，那么存的是0.

2. LIST用了一个技巧，把数组的标号跟存的内容巧妙结合。假如我们要遍历第i个cell中所有粒子，我们去HEAD(i)中找这个Cell的入口，HEAD(i)存的是这个cell最大序号粒子的序号，假设是m。然后我们去找LIST数组中LIST(m)这个元素，这个元素存的是cell中粒子序号第2小的序号，假设是n，然后找list(n)，这样就是是一个循环了。直到遇到存的值为0，认为我们把这个cell遍历完了。

=======

分子动力学模拟程序都是比较tricky的，就是说书上讲一个思路，操作上实际有多种实现方法，而且有的方法很巧妙、难以理解。这样需要你对着程序看，才能理解。你提的这两个问题就是如此，需要反复看程序去理解。

你需要看ftp://ftp.dl.ac.uk/ccp5/ALLEN_TILDESLEY/F.20这个程序，SUBROUTINE LINKS讲的是怎么构建Head跟list这两个至关重要的数列。

       C    ** ZERO HEAD OF CHAIN ARRAY **          DO 10 ICELL = 1, NCELL             HEAD(ICELL) = 0  10      CONTINUE      

先看这里，初始化把HEAD数组所有元素全都设为零。此时，HEAD数组的大小是的CELL个数。

       C    ** SORT ALL ATOMS **          DO 20 I = 1, N             ICELL = 1 + INT ( ( RX(I) + 0.5 ) * CELLI )      :               + INT ( ( RY(I) + 0.5 ) * CELLI ) * M      :               + INT ( ( RZ(I) + 0.5 ) * CELLI ) * M * M             LIST(I)     = HEAD(ICELL)            HEAD(ICELL) = I  20      CONTINUE       

再看这里，遍历所有粒子，看看这个粒子在哪个cell里面，就把它的标号作为这个Cell的head。

注意，在把粒子序号存在HEAD这个数组之前，前一个HEAD值存到了LIST(I)中，这部分与你第二个问题有关，稍后讲解。

问题1解决了，这样的话，HEAD数组里面存的是每个CELL中序号最大粒子的序号。但是有一个细节，就是如果这个CELL里面没有粒子，那么这个CELL的Head就是0。

========

现在解释问题2

LIST存的是什么呢？

按照上述第二个程序，LIST存的东西应该是这样。以两个CELL情况为例。

每个CELL粒子最大序号存在了HEAD数组中，这个序号指出了下个原子序号在数组LIST中的位置。例如上图，我们找第二个cell的head值，我们找到HEAD(2)=10，然后找LIST(10)，LIST(10)=9。然后找LIST(9),LIST(9)=6。然后找LIST(6)，...知道找到0，认为这个cell遍历完了。

然后你就能看懂你课件上的这个图了。

参看 Computer Simulation of Liquids'' by M.P. Allen and D. Tildesley Clarendon Press Oxford 1987.

@专治各种不收敛 把技术细节回答的差不多了，我来介绍一下元胞链表这个算法。

在分子模拟中，经常要计算某个粒子与其他粒子之间的相互作用。这个作用往往与距离密切相关，因此需要频繁的搜索粒子周围的“邻居”。

不妨把粒子比喻成一个个租客，他们住在一栋很大的公寓楼（模拟空间）里。假设此时你要确定A租客的邻居以及室友的名单，最傻大粗的办法当然是把整栋楼的租客都排查一遍，但这么做显然太费事。省事一点的做法是按房间（元胞）号来排查：

1. 判断A自己的房间号，假设为506。
2. 确定包括506自身在内的附近9个房间（405~407，505~507，605~607）。
3. 逐一确定以上9个房间内的租客名单。

显然，为了完成以上步骤，你需要先把公寓楼划分成一个个房间，并且要有每个房间的租客信息表。

在分子模拟中，粒子就是租客，整个模拟空间就是公寓楼，人为划分出来的元胞就是公寓楼的房间，而元胞链表就是房间的租客信息表。

租客信息表里没有真的住人，它只是记录了门牌号、租客个数、每个租客的姓名，床号（粒子的具体坐标）等信息的一个表，它大概长这样：

• 门牌号:516
• 租客1:张狗蛋（5号床铺）
• 租客2:李麻子（2号床铺）
• ...
• 租客n：王小六（m号床铺）

分子模拟中的粒子是会到处游走的，相当于租客经常换房间。因此，租客信息表（元胞链表）需要时不时的进行租客搬出、搬入等增减更新，且房间内住的租客上限不好确定。因此，在计算机中，租客信息表不方便用数组形式表达，往往以链表的形式储存。这也是为什么算法名字中有“链表”二字的原由。

欢迎关注我的专栏，虽然更新有点慢：

如何理解计算物理中的元胞链接列表（Cell Linked List）算法？

如何更好的理解计算化学中的PBE泛函？

请问“重根按重数计算”如何理解呢？

如何理论计算多米诺骨牌推进速度？

如何理解北京计划 5 年内增加 150 万套住房的消息？会带来哪些影响？

计算机如何理解图像?

中科院启动「太极二号」双星计划探测空间引力波，如何理解这一计划，具有哪些意义？

如何理解《权力的游戏》第八季第三集中的战斗计划?

如何看待生、化方向高档次文章越来越多带理论计算的现象？

数字人民币主要定位于 M0，是法定货币的数字化形态，「且不计付利息，具有非盈利性」，如何理解这一定位？

理论与计算化学是如何指导实验的？这种指导能达到什么程度？

Stefano Baroni在凝聚态理论与计算方面做了哪些重要工作，影响力如何？

如何理性看待卫计委为解决儿科医师，急诊医师紧缺而采取的执业医师考试定向加分录取政策？

计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？

诺姆•乔姆斯基的理论在现代计算机语言学界被如何看待？

如何评价文章《杨振宁的最后一战》对超大对撞机计划与超弦理论的批判？

如何理解「文官的衣服上绣的是禽，武官的衣服上绣的是兽。披上了这身皮，我们哪一个不是衣冠禽兽」这句话？

如何理解自称迪士尼在逃公主的女生？

如何理解自由主义？新自由主义又是什么？

如何理解无政府主义？