تحسين خوارزمية البحث في C

Question

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

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}

Answer 1

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

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

Answer 2

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

علاوة على ذلك، فإن المتغير i ليس له تأثير كبير، حيث تظل الكلمة ثابتة طوال الوظيفة والباقي كبير جدًا بحيث لا يمكن احتواؤه في أي سجل.إنها مسألة حجم ذاكرة التخزين المؤقت فقط وما إذا كان من الممكن احتواء المصفوفة بأكملها هناك.

مقارنات السلسلة مكلفة إلى حد ما من الناحية الحسابية.

هل يمكنك ربما استخدام نوع من التجزئة للمصفوفة قبل البحث؟

Answer 3

هناك تقنية معروفة باسم الطريقة الحارسة.لاستخدام الطريقة الحارسة، يجب أن تعرف طول "المصفوفة []".يمكنك إزالة المقارنة "array[i] != NULL" باستخدام Sental.

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

Answer 4

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

ولكن يمكنك جعل الأمور أسرع قليلاً عن طريق استبدال أشياء مثل

for (i = 0; i < n; ++i)
    foo(a[i]);

مع

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

إذا كانت هناك قيمة معروفة في نهاية المصفوفة (على سبيل المثال:NULL) يمكنك إزالة عداد الحلقة:

for (p = a; *p != NULL; ++p)
    foo(*p)

حظا سعيدا، هذا كتاب عظيم!

Answer 5

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

بخلاف ذلك لا يمكنك فعل الكثير.لا يمكنك الفرز كما يبدو أنك تبحث عن نص داخل نص أكبر.لن يعمل البحث الثنائي أيضًا لأنه من غير المرجح أن يتم فرز النص.

2p الخاص بي (C-psuedocode):

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

Answer 6

مارك هاريسون:لن تنتهي حلقة for الخاصة بك أبدًا!(++p له مسافة بادئة، لكنه ليس في الواقع ضمن for :-)

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

Answer 7

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

char s[] = "\x05Hello";

ثم يمكنك القيام بما يلي:

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

وللحصول على سرعة كبيرة، أضف تلميحات الجلب المسبق للذاكرة لبدء السلسلة + 64، + 128 وبداية السلسلة التالية.ولكن هذا مجرد جنون.:-)

Answer 8

هناك طريقة سريعة أخرى للقيام بذلك وهي جعل المترجم الخاص بك يستخدم memcmp المحسّن لـ SSE2.استخدم مصفوفات الأحرف ذات الطول الثابت وقم بمحاذاتها بحيث تبدأ السلسلة بمحاذاة 64 بايت.إذن أعتقد أنه يمكنك الحصول على وظائف memcmp الجيدة إذا قمت بتمرير const char match[64] بدلاً من const char *match في الوظيفة، أو مطابقة strncpy في مصفوفة 64,128,256، مهما كانت صفيف البايت.

بالتفكير أكثر قليلاً في هذا الأمر، قد تكون وظائف مطابقة SSE2 هذه جزءًا من حزم مثل مكتبات تسريع Intel وAMD.التحقق منها.

Answer 9

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

إذا كنت على استعداد لقضاء بعض الوقت مقدمًا في المعالجة المسبقة للمصفوفة المرجعية، فيجب عليك البحث في Google عن "أسرع برنامج سكرابل في العالم" وتنفيذ ذلك.المفسد:إنه DAG مُحسّن لعمليات البحث عن الشخصيات.

Answer 10

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}