가장 빠른 기본 변환 방법?
https://stackoverflow.com/questions/1235371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
지금 저는 정수를 초당 여러 번 기본 62 문자열로 변환해야 하는 프로젝트를 진행하고 있습니다.이 변환이 빨리 완료될수록 좋습니다.
문제는 나만의 기본 변환 방법을 빠르게 얻는 데 어려움을 겪고 있다는 것입니다. 그리고 믿을 수 있는.문자열을 사용하면 일반적으로 안정적이고 잘 작동하지만 속도가 느립니다.char 배열을 사용하면 일반적으로 훨씬 빠르지만 매우 지저분하고 신뢰할 수 없습니다.(힙 손상, 일치해야 하는 문자열 비교가 음수 반환 등을 생성합니다.)
그렇다면 매우 큰 정수를 기본 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';
}
나는 이것을 내 애플리케이션의 일부인 클래스에서 추출했으며 일부 코드는 소유 클래스가 없어도 이해가 되도록 수정되었습니다.
해결책
아마도 당신이 원하는 것은 ITOA의 일부 버전 일 것입니다. 다음은 성능 테스트가 포함 된 다양한 버전의 ITOA를 보여주는 링크입니다.http://www.jb.man.ac.uk/~slowe/cpp/itoa.html
일반적으로 저는이 작업을 수행하는 두 가지 방법을 알고 있습니다. 한 번에 한 번에 한 자리를 제거하기 위해 연속적인 부서를 수행하는 한 가지 방법. 또 다른 방법은 "블록"에서 변환을 전제하는 것입니다. 따라서 크기 62^3의 텍스트 변환을 위해 int 블록을 사전 컴퓨팅 한 다음 한 번에 숫자 3을 수행 할 수 있습니다. 메모리 레이아웃과 조회를 효율적으로 수행하면 런타임에 약간 더 빠를 수 있지만 시작 페널티가 발생합니다.
다른 팁
나는 원래 이것을 찾은 곳을 기억할 수 없기 때문에 기분이 나쁘지만 코드에서 이것을 사용하고 있으며 꽤 빠른 것으로 나타났습니다. 내가 확신하는 특정 장소에서 더 효율적으로 이것을 수정할 수 있습니다.
오 그리고 이것이 Java로 작성 되었기 때문에 더 나빠지지만 빠른 C & P와 Refactor는 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와 함께 시작하기 전에 문자열 공간을 예약하여 문자열 클래스를 더 빨리 만들 수 있습니다.
문자열이 역순으로 나옵니다. 하위 주문베이스 -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와 같은 숫자를 변환하여 의미하는 바를 확인하십시오). 그러나 이것은 귀하의 응용 프로그램에 중요하지 않을 수 있습니다.
다음은 Base 10 ~ N에 PHP에서 사용하는 솔루션입니다 (이 예에서 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;
}
}
내가 시도한 몇 가지 답변이 내가 예상 한 출력을 생성하지 않았기 때문에 다른 답변을 쌓고 있습니다. 그러나 이것은 속도가 아닌 가독성에 최적화됩니다.
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;
}
