Hello, all!
Есть модуль проверки орфографии, думаю в финальном релизе он будет выделен в оттдельную dll-ку.
Данные для построения структуры данных считываются из текстового файла. После оптимизации у меня получилось добиться скорости построения этой стркуктуры за 0.2 сек для файла, размером 2MB. Слова с ошибками выдаются практически мгновенно, даже не считал, но человеческий глаз такой скорости не улавливает.
Модуль этот будет применяться в следующем контексте:
пользователь вводит слова для поиска в строке запроса. Перед началом поиска нужно запустить ф-цию проверки орфографии, которая выдаст неправильные, на взгляд программы слова. Проблема в том, что при размере файла 2MB модуль проверки орфографии отжирает 50 mb памяти.
Есть 2 варианта: 1) постоянно держать его в памяти
2) каждый раз считывать данные из файла, затрачивая при этом времени около 0.7 сек (это минимум, т.к. текстовый файл с данными будет большой)
Преимущества 1-го варианта скорость, но памяти мнгого нужно.
Во 2-м случае все наоборот.
Не знаю как поступить ( (c) какая-то реклама)
Может уважаемое Community что посоветует?
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Не знаю как поступить ( (c) какая-то реклама) DG>Может уважаемое Community что посоветует?
Зависит от многих вещей.
Целевая платформа: доступный объём памяти для твоего приложения, критичность ко времени выполнения.
Потенциальное увеличение размера структуры в будущем (обогащение словаря)
... ещё что-нибудь?
Опять-таки, может быть возможно более компактно представить структуру в памяти?
Dr.Gigabit wrote:
> Данные для построения структуры данных считываются из текстового файла. После оптимизации у меня получилось добиться скорости построения этой стркуктуры за 0.2 сек для файла, размером 2MB.
Файла со словарем или..?
Что за структура? Бинарное дерево, хэш-таблица, тернарное дерево,...?
Диллема она на то и диллема, что для нее не существует хорошего выбора. Необходимо сблизить две противоположности -память/скорость через реализацию иерархических кэшей (хотя бы один промежуточный уровень). Это может существенно уменьшить сложность по памяти, правда при некотором понижении в скорости. В итоге можно прийти к оптимальном решению.
Это общие соображения, детали зависят от вашей конкретной реализации структуры данных. Вообще судя по постановке задачи (большие объемы данных — максимано возможная скорость), неплохим решением будут B-деревья.
Здравствуйте, MaximE, Вы писали:
ME>Dr.Gigabit wrote:
>> Данные для построения структуры данных считываются из текстового файла. После оптимизации у меня получилось добиться скорости построения этой стркуктуры за 0.2 сек для файла, размером 2MB.
ME>Файла со словарем или..?
Файла со словарем...
ME>Что за структура? Бинарное дерево, хэш-таблица, тернарное дерево,...?
Тернарное. По сравнению со стандартной реализацией мое работает где-то раз 5-6 быстрее.
ME>-- ME>Maxim Yegorushkin
Здравствуйте, Тигра, Вы писали:
Т>Здравствуйте, Dr.Gigabit, Вы писали:
DG>>Не знаю как поступить ( (c) какая-то реклама) DG>>Может уважаемое Community что посоветует?
Т>Зависит от многих вещей.
Т> Целевая платформа: доступный объём памяти для твоего приложения, критичность ко времени выполнения.
Объем памяти не фиксирован и заранее не известен. Можно, конечно, в минимальных системных требованиях затребовать минимум 512 mb.
Но это же не наш метод? (с) Кавказская пленница (СССР, год не помню)
А вот критичность по времени — максимальная. Дело в том, что это поисковик, и там много других вещей, на которые действительно нужно время
Т> Потенциальное увеличение размера структуры в будущем (обогащение словаря) Т> ... ещё что-нибудь?
Т>Опять-таки, может быть возможно более компактно представить структуру в памяти?
Здесь, скорее вопрос об использовании каких-то возможностей системы(прога будет работать под Windows) ибо человеческих(моих) возможнотей уже не хватает. Вроде все по максимому оптимизировал.
Здравствуйте, misha_sk, Вы писали:
_>Диллема она на то и диллема, что для нее не существует хорошего выбора. Необходимо сблизить две противоположности -память/скорость через реализацию иерархических кэшей (хотя бы один промежуточный уровень). Это может существенно уменьшить сложность по памяти, правда при некотором понижении в скорости. В итоге можно прийти к оптимальном решению. _>Это общие соображения, детали зависят от вашей конкретной реализации структуры данных. Вообще судя по постановке задачи (большие объемы данных — максимано возможная скорость), неплохим решением будут B-деревья.
Тернарные деревья в данном случае эффективнее. А за идею спасибо — будем думать.
[]
>>> Данные для построения структуры данных считываются из текстового файла. После оптимизации у меня получилось добиться скорости построения этой стркуктуры за 0.2 сек для файла, размером 2MB. > > ME>Файла со словарем или..? > Файла со словарем... > > ME>Что за структура? Бинарное дерево, хэш-таблица, тернарное дерево,...? > Тернарное. По сравнению со стандартной реализацией мое работает где-то раз 5-6 быстрее.
С++ стандартная библиотека не предоставляет тернарных деревьев
Построй дерево однажды. Храни узлы в массиве, используя индексы вместо указателей, чтобы отвязаться от базового адреса массива. Сохрани массив с построенным деревом в файд. Затем отоброжай этот файл в память по любому адресу в режиме read-only. Так ты сможешь не хранить постоянно дерево в памяти, и не тратить время на его последующие построения. Кроме того, отображеный в память в режиме read-only файл не будет выгружаться в своп-файл при нехватки памяти.
DG> Данные для построения структуры данных считываются из текстового файла. DG>После оптимизации у меня получилось добиться скорости построения этой DG>стркуктуры за 0.2 сек для файла, размером 2MB.
... DG> Есть 2 варианта: DG>постоянно держать его в памяти[/*] DG>каждый раз считывать данные из файла, затрачивая при этом времени около 0.7 сек (это минимум, т.к. текстовый файл с данными будет большой)[/*]DG>Преимущества 1-го варианта скорость, но памяти мнгого нужно. DG>Во 2-м случае все наоборот.
Может всётаки использовать не текстовый файл, а предварительно подготовленный бинарный?
Насколько я понял по описанию, изменятся пользователем структура не будет, или будет очень редко.
Соответственно можно разбить данные на 2 класса — данные и индекс поиска.
Далее можно сделать так:
Сваливаешь все строки в один большой массив, в индексе указываешь индексы в массиве, после чего сохраняешь это на диск.
Можно при чтении индексы на указатели подменить, а можно алгоритм подшаманить.
В любом случае читаться такая структура будет гораздо быстрее текстового файла.
Если использовать mmap, и алгоритм перевести на работу с индексами, памяти будет использоваться ровно столько, сколько её занимают данные на диске.
Единственный минус — это усложнение добавления слова.
Но, т.к. похоже это происходит достаточно редко, то скорость тут не критична.
<skipped>
DG>Преимущества 1-го варианта скорость, но памяти мнгого нужно. DG>Во 2-м случае все наоборот.
DG>Не знаю как поступить ( (c) какая-то реклама) DG>Может уважаемое Community что посоветует?
В библиотеке пусть это настраивается. А приложение,использующее библиотеку может определять количество доступной физической памяти и взависимости от этого выбирать алгоритм.
Вообще 50 метров не кажется критичным при современном положении вещей. Правда, ведь и файл может быть больше 2 мегабайт ?
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Hello, all! DG> Есть модуль проверки орфографии, думаю в финальном релизе он будет выделен в оттдельную dll-ку. DG> Данные для построения структуры данных считываются из текстового файла. После оптимизации у меня получилось добиться скорости построения этой стркуктуры за 0.2 сек для файла, размером 2MB. Слова с ошибками выдаются практически мгновенно, даже не считал, но человеческий глаз такой скорости не улавливает. DG> Модуль этот будет применяться в следующем контексте: DG> пользователь вводит слова для поиска в строке запроса. Перед началом поиска нужно запустить ф-цию проверки орфографии, которая выдаст неправильные, на взгляд программы слова. Проблема в том, что при размере файла 2MB модуль проверки орфографии отжирает 50 mb памяти. DG> Есть 2 варианта: 1) постоянно держать его в памяти DG> 2) каждый раз считывать данные из файла, затрачивая при этом времени около 0.7 сек (это минимум, т.к. текстовый файл с данными будет большой)
DG>Преимущества 1-го варианта скорость, но памяти мнгого нужно. DG>Во 2-м случае все наоборот.
DG>Не знаю как поступить ( (c) какая-то реклама) DG>Может уважаемое Community что посоветует?
Может тебе реализовать оба варианта и вызывать один либо другой в зависимости от колличества оперативки на компьютере ?
Здравствуйте, Tonal-, Вы писали:
T>Может всётаки использовать не текстовый файл, а предварительно подготовленный бинарный? T>Насколько я понял по описанию, изменятся пользователем структура не будет, или будет очень редко. T>Соответственно можно разбить данные на 2 класса — данные и индекс поиска. T>Далее можно сделать так: T>Сваливаешь все строки в один большой массив, в индексе указываешь индексы в массиве, после чего сохраняешь это на диск. T>Можно при чтении индексы на указатели подменить, а можно алгоритм подшаманить. T>В любом случае читаться такая структура будет гораздо быстрее текстового файла.
У вас есть какие-то данные по скорости поискса при использовании такой структуры? Может где глянуть можно подобные реализации или почитать?
Пожалуй и над этим стоит подумать, т.к. вы не первый, кто советует мне подобную идею.
В том то и соль, что алгоритм почти не изменяется,
если заменить все указатели на узлы на индексы в массиве узлов,
а указатели на строки на индексы в массиве символов.
Такую структуру можно напрямую записывать и восстанавливать с диска.
Причём, если использовать отображение в память, то не понадобится
ни прямого выделения памяти, ни чтения из файла.
Соответственно скорость работы алгоритм почти не изменится.
Просто вместо обращения по указателю — обращение по индексу.
DG>Пожалуй и над этим стоит подумать, т.к. вы не первый, кто советует мне подобную идею.
У меня когда-то был проектик где применялась индексация слов в документах.
Что-то около 250000 слов и 150-160мб текстов.
Всё жило тогда ещё в парадоксовских табличках.
Для текстов естественно применялось сжатие, так что таблица с ними была не очень большой.
Самой большой оказалась табличка индекса из 2х полей — id_word, id_topic ~100мб.
Она же нехило тормазила при запросах, что было критично...
Вынес индекс в бинарный файл, приделал бинарный поиск, и забыл о тормазах.
Ну и в качестве бонуса размер индекса стал ~ 10мб...
(с) Кавказская пленница (СССР, год не помню)
