Comments 21
Статью плюсанул, за старания и все такое… но по факту — убилбы (сам балдист просто и постоянно натыкаюсь на этих умников :( )
Поделитесь программкой? было бы интересно потыкать =)
Вспомнилась одна игра, круг разделен на 4 сектора, которые меняют цвета, и чем дальше, тем длиннее последовательности надо запоминать, я написал на vb6 программу, которая делала все за меня, несколько часов кликала(медленно, чтобы не было подозрений) и прошла игру. Потом нашелся товарищ, который с карандашом и листиком бумаги меня обошел, но мне стало его жалко и бота больше не запускал :).
> так что эту проверку нужно провести только в самом конце, перед поиском в словаре.
То есть ваш метод учитывает, что буква, которую вы вписываете может оказаться первой, последней и вообще в середине слова? Интересно было бы собрать статистику — насколько часто буква будет внутри слова? Может быть такие варианты статистически не стоит рассматривать? Тогда задача упрощается и скорость работы алгоритма можно кардинально увеличить.
> Для того, чтобы не искать сначала в массиве индексов искомые 2 буквы, он был сделан полным, то есть содержал даже те пары букв, на которые в словаре нет ни одного слова.
Ооо, да вы, батенька, хеш-таблицу изобрели и функцию hash ( ) у строки переопределили :)
То есть ваш метод учитывает, что буква, которую вы вписываете может оказаться первой, последней и вообще в середине слова? Интересно было бы собрать статистику — насколько часто буква будет внутри слова? Может быть такие варианты статистически не стоит рассматривать? Тогда задача упрощается и скорость работы алгоритма можно кардинально увеличить.
> Для того, чтобы не искать сначала в массиве индексов искомые 2 буквы, он был сделан полным, то есть содержал даже те пары букв, на которые в словаре нет ни одного слова.
Ооо, да вы, батенька, хеш-таблицу изобрели и функцию hash ( ) у строки переопределили :)
Не. Такой способ ускорения — это как jpeg-сжатие, то есть с потерей некоторых (пусть даже редких) вариантов! Хотелось решить задачу на 100%
Да? Это называется хеш-таблица?))))
Да? Это называется хеш-таблица?))))
ru.wikipedia.org/wiki/Хеш-таблица
Насколько я помню, оптимальным размером таблицы индексов считают 0.75 от числа элементов (но это верно для хорошо работающей хеш-функции, а ваша функция не очень равномерное распределение имеет). Этим объясняется, что вы не получили существенного прироста производительности при переходе от 10-битной к 15-битной хеш-функции от массива длиной 1024 пар букв к массиву длиной 32к трехбуквенных сочетаний (для красоты забудем про 'ё')
Насколько я помню, оптимальным размером таблицы индексов считают 0.75 от числа элементов (но это верно для хорошо работающей хеш-функции, а ваша функция не очень равномерное распределение имеет). Этим объясняется, что вы не получили существенного прироста производительности при переходе от 10-битной к 15-битной хеш-функции от массива длиной 1024 пар букв к массиву длиной 32к трехбуквенных сочетаний (для красоты забудем про 'ё')
Спасибо, ценное замечание! Мне кажется это вообще такое «правило рычага» — выигрываешь в скорости, проигрываешь в памяти (если делать большие хэш-таблицы)
Я решал похожую задачу контекстного поиска по многомегабайтной базе «Гарант» в начале 90-ых. Тогда не было интернета и компьютеров с памятью больше 4 мегабайт, а виндовс была графической средой для запуска пасьянса «косынка». Визуал бейсика не было, был простой бейсик (но речь не о бейсике, а об алгоритмах и структурах данных).
Слова в словаре были представлены в виде дерева, где буквы были ребрами (ну то есть из корня дерева выходило 33 ребра грубо говоря), а в узлах хранилась дополнительная инофрмация (в вашем случае — есть ли такое слово в языке). То есть вам можно обойтись и без базы данных — просто представив словарь в виде дерева. На мой взгляд, это будет и компактнее, и быстрее чем с использованием базы даных.
Слова в словаре были представлены в виде дерева, где буквы были ребрами (ну то есть из корня дерева выходило 33 ребра грубо говоря), а в узлах хранилась дополнительная инофрмация (в вашем случае — есть ли такое слово в языке). То есть вам можно обойтись и без базы данных — просто представив словарь в виде дерева. На мой взгляд, это будет и компактнее, и быстрее чем с использованием базы даных.
а какой был размер словаря?
Все слова, встречающиеся в текстах, обрезались по первым N буквам. (N как правило было равно 5, то есть на запрос «коростель» находились все документы, в которых были слова «короста», «коростели» итд — но и это давало очень неплохие результаты для возможности последующего уточнения, которое зачастую уже не нужно было). Так как программа распространялась на дискетах, то экономили каждый килобайт. Да и памяти было 640килобайт минус операционка и резидентные программы. Когда на ХТ-компьютере программа на введенное пользователем слово в несколькомегабайтной (я уже не помню — пять? десять? порядок был примерно такой) полнотекстовой базе данных находила это слово в документах за одну-две секунды и выдавала их список — народ реально впечатлялся.
В вашем случае словарь из 150к слов — по современным меркам это копейки — для хранения дерева нужно несколько метров оперативки-то всего.
В вашем случае словарь из 150к слов — по современным меркам это копейки — для хранения дерева нужно несколько метров оперативки-то всего.
Да, вариант с деревом красивый! В Паскале он реализовывался с помощью связанных списков. Ну или «куча». Даже не знаю, есть ли в Visual Basic динамическое выделение памяти, чтобы создать такую структуру
Ну, если и дальше будете пинать балду — вас из песочницы не выпустят :)
Не так уж важно какой язык вы предпочитаете, но владеть хотя бы одним должны :)
ЗЫ. Вспомнилось, как я эту программу-индексатор сперва написал на паскале, потом переписал на си так стал сишником, а потом обратно на паскаль, потому что вышел турбо-паскаль 7.0 в котором был… как его… 32-битный flat-mode
Не так уж важно какой язык вы предпочитаете, но владеть хотя бы одним должны :)
ЗЫ. Вспомнилось, как я эту программу-индексатор сперва написал на паскале, потом переписал на си так стал сишником, а потом обратно на паскаль, потому что вышел турбо-паскаль 7.0 в котором был… как его… 32-битный flat-mode
Не рассматривали Trie в качестве способа индексации? Тогда обход поля был бы синхронен с обходом индекса
Нет, не рассматривал! Мне тут коллега bachin указал на этот способ! Но я не знаю, можно ли в VBA строить динамические связанные списки… Спасибо за ссылку
Ну, так как вам не приходится в процессе игры активно добавлять и удалять слова из индекса, то можно поиск и на бейсике, наверно, написать — все операции производятся над массивом байт, который читается из файла :)
Конечно, нужна будет тулза, которая этот файл создаст в нужном формате из plain-text файла…
Ну, опять же можно взять сразу большой кусок памяти и заполнять его… Будет безумно медленно, но индексацию-то один раз надо провести, разве что потом придется переиндексировать если захочется слов добавить. Но можно и без динамической выделяемой памяти сделать и без указателей. Стоя, в гамаке и в скафандрах.
Конечно, нужна будет тулза, которая этот файл создаст в нужном формате из plain-text файла…
Ну, опять же можно взять сразу большой кусок памяти и заполнять его… Будет безумно медленно, но индексацию-то один раз надо провести, разве что потом придется переиндексировать если захочется слов добавить. Но можно и без динамической выделяемой памяти сделать и без указателей. Стоя, в гамаке и в скафандрах.
2 секунды на ход это слишком много, я делал реализацию, в которой на поле 9х9 и словаре 110000 слов на ход тратилось 16 миллисекунд
Sign up to leave a comment.
Как я гонял Балду на Visual Basic for Applications для MS Access