كيفية إعادة تشكيل هذا الروتين لتجنب استخدام العودية؟

Question

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

في الأساس ، يتطلب الجزء الثاني من الخوارزمية روتينًا دمج قائمتين فرزتين.

هذه هي طريقي للتنفيذ الطويل الذي يمكن أن يستخدم بعض إعادة الطرد:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    if (sLeft.Count == 0 || sRight.Count == 0)
    {
        sLeft.AddRange(sRight);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count == 1)
    {
        if (sLeft[0] <= sRight[0])
            sLeft.Add(sRight[0]);
        else
            sLeft.Insert(0, sRight[0]);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count > 1)
    {
        for (int i=0; i<sRight.Count; i++)
        {
            if (sLeft[0] <= sRight[i])
            {
                sRight.Insert(i, sLeft[0]);
                return sRight;
            }
        }
        sRight.Add(sLeft[0]);
        return sRight;
    }
    else if (sLeft.Count > 1 && sRight.Count == 1)
    {
        for (int i=0; i<sLeft.Count; i++)
        {
            if (sRight[0] <= sLeft[i])
            {
                sLeft.Insert(i, sRight[0]);
                return sLeft;
            }
        }
        sLeft.Add(sRight[0]);
        return sLeft;
    }
    else
    {
        List<int> list = new List<int>();
        if (sLeft[0] <= sRight[0])
        {
            list.Add(sLeft[0]);
            sLeft.RemoveAt(0);
        }
        else
        {
            list.Add(sRight[0]);
            sRight.RemoveAt(0);
        }

        list.AddRange(MergeSortedLists(sLeft, sRight));
        return list;
    }       
}

من المؤكد أنه يمكن تحسين/تقصير هذا الروتين عن طريق الإزالة العودية, ، وما إلى ذلك ، هناك حتى طرق أخرى لدمج قوائم مرتبة. لذا أي إعادة البناء هو موضع ترحيب.

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

شكرًا لك!

Answer 1

كنقطة انطلاق ، أود إزالة حالاتك الخاصة عندما يكون لأي من القوائم Count == 1 - يمكن التعامل معها من خلال قضيتك الأكثر عمومية (تكرار حاليًا).

ال if (sLeft.Count > 1 && sRight.Count == 0) إرادة أبداً كن صحيحًا لأنك راجعت sRight.Count == 0 في البداية - لذلك لن يتم الوصول إلى هذا الرمز أبدًا وهو لا لزوم له.

أخيرًا ، بدلاً من التكرار (وهو أمر مكلف للغاية في هذه الحالة بسبب عدد القوائم الجديدة التي تنشئها - واحد لكل عنصر!) ، سأفعل شيئًا كهذا في else (في الواقع ، يمكن أن يحل هذا محل طريقتك بالكامل):

List<int> list = new List<int>();

while (sLeft.Count > 0 && sRight.Count > 0)
{
    if (sLeft[0] <= sRight[0])
    {
        list.Add(sLeft[0]);
        sLeft.RemoveAt(0);
    }
    else
    {
        list.Add(sRight[0]);
        sRight.RemoveAt(0);
    }
}

// one of these two is already empty; the other is in sorted order...
list.AddRange(sLeft);
list.AddRange(sRight);
return list;

(من الناحية المثالية ، سأعيد استخدام هذا لاستخدام فهارس عدد صحيح مقابل كل قائمة ، بدلاً من الاستخدام .RemoveAt, ، نظرًا لأنه من الأداء أكثر من خلال القائمة من تدميرها ، ولأنه قد يكون من المفيد ترك القوائم الأصلية سليمة. لا يزال هذا رمزًا أكثر كفاءة من الأصل ، رغم ذلك!)

Answer 2

دمج قائمتين فرزتين يمكن القيام بهما في O (n).

List<int> lList, rList, resultList;
int r,l = 0;

while(l < lList.Count && r < rList.Count)
{
  if(lList[l] < rList[r]
    resultList.Add(lList[l++]);
  else
    resultList.Add(rList[r++]);
}
//And add the missing parts.
while(l < lList.Count)
  resultList.Add(lList[l++]);
while(r < rList.Count)
  resultList.Add(rList[r++]);

Answer 3

سيكون رأيي في هذا:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    List<int> result = new List<int>();
    int indexLeft = 0;
    int indexRight = 0;

    while (indexLeft < sLeft.Count || indexRight < sRight.Count)
    {
        if (indexRight == sRight.Count ||
            (indexLeft < sLeft.Count && sLeft[indexLeft] < sRight[indexRight]))
        {
            result.Add(sLeft[indexLeft]);
            indexLeft++;
        }
        else
        {
            result.Add(sRight[indexRight]);
            indexRight++;
        }
    }
    return result;
}

بالضبط ما سأفعله إذا اضطررت إلى القيام بذلك باليد. =)

Answer 4

هل أنت متأكد حقًا من أن الكود الخاص بك يعمل على الإطلاق؟ دون اختباره ، أرى ما يلي:

...
else if (sLeft.Count > 1 && sRight.Count == 0)  //<-- sRight is empty
{
    for (int i=0; i<sLeft.Count; i++)
    {
        if (sRight[0] <= sLeft[i]) //<-- IndexError?
        {
            sLeft.Insert(i, sRight[0]);
            return sLeft;
        }
    }
    sLeft.Add(sRight[0]);
    return sLeft;
}
...

Answer 5

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

class MergeEnumerable<T> : IEnumerable<T>
    {
        public IEnumerator<T> GetEnumerator()
        {
            var left = _left.GetEnumerator();
            var right = _right.GetEnumerator();
            var leftHasSome = left.MoveNext();
            var rightHasSome = right.MoveNext();
            while (leftHasSome || rightHasSome)
            {
                if (leftHasSome && rightHasSome)
                {
                  if(_comparer.Compare(left.Current,right.Current) < 0)
                  {
                    yield return returner(left);
                  } else {
                    yield return returner(right);
                  }
                }
                else if (rightHasSome)
                {
                    returner(right);
                }
                else
                {
                    returner(left);
                }
            }
        }

        private T returner(IEnumerator<T> enumerator)
        {
            var current = enumerator.Current;
            enumerator.MoveNext();
            return current;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        private IEnumerable<T> _left;
        private IEnumerable<T> _right;
        private IComparer<T> _comparer;

        MergeEnumerable(IEnumerable<T> left, IEnumerable<T> right, IComparer<T> comparer)
        {
            _left = left;
            _right = right;
            _comparer = comparer;
        }
    }

تعديل: إنه في الأساس نفس تطبيق Sergey Osypchuk إرادته من البداية إلى النهاية عند النظر إلى الفرز فقط يكون أسرع ولكن الكمون سيكون أعلى أيضًا بسبب حقيقة فرز القائمة بأكملها مقدمًا. هكذا قلت اعتمادًا على الاستخدام ، قد أتعامل مع هذا النهج وسيكون البديل شيئًا مشابهًا لسيرجي أوسيبتشوك

Answer 6

غالبًا ما يمكنك استخدام مكدس بدلاً من استخدام العودية

Answer 7

قائمة الدمج (حسب النظرية ، يتم فرز قوائم الإدخال مسبقًا) يمكن تنفيذ الفرز بالطريقة التالية:

List<int> MergeSorting(List<int> a, List<int> b)
    {
        int apos = 0;
        int bpos = 0;
        List<int> result = new List<int>();
        while (apos < a.Count && bpos < b.Count)
        {
            int avalue = int.MaxValue;
            int bvalue = int.MaxValue;
            if (apos < a.Count)
                avalue = a[apos];
            if (bpos < b.Count)
                bvalue = b[bpos];
            if (avalue < bvalue)
            {
                result.Add(avalue);
                apos++;
            }
            else
            {
                result.Add(bvalue);
                bpos++;
            }
        }
        return result;
    }

في حالة بدء تشغيل القائمة غير المصنفة ، تحتاج إلى تقسيمها عن طريق الفرز اللاحق و Marge لهم باستخدام الوظيفة أعلاه

Answer 8

أنا لا أستخدم عودة لدمج نوع. يمكنك إجراء تمريرات تكرارية على المدخلات ، مع الاستفادة من حقيقة أن حجم الكتلة المصنفة يتضاعف مع كل تمريرة دمج. تتبع حجم الكتلة وعدد العناصر التي قمت بمعالجتها من كل قائمة إدخال ؛ عندما تكون متساوية ، يتم استنفاد القائمة. عند استنفاد كلا القائمتين ، يمكنك الانتقال إلى الزوج التالي من الكتل. عندما يكون حجم الكتلة أكبر من أو يساوي حجم الإدخال الخاص بك ، فأنت تنتهي.

يحرر: كانت بعض المعلومات التي تركتها من قبل غير صحيحة ، بسبب سوء فهمي - القائمة في C# تشبه صفيف وليس قائمة مرتبطة. اعتذاري.