c# - 泛指校验的快速算法

Question

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

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

我现在有三个候选人(好吧，实际上是两个)使用以下逻辑:

方法 1: 我将一个输入 N 拆分为其组成数字的字节数组，使用 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;
 }

方法二:这个方法是基于有点可疑的逻辑，但是我将输入的N拆分成一个由组成数字组成的字节数组，然后进行以下测试:

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

方法 3: 我不喜欢这种方法，所以不是真正的候选人，但我将 int 转换为字符串，然后使用 String.Contains 来确定是否需要字符串是泛指的。

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

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

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

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

Answer 1

方法一

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

方法二

再次检查数字是否可以被 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#。