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

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

11 голосов
/ 05 августа 2009

Сейчас я работаю над проектом, который требует преобразования целого числа в базовую строку 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';
}

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

Ответы [ 8 ]

5 голосов
/ 06 августа 2009

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

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

5 голосов
/ 06 августа 2009

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

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

5 голосов
/ 06 августа 2009

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

Да, и я чувствую себя хуже, потому что это написано на 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;
     }

 }
2 голосов
/ 06 августа 2009

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

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

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

1 голос
/ 06 августа 2009

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

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

1 голос
/ 06 августа 2009

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

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

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

0 голосов
/ 11 марта 2014

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

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;
}
0 голосов
/ 03 сентября 2010

Вот решение, которое я использую в 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;
        }

}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...