Я сканирую большой источник данных, в настоящее время около 8 миллионов записей, извлекая по строке для каждой записи, которую я хочу в алфавитном порядке.
Currentlty Я помещаю их в массив, затем сортирую индекс по ним, используя qsort(), который работает нормально.
Но из любопытства я подумываю вместо этого вставить каждую строку в структуру данных, которая поддерживает их в алфавитном порядке, когда я сканирую их из источника данных, частично для опыта его добавления, частично потому, что он будет работать быстрее без ожидание завершения сортировки после завершения сканирования (-:
Какую структуру данных было бы наиболее просто реализовать в C?
UPDATE
Для пояснения, единственные операции, которые мне нужно выполнить, - это вставить элемент и сбросить индекс, когда он будет выполнен. Я имею в виду, что для каждого элемента в исходном порядке выводится целое число, представляющее порядок, в котором он находится после сортировки.
РЕЗЮМЕ
- Самым простым для реализации являются деревья двоичного поиска.
- Самобалансирующиеся бинарные деревья намного лучше, но их нетривиально реализовать.
- Вставка может быть выполнена итеративно, но обход по порядку для сброса результатов и обход по порядку для удаления дерева, когда это сделано, оба требуют либо рекурсии, либо явного стека.
- Без реализации балансировки, запуски упорядоченного ввода приведут к вырожденному наихудшему случаю, который является связанным списком. Это означает глубокие деревья, которые сильно влияют на скорость операции вставки.
- Немного перетасовывая ввод, можно существенно разбить упорядоченный ввод и проще реализовать это балансирование.