Выбор хорошего алгоритма сортировки

Приложение Java проводит большую часть времени, сортируя некоторые ключи и удаляя дубликаты.Выбор хорошего алгоритма сортировки

Поэтому выбор адаптированного алгоритма сортировки является обязательным.

Ключи представляют собой целые числа (около 256 бит, но необязательно), а размеры массива составляют от 1000 до 100000 ключей.

Входные массивы состоят из последовательных групп клавиш. Эти группы уже отсортированы и малы (около 10 ключей).

Образец массива (3 группы, 32bits ключи):

После сортировки и удаления дубликатов:

Любой жесткий? Есть идеи ? Любая ссылка?

Благодаря

PS: после просмотра алгоритмов сортировки, включая множество вариаций сортировки слиянием, поразрядной сортировки, кви ... Я продолжаю копать вокруг хэш-карт.

PPS: наконец, я разветвил сортировку Java-наследия, добавленную фильтрацию и концепцию отсортированных групп. Это обеспечивает отличное ускорение.

источник

2013-09-08 Anonymous

Пожалуйста, поделитесь своими мыслями, что у вас есть. Вы что-нибудь пробовали? – dasblinkenlight

Мы не знаем, чего вы не знаете. Вопрос мне кажется прямым. Что вы находите сложным? –

Сортировка 100 000 целых чисел должно быть довольно быстрым. Но что такое «256-битное» целое число? Являются ли эти большие целые числа? – user949300

Merge Сортировка (http://en.wikipedia.org/wiki/Merge_sort)

Поскольку ваш входных данных отсортированы у вас есть фора. Вы можете ввести 1-е значение из каждого списка в PriorityQueue, вынуть наименьшее и добавить следующее значение из этого списка в очередь. Повторение. С некоторыми проверками, чтобы добраться до конца. :-)

Я уверен, что есть ответы SO с более подробной информацией.

еще некоторые ссылки:

http://www.cs.washington.edu/education/courses/cse373/06sp/handouts/lecture08.pdf

Algorithm for N-way merge

и мой собственный ответ с довольно полным кодом Java:

Merging multiple sorted csv files with complex comparison

источник

2013-09-08 16:11:59 user949300

Может ли Merge sort эффективно удалять дубликаты? –

Хорошая точка. Обычно он будет включать в себя дубликаты. Но если вы добавили некоторую простую логику, чтобы проверить, что значение, которое вы собираетесь добавить, это не тот, который вы только что добавили, это должно быть o.k. – user949300

Если ключи отсортированы на месте, тогда клавиши будут перемещаться много. Не уверен, что это эффективно. У вас есть ссылки для оптимизации реализации? –

Я предлагаю вам использовать Collections.sort здесь, поскольку это позаботится о дубликатах (если вы создадите SET для чисел), а сложность времени сортировки - O (nlogn), которая так же хороша, как и получает.

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

источник

2013-09-08 16:11:21 Neeraj

Collections.sort() не удаляет дубликаты. –

Извините за двусмысленность. Когда я упоминал о коллекциях, я имел в виду, что подлежащая структура данных будет набором. – Neeraj

Вы можете только Collections.sort() Список. Вы можете использовать TreeSet, но тогда вам не нужно сортировать(). –

Самым простым решением без какой-либо более подробной информации является

Вы должны уметь читать все строки в TreeSet и распечатывать их в конце.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
TreeSet<String> sortedSet = new TreeSet<String>(); 
for(String line; (line = br.readLine()) != null;) 
    sortedSet.add(line); 
for (String s : sortedSet) 
    System.out.println(s);

источник

2013-09-08 16:13:11

Поскольку входные данные уже в значительной степени отсортированы, это сделает уродливое дерево. Я подозреваю, что более «нормальный» алгоритм помещает их все в набор, затем создаёт список, затем сборники.sort() может быть быстрее. Я не уверен, почему сортировка OP медленная, 100 000 целых чисел не так много, поэтому мне определенно нравится ваш очень быстрый и простой подход. – user949300

@ user949300 TreeSet должен быть сбалансированным деревом. Сорт слияния, возможно, более эффективен, но гораздо сложнее. Я подозреваю, что потраченное время заключается в разборе и сравнении ключей, а не в самой сортировке. –

Возможно, вы правы, где время тратится. Я сделал сортировку слияния, когда обрабатывал десятки миллионов сложных строк из десятков файлов. – user949300

При сортировке совершенно новый массив каждый раз, вы можете воспользоваться Quick sort или, может быть Bucket sort

Если массив является обновление Fibonacci heap (наиболее эффективный, хотя комплекс), Binomial heap, или просто Binary heap.

источник

2013-09-08 16:16:34 sshilovsky

Поскольку ваши ключи сортировки являются целыми числами в ограниченном диапазоне, вы можете использовать radix sort. Сорт radix имеет линейную временную сложность, в то время как более общие алгоритмы сортировки, основанные на сравнении, имеют минимальное время O (n log n) для сортировки n элементов, что делает алгоритмы сортировки и аналогичные алгоритмы сортировки лучше для больших наборов данных.

источник

2013-09-08 16:16:51 Joni

Я выбрал несколько репрезентативных массивов и проверил сортировку Radix. Тим сортируется быстрее, чем сортировка по методу radix. –

В качестве сортировки, основанной на сравнении элементов с временной сложностью O (n log n), для больших наборов данных Tim sort гарантированно будет медленнее, чем сортировка по методу radix. Для небольших наборов данных время выполнения определяется деталями реализации; например, насколько эффективно кэш ЦП используется в вашей конкретной реализации алгоритма. – Joni

Приложение обычно работает на относительно новой рабочей станции. Знаете ли вы какую-либо оптимизированную реализацию сортировки радиуса? Может быть, у меня все в порядке. –

Вы можете просто перебрать все элементы и поместить их все в Set. В частности, поместите все элементы в TreeSet, чтобы дать вам правильный порядок. Это также автоматически удалит дубликаты. Ваш код будет на самом деле очень просто -

Set<int> sortedUniqueKeys = new TreeSet<int>(keys);

Где ключи является несортированный массив целочисленных дубликатов ключей. Все удаление сортировки/дублирования выполняется в конструкторе и (предположительно) быстро.

источник

2013-09-08 16:17:04

Я проверю выступления TreeSet. –

Нет TreeSet является самым медленным среди тестируемых решений. –

@sylvain Да, я забыл упомянуть об этом. Это именно тот компромисс, который вы ожидаете - супер простой код, но так как он настолько прост, что теряет кучу оптимизации. –

Выбор хорошего алгоритма сортировки

ответ

Смежные вопросы