0

我目前正在尝试编写代码，这将有助于计算为游戏 StarMade 设置的高效反应器。我正在使用递归方法来探索元素的 3d 树并找到所有相关组。例如。组 - 它是一组元素，彼此靠近。在图片上是这样的：

XOX
OOX
XXO

其中 O 什么都不是，X 是反应器（元素）。在这张图片上有 3 组元素。[0,0], [2,0]-[2,1], [0,2]-[1,2] 另一种变体：

XXX
OOX
XXX

这里只有一组，因为所有元素都彼此靠近。这是我的代码：

 void CheckGroup(int x, int y, int z, Group group)
    {
        if(x >= maxz || x < 0 || y >= maxy || y < 0 || z >= maxz || z < 0)
        {
            return;
        }

        if (reactorsChecked[x, y, z])
        {
            return;
        }
        reactorsChecked[x, y, z] = true;
        if (reactors[x, y, z])
        {
            if (group == null)
            {
                group = new Group();
                group.MaxX = x;
                group.MaxY = y;
                group.MaxZ = z;
                group.MinX = x;
                group.MinY = y;
                group.MinZ = z;
                group.Blocks = 1;
            }
            else
            {
                group.MaxX = Math.Max(group.MaxX, x);
                group.MaxY = Math.Max(group.MaxY, y);
                group.MaxZ = Math.Max(group.MaxZ, z);
                group.MinX = Math.Min(group.MinX, x);
                group.MinY = Math.Min(group.MinY, y);
                group.MinZ = Math.Min(group.MinZ, z);
                group.Blocks += 1;
            }

            CheckGroup(x + 1, y, z, group);
            CheckGroup(x - 1, y, z, group);

            CheckGroup(x, y + 1, z, group);
            CheckGroup(x, y - 1, z, group);

            CheckGroup(x, y, z + 1, group);
            CheckGroup(x, y, z - 1, group);

            if (!groups.Contains(group))
            {
                groups.Add(group);
            }
        }
    }

group - 是集群的简单类，它存储有关此集群中元素计数和此集群边界框的数据。reactorsChecked - 是简单的 bool[,,] 数组，用于存储我们检查过的元素信息，以避免双打 reactor - 简单的 bool[,,] 随机元素数组。首先我将随机值插入到 reactors 数组中，然后调用 CheckGroup(x,y,z,null)。如果反应器阵列尺寸小于 25x25x25，那么一切正常。在单线程中，数组的大小可以是 100x100x100，一切都会好的。但是，如果我尝试使用 Parallel.For，那么在近 9000 次递归之后我得到了 StackOverflow ......这是完整的代码：

Parallel.For(0, Environment.ProcessorCount, (i) =>
            {
                Calculator calc = new Calculator(x, y, z, max, cycles);
                calcs.Add(calc);
            });

public class Calculator
{
    Random rnd = new Random();
    //List<Group> groups = new List<Group>();
    HashSet<Group> groups = new HashSet<Group>();
    bool[, ,] reactors;
    public bool[, ,] reactorsMax;
    bool[, ,] reactorsChecked;
    public double maxEnergy = 0;
    public string result = "";
    public string resultPic = "";

    int maxx, maxy, maxz;

    public Calculator(int x, int y, int z, int max, int cycles)
    {
        maxx = x;
        maxy = y;
        maxz = z;
        maxEnergy = max;
        for (int i = 0; i < cycles; i++)//check few variants per thread
        {
            Calculate(x,y,z);
        }
    }

    private void Calculate(int X, int Y, int Z)
    {
        //groups = new List<Group>();
        groups = new HashSet<Group>();

        reactors = new bool[X, Y, Z];

        for (int x = 0; x < X; x++)
        {
            for (int y = 0; y < Y; y++)
            {
                for (int z = 0; z < Z; z++)
                {
                    reactors[x, y, z] = rnd.Next(2)==1;//fill array with random values
                }
            }
        }

        reactorsChecked = new bool[X, Y, Z];
        for (int x = 0; x < X; x++)
        {
            for (int y = 0; y < Y; y++)
            {
                for (int z = 0; z < Z; z++)
                {
                    CheckGroup(x, y, z, null);//start calculations
                }
            }
        }
        double sum = 0;
        int blocks = 0;
        foreach(Group g in groups)
        {
            float dims = g.MaxX - g.MinX + g.MaxY - g.MinY + g.MaxZ - g.MinZ + 3;
            sum += (2000000.0f / (1.0f + Math.Pow(1.000696f, (-0.333f * Math.Pow((dims / 3.0f), 1.7)))) - 1000000.0f + 25.0f * g.Blocks);
            blocks += g.Blocks;
        }

        if (sum > maxEnergy)
        {
            maxEnergy = sum;

            reactorsMax = reactors;
        }

    }

    void CheckGroup(int x, int y, int z, Group group)
    {
        if(x >= maxz || x < 0 || y >= maxy || y < 0 || z >= maxz || z < 0)
        {
            return;
        }

        if (reactorsChecked[x, y, z])
        {
            return;
        }
        reactorsChecked[x, y, z] = true;
        if (reactors[x, y, z])
        {
            if (group == null)
            {
                group = new Group();
                group.MaxX = x;
                group.MaxY = y;
                group.MaxZ = z;
                group.MinX = x;
                group.MinY = y;
                group.MinZ = z;
                group.Blocks = 1;
            }
            else
            {
                group.MaxX = Math.Max(group.MaxX, x);
                group.MaxY = Math.Max(group.MaxY, y);
                group.MaxZ = Math.Max(group.MaxZ, z);
                group.MinX = Math.Min(group.MinX, x);
                group.MinY = Math.Min(group.MinY, y);
                group.MinZ = Math.Min(group.MinZ, z);
                group.Blocks += 1;
            }

            CheckGroup(x + 1, y, z, group);
            CheckGroup(x - 1, y, z, group);

            CheckGroup(x, y + 1, z, group);
            CheckGroup(x, y - 1, z, group);

            CheckGroup(x, y, z + 1, group);
            CheckGroup(x, y, z - 1, group);

            if (!groups.Contains(group))
            {
                groups.Add(group);
            }
        }
    }

}

所以主要问题 - 是否可以在 Parallel.For 中避免 stackOverflow，或者将其重写为迭代循环？

Parallel.For 使用默认的 stackSize 值，即使您将使用

Thread(()=>
{
    Parallel.For(...);
},stackSize).Start()

它将使用默认值...

我不喜欢这样的变体：

for(int i = 0; i < cpuCount; i++)
{
    Thread t = new Thread(()=>{calculate();},stackSize).Start()
}

因为我必须管理所有线程，等待所有线程完成，所以它使代码非常复杂......可能有更简单的事情吗？

4

1 回答 1

1

有两种选择：

  1. 使用递归并尝试增加堆栈大小（通过使用Thread(ThreadStart, maxStackSize)构造函数）。应用程序中的堆栈通常设置为 1MB（有关详细信息，请参阅此链接）。特别是在没有优化的调试模式下（没有进行内联优化），这是一个非常有限的值。Paralllel.For()每个语句都有一个带有单独堆栈的线程可能会有所帮助。

  2. 使用迭代外观而不是递归来自己处理堆栈深度。

我个人会选择选项 1。（有或没有单独的堆栈）只有在我知道递归的最大深度的情况下。

在像您这样的大多数情况下，我首选的解决方案是迭代方法。

@LordXaosa 编辑：我试过了，一切正常

int stackSize = 1024*1024*1024;//1GB limit
ManualResetEvent[] mre = new ManualResetEvent[Environment.ProcessorCount];
Parallel.For(0, Environment.ProcessorCount, (i) =>
{
     mre[i] = new ManualResetEvent(false);
     Thread t = new Thread((object reset) =>
     {
           Calculator calc = new Calculator(x, y, z, max, cycles);
           calcs.Add(calc);
           ManualResetEvent m = (ManualResetEvent)reset;
           m.Set();
     }, stackSize / (Environment.ProcessorCount * 4));
     t.Start(mre[i]);
});
WaitHandle.WaitAll(mre);

但也有一个限制...... 50x50x50 数组工作正常，但更多 - 堆栈溢出......在原始游戏中它可以处理 1000x1000x1000 集，所以可能有另一种算法。谢谢你的帮助！

于 2015-03-18T07:04:41.817 回答