最快的碱基转换方法？

Question

现在我正在做一个项目，该项目需要每秒多次将整数转换为基数 62 字符串。这种转换完成得越快越好。

问题是我很难让自己的基本转换方法快速 _可靠_。如果我使用字符串，它通常是可靠的并且运行良好，但速度很慢。如果我使用 char 数组，它通常会快得多，但它也非常混乱且不可靠。 （它会产生堆损坏，应该匹配的字符串比较返回负数等）

那么从一个非常大的整数转换为一个 base 62 键的最快和最可靠的方法是什么？将来，我计划在我的应用程序中使用 SIMD 模型代码，那么这个操作是否可以并行化？

编辑：此操作每秒执行数百万次；一旦操作完成，它就会作为循环的一部分重新开始，所以它运行得越快越好。被转换的整数是任意大小的，并且可以很容易地与 128 位整数（或更大）一样大。

编辑：这是我目前正在使用的功能。

 char* charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int charsetLength = (int)(strlen(charset));

//maxChars is an integer specifying the maximum length of the key
char* currentKey = new char[maxChars];

void integerToKey(unsigned long long location)
{
    unsigned long long num = location;
    int i = 0;

    for(; num > 0; i++)
    {
            currentKey[i] = charset[num % (charsetLength)];
            num /= charsetLength + 1;
    }

    currentKey[i + 1] = '\0';
}

我从属于我的应用程序的一个类中删除了它，并且修改了一些代码，使其在没有其所属类的情况下有意义。

原文由 jakogut 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

可能您想要的是某个版本的 itoa。这是一个链接，显示了各种版本的 itoa 以及性能测试：http: //www.strudel.org.uk/itoa/

一般来说，我知道有两种方法可以做到这一点。它执行连续除法的一种方法是一次去掉一个数字。另一种方法是预先计算“块”中的转换。因此，您可以预先计算一个大小为 62^3 的 int 到文本转换的块，然后一次执行数字 3。如果您有效地进行内存布局和查找，这在运行时可能会稍微快一些，但会导致启动损失。

原文由 Corwin Joy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

在我的脑海中，我希望实现看起来很像这样。

 const char lookUpTable[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
  'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
  'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
  'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };

std::string ConvertToBase62( int integer )
{
   char res[MAX_BASE62_LENGTH];
   char* pWritePos = res;
   int leftOver = integer;
   while( leftOver )
   {
      int value62     = leftOver % 62;
      *pWritePos      = lookUpTable[value62];
      pWritePos++;

      leftOver        /= value62;
   }
   *pWritePos = 0;

   return std::string( res );
}

目前，这不是非常可优化的 SIMD。没有 SIMD 模数。

如果我们自己做模数，我们可以反过来重写循环如下。

    while( leftOver )
   {
      const int newLeftOver = leftOver / 62;
      int digit62     = leftOver - (62 * newLeftOver);
      *pWritePos      = lookUpTable[digit62];
      pWritePos++;

      leftOver        = newLeftOver;
   }

现在我们有了一些很容易 SIMD 的东西，如果不是为了那个查找…

尽管您仍然可以通过同时对多个值进行取模来获得很好的速度提升。甚至可能值得再次展开循环，这样您就可以在前一组正在计算时处理接下来的 4 个左右的模数（由于指令延迟）。您应该能够通过这种方式非常有效地隐藏延迟。 #

如果我能想出一种消除表格查找的方法，我会回来的……

编辑：也就是说，您可以从 32 位整数中获得的最大 base62 位数是 6，您应该能够完全展开循环并同时处理所有 6 位数字。我不完全确定 SIMD 会在这里给你带来很大的胜利。这将是一个有趣的实验，但我真的怀疑你是否会在上面的循环中获得这么多的加速。如果有人没有在我的开发机器的键盘上倒茶，那么尝试一下会很有趣:(

编辑2：虽然我想。常量 / 62 可以由编译器使用可怕的幻数巧妙地优化……所以我什至不认为上面的循环会做一个除法。

原文由 Goz 发布，翻译遵循 CC BY-SA 2.5 许可协议