Come refactoring questa routine per evitare l'uso della ricorsione?

Question

Quindi stavo scrivendo un Mergesort in C # come esercizio e anche se ha funzionato, guardando indietro al codice, non c'era spazio per migliorare.

In sostanza, la seconda parte dell'algoritmo richiede una routine per Unisci due liste ordinate .

Questa è la mia strada troppo lunga applicazione che potrebbe usare un po 'di refactoring:

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

Sicuramente questa routine può essere migliorata / accorciato rimuovendo ricorsione , ecc Ci sono anche altri modi per unire 2 liste ordinate. Così qualsiasi refactoring è il benvenuto.

Anche se io ho una risposta, io sono curioso di sapere come sarebbero altri programmatori sarebbero andati su come migliorare questa routine.

Grazie!

Answer 1

Come punto di partenza, vorrei rimuovere i vostri casi particolari per la presenza di una delle liste ha Count == 1 -. Possono essere gestite dal tuo caso più generale (attualmente recursing)

Il if (sLeft.Count > 1 && sRight.Count == 0) sarà non essere vero, perché aver controllato per sRight.Count == 0 alla partenza -. Quindi questo codice non verrà mai raggiunto ed è ridondante

Infine, invece di recursing (che è molto costoso in questo caso a causa del numero di nuove liste create - uno per ogni elemento), mi piacerebbe fare qualcosa di simile nel tuo else (in realtà, questo potrebbe sostituire l'intero metodo):

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;

(Idealmente mi piacerebbe refactoring questa opzione per utilizzare interi indici contro ogni lista, invece di utilizzare .RemoveAt, perché è più performante per scorrere l'elenco di distruggerlo, e perché potrebbe essere utile lasciare intatte le liste originali. Questo è ancora il codice più efficiente rispetto all'originale, però!)

Answer 2

Unione di due liste ordinate può essere fatto in 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

Il mio prendere su questo potrebbe essere:

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

Esattamente quello che farei se dovessi farlo a mano. =)

Answer 4

Sei davvero sicuro il codice funziona a tutti? Senza prove, compaiono i seguenti:

...
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

È stavi chiedendo differrent avvicina pure. Potrei fare come sotto a seconda dell'utilizzo. Il sotto il codice è pigro quindi non sarà sorta l'intero elenco in una sola volta, ma solo quando gli elementi sono richiesti.

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

Modifica E 'fondamentalmente la stessa implementatin come Sergey Osypchuk la sua volontà, dall'inizio alla fine quando si cerca solo al di smistamento essere più veloce, ma la latenza sarà maggiore, come pure per il fatto di ordinare l'intera lista anticipo. Così come ho detto a seconda dell'utilizzo che potrebbe andare con questo approccio e un'alternativa sarebbe qualcosa di simile a Sergey Osypchuk

Answer 6

Spesso è possibile utilizzare una pila, invece di utilizzare la ricorsione

Answer 7

Elenco Merge (dalla teoria, liste di input sono allineati in anticipo) l'ordinamento potrebbero essere attuate nel modo seguente:

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

Nel caso in cui si inizia con la lista non ordinata è necessario dividerlo da subsequence ordinata e di Marge utilizzando funzione di cui sopra

Answer 8

Non ho mai utilizzare la ricorsione per merge sort. È possibile effettuare iterativo passa sopra l'ingresso, approfittando del fatto che le doppie ordinate dimensioni del blocco con ogni passaggio unione. Tenere traccia della dimensione del blocco e il numero di articoli che hai trasformati a base di ogni lista di input; quando sono uguali, l'elenco è esaurito. Quando entrambe le graduatorie ad esaurimento si può passare alla successiva coppia di blocchi. Quando la dimensione del blocco è superiore o pari alle dimensioni di ingresso, il gioco è fatto.

Modifica Alcune delle informazioni che avevo lasciato in precedenza era errato, a causa del mio equivoco - un elenco in C # è simile a una matrice e non una lista collegata. Le mie scuse.