Optimierung der Fehlersortiermethode

  • Ich habe gerade diese Sortiermethode erstellt. Es läuft gut und der Code sieht in meinen Augen gut aus.

    Ist es möglich, es zu optimieren, damit es schneller läuft? Wenn es jetzt \ $ O (n ^ 3) \ $ ist, wäre es interessant, es in \ $ O (n ^ 2) \ $ oder etwas Ähnliches zu ändern.

    Seite Frage: Dies ist \ $ O (n ^ 3) \ $, richtig (ich mag nur \ $ O (n ^ 2) \ $ und darunter)?

     List<Log> errors = _logHandler.GetErrors(daysBack);
            List<Log> errorsSorted = new List<Log>();
            for (int i = 0; i < errors.Count; i++)
            {
                bool inserted = false;
                for (int j = 0; j < errorsSorted.Count; j++)
                {
                    if (errors[i].Date < errorsSorted[j].Date)
                    {
                        List<Log> tempList = new List<Log>();
                        tempList.AddRange(errorsSorted.GetRange(j, 
                            errorsSorted.Count - j));
    
                        errorsSorted[j] = errors[i]; // replace at bigger date index
                        inserted = true;
    
                        errorsSorted.RemoveRange(j+1, errorsSorted.Count - (j+1));
    
                        // move all bigger dates one place to the right..
                        foreach (Log log in tempList) 
                        {
                            errorsSorted.Add(log);
                        }
                        break;
                    }
                }
                if (!inserted)
                {
                    errorsSorted.Add(errors[i]); // No date is bigger, add at the end
                }
            }
     
    06 March 2015
    NateJ
1 answer
  • Nun, es wäre naheliegend, einen besseren Algorithmus zu verwenden, dh den eingebauten:

     errors.Sort((x,y) => x.Date.CompareTo(y.Date));
     

    Sie können mit Ihrem Code eine effektivere Methode zum Verschieben der Elemente verwenden. Im Moment verschieben Sie Elemente von einer Liste in eine andere, um ein Element einzufügen, aber die Klasse List<T> kann selbst ein Element einfügen. Es wird etwas schneller, da Sie die Elemente nur einmal und nicht zweimal für jede Einfügung kopieren.

    Viel besser wäre es, stattdessen eine verknüpfte Liste zu verwenden. Es wird viel schneller sein, da das Einfügen eines Elements O (1) anstelle von O (n) ist (wobei n die Anzahl der Elemente ist, die verschoben werden müssen). So etwas (nicht getestet):

     List<Log> errors = _logHandler.GetErrors(daysBack);
    LinkedList<Log> errorsSorted = new LinkedList<Log>();
    foreach (Log error in errors) {
      LinkedListNode<Log> node = errorsSorted.Last;
      while (node != null && error.Date < node.Value.Date) {
        node = node.Previous;
      }
      if (node != null) {
        errorsSorted.AddAfter(node, error);
      } else {
        errorsSorted.AddFirst(error);
      }
    }
     

    Dies ist das Einfügungssortierung , die eine Worst-Case-Performance von O (n ^ 2) und eine Best-Case-Performance von O (n) aufweist. Beachten Sie, dass die sortierte Liste von Anfang an anstelle des Anfangs durchsucht wird. Dies gibt die Leistung O (n), wenn die Liste bereits sortiert ist.

    25 November 2011
    Jens Bannmann