Серьезная задачка для программистов
14.09.2010 технологии
Дано: существует некий Объект, который обладает однотипными признаками в формате «ключ-значение». Ключей много — сотни и даже тысячи. А теперь представьте, что таких объектов тоже очень много — сотни тысяч и даже миллионы. Количество признаков у каждого объекта может значительно отличаться.
Задача: отсортировать базу объектов по количеству совпадений ключей и значений с ключами и значениями Объекта. То есть верх списка должен начинаться с объектов, у которых максимальное количество таких же ключей как у исходного Объекта имеют то же значение, что и значения ключей самого Объекта.
Проще говоря, наверху списка должны оказаться объекты, более всего похожие на исходный Объект.
Проблема: всё это должно выполняться не часы и даже не минуты. Максимально быстро! Производительность очень важна.
Если вдруг эта задача вам кажется лёгкой, попробуйте решить похожую задачу: определите наиболее отличные объекты, но при этом обладающие максимальным количеством тех же ключей, что и у исходного Объекта (у них значения ключей будут другими).
Эта задача периодически поглощает мои мысли на протяжении уже более трёх лет. Подвижки есть, но всё равно до сих пор нет чёткого видения. Очевидно, что задача очень ресурсоёмкая, потому я думаю, что решение прежде всего заключается в способе организации такой сложной базы данных и очень быстрого взаимодействия с ней.
Если у вас нет решения, пишите просто любые идеи, подскажите направление. Или, возможно, вам не вполне понятны условия задачи, тогда задавайте вопросы, уточняйте.
Обсудим?
Комментирование этой статьи закрыто.
« Игра в города: новый рекорд! Ищу замену, нужен модератор технического раздела »
Я пока пришёл примерно к таким наброскам:
1. Индексы. Придумать алгоритм преобразования всех ключей и значений в определённый индекс, и потом уже сравнивать индексы объектов, а не все ключи и значения. Но пока не разработал такой алгоритм и даже не уверен, что это возможно. Да и сомневаюсь, что только это сможет вытянуть достаточную производительность.
2. Предварительная выборка. Вести дополнительную статистическую базу данных частоты встречаемости значений для каждого ключа. Тогда можно будет сравнивать не со всеми объектами, а только с той частью, которая соответствует проценту нормальности исходного Объекта.
Для размеров в единицы миллионов записей, такой вариант должен сработать:
таблица tablename (id, object_id, key_id, value). поле value очень желательно чтобы было небольшого размера (не километровый текст, если текст – то возможно нужно дополнительно хэшировать). Создаем индекс на (object_id, key_id). И пробуем выгребать данные таким запросом:
SELECT object_id, COUNT from tablename where
(key_id, value) IN (SELECT key_id, value from tablename where id = ?) GROUP BY object_id HAVING count(*) > пороговое_значение ORDER BY 1, 2 DESC.
Сильно лучше этого варианта врядли можно придумать. Если будет тормозить – нужно поиграться с настройками СУБД и покурить EXPLAIN запроса.. Индекс должен быть маленьким и влезать в память. Некоторые ухищрения типа кластеризации по индексу могут ещё неслабо помочь.
Как-то так.
COUNT (*) естественно в запросе. Парсер у тебя кушает что не нужно.
Индекс не тот написал.. на (key_id, value) должен быть.
Подзапрос вида IN (SELECT …) будет таки весьма значительно тормозить.
А ты не хочешь посмотреть в сторону noSQL решений? MongoDB, например. Там это и хранить очень правильно получится, и работать будет шустро.
По описанию ассоциируется с алгоритмом Slope One, использующимся для рекомендаций, где степень похожести товаров определяется косинусом угла между векторами покупок. Если я правильно уловил суть задачи. Идея – посмотреть реализации Slope One в поисках интересных решений.
Это map/reduce задача (http://en.wikipedia.org/wiki/MapReduce). Пространство ключей надо побить на куски, каждый кусок обработать отдельно (map) и результаты собрать (reduce). Если это сервис, мапперы могут держать свой кусок всегда загруженным.
Я использую поисковый движок sphinx для подобных задач. Он строит свой не sql индекс, из-за чего работает очень быстро. Обычными php-mysql алгоритмами такую задачу быстро не решить.
3 года, жесть :) В универе на 2 курсе кажется рассказывали об этом.
Представь все объекты в виде векторов, все сводится к типичной задаче нахождения ближайшего соседа.
Есть библиотеки, реализующие, например, R-деревья. Погугли по названию задачи, найдешь очень много вариантов решения в том числе и для больших объемов данных.
Если к NNS притянуть никак, то гугли задачи классификации и симиларити сёрч.
Это задача ревалентности. Нихуя она не тривиальная и не типичная.
Тормоз пишет свой Яндекс?
Парни, я же нигде не ставил никаких ограничений, почему же вы сами себя ограничиваете? Я про тех, кто упомянает SQL и PHP. Пусть задача решается наиболее подходящим способом.
Из языков для такой задачи я уже присматривался к Эрлангу. Ну а тип БД — вряд ли SQL, пока я так думаю.
В любом случае за ссылки и решения большущее спасибо — обязательно всё внимательно изучу. Надеюсь, варианты будут ещё :)
Как упоминал IAD, sphinx действительно может решать подобные задачи, посмотри на него в первую очередь.
Java Developer: даже больше скажу, это единственное известное мне решение (адаптивное, масштабируемое и быстрое), после длительного анализа различных продуктов.
Тормоз: А практическое приложение какое?
IAD,Java Developer: Сфинкс это наколеночное паделие, которое(кроме сливания дельт в индекс) делается за несколько вечеров.
Практическое приложение не буду раскрывать, революционная штука :) И к SEO не имеет ни малейшего отношения, если что.
Тормоз) само по себе математическое решение данной задачи по твоим критериям – чуть ли не премия Клейна и Тьюринга.
Голого алгоритма хватит, чтобы получить мировую славу.
Почему? В чём именно ошибаются выше авторы предложенных направлений решения, на твой взгляд?
Slope One походит на то что тебе надо
Спасибо! И на это посмотрю.
Алгоритмы, предложенные товарищами, не используются наукой для определения ревалентности:)
Если это текст, то ,модификации Байеса+SVM+ебаться с весами коофициентов.
Если это извлечение информации, то где-то так: модификации SVM+TF-IDF+ModSimpl()
и работать с этими связками.
В коммерческих системах юзается SVM+TF-IDF.
смотря по ситуации.
В общем, это отдельная область науки, которая уже лет 30 пытается сделать то, что хочешь ты. Потуги есть, но мощностей нет:) Но вот в коммерческих системах можно встретить очень эффективные связки. Стоит почитать их доклады.
гугл и яндекс пока курят в стороне – они физически не вытянут некоторые алгоритмы(как раз с тысячами признаков)
А где что можно прочитать про эту ревалентность? Google считает, что это ошибочное написание «релевантности», никаких толковых статей не нашёл. Ты точно с термином не ошибся?
Soeti, хотелось бы услышать подробнее про эффективные связки коммерческих систем, которые гугл физически не может вытянуть. У них алгоритмы лучше, или ресурсов больше, или то и другое?
Valenok, кстати, спасибо за письмо, я пока не отвечаю, потому что не проверял сервер. Вместо программирования сейчас, в основном, читаю «Совершенный код», для программирования какое-то сонливое состояние. Ближе к утру или завтра сделаю.
строишь свой индекс, хоть на том же бинарном файле, хеш табличку indexhash => array(ids) и делаешь плейн дб по этому индексу. объяснять не буду, очень долго, но я делал подобную штучку недавно для одного достаточно известного в сео кругах сайта в рунете под ГЕО задачу – поиск информации об IP по большой базе 400к строк с данными, время поиска – 0.0001-0.001, при том, что там были текстовые данные + пересекающиеся диапазоны адресов. это скорость на пхп :)
А как сделать индекс? Ну вот, пример, допустим, объекты из задачи выглядят так:
1 {
огурец:зелёный
помидор:красный
морковь:жёлтая
смородина:чёрная
лук:зелёный
}
2 {
огурец:светло-зелёный
помидор:жёлтый
морковь:вкусная
лук:острый
}
3 {
морковь:жёлтая
}
Какой может быть алгоритм создания хэшей, чтобы быстро отсортировать вторые два объекта по степени похожести с первым? Не забывая про количественные условия задачи. Сортировка, кстати, в этом примере должна быть такой: 3, 2.
P.S. То есть я думаю, что ты не вник в задачу и твой опыт здесь вообще никак не применить. Обрати внимание, что данные объектов совершенно разные, где-то одни ключи, где-то другие. И количество этих ключей у каждого объекта может быть более 1000.
P.P.S. А у другого объекта сотня или меньше.
1. Там опечатка.(реВалентность). Ищи по названиям алгоритмов
2. Коммерческие системы не работают с такими громадными объемами данных. Всё просто)
3. Тормоз, ты в предложенной конструкции путаешь понятия. В данном случае ключ у тебя Морковь, а значение желтый.
Не знаю как в «пехепе», но перл хавает такие конструкции на ура.
Называются хеш массивов. Может быть и хеш хешей массивов.
Если псевдокодом, то:
push($Hesh{‘морковь’}[‘первый элемент массива по ключу’],‘желтый’ )
В итоге, после обработки базы данных в таком формате выходной хеш будет выглядеть:
print @{$Hesh{‘морковь’}}
…
желтый
вкусный
Конструкция может быть усложнена, что в итоге приведет тебя к осознанию необходимости курить графы, конечные автоматы и нейронные сети:)
Ничего я не путаю, я сразу написал ключ:значение, так у меня и есть в примере с морковкой.
А с хешами массивов можешь пояснить, что они нам дают? Не вижу ни малейшего приближения к решению.
Если я правильно понял задачу, то подготовительные действия можно сделать не особо парясь с временем?
1) Представляем связку «ключ-значение» единым словом
2) Создаем вторую таблицу где перечисляем номера строк в которых есть каждое «слово»
«огурец:зелёный» : 1
«помидор:красный» : 1
«морковь:жёлтая» : 1,3
«смородина:чёрная» : 1
«лук:зелёный» : 1
«огурец:светло-зелёный» : 2
«помидор:жёлтый» : 2
«морковь:вкусная» : 2
«лук:острый» : 2
(объем памяти занимаемый таблицей получается точно такой же)
Подготовились.
Получаем запрос.
Распаковываем его на «слова» и по очереди проверяем каждое.
Тут возможны два варианта, но во втором я сам запутался поэтому только один.
Вариант:
Создать массив и потом его отсортировать.
Как это сделать быстрее?
Создать еще один одно размерный массив (массив_А) и использовать его для указателей. То есть получив список записей в которых есть это слово каждой записи присвоить порядковый номер (который хранить в массиве_А), в другом массиве (массив_Б) использовать порядковый номер из массива_А как указатель адреса и просто делать +1. И потом отсортировать.
Вообще то нам не надо сортировать весь миллионный список от 1 до последнего элемента, нам надо отсортировать по совпадениям, а значит позиций может быть столько сколько слов в запросе.
Поэтому надо найти самое большое значение. Вывести строки имеющие такое же, потом вывести строки имеющее на единицу меньше и т.д. Так что сортировка не будет отнимать столько ресурсов сколько обычно.
Дополнения:
1) При выборе слов использовать слова как указатели, вместо того чтобы искать их. Если это технически возможно и оправданно.
2) Если не нужен весь список сразу можно заранее просчитать некоторое количество позиций.
(Типа как первая страница у яндекса. Просто 10 позиций по каждому запросу составить заранее)
Даже если нужен весь список, можно заранее просчитать некоторую часть, (например имеющие более 10 совпавших слов, и потом просто строки исключать не просчитывая, этим мы значительно сокращаем количество действий «+1» описанных ранее. В общем по правилу Парето просчитав 20% значений мы выполним 80% работы )
Что думаешь? Или я где то не так тебя понял?
Интересная мысль, надо будет её обдумать тщательнее. Спасибо. Хотя, скорей всего всё равно очень затратно получится.
Примерное решение задачи:
На вход подаются данные, разделенные tab
$ cat data.txt
1 огурец:зелёный
1 помидор:красный
1 морковь:жёлтая
1 смородина:чёрная
1 лук:зелёный
2 огурец:светло-зелёный
2 помидор:жёлтый
2 морковь:вкусная
2 лук:острый
3 морковь:жёлтая
строим индекс для «ключ:значение»
$ cut -f2 data.txt| sort -u | awk -vOFS=»\t» ‘{print NR,$0}’ >ids.txt
создаем базу в которой лежат объекты и их атрибуты (id шники «ключ:значене»)
$ awk ‘BEGIN{while (getline <«ids.txt»){H[$2]=$1;++maxid}for(i=1;i<=maxid;++i)res[i]=0}pn&&pn!=$1{printf(»%s», pn); for(i=1;i<=maxid;++i)printf(»\t%s»,res[i]);printf(»\n»);for(i=1;i<=maxid;++i)res[i]=0}{pn=$1;res[H[$2]]=1;}END{if(pn){printf(»%s», pn); for(i=1;i<=maxid;++i)printf(»\t%s»,res[i]);printf(»\n»)}}’ data.txt >db.txt
поиск и результат из базы по объекту 1:
$ awk -vK=1 ‘BEGIN{while(getline <«db.txt»)if($1==K)for(i=2;i<=NF;++i)if($i)mask[i-1]=1}{r=0;for(i=2;i<=NF;++i)if($i&&mask[i-1])++r;print $1,r}’ db.txt | sort -k2,2rn
1 5
3 1
2 0
здесь объект + количество совпадений «ключ:значение»
это решение на коленке. поиск ключа лучше сделать бинарным поиском, базу написать на C++, и сравнивать маски побитово.
8000 возможных комбинаций «ключ:значение» можно засунуть в 1кб на 1 объект, и это без сжатия!
Ускорять еще есть куда… :)
Я нифига не понял. Ты мог бы объяснить суть своего решения просто словами?
Суть решения проста:
Нужно подготовить базу в которой будут ключ: объект, значения: idшники признаков.
Для того что бы отсортировать объекты по похожести на искомый объект нужно ввести меру сходства. В твоем случае это количество совпадающих признаков с признаками исходного объекта.
Алгоритм ранжирования:
1) Ищем искомый объект в базе.
база отсортирована по ключу, лучше всего искать бинарным поиском.
2) Потом пробегаем по всей базе (самая ресурсоемкая операция) и считаем для каждого ключа количество совпадающих id признаков с исходным объектом.
3) заносим в массив ключ – количество совпадений.
4) сортируем массив по количеству совпадений.
5) берем N первых элементов.
Как это можно ускорить:
Пункты 4-5 лучше объединить используя partial_sort.
В пункте 3 в массив заносить не все ключи. а только если количество совпадений больше какого то числа.
И самое главное это уменьшить размер базы. Для этого нужно закодировать значения idшников.
Значения можно закодировать по разному:
a) битовая маска 1 бит на 1id.
b) записать числа с инкрементальным сжатием.
c) комбинация из a и b. часть самых частотных признаков закодировать битами остальные числами.
Писать лучше на C++, в качестве базы я бы выбрал berkeleydb.
Ясно, спасибо.
Вот этот второй пункт и убивает всё, я так думаю. Сомневаюсь, что эта штука хотя бы за секунду отработает при миллионной базе с тысячами ключей для каждого объекта.
Но тестировать, конечно, но не очень верю в такой алгоритм.
Нужно тестировать…
Можно прицепить сверху всего этого кеш, и после «прогрева» будет моментальная скорость…
Именно поэтому я предложил юзать вторую базу, при ней поиск будет осуществляться не среди миллионов строк, а просто среди большого количества слов.
И то если язык программирования технически не позволяет использовать значения как что то типа указателей, например определить переменную «морковь:жёлтая» и когда поступит такое слово вместо того чтобы его искать достаточно будет обратиться к соответствующей переменной.
Так же для ускорения можно проявить фантазию, и еще больше усложнить структуру проведя предварительные вычисления. Например составить еще одну дополнительную базу которая будет содержать только ключи (огурец, морковь, помидор) и указывать с какой строки эти ключи начинаются в основной базе.
Тоесть если общая база будет содержать миллион слов, и чтобы найти нужное слово надо будет проверить в среднем пол миллиона записей, то с вспомогательной базой, например она будет 50000 строк, мы сначала находим значение в ней а потом ищем с нужного места в основной.
Получается, что проверить надо будет в 20 раза меньший объем.
Можно пойти еще дальше и ввести еще пару таких таблиц. Например для первого символа.
Соответственно главная база слов должна быть предварительно отсортирована, но это итак понятно, иначе метод не работал бы.
Понял идею?
И вот на подобных мелочах можно выигрывать, просто не надо искать алгоритм в пять строк. Если критична скорость, значит нужно все что возможно рассчитать заранее.
Nugos, моментальная скорость для такой задачи наверняка вообще не достижима :)
Elsper, подобные штуки увеличивают скорость на величины около порядка, не больше, увы. Я тоже продумывал варианты предварительной выборки с дополнительными базами.
Тут мне подсказали ещё решение с двухмерной матрицей, над ним теперь размышляю.
Написал программу на C++.
Вариант a. как предлагал я.
Вариант b. строим дополнительный инвертированный индекс, как предлагает elsper:
ключ: id-признака
значения: id-объектов с этим признаком.
Тестировал на 100к и 1000к объектах с ~10-6000 признаками.
Результаты примерно следующие:
время одного запроса 10 результатов наиболее похожих на оригинал
набор 100К:
a) 2.4-3.1c
b) 0.3-1.4c
набор 1М:
a) 26-32с
b) 10-25с
объем базы:
для 100к: 110М
для 1М: 1.1G
Инвертированный индекс занимает примерно столько же
инвертированный индекс
Спасибо! Интересные результаты.
nugops, а можешь прикрутить еще ускорение поиска? Ну то что я выше описал.
Я правда не знаю как там у тебя ищется нужная строка но по идее с нуля и пока не найдется.
Так вот можно искать не с нуля, а с конкретной позиции в которой идут строки, которые например имеют одну первую букву, и вычислить с какой строки начинается каждый из символов заранее.
Как сказал НИКИТА, об этом рассказывается в универе – у меня было вроде на 3-м курсе в лекциях «базы данных».
все, что я оттуда помню: «бла бла бла… нормирование ключей, бла бла бла… вот такие вот как вы и делают БД для сотовых операторов…бла бла.. а там надо, чтобы баланс изменялся в реальном времени, а если абонентов миллион?…бла бла бла…нормирование ключей»
потом воспоминания с работы: «щас для бизнеса дешевле купить дополнительную планку памяти или другого оборудования, нежели потратить деньги и время на программиста, который бы все это добро оптимизировал до максимальной скорости»
«Ну а тип БД — вряд ли SQL» – насколько помнится SQL это всего-лишь навсего язык запроса к БД, а не тип БД.
ну и собственно решение – кластеры, кластеры… много кластеров – одни делают выборку в определенном диапазоне БД – другие синхронизируют результат.
такие велосипеды здесь :))
есть жутко удобный и гибкий sphinx тестировался на 200 лямах записей в бд, всё летает.
я правда не уверен что api его в том виде в котором оно есть подойдет под задачу, но с напильником все возможно.
Не глядя уверен на 90%, что API «Сфинкса» ни в каком виде не подойдёт для решения задачи. И что значит «тестировался на 200 лямах записей в бд»? Выборку по несложным запросам любая БД сделает.
тормоз, сфинкс – полнотекстовый поисковый двиг, на 200 лямах строк, тотже мускуль ляжет даже не пытаясь подняться) сфинкс рулит, к тому же у него еще и стимер есть
ОК, ну а как ты данную задачу решал бы с помощью «Сфинкса»? :) Привет, кстати! Ты где пропадал? У тебя даже домен недоступен был.
> Привет, кстати! Ты где пропадал? У тебя даже домен недоступен был.
заработался :)
а домен один хуй не денег, ничего не приносит – обламывало после переезда на другой серв настроить все, вот с полнедели назад настроил)
ОК, ну а как ты данную задачу решал бы с помощью «Сфинкса»? :)
я бы писал свою бинарную базу, и в ней сортировал, я уже писал вроде где то в начале этого треда :)
я недавно подобным алгоритмом делал geoip resolver для tak.ru, скорость поиска ПЕРЕСЕКАЮЩИХСЯ диапазонов адресов ~ 0.0001 секунды. если захешить данные в память и обрабатывать сотни тысяч адресов, скорость можно поднять в десяток раз смело, только им этого не надо, у них до этого алгоритм с помощью базы работающий выдавал результаты за 0.2-2 секунды) они и там пищали от счастья)
зы: в бинарной базе порядка 700 000 пересекающихся диапазонов с данными о городе, стране, границах диапазонов и какой то другой еще метаинформацией, база занимала по моему порядка 30 мегабайт, если не ошибаюсь.
Точно, извини, ты ж тут отвечал одним из первых. Однако я очень сомневаюсь в применимости твоего решения к данной задаче, мне кажется ты просто не вник.
Оффтоп: а куда переехал, у кого хостишься? Я тоже скоро переезжаю.
переехал в hetzner.de, все равно все «крутые руских хостеры» – реселлеры немцев, избавился от прокладки.
все задачи на первый взгляд – сложные. на второй становится яснее, что сложно – побороть страх и только. думаю что задачу можно решить бинарно, притом еще и получив великолепную скорость. и да, не за 2 часа, дня 2-3 поковыряться придется чтобы составить хороший индекс. а то, что полей у объекта может быть неизвестное количество – не страшно нисколько, всего то соотношение один ко многим.
итак, смотри. при перестройке базы – перебираем все ключи у полей, находим всевозможные ключи, составляем массивы итемов, которые обладают данными ключами, в зависимости от набора значений – если большой % повторов вариантов ответа, то можно индексную базу ответов составить, чтобы основной индексы был меньше(храним указатели на значения, а не сами значения).
получили группы – {index: [… items ..], index2: [], …}
сохраняем это в удобном виде, записывая «где искать начало индекса», возможно для скорости – записываем «где искать начало индекса ‘index-item_id’», получаем большой бинарный файл, хорошо если у нас будет точное месторасположение fieldid-itemid, то тогда, можно будет найти все объекты, которые содержат необходимое поле, проверить значение этого поля.
ну и пишем классец для работы с этой всей кучей. уверен что можно добиться великолепной скорости на базе практически любого размера. главное – придумать как максимально удобно расопложить индексы и значения
Буду думать, спасибо.
Тормоз, загони в базу 100 лям записей, а потом попробуй поискать посортировать. В лучшем случае займет пару секунд, в худшем мускул безнадежно повиснет. А если это дело будет под трафом, то разговор ниочем, наепнется всё :)
Сфинкс дает возможность выборки и сортировки за 0.0xx времени. А вот «как» – это уже конкретно под задачу курить доки, но гибкость у него очень даже.
Спасибо, почитаю про «Сфинкс» тоже.
Тормоз ты решил эту задачу?
У меня такаяже хрень теперь и нужно найти наиболее похожие
Что за хрень? Расскажи для чего.
архиватор?