Есть собственно конкретная задача: даны 2 "строки" в одной скажем 1000 слов и она хранится в памяти и эта строка постоянно и полностью меняется, другая хранится в файле и имеет очень большой размер.
Нужно произвести МАКСИМАЛЬНО быстрый поиск слов первой строки во второй, то есть найти совпадает ли хоть одно слово из первой строки хотябы с одним словом второй и если да то какое с каким.
Таких поисков нужно производить n штук параллельно. Нагрузка очень большая.
Это только частный пример.
Так как с такой областью как программирование серверов баз данных я ни бум бум, собственно вылезает множество вопросов:
как лучше хранить данные в файле? маппить в память? чем и как лучше читать и записывать?? как производить БЫСТРЫЙ поиск??? индексирование??? организацию многопоточности? можно ли организовать быстрый неточный поиск???какие алгоритмы лучше всего??? какие функции под windows лучше использовать?? поддержку unicode?
ну ессесно все это с возможность расширения,
SQL тут ессесно не нужен
Есть ли где почитать?? исходники??? чем проще тем лучше... алгоритмы?
Заранее примногоблагодарен:)
Здравствуйте, ilyxan, Вы писали:
I>Есть собственно конкретная задача: даны 2 "строки" в одной скажем 1000 слов и она хранится в памяти и эта строка постоянно и полностью меняется, другая хранится в файле и имеет очень большой размер. I>Нужно произвести МАКСИМАЛЬНО быстрый поиск слов первой строки во второй, то есть найти совпадает ли хоть одно слово из первой строки хотябы с одним словом второй и если да то какое с каким. I>Таких поисков нужно производить n штук параллельно. Нагрузка очень большая. I>Это только частный пример.
I>Так как с такой областью как программирование серверов баз данных я ни бум бум, собственно вылезает множество вопросов: I>как лучше хранить данные в файле? маппить в память? чем и как лучше читать и записывать?? как производить БЫСТРЫЙ поиск??? индексирование??? организацию многопоточности? можно ли организовать быстрый неточный поиск???какие алгоритмы лучше всего??? какие функции под windows лучше использовать?? поддержку unicode? I>ну ессесно все это с возможность расширения, I>SQL тут ессесно не нужен I>Есть ли где почитать?? исходники??? чем проще тем лучше... алгоритмы? I>Заранее примногоблагодарен
1. не строки видимо тогда, а таблички "слов".. с одной колонкой то есть..
одна <первая_строка> и вторая <вторая_строка>
2. видимо нужно проводить быстро много запросов типа
select * from <вторая_строка> where <вторая_строка>.<слово>=<выбранное_тобой_слово_из_первой_строки>
Результаты таких запросов и так работают очень быстро.. На любых размерах второй строки (сложность n*log(n)) Конечно если проиндексировать вторую строку.. Хотя в принципе можно ручками написать и быстрее (сложность max_length(слово из второй строки))
3. Но тебе видно нужно ишо быстре.. и парелельнее.. Ну чтож.. Ставишь несколько компьютеров с одной и той же БД.. Настраиваешь репликацию с одной БД.. Читаешь запросы (слова первой строки) и раскидываешь их по разным БД, так чтобы равномерно.. ПО для равномерной загрузки скажем нескольких паралельных mysql-серваков в сети найти можно.. Примерно так работают всякие google (запрос паралелится на примерно 1000 mysql машин)..
Здравствуйте, ilyxan, Вы писали:
I>Есть собственно конкретная задача: даны 2 "строки" в одной скажем 1000 слов и она хранится в памяти и эта строка постоянно и полностью меняется, другая хранится в файле и имеет очень большой размер. I>Нужно произвести МАКСИМАЛЬНО быстрый поиск слов первой строки во второй, то есть найти совпадает ли хоть одно слово из первой строки хотябы с одним словом второй и если да то какое с каким. I>Таких поисков нужно производить n штук параллельно. Нагрузка очень большая.
В базах как правило используется b-tree поиск, у него сложность n*log(n). В принципе для данной задачи можно использовать хэш таблицы, что будет быстрее, там сложность n*log(1).
Что же касается именно поиска подстроки в строке, особенно с возможностью не четкого поиска, то ключевые слова тут "Кнутт-Морис-Пратт", "Бойер-Мур", "Shift-End" — Это все названия нарошных алгоритмов для поиска подстрок.
Вообщем все зависит от трудоемкости и требуемой скорости. Если задача стоит так, что надо выжать максимальную скорость и при этом трудозатраты не важны, то собственноручно написанный вариант в конечном итоге окажется быстрее. Однако возможно хватит и поизводительности обычной БД, в таком случае проще спроецировать строки на реляционную структуру и ни о чем не думать. Просто на чтение даже неоптимизированная БД работает как пулемет.
I>как лучше хранить данные в файле? маппить в память? чем и как лучше читать и записывать?? как производить БЫСТРЫЙ поиск??? индексирование??? организацию многопоточности? можно ли организовать быстрый неточный поиск???какие алгоритмы лучше всего??? какие функции под windows лучше использовать?? поддержку unicode? I>ну ессесно все это с возможность расширения, I>SQL тут ессесно не нужен
Хм, да как сказать. В поноценных СУБД множество мелочей уже сделано и сделано хорошо, скорее всего намного лучше, чем ты сделаешь сам за первые две попытки
В любом случае я бы сначала сделал хранение и поиск на основе БД, посмотрел бы как все это работает, отладил бы все остальное, что с хранением и поиском не связно, и уже потом, если производительности БД окажется недостаточно, то стал бы писать что-то свое, более оптимальное.
I>Есть ли где почитать?? исходники??? чем проще тем лучше... алгоритмы?
Вообще про некоторые алгоритмы можно почитать тут: http://rsdn.ru/article/alg/bintree.xml
Здравствуйте, vvaizh, Вы писали:
V>1. не строки видимо тогда, а таблички "слов".. с одной колонкой то есть.. V> одна <первая_строка> и вторая <вторая_строка> V>2. видимо нужно проводить быстро много запросов типа V>
V>select * from <вторая_строка> where <вторая_строка>.<слово>=<выбранное_тобой_слово_из_первой_строки>
V>
V>Результаты таких запросов и так работают очень быстро.. На любых размерах второй строки (сложность n*log(n)) Конечно если проиндексировать вторую строку.. Хотя в принципе можно ручками написать и быстрее (сложность max_length(слово из второй строки))
да мне не запрос написать а сам СЕРВЕР бд.... архитектура вот как она есть... крохотный при крохотный MySQL сервер своими руками:) чтобы встроить в свою программулину...
Здравствуйте, ilyxan, Вы писали:
I>Здравствуйте, vvaizh, Вы писали:
V>>1. не строки видимо тогда, а таблички "слов".. с одной колонкой то есть.. V>> одна <первая_строка> и вторая <вторая_строка> V>>2. видимо нужно проводить быстро много запросов типа V>>
V>>select * from <вторая_строка> where <вторая_строка>.<слово>=<выбранное_тобой_слово_из_первой_строки>
V>>
V>>Результаты таких запросов и так работают очень быстро.. На любых размерах второй строки (сложность n*log(n)) Конечно если проиндексировать вторую строку.. Хотя в принципе можно ручками написать и быстрее (сложность max_length(слово из второй строки))
I>да мне не запрос написать а сам СЕРВЕР бд.... архитектура вот как она есть... крохотный при крохотный MySQL сервер своими руками чтобы встроить в свою программулину...
ну как бы есть и встраиваемая версия.. бери да встраивай..
если хочешь без sql-запросов сразу индексы ейные пользовать, дык и так вроде люди тоже делают..
myISAM он в исходниках, и некоторые тесты для него есть..
есть другие СУБД с открытым кодом.. FireBird, PostgreeSQL.. у них тоже есть встраиваемые варианты..
все они b-tree юзают для быстрого поиска.. Качай исходники да разбирайся..
ссылки на алгоритмы тебе выше кидали.. непонятно в чем проблема
Здравствуйте, Merle, Вы писали:
M>Здравствуйте, ilyxan, Вы писали:
I>>Есть собственно конкретная задача: даны 2 "строки" в одной скажем 1000 слов и она хранится в памяти и эта строка постоянно и полностью меняется, другая хранится в файле и имеет очень большой размер. I>>Нужно произвести МАКСИМАЛЬНО быстрый поиск слов первой строки во второй, то есть найти совпадает ли хоть одно слово из первой строки хотябы с одним словом второй и если да то какое с каким. I>>Таких поисков нужно производить n штук параллельно. Нагрузка очень большая. M>В базах как правило используется b-tree поиск, у него сложность n*log(n). В принципе для данной задачи можно использовать хэш таблицы, что будет быстрее, там сложность n*log(1).
может я что то упустил...
всегда думал что log(1)==0..
поправтье меня пожалуйста.. а то какое то ощущение непонятности остается.. ну или сами поправтьесь..
V>ну как бы есть и встраиваемая версия.. бери да встраивай.. V>если хочешь без sql-запросов сразу индексы ейные пользовать, дык и так вроде люди тоже делают.. V>myISAM он в исходниках, и некоторые тесты для него есть..
да есть то оно есть, они большие громоздкие, мне нужно меньше...:) нашел в форуме ссылку на Книжника — вот там у него исходнички очень хорошие — изучаемс:)) главное небольшие)
V>есть другие СУБД с открытым кодом.. FireBird, PostgreeSQL.. у них тоже есть встраиваемые варианты.. V>все они b-tree юзают для быстрого поиска.. Качай исходники да разбирайся..
С самими базами знаком, исходники есть... суть в том что время критично... разбираться с исходниках и выдирать небольшие кусочки трудоемко, проще написать свое, тем более что мне не так уж и много для счастья надо:))
V>ссылки на алгоритмы тебе выше кидали.. непонятно в чем проблема
Да я только сейчас заметил пост с ссылками и алгоритмами:)) уже начал ковырять... кучу вопросов уже отпало:)))
Здравствуйте, Merle, Вы писали:
M>Хм, да как сказать. В поноценных СУБД множество мелочей уже сделано и сделано хорошо, скорее всего намного лучше, чем ты сделаешь сам за первые две попытки :) M>В любом случае я бы сначала сделал хранение и поиск на основе БД, посмотрел бы как все это работает, отладил бы все остальное, что с хранением и поиском не связно, и уже потом, если производительности БД окажется недостаточно, то стал бы писать что-то свое, более оптимальное.
Да я вот тоже решил сделать хранение и поиск сначало... нафик хэш таблицы — буду пока деревья использовать... но скоро возникнут кучу других вопросов — многопоточность... оптимизация
За алгоритмы и ссылки большое человеческое спасибо:))
Здравствуйте, vvaizh, Вы писали:
M>>В базах как правило используется b-tree поиск, у него сложность n*log(n). В принципе для данной задачи можно использовать хэш таблицы, что будет быстрее, там сложность n*log(1). V>может я что то упустил... V>всегда думал что log(1)==0..
Уупс, это я с просоня... Поиск по хеш таблице идет за константное время и не зависит от размера таблицы, соответственно сложность там O(1).
Здравствуйте, Merle, Вы писали:
M>Здравствуйте, vvaizh, Вы писали:
хъ
M>Уупс, это я с просоня... Поиск по хеш таблице идет за константное время и не зависит от размера таблицы, соответственно сложность там O(1).
Поиск будет таковым, если мы найдем идеальную хеш-функцию. В принципе, это реально, но только если заранее известна выборка.
Я не знаю какую хеш-функцию использует SQL Server, но он никогда не выберет значение за постоянное время. Надо сказать, что SQL Server очень редко прибегает к хешированию — только на больших выборках при объединении, когда данные не упорядочены. Это обусловлено тем, что loop join гарантировано будет выполняться O(n*m), тогда как hash join — O(m+n+f1(n)+f2(m)), где f1 и f2 — время, потеряное на хеширование и другие накладные расходы.
Это раз.
Два. Фулскан имеет сложность — (максимальное время выборки) О(n), т.е. время напрямую зависит от количества строк. Поиск по индексу — О(log(n)), что конечно меньше фулскана и намного меньше, чем n*log(n).
Чтоже касается исходного сообщения: нужно использовать то, что уже давно придумали — STL.
Здравствуйте, Alexey Shirshov, Вы писали:
AS>Я не знаю какую хеш-функцию использует SQL Server, но он никогда не выберет значение за постоянное время.
А он-то тут причем? Это вообще отдельная пестня...
AS> Надо сказать, что SQL Server очень редко прибегает к хешированию — только на больших выборках при объединении, когда данные не упорядочены.
Думаешь это редкость?
Здравствуйте, Merle, Вы писали:
M>Здравствуйте, Alexey Shirshov, Вы писали:
AS>>Я не знаю какую хеш-функцию использует SQL Server, но он никогда не выберет значение за постоянное время. M>А он-то тут причем? Это вообще отдельная пестня...
Ну я всегда про него думаю.
AS>> Надо сказать, что SQL Server очень редко прибегает к хешированию — только на больших выборках при объединении, когда данные не упорядочены. M>Думаешь это редкость?
Отностительная. Во всяком случае, на моем опыте их возникало гораздо меньше.
Мы уже победили, просто это еще не так заметно...
