在连续渗透中处理大量数据
Dealing with huge amounts of data in continuum percolation
对于我目前参与的小组项目，我们必须模拟以下内容：
取一个边长 n 的正方形。在正方形上均匀分布一定数量的单位圆盘。找到从正方形的左侧延伸到右侧的连接的磁盘组件之前所需的磁盘数。然后求出需要的圆盘数，直到方格完全被圆盘填满。
它没有明确说明，但我们假设这是在 Matlab 中完成的，因为我们在本课程的其他部分使用它。对于第一个问题，找到一条从左到右的路径，我编写了两种可行的方法。一个使用邻接列表和 Matlab 中的图形工具来查找连接的节点。这种方法足够快，但是对于我们需要做的事情来说占用了太多的内存。另一种方法使用递归搜索算法而不存储邻接信息，但速度太慢。
当我们需要正方形的大小为 n=1000 和 n=10000 时，问题就出现了。我们预测这将需要数千万个圆，或者更多，我们根本看不出我们应该如何处理这个，因为任何邻接列表或矩阵都会大得离谱，不使用一个似乎需要大量的时间。感谢任何想法和想法，谢谢
让我们将您的问题重新表述为这样的决策问题：
Starting with seed s for the PRNG, randomly distribute m unit disks in an n x n square, and determine whether or not they make a connected path from the left side to the right.
和：
Starting with seed s for the PRNG, randomly distribute m unit disks in an n x n square, and determine whether or not they cover the entire square.
如果你能解决这些决策问题，那么你可以通过对可能值进行二分搜索来找到 m 的最小值。
您可以像这样生成磁盘来解决这些决策问题，而无需使用大量 RAM：
- 用给定的种子初始化你的 PRNG s
- 对于每个磁盘 1 ... m，随机 select 它将进入的列（即 floor(center.x)）。累加所有列的计数以确定每个列中将放入多少个磁盘。设 COUNT(col) 为要在列 col
中生成的磁盘数
- 对于 0 ... n-1 中的每个列，生成在该列内均匀分布的 COUNT(col) 个磁盘。
现在您主要是从左到右生成磁盘。上面两个决策题都有从左到右的解法，一次只需要看到一两列的盘子，所以你只需要记住一两列的盘子。
对于完全覆盖问题，从左到右计算并确定正方形中的每一列是否被完全覆盖，使用该列和相邻列的磁盘。没有其他磁盘可能到达。
对于左右路径问题，使用 union-find 从左到右工作以跟踪当前列中的哪些磁盘连接到左侧以及彼此连接。当你到达最后一列时，你可以检查最后一列中的任何磁盘是否连接到左侧并延伸到右侧。
对于我目前参与的小组项目，我们必须模拟以下内容： 取一个边长 n 的正方形。在正方形上均匀分布一定数量的单位圆盘。找到从正方形的左侧延伸到右侧的连接的磁盘组件之前所需的磁盘数。然后求出需要的圆盘数，直到方格完全被圆盘填满。
它没有明确说明，但我们假设这是在 Matlab 中完成的，因为我们在本课程的其他部分使用它。对于第一个问题，找到一条从左到右的路径，我编写了两种可行的方法。一个使用邻接列表和 Matlab 中的图形工具来查找连接的节点。这种方法足够快，但是对于我们需要做的事情来说占用了太多的内存。另一种方法使用递归搜索算法而不存储邻接信息，但速度太慢。
当我们需要正方形的大小为 n=1000 和 n=10000 时，问题就出现了。我们预测这将需要数千万个圆，或者更多，我们根本看不出我们应该如何处理这个，因为任何邻接列表或矩阵都会大得离谱，不使用一个似乎需要大量的时间。感谢任何想法和想法，谢谢
让我们将您的问题重新表述为这样的决策问题：
Starting with seed s for the PRNG, randomly distribute m unit disks in an n x n square, and determine whether or not they make a connected path from the left side to the right.
和：
Starting with seed s for the PRNG, randomly distribute m unit disks in an n x n square, and determine whether or not they cover the entire square.
如果你能解决这些决策问题，那么你可以通过对可能值进行二分搜索来找到 m 的最小值。
您可以像这样生成磁盘来解决这些决策问题，而无需使用大量 RAM：
- 用给定的种子初始化你的 PRNG s
- 对于每个磁盘 1 ... m，随机 select 它将进入的列（即 floor(center.x)）。累加所有列的计数以确定每个列中将放入多少个磁盘。设 COUNT(col) 为要在列 col 中生成的磁盘数
- 对于 0 ... n-1 中的每个列，生成在该列内均匀分布的 COUNT(col) 个磁盘。
现在您主要是从左到右生成磁盘。上面两个决策题都有从左到右的解法，一次只需要看到一两列的盘子，所以你只需要记住一两列的盘子。
对于完全覆盖问题，从左到右计算并确定正方形中的每一列是否被完全覆盖，使用该列和相邻列的磁盘。没有其他磁盘可能到达。
对于左右路径问题，使用 union-find 从左到右工作以跟踪当前列中的哪些磁盘连接到左侧以及彼此连接。当你到达最后一列时，你可以检查最后一列中的任何磁盘是否连接到左侧并延伸到右侧。