Что происходит быстрее, сортировка вектора, а затем вставка его в дерево AVL или ввод его непосредственно?

Question

Итак, вот что:

У меня есть миллионы, возможно миллиарды строк, которые я пытаюсь разобрать и разместить в сортированной структуре, скажем, у меня 5 000 000 строк. Я пытаюсь написать быструю программу, которая может поместить все эти строки из несортированного вектора в упорядоченную структуру данных, которая также может быстро искать структуру, поэтому аргументация для дерева AVL (в конечном итоге я планирую использовать хэш таблицу az для более быстрого поиска, но это произойдет позже). Сначала я беру все строки в вектор, но все они перепутаны, несортированы и разной длины. Мне не нужны повторяющиеся строки в моем дереве, поэтому, если программа найдет строки «hello» и «hello», у нее будет только одна запись AVL и будет увеличивать целочисленный держатель для частоты появления этой строки.

Итак, мой вопрос заключается в следующем: было бы быстрее отсортировать вектор сначала (используя что-то быстро, как многопоточное quicksort или что-то еще), а затем ввести его в дерево AVL, после того как все слова будут отсортированы вместе с другими словами, ИЛИ, быстрее ли просто поместить все данные из несортированного вектора в дерево AVL и постоянно проверять дерево AVL на то, существует ли уже слово, а затем увеличивать его.

Так представить его в порядок операций здесь являются два случая:

CASE A: 

> Get input/parse strings 
> Put strings into vector (unsorted) 
> Put vector into array or linked-list 
> Quicksort that array/llist 
> Input that sorted array into the AVL Tree 

CASE B: 

> Get input/parse strings 
> Put strings into vector (unsorted) 
> Insert vector data into AVL tree 
> During insertion, check if there are duplicate words, if so, increment the counter 

каком случае быстрее ??

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

Answer 1

Подумайте, как работает балансировка для деревьев AVL. Он работает лучше всего, если «средние значения» на первом месте. С помощью сортированного ввода вам потребуется много перебалансировки, поэтому предварительная сортировка, вероятно, принесет больше вреда, чем пользы.

Для примера рассмотрим следующую AVL дерево держит значения 1-6:

4 
/\ 
    2 5 
/\ \ 
1 3 6 

Если заказ вход 4, 2, 5, 1, 3, 6, вы никогда не нужно, чтобы сбалансировать дерево. В отличие от этого, для отсортированного ввода 1, 2, 3, 4, 5, 6, вам потребуется много повторно балансировать операции:

1  +3  2  +4  2  +5  2  +6  3 
    \ ---> /\ ---> /\  ---> /\  ---> /\ 
    2  1 3  1 3   1 4   2 5 
           \   /\  //\ 
           4   3 5  1 4 6 

---

UPDATE оригинальный вопрос, был ли сортировка данных перед вставкой в ​​дерево AVL может улучшить производительность. Теперь ОР отредактировал вопрос, перейдя к своей конкретной проблеме.

но какой лучший способ эффективно вставить, когда слово уже находится на дереве где-то? Как я могу убедиться, что найду? Это где моя сортировка может прийти?

Вся точка дерева AVL является эффективно находить данные, так что я не понимаю вопрос. Должно быть очевидно, как пересечь двоичное дерево поиска, чтобы найти значение. Зачем вам сортировать данные для этого?

Обратите внимание: деревья двоичного поиска являются хорошей структурой данных для хранения ключей, но также могут управлять произвольными данными, связанными с этими ключами. В вашем случае вы хотите сохранить счет вместе с вашими ключами. Поэтому вам не требуется дерево слов/строк, а дерево пар (строка, целое число), которые представляют слово и его количество. Для порядка дерева просто рассмотрите строковый ключ, т. Е. Слово.

Для каждого слова, которое нужно вставить, найдите его в дереве. Если он уже существует, обновите количество слов. В противном случае вставьте новую пару со словом.

Последнее примечание: Стандартная библиотека C++ поставляется с типом map, который обычно (всегда?) Реализован с использованием дерева балансировки (AVL или красно-черного). Вы сэкономите себе много работы и исправления ошибок, просто используя эту реализацию. Так как C++ 11 существует также un unordered_map, обычно (всегда?), Реализованный с использованием хеш-таблицы.

Answer 2

Это может быть не быстрее в реальном мире.

При вставке вашего отсортированного вектора в дерево AVL вставьте его, как будто это дерево. Сначала вставьте середину, а затем рекурсивно середину левой части и середины правой части и так далее. Если все значения в векторе распределены равномерно, вам не придется перебалансировать свое дерево. (Теоретически.)

Лучше все же вы можете построить свое собственное дерево из отсортированного вектора (если вы управляете внутренним память) или просто использовать вначале двоичный поиск.

Единственный способ получить объективный ответ - проверить и измерить.

Answer 3

1-Вставка в дерево AVL - O (Log n). Сортировка - O (nLogN), поэтому сортировка перед вставками приведет к снижению производительности. 2 - Для целей подсчета вы можете использовать хеш-таблицу, чтобы найти количество вхождений каждого слова. Прокрутите все слова, обновите счетчик для каждого слова в хеш-таблице, затем вставьте слова в дерево AVL, используя хеш-таблицу, чтобы проверить, было ли это слово вставлено или нет, и если не вставить его со связанным счетчиком.

Answer 4

Я преобразую свой комментарий в ответ.

Если набор строк задан заранее, то вы не собираетесь добавлять к нему дополнительные строки после начальной загрузки, то самым быстрым, вероятно, не будет использовать дерево AVL (или любое другое дерево) вообще.

Просто загрузите строки в std::vector, сортировки (O (N * LogN), удалить уников (std::uniq, O (N)), а затем для поиска std::lower_bound (O (LogN)).

Имея такая же сложность, как и дерево AVL, скорее всего, на практике это будет быстрее, из-за повышенной кэш-совместимости.

Answer 5

«но как лучше всего эффективно вставить, когда слово уже находится на дереве где-нибудь? что я нахожу это? Это где моя сортировка может прийти?"

почему бы вам не использовать карту когда: ключ = слово, значение = слово индекс

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