最快基转换方法？

https://stackoverflow.com/questions/1235371

c++
base

22-07-2019
|

题

现在我正在这需要一个整数转换为一个基座62串多次的第二项目。越快此转换完成时，就更好了。

的问题是，我有一个很难让我自己的基地转换方法要快的和的可靠。如果我使用的字符串，它通常是可靠的，并且效果很好，但它的速度慢。如果我用字符数组，这是通常速度更快，但它也很凌乱，和不可靠的。（它产生堆损坏，字符串的比较应该匹配返回一个负等）

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

我撕开此列一类是我的应用程序的一部分的，和一些代码被修改，使得它是有意义SANS其所属类。

解决方案

也许你想要的是itoa的一些版本。下面是显示了性能测试itoa的各种版本的链接： http://www.jb.man.ac.uk/~slowe /cpp/itoa.html

在一般情况下，我知道有两种方法可以做到这一点。单程它执行连续分裂以一次剥离一个数字。另一种方法是预先计算的转换中的“块”。所以，你可以预先计算为int的大小62 ^ 3的文本转换块然后做数字3在同一时间。只要你做的内存布局和查询效率这可以在运行时速度稍快，但招致启动点球。

其他提示

我觉得不好，因为我不记得在那里我最初发现这一点，但我已经在我的代码利用了这一点，并发现它是非常快。你可以修改这是在某些地方更有效的，我相信。

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

 }

关闭我的头顶，我期望的实现看起来很像这一点。

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 optimisable。没有SIMD模。

如果我们做模自己，我们可以依次改写循环如下：

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

      leftOver        = newLeftOver;
   }

现在我们有一些，如果不是为查找这将是很容易SIMD ...

虽然你仍然可以通过同时做多个值的模获得了良好的速度提高。它很可能甚至是值得展开循环，第二次这样你就可以处理下一个4个左右modulos而前一组的计算（由于指令延迟）。你应该能够非常有效地隐藏延迟这种方式。＃

我会回来，如果我能想到的办法消除查表...

编辑：那就是说，你可以从32位整数得到的base62的最大位数是6，你就应该能够同时完全放松的循环和处理所有6位数字。我不能完全肯定SIMD会给你在这里多一个双赢的。这将会是一个有趣的实验，但我真的怀疑你会得到所有的东西，一个加速过上述循环。将是有趣的尝试，如果有人没有倒茶了我开发机的键盘：（

编辑2：虽然我想。恒定/ 62能够巧妙地利用吓人幻数的编译器优化...所以不连估计上述环路会做除法。

有在上面的倒车问题 - 低订单进来第一生成的字符串中 - 因为这取决于生成的字符串的后续使用，我不知道如果这实际上是一个问题

通常这种基数转换可以通过在基数*基数块做它被加速在你的情况一个char [2] [62 * 62]需要。此阵列可在初始化时被构造（它是常数）。

此必须虽然基准。使用的鸿沟成本是巨大的，从而节省了一半的分歧是稳赚。这取决于缓存此7000+字节表和除法的成本的能力。

如果你正在堆损坏，你必须超越你在这里展示的代码的问题。

开始之前，用绳子::储备可以使字符串类更快地预留空间的字符串。

您字符串出来以相反的顺序，低阶基-62位是字符串中的第一个字符。这也许可以解释的比较问题。

您实现几乎一样快，因为它是会得到。我会建议一些改动，但：

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分），也有可能是整型的不同值不正确地得到转换为相同的字符串。对于基座62，则0和62将被编码为"0"。

这是很难说是否上述任一变化会引发您的报告堆损坏的问题，没有一点更多的内容（如maxChars的值）。

此外，你应该知道，上面的代码会写在相反的顺序（基数为10尝试，转换一个数字，如12345，看看我的意思）的字符串表示的数字。这可能不是问题，希望您的应用程序，虽然。

下面是我在PHP（在本实施例62）使用用于基本10至N中的溶液，点击我的整个后是在这里： 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;
        }

}

我打桩用另一种答案，因为一对夫妇的答案我想没有产生我期望的输出。虽然，这是为了便于阅读优化，而不是速度。

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;
}

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow