Как стать автором
Обновить

Комментарии 62

видимо вы хотели подчеркнуть разницу между Judy на C и Judy на PHP… :)
Очень интересно. Маленькое замечание — в графиках съелась легенда.
Да, длинные строки там обрезались. Судя по всему, это фича Google Charts.
Для этого есть ссылки на большие версии графиков.
Добавьте, пожалуйста, в тест SplFixedArray. Или уже поздно?
В SplFixedArray есть часть «fixed», которая делает их принципиально не подходящими под задачу «хранение больших массивов при минимуме памяти».
Просто прогнать бенчмарки можно, но как вариант решения задачи они даже не рассматривались.
Интересная у вас компания. Мне нравится то, что вы делаете.
Спасибо! Нам тоже наша компания очень нравится :) И еще у нас полно вакансий.
Буквально пару дней назад в php-judy были залиты улучшения по производительности (версия 0.1.6)
Это наши патчи и мёржили.
Поэтому и статью придержали немного, т.к. ждали мёржа и релиза новой версии.
А, вот оно, что. Я на ник сразу внимание не обратил :-)
Я просто в твиттере мейнтейнера прочитал на днях «Got a bunch of great pull request from @_tony2001_». И тут вижу статью на Хабре. Думал совпадение.
Очень сильно Вы верите в совпадения, мой друг. :)
лежит убитый анатолий три дырки в теле у него а рядом николай с трезубцем но это совпадение.
Интересно узнать о задачах, под которые нужны массивы в миллионы элементов. Желательно с подробностями.
select * from badoo.users
$users = mysql_query('select * from badoo.users');
for ($user in $users) {
    if ($user['login'] == $login && $user['password'] == md5($password)) {
      //...
    }
}


так?
как вы смогли вытащить у нас часть кода? =\
Да еще и хеш без соли! Эх, баду-баду…
Не мог оставить без внимания написанный код. Даже если вы написали его для демонстрации какого-то общего принципа, то делайте уж тогда это качественно.
1. Пора бы уже забыть про все функции начинающиеся на mysql_* (http://www.php.net/manual/ru/intro.mysql.php)
2. Даже в официальной документации php написано, что использовать md5 крайне не желательно, особенно для паролей! (http://www.php.net/manual/ru/faq.passwords.php#faq.passwords.fasthash)
Не забывайте, что ваш код читают сотни и потом некоторые начинают делать также.
Заранее извиняюсь за занудство.
Ну, если что, то и цикл не for-in, а foreach-as.
Да и не foreach-as, а что-то там про while(mysql_fetch() !== null).
Ну как вспомнил, так вспомнил. Это всё дурное влияние питона :)

А если кто-то прочитает мой код и не поймёт шутки, и будет делать так же — ну, ссзб :)

И вообще, это был намёк, что выборка юзеров не является задачей. Это способ решения какой-то задачи, о которой изначально и было спрошено. Но намёк был слишком тонким, никто не понял. Со мной такое бывает.
почти все поняли, я думаю :)
Ребят, за что минусуете? Если я что не так написал, аргументируйте и я заберу свои слова
Интересно получается :)
То есть можно в примерах пользоваться mysql_ и md5, ведь всё равно все знают, что эти функции нельзя использовать.
Хочу заметить, что я указал не на синтаксические ошибки, которые выдаст интерпретатор при первом же запуске, а на фундаментальные, которые неопытный человек не заметит.
Нет, не поэтому.

Оригинальный код nolar намеренно был глуп и с ошибками, чтобы подчеркнуть шутку symbix. Поэтому вы, де факто, пояснили шутку, которую, я подозреваю, большинство поняли сами.
Да, вполне возможно
В смысле, полный перебор логинов по базе не является ошибкой? Он не был упомянут.
> $users = mysql_query('select * from badoo.users');
это будут данные только с одного шарда, который содержит около 100К записей.
так-что в этом случае можно обойтись и простым массивом.
Но только это будет не просто массив на 100k записей, а массив из массивов по count(columns) — так что уже стоит попробовать judy. Но это всё так, just for fun, мы не такие задачи с помощью judy решаем.
Спасибо, настроение на остаток дня подняли =)
Анализ статистических данных, пересчет/определение рейтингов пользователей например.
В какой-то момент для одной из бизнес задач нам потребовалась графовая база данных. Данные в неё нужно было как-то загружать, а при нашем масштабе данных было иногда мало, а иногда очень много, порядка озвученных 100k-1M. В основном это нужно было для того, чтобы не загружать в C-сервис уже имеющиеся в нём данные, потому каждая часть графа собиралась предварительно в PHP и в ней исключались дублирующиеся связи.
у моего друга, в проекте обсчета биллинга более 10 млн элементов — вылетело все по памятти.
judy массивы здесь могли бы существенно помочь.
Честно говоря не знаю, как у нас биллинг считается, но в BI используют специализированные базы. Но после одного успешного применения judy уже разные команды начали думать как им это расширение может помочь.
там где есть нагрузка — идет борьба за ресурсы
там где есть объемы — идет борьба за ресурсы.
все что сберегает ресурсы — может нам помочь :)

так, что где есть нагрузка и объемы всегда найдет применение judy массивам
И все равно мне кажется, что такие вычисления стоит перенести на более производительные языки. Например D(имеет очень хороший фреймворк для веба)
По-настоящему тяжелые вещи мы выносим в демоны на C/C++.
Здесь как раз речь не о вычислениях, а о больших массивах данных, причем эти массивы грузятся в результате в один из демонов.
А вы эти сишные демоны кластеризуете? Если да, то интересно как вы обеспечиваете консистентность данных в разных инстансах демона или как живете с неконсистентностью.
Некоторые демоны шардируются по user_id, некоторые шардируются по странам. Многие из них реплицируют данные на другую площадку (у нас на данный момент по 1 площадке на каждом полушарии).

В случае репликации консистентность опять же обеспечивается по-разному. В зависимости от типа хранимых данных. Например по времени. Типа «реплика, у тебя какое последнее время обновления? ну на тебе то что новее, теперь мы одинаковые». Это не 100% консистентность, но для наших задач ее хватает.
Чуть выше Sannis ответил.
Judy-массивы вряд ли смогут заменить штатные массивы в PHP

Я бы заметил, что Judy массивы не сереализуются/десереализуются штатными методами что еще больше сужает сферу их применения из PHP.
Будет надо — сделаем патч. Но пока я себе слабо представляю для чего нужна сериализация массива на миллионы элементов.
в memcached положить! все, ухожу, ухожу
Лучше в redis.
положит в своп сервер твой редис…
а что — редис у тебя не ложил сервер?
У меня, нет.
Ну на правах примера притянутого за уши — хранение редко изменяемых данных, в духе словарей, в той же shared memory с целью использования несколькими процессами. Хотя в сравнении с redis + igbinary выигрыш наверное будет не очень большой.
В таком случае, вероятно, имеет смысл завести узкоспециализированного демона, который будет хранить именно Judy-массивы, а не инты в виде строк. Конечно, для общения с демоном так или иначе понадобится какой-то механизм сериализации для передачи данных по сети. У нас в качестве стандарта принято использовать Google Protocol Buffers. Но это не сериализация объекта, это протокол общения с демоном.
Патентованность все-таки сильно смущает. Какая разница, реализация LGPL или нет.
В айпаде патентованный прямоугольник не смущает? :)
А LGPL или нет — разница большая. Авторы, конечно, могут сменить лицензию на свой код, но не задним числом. А значит, этот код всегда будет публично доступен под LGPL.
А зачем использовать-поддерживать патентованный алгоритм (и тратить на него силы — слать патчи, например), если если много непатентованных, которые ту же задачу решат?

Почему я думаю, что есть много других вариантов, которые бы работали так же эффективно (или еще эффективнее):

вот есть какие-то массивы цифр, которые сначала хранятся в хэш-таблице (что, понятное дело, плохо). Потом вы их начинаете хранить в Judy Array и они занимают меньше памяти. Если я правильно понял графики, то было 100М цифр, которые при 4байтных данных заняли бы в простом массиве 400М. Если данные случайные, то меньше 400М они занимать и не могут — но они занимают в двух из трех Judy-массивах меньше. Значит, у данных есть какая-то структура (ну, например, большинство записей — нули). А раз у данных есть структура, то есть и более эффективные способы их хранения, чем просто массив (ну, например, разряженные матрицы).

Вы про структуру ничего не рассказываете, и ни с чем другим, кроме array, не сравниваете (который, очевидно, ужасен для хранения цифр), поэтому красивые бенчмарки и графики довольно бессмысленными кажутся. Из них можно сделать вывод, что иногда Judy Array будут работать лучше array, вот и все — а это и так вполне очевидно, иначе зачем бы биндинги делали к ним, и т.д.
Во-первых, я не совсем понимаю ваше отношение к патентованным алгоритмам.
То есть, да, софтварные патенты — зло и всё такое, я совершенно согласен. Но они сть и это факт. В данном случае человек запатентовал алгоритм и намеренно выложил его имплементацию в общий доступ, т.е. фактически защитил нас от патентных троллей. Не вижу в этом ничего плохого.

Во-вторых, расскажите плз про более эффективные алгоритмы, я совсем не против еще более улучшить и демона, и скрипты.
Задача такая: хранить много не очень больших (макс. десятки тысяч элементов) списков интов, по которым надо быстро проходить и по которым должны быть быстрые лукапы. Ну, и памяти они должны занимать минимум, конечно.
На данный момент это всё реализовано на Judy1.

В-третьих, да, вещи довольно очевидные, но я и не претендую на открытие Америки. С другой стороны, я уверен, что большинство про Judy не слышали и с удовольствием посмотрят на красивые диаграммки и узнают про новый инструмент.
Отношение такое: человек, запатентовавший алгоритм, может потенциально получить от этого выгоду, если алгоритм кто-то использует. Чтоб не поощрять патентование алгоритмов, лучше не использовать патентованные алгоритмы (и не пропогандировать их использование) — в этом случае у патентообладателя не будет возможности получить выгоду, и патентование оттого станет бессмысленным.

Про задачу — все еще не понял :) Есть N множеств чисел, в каждом множестве не более 100тыс элементов, и нужно понять, входит ли данное число в n-ное множество? Judy1 для этого хорош, это да. Можно еще какой-нибудь сжатый/разряженный bitarray найти, или двоичное дерево поиска использовать; если ошибки допустимы — можно использовать фильтр Блума (если недопустимы — то тоже можно, например, как «первый уровень», отсекать элементы, которых заведомо нет в множестве). Или задачу как-то переформулировать. Готового решения на php я в любом случае придумать не смогу, т.к. слабо в экосистеме разбираюсь.
>Есть N множеств чисел, в каждом множестве не более 100тыс элементов,
>и нужно понять, входит ли данное число в n-ное множество?

Да, но еще надо проходить по этому множеству от начала до конца и чтобы это множество занимало минимум памяти.
Решение меня интересует не на PHP, конечно, а на С — мы же ищем более эффективный алгоритм, чем Judy.
Потенциально может.

Но есть и другой вариант: запатентовать алгоритм для того, чтобы его не запатентовал кто-то другой, например, патентный тролль.

В комбинации с выкладыванием реализации в общий доступ вариант 2 более вероятен.
А где примеры использования таких массивов?
Все аналогично штатным массивам: $judy[] = $value; $value = $judy[0];
Только здесь жестко фиксирован тип индексов и значения элементов ограничены соотв-м типом.
Я всё понимаю. Но почему-то не увидел в топике самого простого: создания массива.
Я всё понимаю(почти) и всё уже нашёл. Просто, я не понимаю почему статья о Judy массивах не содержит примера кода использования Judy массива. При этом содержит пример использования нативного массива.
Спасибо Тони 2001 за интересный рассказ о Judy массивах, а так же за его
интересное и полезное расширение, которое хорошо подойдет для расчетных задач (статистика и биллинг).

Непременно буду иметь его ввиду. Сам хотел сделать нечто подобное ;), даже это обсуждалось на Хабре более года назад в одной из тем про структуры данных, но просто не было подходящего проекта под эту задачу.

Лично я собирался использовать judy массивы в своих сишных проектах, по этому немного в теме,
но в конечном итоге стал использовать dict (libdict) и tokyocabinet в силу их более понятного АПИ, а так же решаемому объему задач (мне более 100 M элементов не надо).

Мы, все расчетные задачи выносим в бэдграунд, которые реализованы как сишные демоны. Да и пользователей у нас 25М, а не 100+М как в Баду…

Зарегистрируйтесь на Хабре , чтобы оставить комментарий