1

我有一种方法可以将value转换为长度length的newBase数。

英文的逻辑是：

If we calculated every possible combination of numbers from 0 to (c-1)
with a length of x
what set would occur at point i

虽然下面的方法确实工作得很好，因为使用了非常大的数字，它可能需要很长时间才能完成：

例如 value=(((65536^480000)-1)/2), newbase=(65536), length=(480000) 在 64 位架构，四核 PC 上大约需要一个小时才能完成。

private int[] GetValues(BigInteger value, int newBase, int length)
{
    Stack<int> result = new Stack<int>();

    while (value > 0)
    {
        result.Push((int)(value % newBase));

        if (value < newBase)
            value = 0;
        else
            value = value / newBase;
    }

    for (var i = result.Count; i < length; i++)
    {
        result.Push(0);
    }

    return result.ToArray();
}

我的问题是，如何将此方法更改为允许多个线程计算部分数字的方法？

我正在使用 C#，但如果你不熟悉它，那么伪代码也可以。

注意：该方法来自这个问题：Cartesian product subset returns set of most 0

4

1 回答 1

2

如果该GetValues方法确实是瓶颈，那么您可以采取一些措施来加快速度。

newBase首先，您每次都在循环中除以。由于newBaseis a int，并且BigIntegerdivide 方法除以 a BigInteger，因此您可能会在每次迭代中产生int-to-转换的成本。BigInteger你可能会考虑：

BigInteger bigNewBase = newBase;

此外，您可以通过调用DivRem将分割数减半：

while (value > 0)
{
    BigInteger rem;
    value = BigInteger.DivRem(value, bigNewBase, out rem);
    result.Push((int)rem);
}

正如评论中提到的那样，另一种优化是将数字存储在预先分配的数组中。您必须调用Array.Reverse以使它们按正确的顺序排列，但这几乎不需要时间。

顺便说一下，这种方法不适合并行化，因为计算每个数字取决于前一个数字的计算。

于 2014-03-24T23:55:49.897 回答