ну почему... PR его (ведь вывод основывается на PR ) можно посчитать сразу (при краулинге). Так и делается. После этого отсортировать массивы по PR. А они отсортированны изначально - при краулинге. После этого найти интерсекшен, и опять же отсортировать по убыванию PR. А после этого уже выполнять текстовый поиск по первым 10.. А точнее - пока не наберется 10 результатов.
Как сортировать страницы - поисковик знает заранее. Это определяется PRом. А в вашем случае (если вы дойдете до PR) можно хранить отдельно. И сортировка 4000 ссылок по убыванию PR это будет опять же быстрее чем полнотекстовый поиск.
да без разницы - юних\линух\винда.
на VMWare в ring0 используется JIT компиляция, но все равно ring0 полу-интерпретируемый. В отличии от ring3. А переходы в ring0 есть всегда.
Кстати. сейчас сделал простой текстовый поиск по 450 метрам исходников.
Он выполнился за 1 минуту, на вышеприведенной машине. Так что что-то у вас не то со скоростью.
знаете. вот сейчас набросал интерсекшен , без какой-либо особой оптимизации.
#include "stdafx.h" #include <windows.h> #include <stdio.h> #include <map> #include <vector> using namespace std; typedef map<DWORD,unsigned short> Tmap_addr; typedef vector<DWORD> TVec_results; int _tmain(int argc, _TCHAR* argv[]) { Tmap_addr map1; Tmap_addr map2; Tmap_addr map3; TVec_results results; srand (GetTickCount()); DWORD t1=GetTickCount(); do { map1[rand()]=0; } while (map1.size()<4000); do { map2[rand()]=0; } while (map2.size()<4000); do { map3[rand()]=0; } while (map3.size()<4000); DWORD t2=GetTickCount(); printf("Time to prepare : %d\n",t2-t1); t1=GetTickCount(); Tmap_addr::iterator i; DWORD dwOps=0; for (i=map1.begin();i!=map1.end();i++) { DWORD val=i->first; if (map2.end()!=map2.find(val) && map3.end()!=map3.find(val)) { results.push_back(val); } dwOps++; } t2=GetTickCount(); printf ("intersection time : %d\n Intersection result : %d", t2-t1, results.size()); return 0; }
У меня сейчас машина : IBM Thinkpad T42p, Intel Centrino 1.7 GHz
результаты следующие :
Time to prepare: 30 Intersection time : 10 Intersection result : 49
Как видите, чтоб найти пересечение 3 массивов мне понадобилось 10 миллисекунд. Так что где-то вы не правильно считаете...
Естественно не все так просто. Но поверьте - это один из принципов. Вы можете посмотреть это даже сами : сделайте запрос по какому-либо слову, где вы будете ожидать, 50 результатов, к примеру. Гугль скажет вам - 50 результатов, и кликните сразу на 5-ю страницу поиска. Гугль вам покажет 3-ю страницу, и скажет, что больше нет страниц. Такое весьма часто встречается. Поэкспериментируйте. Это и яндекса касается и других.
Нет. Переход ring3->ring0 и обратно в случае виртуальной машины - это ОЧЕНЬ ресурсоемкий процесс. Это не 5000 тактов, как на реальной машине. Это НАМНОГО дольше. А работа ядра всегда есть.
Приблизительно так. Мы за базу взяли многосерч. Но помимо этого там еще есть pay per click модуль - вот там приблизительно так организовано.
Я с вами полностью согласен в плане того, что вы написали выше. Но это, на мой взгляд, не противоречит написанному мною. Т.к. то, что вы описали - это и есть "некомфортная работа". И примеров я могу привести много, когда это нужно, но это не получается. Я последние несколько лет как раз работаю с большими количествами информации. И поверьте - частенько приходилось раньше (пока принудительно в ядре не выставил размер окружения большим) тыкаться что-то сделать, и обламываться с воплями Argument list too long и иже с ними.
касательно xfs:
http://www-128.ibm.com/developerworks/library/l-fs9.html
Я написал в вышеприведенной команде : rm -f * . где вы там нашли длинную командную строку?
Ну. и естественно (правда глупо на этом форуме такую ссылку давать - сочтут необоснованными понтами) :
http://www.google.com/search?q=argument+list+too+long
Почитайте, это полезно.
Какие наглые модераторы нынче, причем тут древние ядра? Я говорю не о десятках тысяч файлов. Я говорю о количестве файлов в одном каталоге. И о сотнях тысяч файлов. У вас есть опыт работы с таким количеством файлов? По всей видисости нет. А мой поисковик сейчас имеет в файловой системе больше 2 миллионов файлов. И мои программисты год назад сталкивались как раз с этой проблемой, что ext3 просто не могла по-человечески работать.
Кстати, предлагаю не давить своим авторитетом модератора, и необоснованными заявлениями.
Исходя из вашего поста, я понял, что вы находили пересечение трех массивов , где каждый состоит из 4000 элементов. И это вы делали 1.5 часа? Честно, не верю. Ну или я не знаю на чем это писать нужно 😕
Почему? Зачем вам нужно сразу выдавать все результаты. Можете проанализировать тот же гугль , или более приближенный, и с открытыми исходниками - многосерч. Они выдают и ищут отлько первые 10 результатов. Искать следующие 10 результатов они начинают _ТОЛЬКО_ при нажатии кнопки next. Они никогда не формируют весь result set сразу.
То, что гостевая машина работает быстрее чем реальная? Зря вы так :)
У меня очень хорошее представление об устройстве линукса, поверьте. :)
[root@host315 huge]# ls | wc 66001 66001 384900 [root@host315 huge]# rm -f * bash: /bin/rm: Argument list too long
А какие предложения? Чтоб быстро было. Reiser? Не смешите.
А кто мешает, когда вы найдете список адресов для каждого слова, найти вначале пересечение массивов - чтоб построковый поиск выполнять в тех файлах, в который однозначно есть указанные слова. Этим действием вы еще больше сократите объем информации, которую нужно обработать.
И не забывайте - вначале вам нужно всего первые 10 результатов. Соответственно вам нужно просмотреть только первые 10 файлов из результатов пересечения (грубо говоря). И дать знать, что есть еще результаты, которые вы начнете анализировать по нажатии на кнопочку Next results.
И еще немного дополнений : очень большое значение имеет алгоритм текстового поиска. Скорость может отличаться в десятки раз в разных алгоритмах.
И еще немаловажное значение имеет аппаратная платформа.
Простой пример :
Текстовая база на 3 миллиона статей, на моем домашнем сервере для тестов с конфигурацией :
AMD Athlon(tm) 64 X2 Dual Core Processor 4800+
Cache 1024kb
4GB Dual-Channel Ram
дисковая подсистема : два SATA-2 диска, организованных в страйп.
импортируется за 3 часа.
Это парсинг 3 гигового XML файла + инсерты, инсерты и еще раз инерты в мускуль.
да, тестовая машина крутится на виртуальной машине (VMware) , которая собственно и живет на вышеприведенной конфигурации.
А теперь посмотрим на ту же самую работу, но уже на другой конфигурации :
Intel(R) Pentium(R) 4 CPU 2.80GHz
cache 1024 kb
1GB RAM
SCSI диск без страйпа.
база импортируется на _реальной_ машине , а не под VMWare-гостевой уже больше 12 часов.
Как видите - разница в скорости _очень_ существенна.
Не так.
размер базы (кстати, а кто сказал что это база должна быть (об этом позже) = количество общеупотребимых слов в языке + количество терминов предметной области. А это не больше 500000 слов, а реально это порядка 30000.
Т.к. если слово в документе встречается 10 раз, то в таблице ссылка-то должна быть одна.
Не так ли?
А касательно организации ссылок. Ну в худшем случае мы занесем в базу слово "в", которое будет встречаться в любом документе. То получим 400000 ссылок. Это не так уж и много кстати. Всего 12 мегабайт информации (заметь - это максимальный размер одной записи в таблице, в вашем случае).
Так вот. Для хранения я предлагаю использовать древовидную структуру файлов в файловой системе. Т.е. делим слово на буквы, и буквы будут являться путем к файлу с ссылками. К примеру слово "статья". Допустим индекс будет иметь уровень вложенности 2, соответственно файл с ссылками на документы по слову "статья" будет находиться по пути :
/с/т/статья
Уловили суть? Вы получаете доступ к любому файлу за 3 операции (два открытия каталога + открытие файла). При этом избегаете перегрузки структуры каталогов (на каждом уровне будет не больше 32 объектов). Это кстати очень важно. ибо , к примеру в линуксе 8192 объекта в каталоге - критическое количество для комфортной работы. (при большем кол-ве rm -f * не будет работать к примеру, или ls ... )
ну и касательно более низкого уровня - рекомендую использовать файловую XFS от SGI - она лучше всех справляется с большим количеством файлов.
Да, вы считаете что это будет медленно. Да. Это будет медленно. Но с таким объемом информации быстро не будет. Либо очень дорогое железо нужно.
Но здесь придет на помощь кеш серпов, как я уже писал в первом посте. Вы имеете серп по запросу : "статья 241", сохраните его в отдельное хранилище, и перед тем, как делать полнотекстовый поиск по документам, и вообще обращаться к базе - посмотрите, а вдруг это уже запрашивали. В качестве методики организации кеша - можно использовать мое предложение по организации в FS.
попробуй "оглавление" чтоли сделать.
1) Имеешь таблиц у : слово => документы, в которых встречается
2) режешь статьи на слова (опять же содержащие смысл + в базовой форме), и ставишь соответствующие ссылки в таблице.
тогда никаких like не нужно.
при запросе - определяешь наборы документов, где встречаются слова из запроса.
после этого выделяешь документы, где встречаются все слова запроса.
да ну. ничего предосудительного не вижу.
Это найти при желании в гугле за пару минут можно.
тут ищи. там много подобных программ есть.
http://www.rvb.ru/soft/catalogue/c04.html
Бобер, вы зря недооцениваете возможности мускуля.
В свое время я работал с базами размером в несколько миллионов записей. Все было весьма шустро. Так что (имхо) наворачивать бесполезно.
Рекомендую скорость селекта погонять.
А индексы строить - это (имхо) будет весьма долго по разработке. И не думаю, что быстрее по скорости. Мускуль он ведь тоже индексы строит :)
