Какой основной алгоритм выбрать для построения отсортированного списка? А как добиться максимальной производительности при добавлении в отсортированный список?

Question

Например, у меня есть неопределенное количество пар (ключ, значение). И я хочу построить отсортированный список во время итерации через эти пары (это длительная операция).

Я думаю использовать BinaryTree в качестве отсортированной структуры и строить список из дерева после итераций.

Как вы вообще думаете, этот метод быстрее, чем простая сортировка списка, полученного из итерации по парам?

Как лучше всего решить эту проблему?

Есть ли какие-нибудь элементы API Java для этой проблемы?

Answer 1

Вы можете выбросить их все в TreeMap и позволить Java обрабатывать сортировку. Затем вы можете перебирать карту и получать ключи в их отсортированном порядке.

Answer 2

Как вы думаете в целом, это метод быстрее, чем простая сортировка список получен из повторяющегося корыта пары?

Нет. Если сортировка и дерево реализованы правильно, сложность обоих идентична: O (n * log (n)). Для постоянных факторов лучше всего сделать некоторые тесты самостоятельно. Дерево, вероятно, потребует больше памяти, по крайней мере, по сравнению с алгоритмом сортировки на месте, например быстрой сортировкой.

API Java:

• java.util.TreeMap для дерева
• java.util.Collections.sort() для сортировки

Answer 3

Если вам абсолютно необходимо использовать список, вы можете использовать Collections.binarySearch , чтобы определить правильную точку вставки для добавления нового элемента в список, таким образом поддерживая отсортированный порядок, фактически не требуя каких-либо операций сортировки.

Answer 4

В C ++ производительность STL может быть достаточно хорошей для первоначальной реализации - избегая «преждевременной оптимизации» - при условии, что вы работаете в одном потоке, в противном случае я всегда рекомендую Duffy «Параллельное программирование в Windows».