在一些处理数字的程序中，我有一个在三个维度上只能为 1 或 0 的函数。我事先不知道该函数，但我需要知道该函数的总“表面”等于零。在类似的问题中，我可以在英国地图的二维表示上绘制一个矩形。该函数在海上等于 0，在地球上等于 1。我需要知道总水面。我想知道执行此操作的最佳并行算法或方法是什么。
我首先想到了以下方法； a) 将二维地图区域划分为矩形网格。对于属于每个单元格中心的每个点，检查它是否是水土。这可以并行完成。在该过程结束时，我将得到一个包含 1 和 0 的矩阵。我会得到一定精度的面积。现在我想提高这个精度，所以b）选择位于零和一之间边界区域的单元格（执行此操作的最佳标准是什么？），并在这些单元格中，将它们再次划分为连续的单元格并重复该过程直到获得所需的准确度。我猜想，在这个过程中，关键的参数是每个新阶段的网格大小，以及如何存储和检查属于边界区域的单元格。最后，从计算的角度来看，最佳方法是执行最少数量的检查以获得具有所需精度的总表面值的方法。
In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance the function, but I need to know the total "surface" of the function which is equal to zero. In a similar problem I could draw a rectangle over the 2D representation of the map of United Kingdom. The function is equal to 0 at sea, and 1 at the earth. I need to know the total water surface. I wonder what is the best parallel algorithm or method for doing this.
I thought first about the following approach; a) divide 2D map area into a rectangular grid. For each point that belongs to the center of each cell, check whether it is earth of water. This can be done in parallel. At the end of the procedure I will have a matrix with ones and zeroes. I will get the area with some precision. Now I want to increase this precision, so b) choose the cells that are in the border regions between zeroes and ones (what is the best criterion for doing this?) and in those cells, divide them again into successive cells and repeat the process until one gets the desired accuracy. I guess that in this process, the critical parameters are the grid size for each new stage, and how to store and check the cells that belong to the border area. Finally the most optimal method, from the computational point of view, is the one that performs the minimal number of checks in order to get the value of the total surface with the desired accuracy.
发布评论
评论（2）
首先，看起来您正在谈论 3D 函数，例如对于两个坐标 x 和 y，您有
f(x, y) = 0if (x, y ) 属于海洋，否则f(x, y) = 1。话虽如此，您可以使用以下简单的方法。
您的处理器（或处理器核心，或集群中的节点等）
水面。
当然，你可以使用任何其他方法来计算表面积，Mothe Carlo只是一个例子。但想法是相同的：将问题细分为 N 个子问题，并行解决它们，然后合并结果。
更新：对于蒙特卡罗方法，误差估计减小为 1/sqrt(N)，其中 N 是样本数。例如，要将误差减少 2 倍，需要将样本点数量增加 4 倍。
First of all, it looks like you are talking about 3D function, e.g. for two coordinates x and y you have
f(x, y) = 0if (x, y) belongs to the sea, andf(x, y) = 1otherwise.Having said that, you can use the following simple approach.
your processors (or processor cores, or nodes in a cluster, etc.)
surface of the water.
Of course, you can use any other method to calculate the surface, Mothe Carlo was just an example. But the idea is the same: subdivide your problem to N subproblems, solve them in parallel, then combine the results.
Update: For the Monte Carlo method the error estimate decreases as 1/sqrt(N) where N is the number of samples. For instance, to reduce the error by a factor of 2 requires a 4-fold increase in the number of sample points.
我相信你的态度是合理的。
选择位于 0 和 1 之间边界区域的单元格（执行此操作的最佳标准是什么？）
每个单元格有 8 个相关单元格 (3x3) 或 24 个相关单元格 (5x5)。如果 9 或 25 个单元格中至少有一个包含土地，并且这些单元格中至少有一个包含水 - 提高整个单元格（3x3 或 5x5）的精度并再次查询。
当精度足够好时 - 无需分割，只需将土地面积添加到总和中即可。
效率
使用生产者-消费者队列。创建 n 个线程，其中 n 等于计算机上的核心数量。所有线程都应该执行相同的工作：
首先，只需将整个区域划分为合理大小的单元格并将它们全部排队即可。
您还可以通过在混合时不添加所有 9 或 25 个单元格来进行优化，但检查模式（仅顶部/底部/左/右单元格）。
编辑：
准确性和性能之间存在权衡：如果初始像元大小太大，您可能会错过小湖泊或小岛屿。因此，优化标准应该是：从尽可能最大的单元开始，以确保足够的精度。
I believe that your attitude is reasonable.
Choose the cells that area in the border regions between zeroes and ones (what is the best criterion for doing this?)
Each cell has 8 sorrunding cells (3x3), or 24 sorrunding cells (5x5). If at least one of the 9 or 25 cells contains land, and at least one of these cells contains water - increase the accuracy for the whole block of cells (3x3 or 5x5) and query again.
When the accuracy is good enough - instead of splitting, just add the land area to the sum.
Efficiency
Use a producers-consumer queue. Create n threads, where n equals to the number of cores on your machine. All threads should do the same job:
For start, just divide the whole area into reasonable sized cell and equeue all of them.
You can also optimize by not adding all the 9 or 25 cells when there is a mix, but examine the pattern (only top/bottom/left/right cells).
Edit:
There is a tradeoff between accuracy and performance: If the initial cell size is too large, you may miss small lakes or small islands. therefore the optimization criteria should be: start with the largest cells possible that will assure enough accuracy.