c# - 連続した数字の桁積を効率的に計算するには?

Question

たとえば、一連の数値の各数値の桁数の積を計算しようとしています。

21, 22, 23 ... 98, 99 ..

だろう：

2, 4, 6 ... 72, 81 ..

複雑さを軽減するために、 from toや from toなど、限られた長さの数字の [連続した数字]のみを検討します。00199900019999

ただし、数列が大きい場合、たとえばのように、数字を1000000000繰り返し抽出してからすべての数に対して乗算するのは非効率的です。

基本的な考え方は、計算中に遭遇する連続するゼロをスキップすることです。たとえば、次のようになります。

using System.Collections.Generic;
using System.Linq;
using System;

// note the digit product is not given with the iteration
// we would need to provide a delegate for the calculation
public static partial class NumericExtensions {
    public static void NumberIteration(
            this int value, Action<int, int[]> delg, int radix=10) {
        var digits=DigitIterator(value, radix).ToArray();
        var last=digits.Length-1;
        var emptyArray=new int[] { };
        var pow=(Func<int, int, int>)((x, y) => (int)Math.Pow(x, 1+y));
        var weights=Enumerable.Repeat(radix, last-1).Select(pow).ToArray();

        for(int complement=radix-1, i=value, j=i; i>0; i-=1)
            if(i>j)
                delg(i, emptyArray);
            else if(0==digits[0]) {
                delg(i, emptyArray);

                var k=0;

                for(; k<last&&0==digits[k]; k+=1)
                    ;

                var y=(digits[k]-=1);

                if(last==k||0!=y) {
                    if(0==y) { // implied last==k
                        digits=new int[last];
                        last-=1;
                    }

                    for(; k-->0; digits[k]=complement)
                        ;
                }
                else {
                    j=i-weights[k-1];
                }
            }
            else {
                // receives digits of a number which doesn't contain zeros 
                delg(i, digits);

                digits[0]-=1;
            }

        delg(0, emptyArray);
    }

    static IEnumerable<int> DigitIterator(int value, int radix) {
        if(-2<radix&&radix<2)
            radix=radix<0?-2:2;

        for(int remainder; 0!=value; ) {
            value=Math.DivRem(value, radix, out remainder);
            yield return remainder;
        }
    }
}

これは数値の列挙のみを目的としており、ゼロを含む数値が最初に計算されるのを避けるために、数字の積はまだコードによって与えられていません。ただし、計算を実行するデリゲートを提供して数字の積を生成するには、まだ時間がかかります。

連続した数字の桁積を効率的に計算するには?

score 5 · Accepted Answer

編集：「どこからでも始めて、範囲を広げた」バージョン...

このバージョンでは範囲が大幅に拡張されているため、十分な桁数を掛け合わせてを超えると、IEnumerable<long>ではなくが返されます。また、最大 10,000,000,000,000,000 - の全範囲ではありませんが、かなり大きいです:) 好きな場所から開始でき、そこから最後まで続きます。IEnumerable<int>int.MaxValuelong

class DigitProducts
{
    private static readonly int[] Prefilled = CreateFirst10000();

    private static int[] CreateFirst10000()
    {
        // Inefficient but simple, and only executed once.
        int[] values = new int[10000];
        for (int i = 0; i < 10000; i++)
        {
            int product = 1;
            foreach (var digit in i.ToString())
            {
                product *= digit -'0';
            }
            values[i] = product;
        }
        return values;
    }

    public static IEnumerable<long> GetProducts(long startingPoint)
    {
        if (startingPoint >= 10000000000000000L || startingPoint < 0)
        {
            throw new ArgumentOutOfRangeException();
        }
        int a = (int) (startingPoint / 1000000000000L);
        int b = (int) ((startingPoint % 1000000000000L) / 100000000);
        int c = (int) ((startingPoint % 100000000) / 10000);
        int d = (int) (startingPoint % 10000);

        for (; a < 10000; a++)
        {
            long aMultiplier = a == 0 ? 1 : Prefilled[a];
            for (; b < 10000; b++)
            {
                long bMultiplier = a == 0 && b == 0 ? 1
                                 : a != 0 && b < 1000 ? 0
                                 : Prefilled[b];
                for (; c < 10000; c++)
                {
                    long cMultiplier = a == 0 && b == 0 && c == 0 ? 1
                                     : (a != 0 || b != 0) && c < 1000 ? 0
                                     : Prefilled[c];

                    long abcMultiplier = aMultiplier * bMultiplier * cMultiplier;
                    for (; d < 10000; d++)
                    {
                        long dMultiplier = 
                            (a != 0 || b != 0 || c != 0) && d < 1000 ? 0
                            : Prefilled[d];
                        yield return abcMultiplier * dMultiplier;
                    }
                    d = 0;
                }
                c = 0;
            }
            b = 0;
        }
    }
}

編集: パフォーマンス分析

パフォーマンスを詳しく見ていませんが、この時点では、作業の大部分は単純に 10 億を超える値を繰り返し処理しているだけだと思います。値自体を返すだけの単純なforループは、私のラップトップで 5 秒以上かかり、数字の積を反復処理するのに 6 秒以上しかかからないため、最適化の余地はあまりないと思います。開始。別の位置から (効率的に) 開始したい場合は、さらに微調整が必要です。

さて、これはイテレータブロックを使用して結果を生成し、最初の 1000 個の結果を事前計算して処理を少し速くする試みです。

約 1 億 5000 万までテストしましたが、今のところ正しいです。最初の 10 億の結果のみが返されます。それ以上の結果が必要な場合は、最後に別のブロックを追加できます...

static IEnumerable<int> GetProductDigitsFast()
{
    // First generate the first 1000 values to cache them.
    int[] productPerThousand = new int[1000];

    // Up to 9
    for (int x = 0; x < 10; x++)
    {
        productPerThousand[x] = x;
        yield return x;
    }
    // Up to 99
    for (int y = 1; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            productPerThousand[y * 10 + x] = x * y;
            yield return x * y;
        }
    }
    // Up to 999
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < 10; y++)
        {
            for (int z = 0; z < 10; z++)
            {
                int result = x * y * z;
                productPerThousand[x * 100 + y * 10 + z] = x * y * z;
                yield return result;
            }
        }
    }

    // Now use the cached values for the rest
    for (int x = 0; x < 1000; x++)
    {
        int xMultiplier = x == 0 ? 1 : productPerThousand[x];
        for (int y = 0; y < 1000; y++)
        {
            // We've already yielded the first thousand
            if (x == 0 && y == 0)
            {
                continue;
            }
            // If x is non-zero and y is less than 100, we've
            // definitely got a 0, so the result is 0. Otherwise,
            // we just use the productPerThousand.
            int yMultiplier = x == 0 || y >= 100 ? productPerThousand[y]
                                                 : 0;
            int xy = xMultiplier * yMultiplier;
            for (int z = 0; z < 1000; z++)
            {
                if (z < 100)
                {
                    yield return 0;
                }
                else
                {
                    yield return xy * productPerThousand[z];
                }
            }
        }
    }
}

信じられないほど単純なバージョンの結果と比較して、これをテストしました。

static IEnumerable<int> GetProductDigitsSlow()
{
    for (int i = 0; i < 1000000000; i++)
    {
        int product = 1;
        foreach (var digit in i.ToString())
        {
            product *= digit -'0';
        }
        yield return product;
    }
}

このアイデアが役に立つことを願っています...パフォーマンスの点で、ここに示されている他のものとどのように比較されるかわかりません。

編集: これを少し拡張して、結果が 0 になることがわかっている単純なループを使用すると、心配する条件が少なくなりますが、何らかの理由で実際には少し遅くなります。(これには本当に驚きました。) このコードは長くなりますが、従うのが少し簡単になる可能性があります。

static IEnumerable<int> GetProductDigitsFast()
{
    // First generate the first 1000 values to cache them.
    int[] productPerThousand = new int[1000];

    // Up to 9
    for (int x = 0; x < 10; x++)
    {
        productPerThousand[x] = x;
        yield return x;
    }
    // Up to 99
    for (int y = 1; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            productPerThousand[y * 10 + x] = x * y;
            yield return x * y;
        }
    }
    // Up to 999
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < 10; y++)
        {
            for (int z = 0; z < 10; z++)
            {
                int result = x * y * z;
                productPerThousand[x * 100 + y * 10 + z] = x * y * z;
                yield return result;
            }
        }
    }

    // Use the cached values up to 999,999
    for (int x = 1; x < 1000; x++)
    {
        int xMultiplier = productPerThousand[x];
        for (int y = 0; y < 100; y++)
        {
            yield return 0;
        }
        for (int y = 100; y < 1000; y++)
        {
            yield return xMultiplier * y;
        }
    }

    // Now use the cached values for the rest
    for (int x = 1; x < 1000; x++)
    {
        int xMultiplier = productPerThousand[x];
        // Within each billion, the first 100,000 values will all have
        // a second digit of 0, so we can just yield 0.
        for (int y = 0; y < 100 * 1000; y++)
        {
            yield return 0;
        }
        for (int y = 100; y < 1000; y++)
        {
            int yMultiplier = productPerThousand[y];
            int xy = xMultiplier * yMultiplier;
            // Within each thousand, the first 100 values will all have
            // an anti-penulimate digit of 0, so we can just yield 0.
            for (int z = 0; z < 100; z++)
            {
                yield return 0;
            }
            for (int z = 100; z < 1000; z++)
            {
                yield return xy * productPerThousand[z];
            }
        }
    }
}

score 4 · Accepted Answer

次の再帰式を使用して、dp のような方法でこれを行うことができます。

n                   n <= 9
a[n/10] * (n % 10)  n >= 10

ここa[n]で、の数字を掛けた結果ですn。

O(n)これは単純なアルゴリズムにつながります:小さいf(n)を既に計算していると仮定して計算する場合、すべての桁の結果を使用できますが、最後に最後の桁を乗算したものを使用できます。f(·)n

a = range(10)
for i in range(10, 100):
    a.append(a[i / 10] * (i % 10))

a[n - 1] + a[n / 10]最後の桁がではない数値に doを追加するだけで、高価な乗算を取り除くことができます0。

score 2 · Accepted Answer

次のような非常に単純なコードになります。

コード：

public delegate void R(
    R delg, int pow, int rdx=10, int prod=1, int msd=0);

R digitProd=
    default(R)!=(digitProd=default(R))?default(R):
    (delg, pow, rdx, prod, msd) => {
        var x=pow>0?rdx:1;

        for(var call=(pow>1?digitProd:delg); x-->0; )
            if(msd>0)
                call(delg, pow-1, rdx, prod*x, msd);
            else
                call(delg, pow-1, rdx, x, x);
    };

msdは最上位桁で、バイナリの最上位ビットのようなものです。

イテレータパターンの使用を選択しなかった理由は、メソッド呼び出しよりも時間がかかるためです。完全なコード (テスト付き) は、この回答の最後に記載されています。

デリゲートは割り当てられる前に使用できないため、この行default(R)!=(digitProd=default(R))?default(R): ...はの割り当て専用であることに注意してください。digitProd実際には次のように記述できます。

代替構文:

var digitProd=default(R);

digitProd=
    (delg, pow, rdx, prod, msd) => {
        var x=pow>0?rdx:1;

        for(var call=(pow>1?digitProd:delg); x-->0; )
            if(msd>0)
                call(delg, pow-1, rdx, prod*x, msd);
            else
                call(delg, pow-1, rdx, x, x);
    };

この実装の欠点は、特定の数字からではなく、最大桁数から開始できることです。

私がそれを解決するいくつかの簡単なアイデアがあります：

再帰

delegate( Action)は、アルゴリズムと桁積の結果を受け取るデリゲートの両方に対して、末尾呼び出しR再帰として使用される再帰的なデリゲート定義です。

そして、以下の他のアイデアは、再帰の理由を説明しています。
分割なし

連続する数字の場合、除算を使用して各桁を抽出するのは効率が悪いと考えられるため、ダウンカウント方式で再帰を使用して直接数字を操作することにしました。

たとえば、の 3 桁の123数字は、から始まる 3 桁の数字の 1 つです999。

9 8 7 6 5 4 3 2 [1] 0 -- 再帰の最初のレベル

9 8 7 6 5 4 3 [2] 1 0 -- 再帰の第 2 レベル

9 8 7 6 5 4 [3] 2 1 0 -- 再帰の第 3 レベル
キャッシュしない

ご覧のとおり、この答え

数字の各桁を効率的に掛ける方法

キャッシングのメカニズムを使用することをお勧めしますが、連続した数字については、それがキャッシュであるため使用しません。

数値の123, 132, 213, 231, 312, 321場合、桁積は同じです。したがって、キャッシュの場合、格納する項目は同じ数字で順序 (順列) が異なるだけであり、それらを同じキーと見なすことができます。

ただし、桁の並べ替えにも時間がかかります。キーのHashSetコレクションが実装されているため、より多くのアイテムでより多くのストレージを支払うことができます。アイテムを減らしたとしても、同等性の比較に時間を費やします。等値比較にその値を使用するよりも優れたハッシュ関数はないようです。これは、計算している結果にすぎません。たとえば、2 桁の九九表には 0 と 1 を除いて 36 通りの組み合わせしかありません。

したがって、計算が十分に効率的である限り、ストレージにコストをかけずにアルゴリズム自体を仮想キャッシュと見なすことができます。
ゼロを含む数値の計算時間を短縮

連続した数字の桁積については、次のようになります。

10 あたり 1 ゼロ

100 あたり 10 個の連続したゼロ

1000 あたり 100 個の連続ゼロ

等々。per 10で遭遇する 9 個のゼロがまだあることに注意してくださいper 100。ゼロの数は、次のコードで計算できます。
```
static int CountOfZeros(int n, int r=10) {
    var powerSeries=n>0?1:0;

    for(var i=0; n-->0; ++i) {
        var geometricSeries=(1-Pow(r, 1+n))/(1-r);
        powerSeries+=geometricSeries*Pow(r-1, 1+i);
    }

    return powerSeries;
}
```
はn桁数、rは基数です。数は、等比級数とプラス 1から計算されたベキ級数になります。0

たとえば、4 桁の数字で、遭遇するゼロは次のとおりです。

(1)+(((1*9)+11)*9+111)*9 = (1)+(1*9*9*9)+(11*9*9)+(111*9) = 2620

この実装では、ゼロを含む数値の計算を実際にスキップしません。その理由は、再帰の浅いレベルの結果が再帰実装で再利用されるためです。これは、 cachedと見なすことができます。単一のゼロを使用した乗算の試行は、実行前に検出して回避することができ、ゼロを次のレベルの再帰に直接渡すことができます。ただし、乗算するだけでは、パフォーマンスに大きな影響はありません。

完全なコード:

public static partial class TestClass {
    public delegate void R(
        R delg, int pow, int rdx=10, int prod=1, int msd=0);

    public static void TestMethod() {
        var power=9;
        var radix=10;
        var total=Pow(radix, power);

        var value=total;
        var count=0;

        R doNothing=
            (delg, pow, rdx, prod, msd) => {
            };

        R countOnly=
            (delg, pow, rdx, prod, msd) => {
                if(prod>0)
                    count+=1;
            };

        R printProd=
            (delg, pow, rdx, prod, msd) => {
                value-=1;
                countOnly(delg, pow, rdx, prod, msd);
                Console.WriteLine("{0} = {1}", value.ToExpression(), prod);
            };

        R digitProd=
            default(R)!=(digitProd=default(R))?default(R):
            (delg, pow, rdx, prod, msd) => {
                var x=pow>0?rdx:1;

                for(var call=(pow>1?digitProd:delg); x-->0; )
                    if(msd>0)
                        call(delg, pow-1, rdx, prod*x, msd);
                    else
                        call(delg, pow-1, rdx, x, x);
            };

        Console.WriteLine("--- start --- ");

        var watch=Stopwatch.StartNew();
        digitProd(printProd, power);
        watch.Stop();

        Console.WriteLine("  total numbers: {0}", total);
        Console.WriteLine("          zeros: {0}", CountOfZeros(power-1));

        if(count>0)
            Console.WriteLine("      non-zeros: {0}", count);

        var seconds=(decimal)watch.ElapsedMilliseconds/1000;
        Console.WriteLine("elapsed seconds: {0}", seconds);
        Console.WriteLine("--- end --- ");
    }

    static int Pow(int x, int y) {
        return (int)Math.Pow(x, y);
    }

    static int CountOfZeros(int n, int r=10) {
        var powerSeries=n>0?1:0;

        for(var i=0; n-->0; ++i) {
            var geometricSeries=(1-Pow(r, 1+n))/(1-r);
            powerSeries+=geometricSeries*Pow(r-1, 1+i);
        }

        return powerSeries;
    }

    static String ToExpression(this int value) {
        return (""+value).Select(x => ""+x).Aggregate((x, y) => x+"*"+y);
    }
}

コードではdoNothing、countOnly、printProdは、桁積の結果を取得したときに何をするかを示しておりdigitProd、完全なアルゴリズムを実装したものに渡すことができます。たとえば、digitProd(countOnly, power)は増加するだけcountで、最終的な結果は返品と同じになりCountOfZerosます。

score 1 · Accepted Answer

数値の 10 進数を表す配列を作成し、実際に行うのと同じようにその数値を増やします (つまり、オーバーフローが発生した場合は上位の桁を増やします)。

そこから、小さなルックアップテーブルとして使用できる積の配列を使用します。

たとえば、数値 314 は積の配列になります: 3, 3, 12 数値 345 は積の配列になります: 3, 12, 60

ここで、10 進数を増やすと、最も右側の積を左の積で乗算して再計算するだけで済みます。2 番目の桁が変更されると、2 つの積 (右から 2 番目と右外側の積) のみが再計算されます。この方法では、絶対に必要以上に計算することはなく、非常に小さなルックアップテーブルが作成されます。

したがって、番号 321 から始めてインクリメントすると、次のようになります。

digits = 3, 2, 1      products = 3, 6, 6
incrementing then changes the outer right digit and therefore only the outer right product is recalculated
digits = 3, 2, 2      products = 3, 6, 12
This goes up until the second digit is incremented:
digits = 3, 3, 0      products = 3, 9, 0 (two products recalculated)

アイデアを示す例を次に示します (あまり良いコードではありませんが、例として):

using System;
using System.Diagnostics;

namespace Numbers2
{
    class Program
    {
        /// <summary>
        /// Maximum of supported digits. 
        /// </summary>
        const int MAXLENGTH = 20;
        /// <summary>
        /// Contains the number in a decimal format. Index 0 is the righter number. 
        /// </summary>
        private static byte[] digits = new byte[MAXLENGTH];
        /// <summary>
        /// Contains the products of the numbers. Index 0 is the righther number. The left product is equal to the digit on that position. 
        /// All products to the right (i.e. with lower index) are the product of the digit at that position multiplied by the product to the left.
        /// E.g.
        /// 234 will result in the product 2 (=first digit), 6 (=second digit * 2), 24 (=third digit * 6)
        /// </summary>
        private static long[] products = new long[MAXLENGTH];
        /// <summary>
        /// The length of the decimal number. Used for optimisation. 
        /// </summary>
        private static int currentLength = 1;
        /// <summary>
        /// The start value for the calculations. This number will be used to start generated products. 
        /// </summary>
        const long INITIALVALUE = 637926372435;
        /// <summary>
        /// The number of values to calculate. 
        /// </summary>
        const int NROFVALUES = 10000;

        static void Main(string[] args)
        {
            Console.WriteLine("Started at " + DateTime.Now.ToString("HH:mm:ss.fff"));

            // set value and calculate all products
            SetValue(INITIALVALUE);
            UpdateProducts(currentLength - 1);

            for (long i = INITIALVALUE + 1; i <= INITIALVALUE + NROFVALUES; i++)
            {
                int changedByte = Increase();

                Debug.Assert(changedByte >= 0);

                // update the current length (only increase because we're incrementing)
                if (changedByte >= currentLength) currentLength = changedByte + 1;

                // recalculate products that need to be updated
                UpdateProducts(changedByte);

                //Console.WriteLine(i.ToString() + " = " + products[0].ToString());
            }
            Console.WriteLine("Done at " + DateTime.Now.ToString("HH:mm:ss.fff"));
            Console.ReadLine();
        }

        /// <summary>
        /// Sets the value in the digits array (pretty blunt way but just for testing)
        /// </summary>
        /// <param name="value"></param>
        private static void SetValue(long value)
        {
            var chars = value.ToString().ToCharArray();

            for (int i = 0; i < MAXLENGTH; i++)
            {
                int charIndex = (chars.Length - 1) - i;
                if (charIndex >= 0)
                {
                    digits[i] = Byte.Parse(chars[charIndex].ToString());
                    currentLength = i + 1;
                }
                else
                {
                    digits[i] = 0;
                }
            }
        }

        /// <summary>
        /// Recalculate the products and store in products array
        /// </summary>
        /// <param name="changedByte">The index of the digit that was changed. All products up to this index will be recalculated. </param>
        private static void UpdateProducts(int changedByte)
        {
            // calculate other products by multiplying the digit with the left product
            bool previousProductWasZero = false;
            for (int i = changedByte; i >= 0; i--)
            {
                if (previousProductWasZero)
                {
                    products[i] = 0;
                }
                else
                {
                    if (i < currentLength - 1)
                    {
                        products[i] = (int)digits[i] * products[i + 1];
                    }
                    else
                    {
                        products[i] = (int)digits[i];
                    }
                    if (products[i] == 0)
                    {
                        // apply 'zero optimisation'
                        previousProductWasZero = true;
                    }
                }
            }
        }

        /// <summary>
        /// Increases the number and returns the index of the most significant byte that changed. 
        /// </summary>
        /// <returns></returns>
        private static int Increase()
        {
            digits[0]++;
            for (int i = 0; i < MAXLENGTH - 1; i++)
            {
                if (digits[i] == 10)
                {
                    digits[i] = 0;
                    digits[i + 1]++;
                }
                else
                {
                    return i;
                }
            }
            if (digits[MAXLENGTH - 1] == 10)
            {
                digits[MAXLENGTH - 1] = 0;
            }
            return MAXLENGTH - 1;
        }
    }
}

このように、10 億の範囲の 1000 個の数の積を計算することは、1 から 1000 までの数の積を計算するのとほぼ同じ速さです。

ところで、これを何に使おうとしているのか非常に気になります。

score 1 · Accepted Answer

数値の長さとシーケンスの長さに応じて、最適化が行われる場合があります。

数値の最大サイズを制限できるため、係数を増やして数値自体を反復処理できます。

あなたが42という数字を持っているとしましょう：

var Input = 42;
var Product = 1;
var Result = 0;

// Iteration - step 1: 
Result = Input % 10; // = 2
Input -= Result;
Product *= Result;

// Iteration - step 2:
Result = Input % 100 / 10; // = 4
Input -= Result;
Product *= Result;

この操作を適切なループにパックすることができます。これはおそらく、プロセッサのキャッシュに収まるほど小さく、整数全体を反復処理できます。関数呼び出しを回避するため、これもおそらく非常に高速です。

アボート基準としてゼロを考慮したい場合、これの実装は明らかに非常に簡単です。

マシューがすでに言ったように: ルックアップテーブルを使用すると、究極のパフォーマンスと効率が得られます。

シーケンス番号の範囲が狭いほど、ルックアップテーブルは高速になります。遅いメモリからではなく、キャッシュから取得されるためです。

c# - 連続した数字の桁積を効率的に計算するには?

7 に答える 7

Related

Reference