دمج غير متكرر

Question

هل يمكن لأحد أن يشرح باللغة الإنجليزية كيف يعمل فرز الدمج غير المتكرر؟

شكرًا

Answer 1

حلقة من خلال العناصر وجعل كل مجموعة مجاورة من اثنين من خلال تبديل الاثنين عند الضرورة.

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

Answer 2

يعمل فرز الدمج غير المتكرر من خلال النظر في أحجام النوافذ البالغة 1،2،4،8،16..2^n على صفيف الإدخال. لكل نافذة ("k" في الكود أدناه) ، يتم دمج جميع الأزواج المجاورة من النوافذ في مساحة مؤقتة ، ثم إعادة إلى الصفيف.

إليكم وظيفتي الفردية ، نوع الدمج القائم على C ، غير مرغوب فيه. المدخلات والمخرجات في "أ". تخزين مؤقت في "ب". في يوم من الأيام ، أود الحصول على نسخة كانت في مكانها:

float a[50000000],b[50000000];
void mergesort (long num)
{
    int rght, wid, rend;
    int i,j,m,t;

    for (int k=1; k < num; k *= 2 ) {       
        for (int left=0; left+k < num; left += k*2 ) {
            rght = left + k;        
            rend = rght + k;
            if (rend > num) rend = num; 
            m = left; i = left; j = rght; 
            while (i < rght && j < rend) { 
                if (a[i] <= a[j]) {         
                    b[m] = a[i]; i++;
                } else {
                    b[m] = a[j]; j++;
                }
                m++;
            }
            while (i < rght) { 
                b[m]=a[i]; 
                i++; m++;
            }
            while (j < rend) { 
                b[m]=a[j]; 
                j++; m++;
            }
            for (m=left; m < rend; m++) { 
                a[m] = b[m]; 
            }
        }
    }
}

بالمناسبة ، من السهل جدًا إثبات أن هذا O (n log n). تنمو الحلقة الخارجية على حجم النافذة كطاقة اثنين ، لذلك K لديها سجل N تكرارات. على الرغم من وجود العديد من النوافذ التي تغطيها الحلقة الداخلية ، إلا أن جميع النوافذ لـ K تغطى صفيف الإدخال بالضبط ، لذا فإن الحلقة الداخلية هي O (N). الجمع بين الحلقات الداخلية والخارجية: o (n)*o (log n) = o (n log n).

Answer 3

نقلا عن مبرمج:

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

Answer 4

كل من نوع الدمج المتكرر وغير المتكرر لهما نفس التعقيد من O (nlog (n)). وذلك لأن كلا النهجين يستخدمون المكدس بطريقة أو بطريقة أخرى.

في النهج غير المتواصل ، يحدد المستخدم/المبرمج ويستخدم المكدس

في النهج المتكرر ، يتم استخدام مكدس داخليًا بواسطة النظام لتخزين عنوان الإرجاع للوظيفة التي تسمى بشكل متكرر

Answer 5

السبب الرئيسي الذي يجعلك ترغب في استخدام دمج غير متكررة هو تجنب تدفق مكدس التكرار. على سبيل المثال ، أحاول فرز 100 مليون سجل ، كل سجل حوالي 1 كيلو بايت في الطول (= 100 غيغابايت) ، بالترتيب الأبجدي الرقمي. سيستغرق الأمر (N^2) من عمليات 10^16 ، أي سيستغرق تشغيل عقود حتى عند 0.1 ميكروثانية لكل عملية مقارنة. سيستغرق فرز دمج الطلب (N)) أقل من 10^10 عمليات أو أقل من ساعة لتشغيله بنفس السرعة التشغيلية. ومع ذلك ، في النسخة العودية من Mergesort ، ينتج عن نوع العنصر 100 مليون مكالمة متكررة 50 مليون إلى Mergesort (). في بضع مئات من البايت لكل عودة مكدس ، يفيض هذا مكدس العودية على الرغم من أن العملية تتناسب بسهولة مع ذاكرة الكومة. القيام برسم دمج باستخدام الذاكرة المخصصة ديناميكيًا على الكومة- أستخدم الكود الذي توفره Rama Hoetzlein أعلاه ، لكنني أستخدم الذاكرة المخصصة ديناميكيًا على الكومة بدلاً من استخدام المكدس- يمكنني فرز سجلاتي 100 مليون مع نوع دمج غير متكرر وأنا لا أتفوق على المكدس. محادثة مناسبة لموقع "Stack Overflow"!

ملاحظة: شكرًا على الكود ، راما Hoetzlein.

PPS: 100 غيغابايت على الكومة؟ !! حسنًا ، إنها كومة افتراضية على مجموعة Hadoop ، وسيتم تنفيذ Mergesort بالتوازي على العديد من الآلات التي تشارك الحمل ...

Answer 6

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

شفرة :

    int num = input_array.length;
    int left = 0;
    int right;
    int temp;
    int LIMIT = 16;
    if (num <= LIMIT)
    {
        // Single Insertion Sort
        right = 1;
        while(right < num)
        {
            temp = input_array[right];
            while(( left > (-1) ) && ( input_array[left] > temp ))
            {
                input_array[left+1] = input_array[left--];
            }
            input_array[left+1] = temp;
            left = right;
            right++;
        }
    }
    else
    {
        int i;
        int j;
        //Fragmented Insertion Sort
        right = LIMIT;
        while (right <= num)
        {
            i = left + 1;
            j = left;
            while (i < right)
            {
                temp = input_array[i];
                while(( j >= left ) && ( input_array[j] > temp ))
                {
                    input_array[j+1] = input_array[j--];
                }
                input_array[j+1] = temp;
                j = i;
                i++;
            }
            left = right;
            right = right + LIMIT;
        }
        // Remainder Insertion Sort
        i = left + 1;
        j = left;
        while(i < num)
        {
            temp = input_array[i];
            while(( j >= left ) && ( input_array[j] > temp ))
            {
                input_array[j+1] = input_array[j--];
            }
            input_array[j+1] = temp;
            j = i;
            i++;
        }
        // Rama Hoetzlein method
        int[] temp_array = new int[num];
        int[] swap;
        int k = LIMIT;
        while (k < num)
        {
            left = 0;
            i = k;// The mid point
            right = k << 1;
            while (i < num)
            {
                if (right > num)
                {
                    right = num;
                }
                temp = left;
                j = i;
                while ((left < i) && (j < right))
                {
                    if (input_array[left] <= input_array[j])
                    {
                        temp_array[temp++] = input_array[left++];
                    }
                    else
                    {
                        temp_array[temp++] = input_array[j++];
                    }
                }
                while (left < i)
                {
                    temp_array[temp++] = input_array[left++];
                }
                while (j < right)
                {
                    temp_array[temp++] = input_array[j++];
                }
                // Do not copy back the elements to input_array
                left = right;
                i = left + k;
                right = i + k;
            }
            // Instead of copying back in previous loop, copy remaining elements to temp_array, then swap the array pointers
            while (left < num)
            {
                temp_array[left] = input_array[left++];
            }
            swap = input_array;
            input_array = temp_array;
            temp_array = swap;
            k <<= 1;
        }
    }

    return input_array;

Answer 7

فقط في حال كان أي شخص لا يزال يتربص في هذا الموضوع ... لقد قمت بتكييف خوارزمية فرز Rama Hoetzlein من Rama Hoetzlein أعلاه لفرز القوائم المرتبطة المزدوجة. هذا النوع الجديد في مكانه ومستقر ويتجنب قائمة الوقت باهظة الثمن في القائمة التي تقسم الكود الموجود في تطبيقات فرز القائمة المرتبطة الأخرى.

// MergeSort.cpp
// Angus Johnson 2017
// License: Public Domain

#include "io.h"
#include "time.h"
#include "stdlib.h"

struct Node {
    int data;
    Node *next;
    Node *prev;
    Node *jump;
};

inline void Move2Before1(Node *n1, Node *n2)
{
    Node *prev, *next;
    //extricate n2 from linked-list ...
    prev = n2->prev;
    next = n2->next;
    prev->next = next; //nb: prev is always assigned
    if (next) next->prev = prev;
    //insert n2 back into list ...  
    prev = n1->prev;
    if (prev) prev->next = n2;
    n1->prev = n2;
    n2->prev = prev;
    n2->next = n1;
}

void MergeSort(Node *&nodes)
{
    Node *first, *second, *base, *tmp, *prev_base;

    if (!nodes || !nodes->next) return;
    int mul = 1;
    for (;;) {
        first = nodes;
        prev_base = NULL;
        //sort each successive mul group of nodes ...
        while (first) {
            if (mul == 1) {
                second = first->next;
                if (!second) { 
                  first->jump = NULL;
                  break;
                }
                first->jump = second->next;
            }
            else
            {
                second = first->jump;
                if (!second) break;
                first->jump = second->jump;
            }
            base = first;
            int cnt1 = mul, cnt2 = mul;
            //the following 'if' condition marginally improves performance 
            //in an unsorted list but very significantly improves
            //performance when the list is mostly sorted ...
            if (second->data < second->prev->data) 
                while (cnt1 && cnt2) {
                    if (second->data < first->data) {
                        if (first == base) {
                            if (prev_base) prev_base->jump = second;
                            base = second;
                            base->jump = first->jump;
                            if (first == nodes) nodes = second;
                        }
                        tmp = second->next;
                        Move2Before1(first, second);
                        second = tmp;
                        if (!second) { first = NULL; break; }
                        --cnt2;
                    }
                    else
                    {
                        first = first->next;
                        --cnt1;
                    }
                } //while (cnt1 && cnt2)
            first = base->jump;
            prev_base = base;
        } //while (first)
        if (!nodes->jump) break;
        else mul <<= 1;
    } //for (;;)
}

void InsertNewNode(Node *&head, int data)
{
    Node *tmp = new Node;
    tmp->data = data;
    tmp->next = NULL;
    tmp->prev = NULL;
    tmp->jump = NULL;
    if (head) {
        tmp->next = head;
        head->prev = tmp;
        head = tmp;
    }
    else head = tmp;
}

void ClearNodes(Node *head)
{
    if (!head) return;
    while (head) {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

int main()
{  
    srand(time(NULL));
    Node *nodes = NULL, *n;
    const int len = 1000000; //1 million nodes 
    for (int i = 0; i < len; i++)
        InsertNewNode(nodes, rand() >> 4);

    clock_t t = clock();
    MergeSort(nodes);    //~1/2 sec for 1 mill. nodes on Pentium i7. 
    t = clock() - t;
    printf("Sort time: %d msec\n\n", t * 1000 / CLOCKS_PER_SEC);

    n = nodes;
    while (n)
    {
        if (n->prev && n->data < n->prev->data) { 
            printf("oops! sorting's broken\n"); 
            break;
        }
        n = n->next;
    }
    ClearNodes(nodes);
    printf("All done!\n\n");
    getchar();
    return 0;
}

تحرير 2017-10-27: إصلاح خطأ يؤثر على قوائم مرقمة فردية