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 で完了するのに約 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 のセットを返すデカルト積サブセット

4

1 に答える 1

2

そのGetValues方法が本当にボトルネックである場合、それを高速化するためにできることがいくつかあります。

newBaseまず、ループのたびに除算しています。newBaseはintであり、BigInteger除算メソッドは で除算するため、すべての反復で からコンバージョンへのBigIntegerコストが発生する可能性があります。次のことを検討してください。intBigInteger

BigInteger bigNewBase = newBase;

また、 DivRemを呼び出すことで、分割数を半分に削減できます。

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

コメントで誰かが言及したように、もう1つの最適化は、事前に割り当てられた配列に数字を格納することです。それらを適切な順序で取得するにはArray.Reverseを呼び出す必要がありますが、それにはほとんど時間がかかりません。

ちなみに、この方法は、各桁の計算が前の桁の計算に依存するため、並列化には向いていません。

于 2014-03-24T23:55:49.897 に答える