题
现在我正在这需要一个整数转换为一个基座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;
}