Databases
StackOverflow2013
Postsdbo
POIs there a way to improve the speed or efficiency of this lookup? (C/C++)
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs there a way to improve the speed or efficiency of this lookup? (C/C++)
    text
    copied!<p>I have a function I've written to convert from a 64-bit integer to a base 62 string. Originally, I achieved this like so:</p> <pre><code>char* charset = " 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; int charsetLength = strlen(charset); std::string integerToKey(unsigned long long input) { unsigned long long num = input; string key = ""; while(num) { key += charset[num % charsetLength]; num /= charsetLength; } return key; } </code></pre> <p>However, this was too slow.</p> <p>I improved the speed by providing an option to generate a lookup table. The table is about 62<sup>4</sup> strings in size, and is generated like so:</p> <pre><code>// Create the integer to key conversion lookup table int lookupChars; if(lookupDisabled) lookupChars = 1; else largeLookup ? lookupChars = 4 : lookupChars = 2; lookupSize = pow(charsetLength, lookupChars); integerToKeyLookup = new char*[lookupSize]; for(unsigned long i = 0; i &lt; lookupSize; i++) { unsigned long num = i; int j = 0; integerToKeyLookup[i] = new char[lookupChars]; while(num) { integerToKeyLookup[i][j] = charset[num % charsetLength]; num /= charsetLength; j++; } // Null terminate the string integerToKeyLookup[i][j] = '\0'; } </code></pre> <p>The actual conversion then looks like this:</p> <pre><code>std::string integerToKey(unsigned long long input) { unsigned long long num = input; string key = ""; while(num) { key += integerToKeyLookup[num % lookupSize]; num /= lookupSize; } return key; } </code></pre> <p>This improved speed by a large margin, but I still believe it can be improved. Memory usage on a 32-bit system is around 300 MB, and more than 400 MB on a 64-bit system. It seems like I should be able to reduce memory and/or improve speed, but I'm not sure how.</p> <p>If anyone could help me figure out how this table could be further optimized, I'd greatly appreciate it.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload