最速のベース変換方法？
https://stackoverflow.com/questions/1235371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
今、私は整数をベース62文字列に1秒間に何回も変換する必要があるプロジェクトに取り組んでいます。この変換がより速く完了するほど、より良くなります。
問題は、独自の基本変換メソッドを高速に 信頼できるものにするのに苦労していることです。文字列を使用する場合、一般的に信頼性が高く、うまく機能しますが、遅いです。 char配列を使用する場合、通常ははるかに高速ですが、非常に乱雑で信頼性も低くなります。 （ヒープの破損、一致するはずの文字列の比較で負の値が返されるなど）
では、非常に大きな整数からベース62キーに変換する最も高速で信頼性の高い方法は何ですか？将来的には、アプリケーションでSIMDモデルコードを利用する予定ですが、この操作はまったく並列化可能ですか？
編集：この操作は1秒間に数百万回実行されます。操作が終了するとすぐに、ループの一部として再び開始されるため、実行が高速であるほど効果的です。変換される整数は任意のサイズであり、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
一般に、これを行うには2つの方法があります。連続した除算を実行して、一度に1桁を除去する1つの方法。もう1つの方法は、「ブロック」単位でコンバージョンを事前計算することです。したがって、サイズ62 ^ 3のintからテキストへの変換ブロックを事前に計算してから、一度に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モジュロはありません。
自分でモジュロを行うと、次のようにループを書き換えることができます。
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は、恐ろしいマジックナンバーを使用してコンパイラによって巧妙に最適化できます。そのため、上記のループが除算を行うとは考えていません。
上記には逆の問題があります-生成された文字列の下位が最初になります-生成された文字列のその後の使用に依存するため、実際に問題であるかどうかはわかりません。
通常、この種の基数変換は、radix * radixチャンクで行うことで高速化できます。 あなたの場合、char [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の両方が＆quot; 0＆quot; としてエンコードされます。
上記の変更のいずれかが、もう少しコンテキスト（ maxChars の値など）なしで報告されたヒープ破損の問題を引き起こしているかどうかを判断するのは困難です。
また、上記のコードは文字列表現の数字を逆の順序で書き込むことに注意する必要があります（10進数で試して、12345などの数値を変換して意味を確認します）。ただし、これはアプリケーションにとっては重要ではありません。
ここでは、ベース10からN（この例では62）のPHPで使用するソリューションを示します
投稿全体はこちらです： 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;
}
