如何有效地计算连续数字的数字产品？

Question

我正在尝试计算一系列数字的每个数字的数字乘积,例如:

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

将会:

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

为了减少复杂性,我会考虑只有[ 连续编号中的数字的有限长度],如从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;
        }
    }
}

这仅用于枚举数字,以避免首先计算包含零的数字,数字产品尚未由代码给出; 但通过提供代表执行计算生成数字产品仍需要时间.

如何有效地计算连续数字的数字产品？

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秒多一点,所以我认为没有更多的优化空间 - 如果你想从开始.如果您想(有效地)从不同的位置开始,则需要进行更多调整.

好的,这是一个尝试,它使用迭代器块来产生结果,并预先计算前1000个结果以使事情变得更快.

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

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