13

现在我正在做一个项目，该项目需要每秒多次将整数转换为基数 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';
}

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

4

8 回答 8

5

我感觉很糟糕，因为我不记得我最初在哪里找到它，但我一直在我的代码中使用它并且发现它非常快。我敢肯定，您可以在某些地方修改它以提高效率。

哦，我感觉更糟，因为这是用 Java 编写的，但是快速的 c&p 和重构可以让它在 c++ 中工作

public class BaseConverterUtil {

     private static final String baseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

     public static String toBase62( int decimalNumber ) {
         return fromDecimalToOtherBase( 62, decimalNumber );
     }

     public static String toBase36( int decimalNumber ) {
         return fromDecimalToOtherBase( 36, decimalNumber );
     }

     public static String toBase16( int decimalNumber ) {
         return fromDecimalToOtherBase( 16, decimalNumber );
     }

     public static String toBase8( int decimalNumber ) {
         return fromDecimalToOtherBase( 8, decimalNumber );
     }

     public static String toBase2( int decimalNumber ) {
         return fromDecimalToOtherBase( 2, decimalNumber );
     }

     public static int fromBase62( String base62Number ) {
         return fromOtherBaseToDecimal( 62, base62Number );
     }

     public static int fromBase36( String base36Number ) {
         return fromOtherBaseToDecimal( 36, base36Number );
     }

     public static int fromBase16( String base16Number ) {
         return fromOtherBaseToDecimal( 16, base16Number );
     }

     public static int fromBase8( String base8Number ) {
         return fromOtherBaseToDecimal( 8, base8Number );
     }

     public static int fromBase2( String base2Number ) {
         return fromOtherBaseToDecimal( 2, base2Number );
     }

     private static String fromDecimalToOtherBase ( int base, int decimalNumber ) {
         String tempVal = decimalNumber == 0 ? "0" : "";
         int mod = 0;

         while( decimalNumber != 0 ) {
             mod = decimalNumber % base;
             tempVal = baseDigits.substring( mod, mod + 1 ) + tempVal;
             decimalNumber = decimalNumber / base;
         }

         return tempVal;
     }

     private static int fromOtherBaseToDecimal( int base, String number ) {
         int iterator = number.length();
         int returnValue = 0;
         int multiplier = 1;

         while( iterator > 0 ) {
             returnValue = returnValue + ( baseDigits.indexOf( number.substring( iterator - 1, iterator ) ) * multiplier );
             multiplier = multiplier * base;
             --iterator;
         }
         return returnValue;
     }

 }
于 2009-08-05T20:43:32.987 回答
5

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

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 可以由编译器使用可怕的幻数巧妙地优化......所以我什至不认为上面的循环会做一个除法。

于 2009-08-05T20:46:53.400 回答
5

可能您想要的是某个版本的 itoa。这是一个链接，显示了各种版本的 itoa 以及性能测试： http ://www.jb.man.ac.uk/~slowe/cpp/itoa.html

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

于 2009-08-05T20:50:32.643 回答
2

上面有相反的问题 - 生成的字符串中的低阶首先出现 - 我不知道这是否真的是一个问题，因为它取决于生成的字符串的后续使用。

一般来说，这种基数转换可以通过在基数*基数块中进行加速在您的情况下，需要一个 char[2][62*62] 。这个数组可以在初始化时构造（它是常量）。

不过，这必须进行基准测试。分割成本曾经是巨大的，所以节省一半的分割是肯定的胜利。这取决于缓存这个 7000+ 字节表的能力和划分的成本。

于 2009-08-05T21:05:56.217 回答
1

如果您遇到堆损坏，那么您遇到的问题超出了您在此处显示的代码。

您可以通过在开始之前使用 string::reserve 为字符串保留空间来使字符串类更快。

您的字符串以相反的顺序出现，较低的 base-62 数字是字符串中的第一个字符。这可能会解释您的比较问题。

于 2009-08-05T21:50:16.987 回答
1

你的实现几乎和它会得到的一样快。不过，我建议进行一些更改：

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; // use charsetLength
    }
    currentKey[i] = '\0'; // put the null after the last written char
}

第一个更改（除以charsetLength）可能导致您的字符串比较问题。使用您的原始代码（除以charsetLength + 1），可能会有不同的整数值错误地转换为相同的字符串。对于 base 62，那么 0 和 62 都将被编码为"0".

如果没有更多上下文（例如 的值maxChars），很难说上述任何一个更改是否会导致您报告的堆损坏问题。

此外，您应该知道，上面的代码将以相反的顺序写入字符串表示的数字（尝试以 10 为基数并转换一个数字，例如 12345 以了解我的意思）。不过，这对您的应用程序可能无关紧要。

于 2009-08-05T23:58:59.597 回答
0

这是我在 php 中使用的 Base 10 到 N 的解决方案（本例中为 62）
我的整个帖子都在这里： http: //ken-soft.com/ ?p=544

public class BNID {
        // Alphabet of Base N (This is a Base 62 Implementation)
        var $bN = array(
            '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'
        );

        var $baseN;

        function __construct() {
            $this->baseN = count($this->bN);
        }

        // convert base 10 to base N
        function base10ToN($b10num=0) {
            $bNnum = "";
            do {
                $bNnum = $this->bN[$b10num % $this->baseN] . $bNnum;
                $b10num /= $this->baseN;
            } while($b10num >= 1);     
            return $bNnum;
        }

        // convert base N to base 10
        function baseNTo10($bNnum = "") {
           $b10num = 0;
            $len = strlen($bNnum);
            for($i = 0; $i < $len; $i++) {
                $val = array_keys($this->bN, substr($bNnum, $i, 1));
                $b10num += $val[0] * pow($this->baseN, $len - $i - 1);
            }
            return $b10num;
        }

}
于 2010-09-03T14:48:00.553 回答
0

我正在补充另一个答案，因为我尝试的几个答案没有产生我预期的输出。不过，这是针对可读性而非速度进行优化的。

string toStr62(unsigned long long num) {
   string charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
   int base = charset.length();
   string str = num ? "" : "0";

   while (num) {
      str = charset.substr(num % base, 1) + str;
      num /= base;
   }

   return str;
}
于 2014-03-10T20:26:41.687 回答