Comments 62
Очень интересно. Маленькое замечание — в графиках съелась легенда.
+1
Добавьте, пожалуйста, в тест SplFixedArray. Или уже поздно?
+2
Интересная у вас компания. Мне нравится то, что вы делаете.
+6
Буквально пару дней назад в php-judy были залиты улучшения по производительности (версия 0.1.6)
+3
Это наши патчи и мёржили.
Поэтому и статью придержали немного, т.к. ждали мёржа и релиза новой версии.
Поэтому и статью придержали немного, т.к. ждали мёржа и релиза новой версии.
+9
А, вот оно, что. Я на ник сразу внимание не обратил :-)
Я просто в твиттере мейнтейнера прочитал на днях «Got a bunch of great pull request from @_tony2001_». И тут вижу статью на Хабре. Думал совпадение.
Я просто в твиттере мейнтейнера прочитал на днях «Got a bunch of great pull request from @_tony2001_». И тут вижу статью на Хабре. Думал совпадение.
+2
Интересно узнать о задачах, под которые нужны массивы в миллионы элементов. Желательно с подробностями.
+8
select * from badoo.users
+7
$users = mysql_query('select * from badoo.users');
for ($user in $users) {
if ($user['login'] == $login && $user['password'] == md5($password)) {
//...
}
}
так?
+4
как вы смогли вытащить у нас часть кода? =\
+11
Не мог оставить без внимания написанный код. Даже если вы написали его для демонстрации какого-то общего принципа, то делайте уж тогда это качественно.
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)
Не забывайте, что ваш код читают сотни и потом некоторые начинают делать также.
Заранее извиняюсь за занудство.
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)
Не забывайте, что ваш код читают сотни и потом некоторые начинают делать также.
Заранее извиняюсь за занудство.
-12
Ну, если что, то и цикл не for-in, а foreach-as.
Да и не foreach-as, а что-то там про while(mysql_fetch() !== null).
Ну как вспомнил, так вспомнил. Это всё дурное влияние питона :)
А если кто-то прочитает мой код и не поймёт шутки, и будет делать так же — ну, ссзб :)
И вообще, это был намёк, что выборка юзеров не является задачей. Это способ решения какой-то задачи, о которой изначально и было спрошено. Но намёк был слишком тонким, никто не понял. Со мной такое бывает.
Да и не foreach-as, а что-то там про while(mysql_fetch() !== null).
Ну как вспомнил, так вспомнил. Это всё дурное влияние питона :)
А если кто-то прочитает мой код и не поймёт шутки, и будет делать так же — ну, ссзб :)
И вообще, это был намёк, что выборка юзеров не является задачей. Это способ решения какой-то задачи, о которой изначально и было спрошено. Но намёк был слишком тонким, никто не понял. Со мной такое бывает.
+3
Ребят, за что минусуете? Если я что не так написал, аргументируйте и я заберу свои слова
-2
Я подозреваю, за капитанство.
+2
Интересно получается :)
То есть можно в примерах пользоваться mysql_ и md5, ведь всё равно все знают, что эти функции нельзя использовать.
Хочу заметить, что я указал не на синтаксические ошибки, которые выдаст интерпретатор при первом же запуске, а на фундаментальные, которые неопытный человек не заметит.
То есть можно в примерах пользоваться mysql_ и md5, ведь всё равно все знают, что эти функции нельзя использовать.
Хочу заметить, что я указал не на синтаксические ошибки, которые выдаст интерпретатор при первом же запуске, а на фундаментальные, которые неопытный человек не заметит.
0
> $users = mysql_query('select * from badoo.users');
это будут данные только с одного шарда, который содержит около 100К записей.
так-что в этом случае можно обойтись и простым массивом.
это будут данные только с одного шарда, который содержит около 100К записей.
так-что в этом случае можно обойтись и простым массивом.
0
Спасибо, настроение на остаток дня подняли =)
0
Анализ статистических данных, пересчет/определение рейтингов пользователей например.
+3
В какой-то момент для одной из бизнес задач нам потребовалась графовая база данных. Данные в неё нужно было как-то загружать, а при нашем масштабе данных было иногда мало, а иногда очень много, порядка озвученных 100k-1M. В основном это нужно было для того, чтобы не загружать в C-сервис уже имеющиеся в нём данные, потому каждая часть графа собиралась предварительно в PHP и в ней исключались дублирующиеся связи.
0
у моего друга, в проекте обсчета биллинга более 10 млн элементов — вылетело все по памятти.
judy массивы здесь могли бы существенно помочь.
judy массивы здесь могли бы существенно помочь.
0
Честно говоря не знаю, как у нас биллинг считается, но в BI используют специализированные базы. Но после одного успешного применения judy уже разные команды начали думать как им это расширение может помочь.
0
И все равно мне кажется, что такие вычисления стоит перенести на более производительные языки. Например D(имеет очень хороший фреймворк для веба)
0
По-настоящему тяжелые вещи мы выносим в демоны на C/C++.
Здесь как раз речь не о вычислениях, а о больших массивах данных, причем эти массивы грузятся в результате в один из демонов.
Здесь как раз речь не о вычислениях, а о больших массивах данных, причем эти массивы грузятся в результате в один из демонов.
+2
UFO just landed and posted this here
Некоторые демоны шардируются по user_id, некоторые шардируются по странам. Многие из них реплицируют данные на другую площадку (у нас на данный момент по 1 площадке на каждом полушарии).
В случае репликации консистентность опять же обеспечивается по-разному. В зависимости от типа хранимых данных. Например по времени. Типа «реплика, у тебя какое последнее время обновления? ну на тебе то что новее, теперь мы одинаковые». Это не 100% консистентность, но для наших задач ее хватает.
В случае репликации консистентность опять же обеспечивается по-разному. В зависимости от типа хранимых данных. Например по времени. Типа «реплика, у тебя какое последнее время обновления? ну на тебе то что новее, теперь мы одинаковые». Это не 100% консистентность, но для наших задач ее хватает.
+6
Чуть выше Sannis ответил.
+1
Judy-массивы вряд ли смогут заменить штатные массивы в PHP
Я бы заметил, что Judy массивы не сереализуются/десереализуются штатными методами что еще больше сужает сферу их применения из PHP.
+1
Будет надо — сделаем патч. Но пока я себе слабо представляю для чего нужна сериализация массива на миллионы элементов.
+3
в memcached положить! все, ухожу, ухожу
+7
Ну на правах примера притянутого за уши — хранение редко изменяемых данных, в духе словарей, в той же shared memory с целью использования несколькими процессами. Хотя в сравнении с redis + igbinary выигрыш наверное будет не очень большой.
0
В таком случае, вероятно, имеет смысл завести узкоспециализированного демона, который будет хранить именно Judy-массивы, а не инты в виде строк. Конечно, для общения с демоном так или иначе понадобится какой-то механизм сериализации для передачи данных по сети. У нас в качестве стандарта принято использовать Google Protocol Buffers. Но это не сериализация объекта, это протокол общения с демоном.
+2
Патентованность все-таки сильно смущает. Какая разница, реализация LGPL или нет.
+1
В айпаде патентованный прямоугольник не смущает? :)
А LGPL или нет — разница большая. Авторы, конечно, могут сменить лицензию на свой код, но не задним числом. А значит, этот код всегда будет публично доступен под LGPL.
А LGPL или нет — разница большая. Авторы, конечно, могут сменить лицензию на свой код, но не задним числом. А значит, этот код всегда будет публично доступен под LGPL.
+1
А зачем использовать-поддерживать патентованный алгоритм (и тратить на него силы — слать патчи, например), если если много непатентованных, которые ту же задачу решат?
Почему я думаю, что есть много других вариантов, которые бы работали так же эффективно (или еще эффективнее):
вот есть какие-то массивы цифр, которые сначала хранятся в хэш-таблице (что, понятное дело, плохо). Потом вы их начинаете хранить в Judy Array и они занимают меньше памяти. Если я правильно понял графики, то было 100М цифр, которые при 4байтных данных заняли бы в простом массиве 400М. Если данные случайные, то меньше 400М они занимать и не могут — но они занимают в двух из трех Judy-массивах меньше. Значит, у данных есть какая-то структура (ну, например, большинство записей — нули). А раз у данных есть структура, то есть и более эффективные способы их хранения, чем просто массив (ну, например, разряженные матрицы).
Вы про структуру ничего не рассказываете, и ни с чем другим, кроме array, не сравниваете (который, очевидно, ужасен для хранения цифр), поэтому красивые бенчмарки и графики довольно бессмысленными кажутся. Из них можно сделать вывод, что иногда Judy Array будут работать лучше array, вот и все — а это и так вполне очевидно, иначе зачем бы биндинги делали к ним, и т.д.
Почему я думаю, что есть много других вариантов, которые бы работали так же эффективно (или еще эффективнее):
вот есть какие-то массивы цифр, которые сначала хранятся в хэш-таблице (что, понятное дело, плохо). Потом вы их начинаете хранить в Judy Array и они занимают меньше памяти. Если я правильно понял графики, то было 100М цифр, которые при 4байтных данных заняли бы в простом массиве 400М. Если данные случайные, то меньше 400М они занимать и не могут — но они занимают в двух из трех Judy-массивах меньше. Значит, у данных есть какая-то структура (ну, например, большинство записей — нули). А раз у данных есть структура, то есть и более эффективные способы их хранения, чем просто массив (ну, например, разряженные матрицы).
Вы про структуру ничего не рассказываете, и ни с чем другим, кроме array, не сравниваете (который, очевидно, ужасен для хранения цифр), поэтому красивые бенчмарки и графики довольно бессмысленными кажутся. Из них можно сделать вывод, что иногда Judy Array будут работать лучше array, вот и все — а это и так вполне очевидно, иначе зачем бы биндинги делали к ним, и т.д.
0
Во-первых, я не совсем понимаю ваше отношение к патентованным алгоритмам.
То есть, да, софтварные патенты — зло и всё такое, я совершенно согласен. Но они сть и это факт. В данном случае человек запатентовал алгоритм и намеренно выложил его имплементацию в общий доступ, т.е. фактически защитил нас от патентных троллей. Не вижу в этом ничего плохого.
Во-вторых, расскажите плз про более эффективные алгоритмы, я совсем не против еще более улучшить и демона, и скрипты.
Задача такая: хранить много не очень больших (макс. десятки тысяч элементов) списков интов, по которым надо быстро проходить и по которым должны быть быстрые лукапы. Ну, и памяти они должны занимать минимум, конечно.
На данный момент это всё реализовано на Judy1.
В-третьих, да, вещи довольно очевидные, но я и не претендую на открытие Америки. С другой стороны, я уверен, что большинство про Judy не слышали и с удовольствием посмотрят на красивые диаграммки и узнают про новый инструмент.
То есть, да, софтварные патенты — зло и всё такое, я совершенно согласен. Но они сть и это факт. В данном случае человек запатентовал алгоритм и намеренно выложил его имплементацию в общий доступ, т.е. фактически защитил нас от патентных троллей. Не вижу в этом ничего плохого.
Во-вторых, расскажите плз про более эффективные алгоритмы, я совсем не против еще более улучшить и демона, и скрипты.
Задача такая: хранить много не очень больших (макс. десятки тысяч элементов) списков интов, по которым надо быстро проходить и по которым должны быть быстрые лукапы. Ну, и памяти они должны занимать минимум, конечно.
На данный момент это всё реализовано на Judy1.
В-третьих, да, вещи довольно очевидные, но я и не претендую на открытие Америки. С другой стороны, я уверен, что большинство про Judy не слышали и с удовольствием посмотрят на красивые диаграммки и узнают про новый инструмент.
+3
Отношение такое: человек, запатентовавший алгоритм, может потенциально получить от этого выгоду, если алгоритм кто-то использует. Чтоб не поощрять патентование алгоритмов, лучше не использовать патентованные алгоритмы (и не пропогандировать их использование) — в этом случае у патентообладателя не будет возможности получить выгоду, и патентование оттого станет бессмысленным.
Про задачу — все еще не понял :) Есть N множеств чисел, в каждом множестве не более 100тыс элементов, и нужно понять, входит ли данное число в n-ное множество? Judy1 для этого хорош, это да. Можно еще какой-нибудь сжатый/разряженный bitarray найти, или двоичное дерево поиска использовать; если ошибки допустимы — можно использовать фильтр Блума (если недопустимы — то тоже можно, например, как «первый уровень», отсекать элементы, которых заведомо нет в множестве). Или задачу как-то переформулировать. Готового решения на php я в любом случае придумать не смогу, т.к. слабо в экосистеме разбираюсь.
Про задачу — все еще не понял :) Есть N множеств чисел, в каждом множестве не более 100тыс элементов, и нужно понять, входит ли данное число в n-ное множество? Judy1 для этого хорош, это да. Можно еще какой-нибудь сжатый/разряженный bitarray найти, или двоичное дерево поиска использовать; если ошибки допустимы — можно использовать фильтр Блума (если недопустимы — то тоже можно, например, как «первый уровень», отсекать элементы, которых заведомо нет в множестве). Или задачу как-то переформулировать. Готового решения на php я в любом случае придумать не смогу, т.к. слабо в экосистеме разбираюсь.
0
>Есть N множеств чисел, в каждом множестве не более 100тыс элементов,
>и нужно понять, входит ли данное число в n-ное множество?
Да, но еще надо проходить по этому множеству от начала до конца и чтобы это множество занимало минимум памяти.
Решение меня интересует не на PHP, конечно, а на С — мы же ищем более эффективный алгоритм, чем Judy.
>и нужно понять, входит ли данное число в n-ное множество?
Да, но еще надо проходить по этому множеству от начала до конца и чтобы это множество занимало минимум памяти.
Решение меня интересует не на PHP, конечно, а на С — мы же ищем более эффективный алгоритм, чем Judy.
+1
Потенциально может.
Но есть и другой вариант: запатентовать алгоритм для того, чтобы его не запатентовал кто-то другой, например, патентный тролль.
В комбинации с выкладыванием реализации в общий доступ вариант 2 более вероятен.
Но есть и другой вариант: запатентовать алгоритм для того, чтобы его не запатентовал кто-то другой, например, патентный тролль.
В комбинации с выкладыванием реализации в общий доступ вариант 2 более вероятен.
+2
А где примеры использования таких массивов?
+1
Все аналогично штатным массивам: $judy[] = $value; $value = $judy[0];
Только здесь жестко фиксирован тип индексов и значения элементов ограничены соотв-м типом.
Только здесь жестко фиксирован тип индексов и значения элементов ограничены соотв-м типом.
+1
Я всё понимаю. Но почему-то не увидел в топике самого простого: создания массива.
0
Так вот же: www.php.net/manual/en/class.judy.php
0
Спасибо Тони 2001 за интересный рассказ о Judy массивах, а так же за его
интересное и полезное расширение, которое хорошо подойдет для расчетных задач (статистика и биллинг).
Непременно буду иметь его ввиду. Сам хотел сделать нечто подобное ;), даже это обсуждалось на Хабре более года назад в одной из тем про структуры данных, но просто не было подходящего проекта под эту задачу.
Лично я собирался использовать judy массивы в своих сишных проектах, по этому немного в теме,
но в конечном итоге стал использовать dict (libdict) и tokyocabinet в силу их более понятного АПИ, а так же решаемому объему задач (мне более 100 M элементов не надо).
Мы, все расчетные задачи выносим в бэдграунд, которые реализованы как сишные демоны. Да и пользователей у нас 25М, а не 100+М как в Баду…
интересное и полезное расширение, которое хорошо подойдет для расчетных задач (статистика и биллинг).
Непременно буду иметь его ввиду. Сам хотел сделать нечто подобное ;), даже это обсуждалось на Хабре более года назад в одной из тем про структуры данных, но просто не было подходящего проекта под эту задачу.
Лично я собирался использовать judy массивы в своих сишных проектах, по этому немного в теме,
но в конечном итоге стал использовать dict (libdict) и tokyocabinet в силу их более понятного АПИ, а так же решаемому объему задач (мне более 100 M элементов не надо).
Мы, все расчетные задачи выносим в бэдграунд, которые реализованы как сишные демоны. Да и пользователей у нас 25М, а не 100+М как в Баду…
+1
Sign up to leave a comment.
Judy-массивы в PHP