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

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

Ой, и мне хуже, потому что это написано на 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;
     }

 }

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

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

Ваша строка выходит в обратном порядке, цифра с основанием 62 младшего разряда является первым символом в строке. Это может объяснить ваши проблемы со сравнением.

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

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 может быть искусно оптимизирована компилятором, используя страшные магические числа ... поэтому я даже не думаю, что приведенный выше цикл будет делить.

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

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

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

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

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

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

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

Ваша реализация выполняется настолько быстро, насколько это возможно. Я бы посоветовал внести несколько изменений:

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, чтобы понять, что я имею в виду). Однако это может не иметь значения для вашего приложения.