Какой вид делает Java Collections.sort (узлы) использование?
Я полагаю, что здесь вам понадобится Variadic Generics , который еще не существует в Swift, но может существовать когда-нибудь.
В качестве обходного пути вы можете сделать версии вашего метода, которые будут использовать один ключевой путь, два ключевых пути, три ключевых пути и т. Д., Вплоть до наибольшего числа, которое, по вашему мнению, вам целесообразно использовать (а затем, возможно, один). Больше). Возможно, вы сможете сэкономить некоторое время, генерируя варианты, используя Sourcery .
4 ответа
O (n log n) не означает, что число сравнений будет равно или меньше n log n, только что время будет масштабироваться пропорционально n log n. Попробуйте выполнить тесты с 8 или 16 узлами или 32 узлами и проверить время.
Алгоритм A (n), который обрабатывает количество данных n, находится в O (f (n)), для некоторая функция f, если существуют две строго положительные константы C_inf и C_sup такие, что:
C_inf. f (n) Следует отметить две вещи: Фактические константы C могут быть любыми, и do зависят от относительной стоимости операций (в зависимости от языка, виртуальной машины, архитектуры, или ваше фактическое определение операции). Например, на некоторых платформах + и * имеют одинаковую стоимость, на других - более поздние на порядок медленнее. Ожидается количество, обозначенное как «в O (f (n))». Количество операций, основанное на некоторой, вероятно, произвольной модели данных, с которыми вы имеете дело. Например, если ваши данные почти полностью отсортированы, алгоритм сортировки слиянием будет в основном O (n), а не O (n. Log (n)).
Вы отсортировали четыре узла, поэтому вы не получили сортировку слиянием; sort переключается на сортировку вставкой.
В Java методы Arrays.sort () используют сортировку слиянием или настроенную быструю сортировку в зависимости от типов данных и для эффективности реализации переключаются на сортировку вставкой, когда сортируется менее семи элементов массива. . (Википедия, выделение выделено)
Arrays.sort используется косвенно классами Collections.
Недавно принятый отчет об ошибках указывает на то, что реализация Java на Sun будет использовать Python timsort в будущем: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124
(монография timsort, ссылка на которую приведена выше, стоит прочитать).
Я написал кое-что, что вас может заинтересовать в алгоритме сортировки Java, и провел некоторые измерения производительности of Collections.sort () . Алгоритм в настоящее время представляет собой сортировку слиянием с сортировкой вставок , как только вы переходите к определенному размеру подсписков ( NB, этот алгоритм очень вероятно изменится в Java 7 ). [1229 Вы действительно должны принять обозначение Big O как показатель того, как алгоритм будет масштабироваться в целом; для конкретной сортировки точное время будет отличаться от времени, предсказанного этим вычислением (как вы увидите на моем графике, оба алгоритма сортировки, каждый из которых имеет разные характеристики производительности, и поэтому общее время сортировки составляет немного сложнее).
Тем не менее, как грубое руководство, каждый раз, когда вы удваиваете количество элементов, если вы умножите ожидаемое время на 2,2, вы не останетесь в стороне. (Хотя на самом деле не имеет смысла делать это для очень маленьких списков из нескольких элементов.)