#c #algorithm #serialization #data-structures #trie
#c #алгоритм #сериализация #структуры данных #попробуйте
Вопрос:
У меня есть большой словарь английских слов (около 70 тыс. из них), который я загружаю в память в начале программы. Они загружаются в базовую структуру данных trie, и каждый узел trie часто имеет много ссылок от одного узла ко многим другим (например, антонимы слов: «мертвый» -> «живой», «хорошо»). В каждом узле также есть a std::vector<MetaData> , который содержит различные разные метаданные для моей программы.
Теперь проблема заключается во времени загрузки этого файла. Чтение файла с диска, десериализация и выделение структуры данных для вещи в целом занимает много времени (4-5 секунд).
В настоящее время я работаю над тем, чтобы сделать загрузку асинхронной (или по частям, часть из них за кадр), но из-за характера приложения (это мобильная клавиатура), есть просто много случаев, когда его просто нужно быстро загрузить.
Что можно сделать для ускорения загрузки? Пул памяти все? Я сравниваю различные части, чтобы увидеть, что можно оптимизировать, но, похоже, пока что это просто мелочи, которые складываются.
Комментарии:
1. Это также зависит от архитектуры, можете ли вы искать и читать определенную часть файла?
2. Я думаю, вы можете.. хотя я могу сначала загрузить все сериализованные данные в память. После сравнительного анализа эта часть выполняется довольно быстро и не является узким местом.
3. Если вам почему-то не нужна вся структура данных сразу (т. Е. Вы не знаете, куда она «попадет»), вы можете просто «испечь» некоторые смещения для интересующей вас части данных и загрузить структуру в память с помощью word->offset_to_data . Это было бы быстрее. Вы также можете предварительно обработать содержимое перед запуском своего приложения
4. С Qs, подобным этому, с отсутствием множества важных деталей, трудно помочь. — Кажется, у меня были взлеты и падения, без объяснения причин…
5. Как вы передаете поэтапную загрузку. Вместо того, чтобы помещать словарь в один файл, распределите его по нескольким (возможно, сотням или даже тысячам) файлам примерно одинакового размера. Добавьте немного грубой оптимизации, чтобы гарантировать, что требуемая информация, как правило, находится в одном файле, и, скорее всего, вам нужно будет загружать только один или два файла за кадр. То, что пользователь вводит / делает, должно дать вам то, что вам нужно, чтобы определить, какие файлы загружать. В значительной степени, как некоторые видеоигры справляются с этим, если я помню. Томас Мэтьюз дает хорошую отправную точку для организации с помощью таблиц в виде файлов.
Ответ №1:
Если trie является статическим (т. Е. Не Изменяется при запуске программы), затем создайте оптимизированную версию в массиве, используя индексы массива вместо указателей. Затем вы можете сохранить это как свой файл данных. Затем запуск сводится к простой загрузке этого блока данных в память.
Выполнение этого способа делает некоторые вещи менее удобными (например, вам придется использовать массивы, а не std::vector , например), и вам, возможно, придется немного выполнить кастинг, но, немного подумав, вы получите очень компактную и очень быструю структуру данных, которая не страдает от накладных расходов, связанных с распределениемс созданием объекта для каждого узла. Вместо этого это, по сути, массив структур различной длины.
Я сделал это для приложения, которое использовало ориентированный ациклический граф слов (DAWG). Вместо того, чтобы перестраивать DAWG каждый раз при загрузке программы (трудоемкий процесс), у меня была служебная программа, которая создавала DAWG и отправляла его как файл данных вместо списка слов.
Комментарии:
1. Хм, это хорошая идея. Если бы только было легко заменить все ссылки на использование индексов, но я полагаю, что это не относится к области невозможности.
2. Я должен добавить, что trie время от времени меняется, но если все использует индексы вместо указателей и расположено в непрерывной точке в памяти, то, я думаю, это будет просто загрузка памяти, да?
3. @kamziro: если он изменяется во время выполнения программы, то вам нужно выделить больший массив. Или массив уже выделен для увеличения. Это не непреодолимая проблема, но о ней стоит подумать.
Ответ №2:
Не зная деталей, только смутное представление:
Загрузка объемных данных (записей) даст вам базовый словарь.
Для всех перекрестных ссылок, таких как синонимы и антонимы, загружайте и обрабатывайте данные в фоновом режиме, после того, как вы показали «готово». Скорее всего, пока пользователь не введет первый запрос, у вас все в порядке.
Позже
Если файл довольно большой, чтение сжатой версии может выиграть.
Также может помочь BufferedReader с соответствующим увеличенным размером буфера.
Ответ №3:
Вам следует пересмотреть структуру данных, чтобы ускорить загрузку данных.
Кроме того, разделение на несколько таблиц может ускорить процесс.
Например, создайте одну таблицу для слов, другую таблицу для синонимов и дополнительные таблицы для других отношений.
Первая таблица должна иметь организацию. Это позволяет представить таблицу синонимов как ; которая должна загружаться быстро.
Затем вы можете создавать любые внутренние контейнеры из загруженных данных. Причиной наличия разных структур данных для хранения данных и внутренних данных является оптимизация. Структуры, используемые для хранения (и загрузки) данных, оптимизированы для загрузки. Структура внутренних данных оптимизирована для поиска.
Ответ №4:
Еще одна идея, основанная на том факте, что это мобильное приложение для клавиатуры. Некоторые слова используются чаще, чем другие, поэтому, возможно, вы могли бы организовать это так, чтобы часто используемые слова загружались первыми, а редко используемые оставляли загружаться по мере необходимости (или по мере того, как у вас есть время).