Хорошая идея / плохая идея: использовать Qt QSet для очень большого набора данных?

Question

Является ли плохой идеей использовать QSet для отслеживания очень большого набора довольно больших строк? Каждая строка длиной 54 символа (108 байтов). Набор может содержать тысячи записей (пока точно не знаю точное число). QSet будет использоваться только для вставки и запроса на членство.

Если это плохая идея, я определенно открыт для предложений. Мои строки из 54 символов состоят только из 6 различных символов (например, "AAAAAAAAABBBBBBBBBCCCCCCCCCDDDDDDDDDEEEEEEEEEFFFFFFFFF"). Возможно, это хороший кандидат на сжатие? Любые другие предложения приветствуются.

Answer 1

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

Посмотрите на некоторую информацию о радикальных деревьях, деревьях цифрового поиска, красно-черных деревьях и т. Д. Вы увидите, что вам не нужно хранить каждое и каждоеСтрока, а точнее шаблоны.Например, давайте упростим вашу проблему: у нас есть только 3 символа, которые могут появляться не более 2 раз каждый, а каждая строка имеет длину 6 символов.Три возможные строки:

AABBCC, AABCBC и AACBCB

С этими примерами мы могли бы избежать использования максимум 6 + 3 + 4 = 13 узлов вместо полных 18 узлов,не важно, но я тоже не знаю, что ты делаешь.Как и при любом типе сжатия, чем больше шаблонов префиксов используется повторно, тем больше у вас сжатия.

Редактировать: числа 13 и 18 получены из сжатия на уровне пути.Например, в прямом C (для аргумента / обсуждения), если я реализую свой класс хранения строк как обертку вокруг массива, я, вероятно, просто буду иметь массив символьных указателей, каждый указатель будет ссылаться на место в памяти, которое содержит шаблон.В приведенном выше примере это займет 18 символов (6 * 3 = 18).Если добавить размер массива (скажем, что sizeof (char *) равен 4, нашему массиву потребуется 3 * 4 байта памяти = 12 + 18 или 30 байтов для хранения наших шаблонов.

Если яВместо этого я сохраняю шаблоны в своего рода дереве цифрового поиска, я делаю небольшой компромисс: узлы в моем дереве будут больше 1 байта за штуку (1 байт для символа в узле, 4 байта для «следующего»)указатель в каждом узле, по 5 байт.) Первый шаблон, который мы храним, - AABBCC. Это 6 узлов в дереве. Далее - AABCBC. Мы повторно используем путь AAB из первого дерева и нам нужны только 3 дополнительных узла для CBC.последний шаблон - AACBCB. Мы повторно используем AA и нам нужно 4 новых узла для CBCB. Это всего 13 узлов * 5 байт = 65 байт памяти. Однако, если у вас много длинных повторяющихся шаблонов в префиксе вашегоданные, то вы увидите какое-то префиксное сжатие на уровне пути.

Если это не так, я бы посмотрел на сжатие Хаффмана или LZW. Это потребует от вас создания диктатаСписок шаблонов, с которыми связаны целые числа.Когда вы сжимаете, вы создаете словарь и создаете целочисленные идентификаторы для каждого шаблона в вашем тексте.Затем вы заменяете шаблоны в вашем тексте на целочисленные идентификаторы.Когда вы распаковываете, вы делаете наоборот.У меня нет времени, чтобы описать эти алгоритмы более подробно, поэтому вам нужно их найти.

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

Answer 2

QSet звучит как хорошая идея. По сути, это просто хеш-таблица, и она может динамически оптимизировать размер своего сегмента. Идеально подходит.

Еще одно предложение для сжатия ключа: Обрабатывайте его как числовую строку с основанием 6 (представьте, что A = 0, B = 1, ... F = 5) и преобразуйте ее в двоичный (int).

  QByteArray ba("112"); // instead of "BBC"
  int num = ba.toInt(0, 6 /*base*/); // num == 44

6 ^ 3 <2 ^ 8, поэтому мы можем представить каждые 3 символа в вашей строке с помощью 1-байтового целого (или символа) и сделать из него байтовый массив. Это уменьшит размер ключа с 54 до 18 байт. </p>

Answer 3

Я не думаю, что у вас возникнут дополнительные проблемы с использованием QSet для контейнеров другого типа, таких как std :: set, map или vector.Если вас интересует нехватка памяти, это, вероятно, зависит от того, сколько тысяч строк вам нужно сохранить, и если бы был способ кодировать их более кратко.(Например, если символы всегда располагаются в одном и том же порядке, но различаются по относительной длине, сохраняйте длину для каждого символа, а не для всех символов.) Однако даже 50 000 из этих строк составляют всего около 5 МБ, а из 500 000 -только 50 МБ для хранения, без учета накладных расходов на хранение, что является умеренным объемом памяти на современных машинах.

Answer 4

Из вашего предыдущего комментария: «В моих строках всегда будет 54 символа, и всегда будет по 9 каждого символа. Порядок - единственное, что меняется».

Тогда не храните сырые строки. Вы можете просто сжать их в 6 фактически используемых символов, а затем сделать из них QSet. Тривиальное сжатие будет {a, b, c, d, e, f}, и если набор символов известен заранее (и только эти 6 символов), вы даже можете упаковать вещи в 16-битное целое число.