Что быстрее: сортировать вектор, а затем помещать его в дерево AVL или вводить его напрямую?

Итак, вот ситуация:

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

Итак, мой вопрос заключается в следующем: было бы быстрее сначала отсортировать вектор (используя что-то быстрое, например, многопоточную быструю сортировку или что-то еще), а затем ввести его в дерево 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

Which case is faster??

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


c++ performance sorting vector avl-tree
person Jd Francis    schedule 24.11.2014    source источник
comment
Если вы не планируете добавлять больше строк позже, вы можете просто использовать отсортированный вектор и двоичный поиск (также известный как std::lower_bound)   -  person Anton Savin    schedule 24.11.2014
comment
Это зависит от того, есть ли у вас специальная функция для добавления отсортированных элементов в дерево AVL. И в любом случае, вы должны сделать тест, так как результат может быть не интуитивным.   -  person Jarod42    schedule 24.11.2014
comment
Есть ли вариант вставлять в дерево прямо из разбора?   -  person MatthiasB    schedule 24.11.2014
comment
@MatthiasB Добавление непосредственно из синтаксического анализа, вероятно, является вариантом, но добавление его к промежуточному вектору не добавляет слишком много времени, поэтому на самом деле это не проблема.   -  person Jd Francis    schedule 24.11.2014
comment
Если вам нужно хранить столько строк, вам следует рассмотреть tries в качестве структуры данных. Они могут лучше соответствовать вашим требованиям, чем деревья AVL.   -  person Kristian Duske    schedule 24.11.2014
comment
На практике, если у вас есть миллиарды строк, вы не будете хранить их все в памяти, но вам нужен какой-то способ сопоставления структуры данных с файловой системой. Если вам важно время вставки, вам следует вообще не использовать деревья AVL, а использовать базу данных, подобную SQLite, которая реализует b-дерево, оптимизированное для таких задач.   -  person Ferdinand Beyer    schedule 24.11.2014

Ответы (5)


arrow_upward
4
arrow_downward

Подумайте о том, как работает балансировка для деревьев 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

ОБНОВЛЕНИЕ Первоначальный вопрос заключался в том, улучшит ли производительность сортировка данных перед вставкой в ​​дерево AVL. Теперь ОП отредактировал вопрос, перейдя к его конкретной проблеме.

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

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

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

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

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

person Ferdinand Beyer    schedule 24.11.2014

arrow_upward
3
arrow_downward

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

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

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

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

person Anton Savin    schedule 24.11.2014

arrow_upward
2
arrow_downward

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

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

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

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

person 2501    schedule 24.11.2014

arrow_upward
2
arrow_downward

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

person Muhammad Soliman    schedule 24.11.2014
comment
Обратите внимание, что вставка N элементов в дерево AVL — это O(NLogN), поэтому сложность не увеличивается. - person MatthiasB; 24.11.2014
comment
Да, вставка полностью O(NLogN) даже в худшем случае. Добавление шага O (NLogN) перед вставкой в ​​дерево никогда не приведет к вставке O (0), что является случаем, когда вы просто (безубыточность). - person Muhammad Soliman; 24.11.2014

arrow_upward
1
arrow_downward

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

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

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

person ymz    schedule 24.11.2014