3

我正在做一个项目，我需要一个非常快速的算法来检查提供的数字是否是泛数字的。尽管逻辑看起来很合理，但我对下面描述的方法的性能并不特别满意。

我可以分别在大约 520 毫秒、600 毫秒和 1600 毫秒内检查多达 100 万个 9 位数字。我正在开发一个低延迟的应用程序，在生产中我将拥有一个大约 9 或 95 亿个 7 到 9 位数字的数据集，我需要检查这些数字。

我现在有三个候选人（嗯，真的有两个）使用以下逻辑：

方法 1：我将一个 inputN拆分为一个包含其组成数字的字节数组，使用函数对其进行排序，并使用循环检查元素与计数器的一致性Array.Sort来遍历数组：for

 byte[] Digits = SplitDigits(N);
 int len = NumberLength(N);
 Array.Sort(Digits);
 for (int i = 0; i <= len - 1; i++)
 {
     if (i + 1 != Digits[i])
          return false;
 }

方法 2：这种方法基于有点可疑的逻辑，但我将输入拆分N为组成数字的字节数组，然后进行以下测试：

 if (N * (N + 1) * 0.5 == DigitSum(N) && Factorial(len) == DigitProduct(N))
      return true;

方法 3：我不喜欢这种方法，因此不是真正的候选者，但我将 int 转换为字符串，然后用于String.Contains确定所需的字符串是否为 pandigital。

第二种和第三种方法具有相当稳定的运行时间，尽管第一种方法反弹很多 - 它有时可以高达 620 毫秒。

所以理想情况下，我真的很想将百万 9 位标记的运行时间减少到 10 毫秒以下。有什么想法吗？

我在 2GHz 的 Pentium 6100 笔记本电脑上运行它。

PS - 第二种方法的数学逻辑合理吗？

4

2 回答 2

1

方法一

预先计算 362880 个 9 位泛数字的排序列表。这将只需要几毫秒。然后对于每个请求，首先检查该数字是否可以被 9 整除：它必须是泛数字的。如果是，则使用二进制搜索来检查它是否在您的预先计算的列表中。

方法二

再次检查数字是否能被 9 整除。然后使用位向量来跟踪数字的存在。也可以使用模乘法来代替乘法除法。

static bool IsPandigital(int n)
{
    if (n != 9 * (int)((0x1c71c71dL * n) >> 32))
        return false;

    int flags = 0;
    while (n > 0) {
        int q = (int)((0x1999999aL * n) >> 32);
        flags |= 1 << (n - q * 10);
        n = q;
    }
    return flags == 0x3fe;
}

方法 1 的速度为 15ms/1M。方法 2在我的机器上以5.5ms/1M的速度出现。这是在 i7 950 上编译为 x64 的 C#。

于 2013-03-03T20:43:58.467 回答
0

只是一个想法：（在维基百科对泛数字的定义之后）

int n = 1234567890;
int Flags = 0;
int Base = 10;
while(n != 0)
{
    Flags |= 1<<(n % Base); n /= Base;
}
bool bPanDigital = Flags == ((1 << Base) - 1);
于 2013-03-03T18:45:16.877 回答