Группы по алготритмам и подсказки от лора

Нужны мозги

стаковерфлоу?

есть данные задаваемые в виде таких векторов
векторами длиной N где каждый элемент является списком допустимых значений

А расскажите немного подробнее. N - это сколько? Что такое * - любое? Допустимые значения - это набор байт? Как задается позиционный запрос? Набор байт из запроса должен точно совпадать с набором из вектора?

Просто хранить элементы вектора в set (AVL-tree), если большой элемент - perfect hashing строить заранее по этому списку?

1) Это работа с множествами?
2) Если да, то максимальное количество элементов одном множестве?

вероятно, глупость скажу - а вам не поможет чуть модифицированное дерево поиска? на каждый из N элементов по дереву, а для списка значений допускается повторное включение элемента для каждого элемента списка.

<30ms
N=20 при преобразовании в точки, если X определен 2мя значениями

И это бигдата? (20*2*4(sizeof(int))*100*1000) - это 15метров. 4метра на чарах. Знаешь скорость линейного поиска? Упирается чисто в память - на современном железе это в районе 12-15G на канал минимум. Сам посчитаешь? Скорость л3 в районе 20-30G на ведро. Сам посчитаешь?

30мс - это ничто в сегоднящних реалиях для таких цифр.

Опиши по конкретней задачу - я тебе накатаю примеров.

Возможно, я не очень понял задачу (может, пример привести - было бы понятнее), но почему бы не рассматривать ее как обычный поиск с boolean queries?

Каждый Xi - документ, значения - слова в нем, отличие от текстового поиска только в том, что разные слова могут занимать одну и ту же позицию (списки значений). Тогда все упирается в построение инвертированного индекса, булевые запросы работают очень быстро.

Если данные более-менее статичные, то задача довольно простая (100 тысяч документов - это ерундовое кол-во). Если нет - чуть посложнее, надо сделать эффективные обновления индекса.

Если N фиксированное и не очень больше, то все можно сделать еще проще - на каждую позицию свой индекс.

N <= 50
* любое
допустимые значения могут быть инты, даблы, строки

Как задается позиционный запрос?

(a, 1 | 2, * ... F)

Набор байт из запроса должен точно совпадать с набором из вектора?

По позициям. В вышеприведенном подходят вектора где в первой позиции в списке есть элемент «a», во второй позиции 1 или 2, в третьей любой.... в последней False.

вероятно, глупость скажу - а вам не поможет чуть модифицированное дерево поиска?

Как я уже сказал деревьев разных было рассмотрено много, и текущее решение и работает с мутировавшим К-d деревом. Но как показано - все подобные решения работают с т.н. пространством точек - то есть на гиперплоскости задается точка с координатами вектора. У меня в векторах списки допустимых кординат. То есть для сведения к гиперпространству надо их разложить в простые вектора - это декартово произвидение всех списков вектора. Как видно при N=20 и не более 2х значений в позиции вектора - количество перестановок 2^20=1M. При 1000 таких элементах и 100 байтах на значение объем потребляемой памяти 100G. А мне надо десятки тысяч и списки там подлинее. То есть не все так просто.

это 15метров.

Ага щаз. Количество перестановок при N=20 это не 20*2, а 2^20.

что разные слова могут занимать одну и ту же позицию

Это существенное отличие с точки зрения объема операций. Если там одно слово =- то это одна операция сравнения (индексированная или нет не важно). А если там списки - все возводится в соответствующие степени. Вектор:

([1,2], [a,b]) -> X1

В линейный индексируемый вид разворачивается в 4 записи.
(1,a) -> X1
(1,b) -> X1
(2,a) -> X1
(2,b) -> X1

Добавь третью координату с двумя значениями - и записей уже 8, Добавь в первую позицию еще одно значение и записей уже 16. А у меня в такой позиции может быть 1-50 элементов, и таких позиций до 50, Если возьмем что средняя длина списка в координате 5 это 5^50 перестановок для одного X. А таких X до 100к.

Берем таких 100k x 1M = 100G точек.

А зачем ты их все помнишь/хранишь?

чтобы по ним делать query.

А сетка if-ов, с подачей рандомного снаряда/шаблона на вход и с рандомными условиям выбора варианта/ветвления, разве не быстрее будут ?

У тебя никаких требований к закономерности генерируемых данных нет?

А сетка if-ов,

Ине не генерировать - но насчет хардкода это надо подумать.

А зачем все варианты хранить?

Пример:

X1 = ([1,2], [a,b])
X2 = ([1,3], c, F)

Индекс:
1 -> (1, X1), (1, X2)
2 -> (1, X1)
3 -> (1, X2)
a -> (2, X1)
b -> (2, X1)
c -> (2, X2)
F -> (3, X2)

Запрос:
(1, a | c, *)

Исполнение:
1) поднять пост-лист для слова "1", выбрать все элементы с позицией 1
2) поднять пост-лист для слова "а", выбрать все элементы с позицией 2
3) поднять пост-лист для слова "с", выбрать все элементы с позицией 2
4) объединить результаты пунктов 2 и 3
5) пересечь результаты пунктов 1 и 4

С точки зрения объема индекса ситуация «x элементов, в каждом элементе y вариантов» не отличается от ситуации «x * y элементов». В задачах текстового поиска без проблем индексируются коллекции в миллионы документов размером ~тысячи слов на документ.

Единственная проблема - если в векторах могут быть элементы «*». Но ее можно обойти, например, завести специальное слово '*' и обрабатывать, как будто оно есть в запросе на всех позициях.

Это фактически отдельные индексы по разным измерениям. Первые игры были на эрланге - я так и попробовал - там это эпически дорогая операция. Но пересечение - это O(N)+ операция. Разбиение по true/false на 2 - это перебор 100k/2 элементов минимум при пересечении с этими результатами. Плюс по памяти оно будет кушать на каждый запрос мегабайты - представь 50k элементов в виде массива указателей по 4байта - 200k скушает только лукап по boolean пространству.

В задачах текстового поиска без проблем индексируются коллекции в миллионы документов размером ~тысячи слов на документ.

Одномерно. В этом проблема Nслов^(k=1)=N. А у меня Nслов^(k<=50). Даже при маленьких N это охрененные числа.

Попробуй слепить списки в строку и создать полнотекстовой индекс для каждого поля. Можно попробовать round-robin scheme для ускорения поиска по многим индексам.

Для проверки идеи, можно использовать picolisp, поскольку там это уже сделано.

Все-таки я не понимаю, почему N ^ k, а не N * k. В моем примере - где я не прав? Можешь привести пример, где будет видна разница?

Плюсую анонима, посылающего на SO.

1. берём учебник по алгоритмам полнотекстового поиска

2. вдумчиво читаем

3. ....

4. PROFIT!!!11

N <= 50

Вроде бы не очень много? Можно попробовать такой наивный алгоритм:

- Берем исходные вектора. Для каждого столбца выбираем уникальные элементы (и сортируем). Для каждого уникального элемента храним номера строк (векторов) в которых они находятся. Если элементов немного (True/False например), то можно для каждого элемента построить битовую карту

- Для каждого запроса берем пустую битовую карту. Элемент из запроса ищем в соотв. столбце (бинарным поиском). Обновляем битовую карту выборки. И так N раз

Все-таки я не понимаю, почему N ^ k, а не N * k

0|1, 0|1, 0|1 - сколько существует перестановок? Это позиционный двоичный код - 2^3.

В моем примере - где я не прав?

В твоем примере в конце операция сложностью k(пространств)*O(N)+(пересечение множеств, сложность зависит от алгоритма либо O(N^2) либо 2*O(NlogN) + O(N) в случае сортировкой). Не говоря уж о памяти.

То есть алгоритмически работать будет. А вот скорость....

если есть ограничение на память, то я бы стал думать в сторону правила преобразовании ([a,b,c], [1,3].....[T,F]) -> (N1, N2, ..., Nn), где N это обычные числа. В приведённом примере это может быть обычное OR всех значений в перечислении, * - это FFFFF. Приводишь запрос в такие же числа по тому же правилу. Тогда полным перебором по всем цифрам с AND получишь ограниченный набор данных, который можно полностью перебрать и получить результат. Проверок будет очень много, но они элементарные и легко раскладываются по ядрам, оверхед по памяти фактически отсутствуют. Можно сократить перебор приведя его к тройной схеме т.е. ([a,b,c], [1,3].....[T,F]) -> (N1, N2, ..., Nn) -> N сначала с проверкой по N формировать набор данных для проверки по вектору чисел Nn, который формирует окончательный набор для проверки. ну это навскидку, предполагая что запрос формирует достаточно ограниченный набор данных.

Откуда перестановки-то? Для поиска не нужно все эти варианты генерировать.

Обычный инвертированный индекс, операция пересечения пост-листов, современные реализации работают очень быстро.

Индекс, конечно, в памяти целиком никто не хранит, но это не проблема.

Если ты можешь выложить реальные данные и запросы (или алгоритм генерации чего-то похожего), я могу в ближайшие несколько дней прикинуть скорость поиска на примитивной реализации инвертированного индекса, которая под рукой есть.

А алфавит конечный? В смысле допустимо ли заменить

([a,b,c], [1,3].....[T,F]) -> X1

на

([a,b,c], [d,e], ... [y,z])

Если так, то почему обычные регулярные выражения не катят? Скажем если элементы векторов это слова состоящие из нескольких букв, то поиск это просто матчинг регекспа.

нужно делать их быстро: <30ms

Таких X - скажем меньше сотни тысяч

Я может чё-то не понимаю и скажу глупость, но проц 4ГГц за 30мс выполнит 120млн. тактов т.е. по ~1000 тактов на один вектор. Какгбэ даже линейный поиск по образцу должен справляться с задачей.

Какгбэ даже линейный поиск по образцу должен справляться с задачей.

Феном 3GHz, на одном ядре, вызов функции в которой одна битовая опперация ~1G операций на жабе. 80тыс строк реальных данных. N=50 => 4M операций если превратить все в биты. Это 250qps. Мало. У меня сейчас на модификации k-d дерева >1200.

на жабе

Так бы сразу и сказал.

Это 250qps

Феном 3GHz, на одном ядре

Ну а на 4 ядрах будет 1000qps, так?

Феном 3GHz

Судя по мануалу на твоё говно(это же к10?) с ведра ты можешь снять 1Терабита на битопах.

вызов функции в которой одна битовая опперация ~1G операций на жабе

bigdata
latency
java

Ну ты понял.

Научись бенчить вычисления, а не свою жабу. Хотя судя по твоей тотальной нулёвости - ты даже кол-во вычислений от кол-ва данных не отличаешь.

80тыс строк реальных данных. N=50 => 4M операций если превратить все в биты.

Операций над чем? 1Терабит, 4М интов - это 128мегабит. Какбэ оцени разницу.

4М интов - это <16мегабайт в секунду. 16мегабайт - нутыпонял.

Если же у тебя 80к «векторов» по 50битов - это 4мегабита - это полмертра. Полметра в секунду - нутыпонял.

Это 250qps.

Что такое «qps»?

У меня сейчас на модификации k-d дерева >1200

Пацан снял отсилы 20метров/с на феноме. Куллстори.

Так бы сразу и сказал.

Какая разница? Ты думаешь bitwise or будет на сях быстрее чем на жабе настолько радикально что это будет иметь значение?

Ну а на 4 ядрах будет 1000qps, так?

Это порог - все данные надо сводить к битовым маскам и получим мы предел для четірех ядерного приложения. Как я сказал на том же ядре с помощью k-d дерева я делаю 1200qps. А там у меня еще мешок мыслей что можно оптимизиорвать.

с ведра ты можешь снять 1Терабита на битопах.

Это если ничего не делать кроме этих битопов. Мне не эмбеддед в 5килобайт написать надо а кластеризуемый сервер. Проблема не теоретическая - потому решения вида «заточить все на асме» не работают.

Ну ты понял.

Да а понял что ты теоретик. Проходи.

Операций над чем?

Битовых операций. Читать научись.

Что такое «qps»?

Запросов в секунду. Это ты уже сначала читать научись - а потом уже переходи к посылам.

Куллстори.

Мнение чувака который даже не осилил понять задачу - очень важно для нас.

Это если ничего не делать кроме этих битопов.

А что тебе надо делать, кроме них? Ты хоть приведи пример своих реальных данных - тебе поцаны покажут как надо, а так это лишь жалкий кукаретинг.

Яж тебе говорил про память - это с твоей говнопамятью отсилы 12гигов на канал - это меньшее, чем 100гигабит. У тебя есть овер 10операций над каждым битом - тебе мало? На avx(2) - это уже 20операций на каждый бит.

Мне не эмбеддед в 5килобайт написать надо а кластеризуемый сервер.

16метров/с - да, куллстори. Я тебе сказал - хочешь познать некстлевел - выкатывай «реальные данные». Покачто ты прикрываешься жалким кукаретингом.

Сколько же нулю надо нод, чтобы снять 30гигов - датычё 2к. Неслабо. Кластерезуй дальше.

Да а понял что ты теоретик. Проходи.

Ахахаха, кукарекнул жабист, который снял 1G. В отличии от тебя я не теоретик - я понимаю что и как можно снять, и реально ли это.

Запросов в секунду. Это ты уже сначала читать научись - а потом уже переходи к посылам.

Каким образом у тебя может быть 1200запросов, если у тебя время поиска 30мс это хорошо? Чего запросов? К чему запросов? В отличии от тебя я не кукарекаю хрен знает о чем.

Мне не интересна что значит твоя абривиатура. Ты мне скажи с какого бадуна ты её выкатил и как считал.

Мнение чувака который даже не осилил понять задачу - очень важно для нас.

Ты не описал задачу - ты написал какое-то говно, невнятное и идиотское. Для тебя, нулёвого балабола - это возможно что-то из себя представляет, для пацана же, чьи познания в теме чуть больше нуля - твоё объяснение настолько же не точно, насколько твоё представление о реальном мире.

Выкатывай свои «реальные данные», критерии поиска, внятные примеры. А лучше выкладывай объяснение и того для чего тебе это нужно, ибо с таким уровнем с шансом 98% твоё представление о решении твоей задачи - тотальное говно.

Какая разница? Ты думаешь bitwise or будет на сях быстрее чем на жабе настолько радикально что это будет иметь значение?

Ты реально не понимаешь, что в х86 «alu» векторное и конвейерное? Я даже не знаю как идиоту это объяснить - почитай хоть что такое latency и throughput у инструкций. Зависимость по данным.

Суть не в том, что жаба говно - суть в том, что ты говно + жаба говно, поэтому у тебя 3такта на битоп, хотя у него latency 1такт. Я уж не знаю какой жопой надо забенчить, чтобы получить 1G, но ты явно уникум.

Это порог - все данные надо сводить к битовым маскам и получим мы предел для четірех ядерного приложения.

Ну не смеши меня, 1G на ведро. На умножении ты вообще наверное 0.8gflops получаешь на 4ведра. Куллстори.

Явно уникум.

В отличии от тебя я не теоретик - я понимаю что и как можно снять, и реально ли это.

Ты мне тут рассказываешь про брутфорс а если надо больше то надо все переписать поближе к железу и и добавить ядер. С таким подходом - проходи.

Чего запросов? К чему запросов?

То что куча народу все прекрасно поняла а ты не догнал - о чем тебе говорит?

В отличии от тебя я не кукарекаю хрен знает о чем.

Ты даже на понял о чем ты кукарекаешь.

Ты не описал задачу - ты написал какое-то говно, невнятное и идиотское.

Ты разбил мне сердце. Мне очень больно видеть как ты нефига не понял когда все все прекрасно поняли. Мир такой жестокий к тебе, клевому поцону который в теме выше нуля. Тему вообще не понял - но зато задекларировал что выше нуля. Молодец. Переходи к следующей теме - там что нибудь задекларируй. Пользы с тебя тут меньше нуля.

Я уж не знаю какой жопой надо забенчить, чтобы получить 1G, но ты явно уникум.

вызов функции в которой одна битовая опперация
вызов функции в которой одна битовая опперация
вызов функции в которой одна битовая опперация

Ты дебил сначала научись читать.

Проходи уже, не интересен.

Ты дебил сначала научись читать.

Как же смешат эти бомжи, которые даже не понимаю почему они в говне.

Понимаешь идиот - твоя функция будет выдавать абсалютно разные результаты в зависимости от её аргументов и того, куда ты её впихнёшь.

На твоём феноме, при 32битных интах:
//это 2такта.
a = xor(a, 123); b = xor(b, 123); c = xor(c, 123) 
a = xor(a, 123); b = xor(b, 123); c = xor(c, 123) 
//это тоже(2.33)
a = xor(a, 123); a = xor(a, 123); a = xor(a, 123);
//и это(2)
a0 = xor(a0, 123), a1 = xor(a1, 123), a2 = xor(a2, 123), a3 = xor(a3, 123);
b0 = xor(b0, 123), b1 = xor(b1, 123), b2 = xor(b2, 123), b3 = xor(b3, 123);
c0 = xor(c0, 123), c1 = xor(c1, 123), c2 = xor(c2, 123), c3 = xor(c3, 123);

Вечер маленьких открытий для нулёвого ущербана. Ты хоть что-то по примитивной матчасти почитай. Ещё раз повторю, эта область состоит из нюансов на 100%, и где нулёвый ущербан типа тебя ничего не видит - норма пацан понимает и видит нюансы из которых перфоманс и состоит.

Этим и отличается нулёвая ссанина, которая ничего не может, кроме как кукарекать и нести херню от пацана, который видит и понимаешь как надо, что и почему.

Но обоссаному нулёвому жабисту это не надо, ты ещё не дорос до чего-то чуть быстрее калькулятора. Иди бигдать, 16метров/с.

то это 2^20 точек на один X

А зачем тебе из X получать точки?

А лучше скажи некоторые характеристики твоих данных и запросов:

• Пусть в i-м списке вектора могут находится только элементы множества мощьности x(i). Какова сумма x(i) для всех i?
• Пусть в запросе на i-м месте стоит дизъюнкция из y(i) элементов. Чем ограничена сумма всех y(i)?

P.S. А ты знаешь, что объединение или пересечение k списков по N элементов каждый можно сделать за O(N*k*log k)?

А зачем тебе из X получать точки?

1. Это оценка количества перестановок для превращения в плоскую таблицу - объяснение почему «загнать в постгрес» не поможет.

2. Для создания индексирующей структуры вида K-D/R/X и прочих деревьев - превращение в spatial space.

Какова сумма x(i) для всех i?

Скажем в среднем 20 * <=50 = 1000. В реальности там могут быть весьма открытые списки - но вводит их все же человек - поэтому там могут быть множества из 10 элементов в основном - но есть несколько полей где встречается пара тысяч. Таких X мало но они есть - хотя я пытаюсь это пресечь административно - потому что они неверно пользуются системой. Это мощность введенных множеств. Часть из них в принципе бесконечные.

Чем ограничена сумма всех y(i)?

в среднем где-то 50 + 25. Дизъюнкции на практике могу появляться только в некоторых позициях и они небольшие.

А ты знаешь, что объединение или пересечение k списков по N элементов каждый можно сделать за O(N*k*log k)?

Знаю. При true | false лучший случай это бинарное рассечение пространства - N слишком большой.

Часть из них в принципе бесконечные

Это как? Почему раньше не сказал?

N слишком большой.

Здесь N — количество векторов списков. Ты раньше говорил, что оно у тебя не превосходит 100 000. Это, разве, слишком много.

1. Это оценка количества перестановок для превращения в плоскую таблицу - объяснение почему «загнать в постгрес» не поможет.

2. Для создания индексирующей структуры вида K-D/R/X и прочих деревьев - превращение в spatial space.

А если использовать битовые строки?

Всё ещё не понимаю почему ты зациклился на распаковке своих векторов.

Это, разве, слишком много.

А разве мало? Пересечение k=50 N/2.

А если использовать битовые строки?

Как я уже говорил - брутфорс 1G операций на ядро, 80к реальных строк x 50 измерений = 4M -> 250 запросов в секунду.

Всё ещё не понимаю почему ты зациклился на распаковке своих векторов.

Я не зациклился - просто первое решение это - вариант k-d дерева а следовательно надо превратить в spatial space.

spatial space

Что это такое? Гугл такого не находит (по крайней мере не в начале выдачи), а дословный перевод даёт тавтологию: пространственное пространство.

Я про битовые строки в postgres. Я не знаю используется там брутфорс или всё это несколько оптимизируется, поэтому только предположил.

Я не зациклился - просто первое решение это - вариант k-d дерева а следовательно надо превратить в spatial space.

А почему же тогда ты все предложенные тебе идеи рассматриваешь с точки зрения векторов значений, а не векторов списков значений? Первое пришедшее тебе в голову и нужное тебе решения — вовсе не обязана совпадать или быть как-либо связаны между собой.

Что это такое?

spatial data structures

А почему же тогда ты все предложенные тебе идеи рассматриваешь с точки зрения векторов значений, а не векторов списков значений?

:) я не рассматриваю:) Пока тут не предложили то что я уже и так знаю - я просто показываю даунсайды того или иного решения. С раздельной индексацией по каждой координате раздельно - дорогая операция пересечения которая сказывается на производительности. Брутфорс битовых масок - недостаточно производителен. Я сейчас провожу разные испытания разных решений. Есть еще битмап индексы, стратегии кластеризации R и X деревьев, состгресовские реализации для GiST и т.д. Я всем этим займусь. Просто я надеялся на ссылки на что-то принципиально другое, что я не нашел по ссылкам, какие-то другие предложения по сведению данных к другому представлению и следовательно другим алгоритмам.

Брутфорс битовых масок

Или мы с тобой по разному понимаем брутфорс, или этого тебе никто не предлагал.

Странный ты. Характеристики данных из тебя вытаскивать надо. Есть указания про 30 мс и 1000 з/с, но ничего не сказано о железе?

Ну да ладно. Я выскажу свою идею, а ты делай, что хочешь.

Есть «массив» списков. Индексами массива являются:

• значение
• позиция в векторе этого значения

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

• первоначально у каждого списка активен первый элемент,
• затем перебираем все номера векторов начиная с наименьшего (очевидно, что значения всех активных элементов списков будет не менее текущего номера — это будет частью инварианта цикла);
• для каждого номера вектора просматриваем все активные элементы списков: если номер равен активному элементу списка, то
  • вектор удовлетворяет соответствующей части условия запроса и
  • в списке активных становится следующий элемент;
  если не равен, то, очевидно, ветор не удовлетворяет соотвтствующей части условия запроса; если у списка нет активного элемента (всче просмотрены), то вектор условию не удовлетворяет
• после просмотра всех активных элементов списков нам известно удовлетворяет ли вектор запросу

Как видно, имеется два вложенных цикла. Тело внутреннего выполняется не более 100 000 * 50 = 5 000 000 раз.

Так как о железе ты ничего не говорил, то я не знаю подойдёт тебе это решение или нет.