c# - 如何高效计算连续数的位数乘积？

Question

我正在尝试计算数字序列中每个数字的数字乘积，例如:

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

会是:

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

为了降低复杂性，我只考虑 [ consecutive numbers ] 在有限长度的数字中，例如从 001 到 999 或从 0001 到 9999。

但是，当序列很大时，例如 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;
        }
    }
}

这里只是针对数字的枚举，为了避免先计算包含零的数字，代码还没有给出数字乘积；但是通过提供委托(delegate)来执行计算来生成数字产品仍然需要时间。

如何高效计算连续数的乘积？

Answer 1

编辑:“从任何地方开始，扩展范围”版本...

此版本具有显着扩展的范围，因此返回 IEnumerable<long>而不是 IEnumerable<int> - 将足够多的数字相乘，你就超过了 int.MaxValue .它也上升到 10,000,000,000,000,000 - 不完全是 long 的全部范围, 但相当大 :) 你可以从任何你喜欢的地方开始，它会从那里一直持续到结束。

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;
        }
    }
}

---

编辑:性能分析

我没有详细查看性能，但我相信目前大部分工作只是简单地迭代超过十亿个值。一个简单的for仅返回值本身的循环在我的笔记本电脑上需要 5 多秒，而迭代数字产品只需要 6 秒多一点，所以我认为没有更多的优化空间 - 如果你想从头开始.如果您想(有效地)从不同的位置开始，则需要进行更多调整。

---

好的，这里尝试使用迭代器 block 来产生结果，并预先计算前 1000 个结果以加快速度。

我已经测试了大约 1.5 亿，到目前为止它是正确的。它只会返回前十亿个结果——如果你需要更多，你可以在最后添加另一个 block ......

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];
            }
        }
    }
}