Самый быстрый метод преобразования базы?

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

Я вычеркнул это из класса, который является частью моего приложения, и часть кода была изменена так, чтобы иметь смысл без принадлежащего ему класса.

Решение

Вероятно, вам нужна какая-то версия Itoa. Вот ссылка, которая показывает различные версии itoa с тестами производительности: http://www.jb.man.ac.uk/~slowe /cpp/itoa.html

В общем, я знаю два способа сделать это. Один из способов выполнить последовательные деления, чтобы убрать одну цифру за раз. Другой способ состоит в том, чтобы предварительно вычислять преобразования в «блоках». Таким образом, вы можете предварительно вычислить блок преобразования int в текст размером 62 ^ 3, а затем делать цифры 3 за раз. При условии, что вы сделаете макет памяти и эффективный поиск, это может быть немного быстрее во время выполнения, но влечет за собой штраф за запуск.

Другие советы

Я плохо себя чувствую, потому что я не могу вспомнить, где я первоначально нашел это, но я использовал это в своем коде и обнаружил, что это довольно быстро. Вы можете изменить это, чтобы быть более эффективным в определенных местах, я уверен.

Да, и я чувствую себя хуже, потому что это написано на Java, но быстрый c & amp; 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. Там нет SIMD по модулю.

Если мы сделаем Modulo сами, мы могли бы переписать цикл следующим образом.

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

      leftOver        = newLeftOver;
   }

Теперь у нас есть кое-что, что было бы легко SIMD, если бы не этот поиск ...

Хотя вы все еще можете добиться хорошего улучшения скорости, выполнив модуль по нескольким значениям одновременно. Возможно, было бы даже целесообразно развернуть цикл во второй раз, чтобы вы могли обработать следующие 4 или около того по модулю во время вычисления предыдущего набора (из-за задержки инструкций). Таким образом, вы сможете довольно эффективно скрывать задержки. #

Я вернусь, если смогу найти способ устранить поиск в таблице ...

Редактировать. При этом максимальное число цифр base62, которое вы можете получить из 32-разрядного целого числа, равно 6, и вы должны просто иметь возможность полностью разматывать цикл и обрабатывать все 6 цифр одновременно. Я не совсем уверен, что SIMD даст вам большую выгоду здесь. Это был бы интересный эксперимент, но я действительно сомневаюсь, что вы значительно увеличите скорость за цикл выше. Было бы интересно попробовать, если бы кто-нибудь не налил чай на клавиатуру моей машины: (

Редактировать 2: пока я думаю об этом. Константа / 62 может быть коварно оптимизирована компилятором с использованием страшных магических чисел ... так что я даже не думаю, что вышеприведенный цикл мог бы разделить.

в вышеописанном есть обратные проблемы - младшие разряды стоят первыми в сгенерированной строке - я не знаю, действительно ли это проблема, потому что это зависит от последующего использования сгенерированной строки.

Как правило, этот тип преобразования осей можно ускорить, выполнив его в виде осей *. В вашем случае требуется символ [2] [62 * 62]. Этот массив может быть создан во время инициализации (это const).

Это должно быть сравнительно. Раньше стоимость деления была ОГРОМНОЙ, поэтому экономия половины дележей была верной победой. Это зависит от способности кешировать эту таблицу размером более 7000 байтов и стоимости деления.

Если вы получаете повреждение кучи, у вас есть проблемы, помимо кода, который вы здесь показываете.

Вы можете сделать строковый класс быстрее, зарезервировав пространство для строки перед началом, с помощью string :: reserve.

Ваша строка выводится в обратном порядке, цифра base-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 для 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;
        }

}

Я накапливаю другой ответ, потому что несколько попыток, которые я попробовал, не дали ожидаемого результата. Хотя это оптимизировано для удобства чтения, а не для скорости.

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