البحث الأمثل ثنائي في ج؟

Question

وأنا أكتب سجل مفتاح تبدو من حيث انتهى لدي المؤشر بين المفتاح وعدد تفصيل. يتم فرز هذه على المفتاح. هناك بعيدا للقيام بذلك أفضل أن ما لدي لتحسين السرعة؟

typedef struct
{
    char key[MAX_KEYLEN];
    int  rec;
} KeyRecPair;

typedef struct
{
    KeyRecPair *map;
    int         numRecs;
} KeyRecMap;

int GetRecFromKey(char *key, KeyRecMap *theMap)
{
    int cmpValue, bottom = 0;
    int half = theMap->numRecs / 2;
    int top = theMap->numRecs - 1;

    while (bottom != top)
    {
        cmpValue = strncmp(key, theMap->map[half].key, MAX_KEY_LEN); 

        if (cmpValue > 0)
        {
            /*top stays*/
            bottom = half + 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        if (cmpValue < 0)
        {
            /*bottom stays*/
            top = half - 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        return theMap->map[half].rec;
    }

    if (0 == strncmp(key, theMap->map[half].key, MAX_KEY_LEN))
        return theMap->map[half].rec;
    return 0;
}

Answer 1

وسيتم إنفاق جزءا كبيرا من وقتك في strncmp.

وأقترح أن يجبر أن يكون inlined أو إعادة كتابتها مضمنة، لتجنب وظيفة استدعاء فوق رأسه.

إذا كنت تشعر الشجعان قد يكون من الممكن ل انبسط حلقة مرة واحدة أو مرتين، و رؤية كسب الأداء.

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

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

وثمة خيار آخر يتمثل في اختيار طريقة مختلفة لتنظيم البيانات الخاصة بك. تحقق من الأشجار AVL للحصول على الإلهام. اختيار نوع من الثرم وظيفة، مثل الآخرين المذكورة، قد يكون خيارا قابلا للتطبيق

Answer 2

bsearch وظيفة مكتبة ينفذ بحث ثنائي عبر مجموعة ، ونظرا لمناسبة مقارنة الوظيفة التي تنفذ. كونها وظيفة المكتبة، وكذلك الأمثل، هو و (أمل) مجانا علة.

Answer 3

وبدلا من استخدام البحث الثنائي لتحديد موقع هذا البند، خريطة التجزئة قد يكون أكثر ملاءمة لأنه يحتوي O (1) خصائص البحث. ومع ذلك قد تكون بطيئة مع حمولة من التصادم مع نهج ساذج. لكن <لأ href = "http://www.google.com/url؟sa=t&source=web&ct=res&cd=1&url=http٪3A٪2F٪2Flamp.epfl.ch٪2Fpapers٪2Fidealhashtrees.pdf&ei=ZTICSdbuDpSa1wbTpPGvDg&usg=AFQjCNG3s5oYB13F1gBsOsH81nvst2rscg&sig2= yW5rBcQCYjCM8JNhmRYHVg "يختلط =" نوفولو noreferrer "> هذه الورقة يصف طريقة لإنشاء hashmap مثل الشجرة التي لديها O (سجل (ن) / سجل (32)) وقت وصول الذي يتفوق عموما تطبيقات hashmap العادية. (وARAY ثابت + تنفيذ قائمة مرتبطة).

Answer 4

وأي فرصة يمكن استخدام مفتاح ليست سلسلة؟ أو على الأقل أقصر السلاسل الممكنة؟ (ما هو قيمة MAX_KEYLEN) والتي strcmp كل تكرار للحلقة الأرجح هو واحد من أجزاء أبطأ من البحث.

Answer 5

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

وبالإضافة إلى ذلك، تذكر أن المعيار. انه من الصعب معرفة أي من نسختين وظيفة أسرع على نظام حديث (كان أسهل على بلدي Z80). كم عدد إخفاقات التخزين المؤقت قد أو قد لا تكون أكثر أهمية من عدد من الفروع وتوقع خاطئ.

Answer 6

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

        if (cmpValue > 0)
        {
                /*top stays*/
                bottom = half + 1;
                half = bottom + (top - bottom) * 3 / 5;
                continue;
        }
        if (cmpValue < 0)
        {
                /*bottom stays*/
                top = half - 1;
                half = bottom + (top - bottom) * 2 / 5;
                continue;
        }

Answer 7

وبدلا من القسمة على 2 U يمكن أن تجعل الاستفادة من عامل التحول قليلا.

=> ل/ 2 ش يمكن استخدام >> 1

Answer 8

ومنذ كنت ستكون لدينا لحساب half مرة واحدة في الحلقة، لماذا لا تفعل ذلك مرة واحدة، فقط قبل استخدامها؟ ومن شأن ذلك أن قطع خطين معقدة المظهر (على الأقل، نسبيا) من التعليمات البرمجية.

Answer 9

وعلى الرغم من أن أتوقع محسن لائق للقيام بذلك نيابة عنك، كنت وضعت theMap-> تعيين في محلية حتى تكون لديه نصف فرصة لتنتهي في سجل بدلا من dereferencing على كل الوصول. مرة أخرى، كنت أتوقع محسن للقيام بذلك نيابة عنك، لذلك قد تحتاج أيضا إلى التحقق إخراج التجمع.

ونظرت في الإخراج البصرية ستوديو 2008 في إطلاق وأنه يقوم بعمل جيد جدا في التعليمات البرمجية. على سبيل المثال، رمز المقارنة يبدو مثل هذا:

; 30   :         if (cmpValue > 0)
test    eax, eax
jle SHORT $LN11@GetRecFrom
; 31   :         {
; omitted inner block for > case.
$LN11@GetRecFrom:
; 37   :         if (cmpValue < 0)
jge SHORT $LN2@GetRecFrom

وأساسا، انها فرع إلى فرع دون إعادة الاختبار cmpValue. لمسة لطيفة.

وهناك فائدة طفيفة لوضع theMap-> تعيين في محلية، لكنها صغيرة. إذا MAX_KEY_LEN ليس من مضاعفات لطيفة من 4 والبنيات ليست مبطنة، يجب عليك بالتأكيد وضع الباحث الأول في البنية الخاصة بك.