并行化非常大的数组基转换

本文关键字：转换 数组 非常 并行化 | 更新日期: 2023-09-27 17:52:43

我有一个方法将值转换为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上大约需要1小时完成。

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#，但是如果你不熟悉它，那么伪代码也可以。

注意:该方法来自于这个问题:笛卡尔积子集的返回集大部分为0

并行化非常大的数组基转换

如果GetValues方法确实是瓶颈，您可以做几件事来加速它。

首先，每次循环都要除以newBase。由于newBase是int，并且BigIntegerdivide方法除以BigInteger，因此您可能会在每次迭代中产生从int到BigInteger转换的成本。您可以考虑:

BigInteger bigNewBase = newBase;

也可以通过调用DivRem:

将除法的数目减半
while (value > 0)
{
    BigInteger rem;
    value = BigInteger.DivRem(value, bigNewBase, out rem);
    result.Push((int)rem);
}

另一个优化，正如有人在评论中提到的，将数字存储在预分配的数组中。你必须调用Array。将它们按正确的顺序反向排列，但这几乎不需要花费时间。

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

相关文章：