Оптимизация ошибка-метод сортировки


Я просто сделал этот метод сортировки. Она работает нормально, и код выглядит нормально в моих глазах.

Можно ли оптимизировать его, чтобы он работал быстрее? Если это \$o(П^3)\ теперь$, было бы интересно изменить его на \$O(п^2)\$ или что-то подобное.

Побочный вопрос: Это \$O(П^3)\$, Да (мне только нравится \$o(п^2)\$ и ниже)?

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


Комментарии
2 ответа

Вы просто сортировка по дате, верно? Я бы использовал

using System.Linq;
// ....
List<Log> errors = _logHandler.GetErrors(daysBack);
List<Log> errorsSorted = errors.OrderBy(l => l.Date).ToList();

Согласно этой сайте StackOverflow вопрос, Заказатьпо использует quicksort в этом случае, который, как правило, имеет время выполнения о(n записей N).

4
ответ дан 25 ноября 2011 в 11:11 Источник Поделиться

Ну, очевидно, можно было бы использовать более эффективный алгоритм, я.е встроенная:

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

Что вы можете делать с вашим кодом, чтобы использовать более эффективный способ перемещать элементы вокруг. Прямо сейчас вы перемещая элементы из одного списка в другой, чтобы установка элемента, но список класс сам способен вставка элемента. Это будет немного быстрее, потому что вы будете только копировать предметы, а не два раза для каждой вставки.

Гораздо лучше было бы использовать связанный список. Это будет намного быстрее, потому что вставка элемента будет O(1) вместо О(N) (где N-это количество элементов, которые должны быть перемещены). Что-то вроде этого (не проверял):

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

Это сортировка вставками, которая в худшем случае производительность o(п^2) и в лучшем случае производительность o(п). Обратите внимание, что он начал просматривать отсортированный список с конца, а не начала, что дает время o(n) производительность, если список уже отсортирован.

1
ответ дан 25 ноября 2011 в 03:11 Источник Поделиться