BST или хэш-таблица?

Question

У меня есть большие текстовые файлы, над которыми нужно выполнять все виды операций, в основном с проверкой строк за строкой. Данные, как правило, носят характер продаж / транзакций и, как правило, содержат огромное количество избыточной информации в разных строках, например, имена клиентов. Итерации и манипулирование этими данными стали настолько распространенной задачей, что я пишу библиотеку на C, которую я надеюсь сделать доступной как модуль Python.

В одном тесте я обнаружил, что из 1,3 миллиона значений столбцов только ~ 300 000 были уникальными. Перегрузка памяти вызывает беспокойство, поскольку наше веб-приложение на основе Python может обрабатывать одновременные запросы для больших наборов данных.

Моей первой попыткой было прочитать файл и вставить значение каждого столбца в двоичное дерево поиска. Если значение никогда не было видно раньше, выделяется память для хранения строки, в противном случае возвращается указатель на существующее хранилище для этого значения. Это хорошо работает для наборов данных ~ 100 000 строк. Гораздо больше, и все останавливается, и потребление памяти стремительно растет. Я предполагаю, что издержки всех этих указателей узлов в дереве не помогают, и использование strcmp для двоичного поиска становится очень болезненным.

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

Каковы лучшие кандидаты структуры данных в подобной ситуации?

Спасибо за ваше время.

Answer 1

Изменение размера хеш-таблицы не является проблемой, если только у вас нет требования, чтобы каждая вставка в таблицу занимала одинаковое количество времени.Пока вы всегда увеличиваете размер хеш-таблицы на постоянный коэффициент (например, всегда увеличиваете размер на 50%), вычислительные затраты на добавление дополнительного элемента амортизируются O(1).Это означает, что n операции вставки (когда n велико) будут занимать количество времени, пропорциональное n - однако, фактическое время на вставку может сильно отличаться (на практике одна из вставок будеточень медленно, в то время как другие будут очень быстрыми, но среднее значение всех операций невелико).Причина этого в том, что когда вы вставляете дополнительный элемент, который вынуждает таблицу расширяться, например, с 1000000 до 1500000 элементов, эта вставка займет много времени, но теперь вы купили себе 500000 чрезвычайно быстрых будущих вставок, прежде чем вам потребуетсяизменить размер снова.Короче говоря, я бы определенно пошел за хеш-таблицей.

Answer 2

библиотека на C, которую я надеюсь сделать доступен как модуль Python

В Python уже встроены очень эффективные тонко настроенные хеш-таблицы. Я настоятельно рекомендую, чтобы ваша библиотека / модуль сначала работала на Python. Затем проверьте скорость. Если это не достаточно быстро, профилируйте его и удалите все найденные ограничения скорости, возможно, с помощью Cython.

код установки:

shared_table = {}
string_sharer = shared_table.setdefault

сжатие каждой строки ввода:

for i, field in enumerate(fields):
    fields[i] = string_sharer(field, field)

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

Answer 3

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

n=n*2;
bucket=realloc(bucket, sizeof(bucket)*n);
for (i=0,j=n/2; j<n; i++,j++) {
  bucket[j]=bucket[i];
}