бозеба. попробую ради интереса. А каше сама поднимает в память все что читалось 2 раза с диска. так что можно при той же скорости и память экономить, т.к строку ищут обычно по первым неск буквам
я неточно выразился — максимальная длина строки — 50 символов необходимо быстро найти а) множество строк начинающихся с некоторой строки поиска б) множество строк содержащих в себе в любой позиции некоторую подстроку поиска
ну в общем сейчас я сделал такую штуку: для каждой целевой строки мы выполняем ее разбиение на символы и генерим такое деревцо: page1 — первая буква строки page2, page3 — вторая буква строки ну дальше — третья буква и т.д. до 50-й
Ну там дальше по задаче нужно смотреть. Если нужно искать точное совпадение, то всё просто и очевидно, если нужен поиск по префиксу/суффиксу/инфиксу/словоформам, то можно нагенерить нужные подстроки/словоформы для всех строчек, вычислить какие-нибудь хеши (CRC-32/FLV-64) и складировать в B-дерево их. Дальше искать в этом B-дереве и дальше опять же по задаче: можно прямо выбирать отматчившиеся строки, а можно провести дополнительную фильтрацию результатов. В случае с 64-битным хешем, процент коллизий будет очень низкий и в большинстве ситуаций на эти коллизии можно положить хуй. А если что-то готовое нужно, то можно sphinx заюзать.
59 comments
recommend
bookmark
subscribe
plain text @ grep
быстро будет искать? )
надо за сотую секунды, допустим
ых, ну я делаю вот такое btree и исчу
Поиск "ПП Пуп"
^myGlobal("П","П"," ","П","у","п","а")=11192062
^myGlobal("П","П"," ","П","у","п","а","н","ь")=11367503
^myGlobal("П","П"," ","П","у","п","а","ч")=10459254
^myGlobal("П","П"," ","П","у","п","а","ш","к","о")=12646668
^myGlobal("П","П"," ","П","у","п","е","з","а")=11167157
пиздец. В mysql захерачь, да и всё. srsly.
ну тут вопрос как его захерачить чтобы поиск был быстрым, понимаш? )
предыдующу хуйню я делаю в каше
1. Захерачиваешь
2. Делаешь индекс
3. ???
4. Быстрый поиск!
ну ок, я совсем тупой. какой индекс мне надо посторить для миллиарда ебучих строчек чтобы за сотую секунды я находил нужную строку?
спрошу на форуме
хотя щас попробую сравнить
мне скучно и я устал
(ну и базу в память, ага)
лучше просто поиздевайся надо мной)
снимай штанишки, милый))
уже снял, что дальше?
начинай тереться обо мну
я уже делаю это
делай это сильнее, шалун
на самом деле быстрее чем Б-дерево в памяти наверное поиск выполнить невозмножно
https://dev.mysql.com/doc/refman/5.0/en/...
>USING {BTREE | HASH}
трусь сильнее, я очень возбужден, стараюсь все делать хорошо
а теперь заканчивай, или плати
кончил, но мне понравилось и я хочу еще) а дорого платить?
договоримся
бозеба. попробую ради интереса. А каше сама поднимает в память все что читалось 2 раза с диска. так что можно при той же скорости и память экономить, т.к строку ищут обычно по первым неск буквам
но у него же строки по 50 символов
ты меня троллируешь или каким-то образом не прочитал оп-пост?
я неточно выразился — максимальная длина строки — 50 символов
необходимо быстро найти
а) множество строк начинающихся с некоторой строки поиска
б) множество строк содержащих в себе в любой позиции некоторую подстроку поиска
СТАВЬ LIKE))
прозреваю что like получше отработает
ну какой нахуй лайк? )
пиздец. https://dev.mysql.com/doc/refman/5.0/en/...
я это сказал потому что он будет пиздец каким медленным же. что совершенно неприемлемо
нухз
нухз
а можно самому определить хранение индекса и код для выборки данных по этому индексу в мускуле?)
а ты уже попробовал и получилось слишком медленно?
ну в общем сейчас я сделал такую штуку: для каждой целевой строки мы выполняем ее разбиение на символы
и генерим такое деревцо:
page1 — первая буква строки
page2, page3 — вторая буква строки
ну дальше — третья буква и т.д.
до 50-й
все отсортировано
и это работает очень быстро. мне просто интересно было узнать как решаются такие вещи при помощи эскуэля
я тоже подумал что ты нихуя не понял, минутку)
а fulltext search чо, тоже медленный?
дя
итт секта велосипедостроителей. Ни одного бенчмарка, но уже есть велосипеды.
а как он реализуется?
lmgify https://dev.mysql.com/doc/refman/5.0/en/...
я тоже уже вырубаюсь спать, завтра отпишусь сколько по времени получается поиск
префиксальные деревья
бинарное дерево + хеш
алсо задача как-то подебильному поставлена
сгенерирую дорвей, залью, проспамлю форумы/блоги, а потом через гугол буду искать нужную строку
я тебя троллирую(пока ты спишь)
мамку свою троллируй, школьник
ты тупой просто
затралили))
она не спит
B(+)-деревом, например.
ну собсно я так и сделол, а Intersystems Cache — это основная структура хранения данных. эскуэль сосет
вот, например http://dl.dropbox.com/u/12443803/MUMPS_1...
Ну там дальше по задаче нужно смотреть.
Если нужно искать точное совпадение, то всё просто и очевидно, если нужен поиск по префиксу/суффиксу/инфиксу/словоформам, то можно нагенерить нужные подстроки/словоформы для всех строчек, вычислить какие-нибудь хеши (CRC-32/FLV-64) и складировать в B-дерево их.
Дальше искать в этом B-дереве и дальше опять же по задаче: можно прямо выбирать отматчившиеся строки, а можно провести дополнительную фильтрацию результатов. В случае с 64-битным хешем, процент коллизий будет очень низкий и в большинстве ситуаций на эти коллизии можно положить хуй.
А если что-то готовое нужно, то можно sphinx заюзать.
И да, ты украл мой гет и я теперь тебя ненавижу.