أسرع تحويل قاعدة الأسلوب ؟

Question

أنا الآن أعمل على المشروع الذي يتطلب عدد صحيح يمكن تحويلها إلى قاعدة 62 السلسلة عدة مرات في الثانية.وأسرع هذا التحويل يتم الانتهاء أفضل.

المشكلة هي أن أواجه صعوبة في الحصول على بلدي قاعدة أساليب التحويل أن تكون سريعة و موثوق بها.إذا كنت تستخدم سلاسل, عموما موثوق بها و يعمل بشكل جيد, لكنه بطيء.إذا كنت تستخدم شار المصفوفات ، عموما أسرع بكثير, لكنه أيضا فوضوي جدا و لا يمكن الاعتماد عليها.(وتنتج كومة الفساد ، مقارنة السلاسل التي يجب أن مباراة العودة سلبي ، إلخ.)

فما هي الطريقة الأسرع والأكثر موثوقية تحويل من جدا كبير عدد صحيح إلى قاعدة 62 المفتاح ؟ في المستقبل, أنا تخطط لاستخدام SIMD نموذج التعليمات البرمجية في التطبيق الخاص بي ، لذلك هذه العملية parallelizable في كل شيء ؟

تحرير:يتم تنفيذ هذه العملية عدة ملايين مرة في الثانية ؛ بمجرد عملية التشطيبات ، ويبدأ مرة أخرى كجزء من حلقة ، لذا أسرع تشغيله أفضل.صحيح أن تتحول من حجم التعسفي ، ويمكن بسهولة كبيرة مثل 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 لها امتلاك الطبقة.

Answer 1

وربما ما كنت أريده هو بعض نسخة من itoa. هنا هو وجود صلة التي تظهر الإصدارات المختلفة من itoa مع اختبارات الأداء: http://www.jb.man.ac.uk/~slowe /cpp/itoa.html

في عام، أنا أعرف طريقتين للقيام بذلك. طريقة واحدة لأداء الانقسامات المتتالية لتجريدها من رقم واحد في وقت واحد. وهناك طريقة أخرى لprecompute التحويلات في "لبنات". لذلك يمكن أن precompute كتلة من كثافة على تحويل النص من حجم 62 ^ 3 ثم القيام الأرقام 3 في وقت واحد. شريطة أن تفعل تخطيط الذاكرة والبحث بكفاءة هذا يمكن أن يكون أسرع قليلا في وقت التشغيل ولكن يتحمل ركلة جزاء بدء التشغيل.

Answer 2

وأنا أشعر بالضيق لأنني غير قادر على تذكر حيث وجدت أصلا هذا، ولكن لقد تم استخدام هذا في قانون بلدي ووجدت لها أن تكون سريعة جدا. هل يمكن تعديل هذه لتكون أكثر كفاءة في أماكن معينة وأنا واثق.

ويا وأشعر أسوأ لأن هذا هو مكتوب في جاوة، ولكن سريع ج & p و ريفاكتور يمكن الحصول على عمل في ج ++

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;
     }

 }

Answer 3

وقبالة رأس لي رئيس أتوقع تنفيذا لتبدو الكثير من هذا القبيل.

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 );
}

في هذه اللحظة هذا ليس optimisable SIMD جدا. ليس هناك مودولو SIMD.

وإذا لم نفعل مودولو أنفسنا أننا يمكن أن بدورها كتابة حلقة النحو التالي.

   while( leftOver )
   {
      const int newLeftOver = leftOver / 62;
      int digit62     = leftOver - (62 * newLeftOver);     
      *pWritePos      = lookUpTable[digit62];
      pWritePos++;

      leftOver        = newLeftOver;
   }

والآن لدينا شيء من شأنه أن يكون من السهل SIMD لو لم يكن لهذا البحث ...

وعلى الرغم من أنك لا يزال الحصول على تحسين سرعة جيدة عن طريق القيام بما مودولو لعدة قيم في وقت واحد. انها تريد ربما حتى يكون من المفيد الفتح الحلقة مرة ثانية حتى تتمكن من معالجة المقبل 4 أو نحو ذلك MODULOS في حين أن مجموعة سابقة تم احتساب (نظرا لكمون تعليمات). يجب أن تكون قادرة على إخفاء الإختفاء جدا فعال بهذه الطريقة. #

وسأعود اذا كنت استطيع التفكير في طريقة للقضاء على بحث الطاولة ...

وتحرير: وهذا كما قال الحد الأقصى لعدد الأرقام base62 يمكنك الحصول عليها من عدد صحيح 32-بت 6 يجب أن تكون فقط قادرة على الاسترخاء الكامل للحلقة ومعالجة كافة الأرقام 6 في وقت واحد. أنا لست متأكدا تماما أن SIMD تعطيك الكثير من الفوز هنا. انها تريد ان تكون تجربة مثيرة للاهتمام لكنني أشك حقا كنت أحصل كل ذلك بكثير من سرعة على مدى حلقة أعلاه. سيكون من المفيد أن تحاول ذلك إذا كان شخص ما لا سكب الشاي على لوحة المفاتيح بلدي آلة ديف ل: (

وتحرير 2: بينما كنت تفكر في ذلك. ثابت / 62 يمكن أن يكون الأمثل ببراعة من قبل المجمع التي تستخدم فيها أرقام سحرية مخيفة ... لذلك أنا حتى لا يحسب لها حساب في حلقة فوق ستفعل الانقسام.

Answer 4

وهناك قضايا عكس في أعلاه - أوامر منخفضة تأتي أولا في سلسلة لدت - أنا لا أعرف إذا كان هذا هو في الواقع قضية لأنها تعتمد على استخدام لاحقة من السلسلة الناتجة

وعموما هذا النوع من التحويل الجذر يمكن التعجيل من يفعل ذلك في الجذر * قطع الجذر في قضيتك شار [2] [62 * 62] مطلوب. هذه المجموعة يمكن بناؤها في وقت التهيئة (وهو CONST).

وهذا يجب قياسها على الرغم من. تكلفة الفجوة تستخدم ليكون ضخم جدا إنقاذ نصف الانقسامات كان على يقين من الفوز. ذلك يعتمد على القدرة على تخزين هذا الجدول بايت 7000+ وتكلفة الفجوة.

Answer 5

إذا كنت تحصل على الفساد كومة، لديك مشاكل ما بعد رمز كنت تظهر هنا.

ويمكنك جعل الطبقة سلسلة أسرع بحجز مساحة لسلسلة قبل أن تبدأ، مع سلسلة :: الاحتياطي.

وسلسلة الخاص بك هو الخروج بترتيب عكسي، وانخفاض أجل قاعدة-62 الرقم هو الحرف الأول في السلسلة. هذا قد يفسر القضايا المقارنة.

Answer 6

وتنفيذ الخاص بك هو الى حد كبير بالسرعة انها سوف تحصل عليها. أود أن أقترح عددا من التغييرات على الرغم من:

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 لرؤية ما أعنيه). هذا قد لا يهم للتطبيق الخاص بك، وإن كان.

Answer 7

هنا الحل يمكنني استخدام في بي على قاعدة 10 ن (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;
        }

}

Answer 8

وأنا تتراكم على مع إجابة أخرى لبضع إجابات حاولت لم تسفر الناتج كنت أتوقع. رغم ذلك، تم تحسين هذا من أجل قراءة، وليس السرعة.

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;
}