最快的基本转换方法？

Question

现在我正在开发一个项目,它需要一个整数转换为基本62字符串,每秒多次.转换完成得越快越好.

问题是,我有一个很难让我自己的基地转换方法是快速和可靠的.如果我使用字符串,它通常可靠且运行良好,但速度很慢.如果我使用char数组,它通常要快得多,但它也非常混乱,并且不可靠.(它会产生堆损坏,比较应匹配的字符串返回负数等)

那么从一个非常大的整数转换为一个基本的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';
}

我从一个属于我的应用程序的类中删除了这个,并修改了一些代码,以便它没有意义而没有它的拥有类.

Answer 1

我很难过，因为我不记得最初在哪里找到它，但是我一直在代码中使用它，并且发现它非常快。您可以在某些地方修改此设置，使其效率更高。

哦，我感到更糟，因为这是用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;
     }

 }

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模数.

如果我们自己做Modulo,我们可以按如下方式重写循环.

   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进行精巧优化......所以我甚至不认为上面的循环会产生分歧.

Answer 3

可能你想要的是itoa的某个版本.这是一个链接,显示各种版本的itoa和性能测试:http://www.jb.man.ac.uk/~slowe/cpp/itoa.html

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