Month of Testing — 20 тематических вебинаров, 17 спикеров, подготовка к сертификации ISTQB!
×Закрыть

Алгоритмическая задача из проекта

Задача для иллюстрации.
Рассмотрим простой пример из 5 последоватльностей:
А. (1, 3, 5, 20, 35, 123)
B. (1, 3, 5, 20, 39, 123, 277, 302, 388, 500 )
C. (1, 3, 7, 23, 35, 125, 277, 302, 388)
D. (1, 3, 8)

Попробуем выбрать ТОП 1 для каждой из последовательностей:
Возьмем первую последовательность А
А и B => 5 чисел совпало, 4 не совпало
А и С => 3 чисел совпало, 6 не совпало
А и D => 2 числа совпало, 4 не совпало.
Итого наиболее похожая последовательность B

Задача из практики.
Это можно былобы общитать в лоб без эвристик, если бы не:
есть 24 миллиона последовательностей натуральных чисел, все числа от
1 до 1700000
В каждой последовательности от 1 до 1700000 элементов.
Все последовательности имеют не равномерно распределенное количество чисел. Предположим по принципу Паретто, 20% на 80%. Тоесть 20% последовательностей вместе взятые имеют больше чисел, чем остальные 80% вместе взятых последовательностей.

Нужно для каждой из 24 миллиона последовательностей, найти топ 25 наиболее похожих на нее последовательностей из этого же списка.

LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Всем спасибо, отписавшим, докрутил оптимизации. Хорошо еще не протестировал, но время сократилось с около 60 секунд, до комфортных 1-3 сек на один юзерпоиск. Это супер, потому что 60 секунд это равноценно зависшему сайту, пришлось отключить даже эту фичу по умолчанию, сейчас включил.
Напр.
booben.com/?q=айти&p=1
booben.com/?q=доллар&p=1
booben.com/?q=крым&p=1

еще бы хелпер как этим пользоватся
надо первым аргументом указывать название сайта?

Нет, то другие фичи, потом опишу. Конкретно это, ассоциативный поиск. Алгоритм обучается и строит ассоциативные ряды на основе миллионов проиндексированных документов, а потом выискивает наиболее релевантные из них по запросу.
Напр. booben.com/?q=блокчейн&p=1
Ассоциативный ряд
блокчейн биткоина биткоино битка биткойн криптова биткоин биток майнинг майнинга blockcha ico биткоины bitcoin майнить _bitcoin btc битки майнеры майнеров ethereum заробота n2919721 forklog майнинго

допустим
а почему я получаю какойто треш по запросу «php»?

сорри, починил, но ввиду несовершенства парсера, php используется в разметке почти на каждой странице и заасоциировано с другими такимиже тегами
booben.com/?q=php&p=1
Но можно вот так и так чуточку лучше работает
booben.com/?q=пхп&p=1

улучшаю алгоритм по ранкингу страниц в своем поисковике. Завтра кое-что покажу

Для начала надо перекодировать как сами значения, так и номера последовательностей. Каждое число представим в виде битовой позиции этого числа в натуральном ряде. А эту позицию представим в виде двух байтов. Первый байт-количество байт в битовом представлении, а второй байт-номер позиции. Типа значение числа в степени 256. Далее строим новые последовательности вместо значений в которых будет ссылка на дерево каждый элемент которого номер последовательности к которой принадлежит это число. Получим вполне анализируемые деревья с двух-байтовыми значениями. Я долго думал)) Часа 3. Может 5. Интересная задача. Надеюсь хранить перекодированные последовательности не проблема.

Бубен. Срач уже большой. Ты бы уже переформулировал задачу после этого обсуждения более четко и аккуратно. Какая именно метрика, какие данные, какие требования по быстродействию, как часто искать надо, как часто меняются это 24 ляма последовательностей и т.п.

Возможно тебе достаточно построить что-то типа дендрограммы, дерева и его юзать.

Та байдуже метрика, дані і т.д. Як матрицю 24000000×1700000 тримати?

Зачем ее трымаць?
Написать самому кластеризацию, что не потребует полной матрицы.
Для старта кластеризации рпавномерно выбрать данные из выборки и по ней построить начальное дерево, дендрограмму, затем уже менять кластеры, расширяя выборку. Когда некая фукнкция «энергии» кластеризации перестанет сильно меняться останавливать построение.
Затем при поступлении новых данных корректировать кластеры.

Здесь никаких эвристик и в общем будет сходится к фактическому распределению.

Т.е. первое построение дерева будет долго, дальше будет работать достаточно быстро, если распределение данных не будет сильно меняться.

Таке тренування з ресемплінгом вимагатиме дуууже довго часу для збіжності дендограми. Хоча якщо точний розв’язок не потрібний, то може і зійти.

Та байдуже метрика, дані і т.д. Як матрицю 24000000×1700000 тримати?

Кодерки не знают как матрицу разбить на не сколько небольших частей, обработать на разных компьютерах а потом слить результаты вместе?

Этого не нужно. Проще выборками работать с таким в его случае до схождения алгоритма.
Если не сходиться алгоритм, значит алгоритм неверен.

Внизу есть мое сообщение, задача почти решена, осталось дотюнить

Уже кое-что реализовал, сборная солянка многоуровневых оптимизаций.
Во-первых, я действительно сортирую все последовательности по длине. Если последовательность на 1 тыс элементов, то я начинаю просматривать другие последовательности тоже на 1 тыс элементов, постепенно смещаясь в стороны. Таким образом сначала бью в область, которая с большой вероятностью соберет мне почти весь ТОП 25.
Во-вторых, для каждой последовательности в зависимости от ее длины, вычисляю максимальный возможный бал схожести. Если я вижу что даже в happy path я получу меньший балл чем минимальный балл из ТОП 25, то я сразу такую последовательность отбрасываю и не сканирую ибо нет смысла.
В-третьих, я добавил масштабирование последовательности (вы его называете Монте Карло, согласен чемто напоминает). Тоесть грубо говоря уменьшаю последовательность в десять раз, просто взяв из нее каждый десятый элемент. И сначала сравниваю этот черновой вариант. Баллы чернового варианта умножаю на десять (теорвер) и накидываю еще на всякий 30%-50% чтобы покрыть возможную погрешность между уменьшенным масштабом и оригиналом. Если пробация через уменьшенную копию говорит что вариант в принципе может быть годный, перехожу наконец к чистовому сканированию схожести последовательностей.
Всё вместе дало существенный прирост производительности. Пока в первом приближении на порядок, может быть даже больше, нужно дальше тюнить. Скорей всего далее пойду по пути, добавить еще пробацию на более грубом масштабе, должно помочь. Ну и возможно почищу эти 24 млн, там слишком маленькие и слишком длинные последовательности считать мало смысла по предметной области. Попробую оставить миллион, может быть больше. Такое уже более менее реально обсчитать.

Я тебе предложил путь, ты уже сам решаешь идти по нему или нет.
Как бы из срача ты уже можешь сформулировать задачу более четко и после еще раз поискать решение ее.

И это не совсем монтекарло — это выборки, их лучше рандомом делать.
Можно еще несколько выборок в параллель и k-fold применить.

Можете объяснить как работает метрика схожести последовательностей? А именно, как совпадения и несовпадения учитываются вместе?

Пример:
A = {1}
B = {2}
C = {1, 2, 3, 4, 5, 6}

A и B -> 0 совпадение и 1 несовпадение. Совпадений меньше чем А и C но одинаковая длина.
A и C -> 1 совпадение и 5 несовпадений. Совпадений больше чем A и B но по влине явно
Какая из последовательностей B или С является наиболее схожей с A и почему?

У вас интересный пример. Но он интересный, пока последовательностей мало и нет выбора. Когда последовательностей очень много, найти на нее похожую на 30%-50% — это норма. В данном случае и A B C врядли вообще попадут в какой-то ТОП.

Числа могут повторяться? Последовательность неубывающая? Есть ли ограничение на максимальный элемент? Например, 1.7 млн одинаковых чисел — и каждое равно 2^511 — 1 ?

Это можно былобы общитать в лоб без эвристик,

Ниасилил почему нельзя в лоб. Scoreboard содержит номера топ-25 и их счет, это 25*8 = 200 байт. После нахождения топ25 для очередного набора, эти 25 сохраняются куда-то там (у вас точно есть же дисковый сторедж) и процесс повторяется

Как сделать не в лоб, я пока не придумал

Задача для одного набора имеет решение O(nk) где n — кол-во наборов (а не последовательностей, етпа), k — количество элементов в наборе, для которого мы прогоняем поиск.

Позиція елементу в списку має значення?
Без Hadoop не обійтися.

А можно записать в таблицу с булевыми значениями, где номер столбца — номер последовальности, а номер строки- значение чисел(1-1 700 000). Для одной последовальности витягиваете матрицу всех последовальности где встречаеться елементи матрици. По последней матрице делаете суму елементов и выбираете 25 наибольшых значений.

где взять память на матрицу 1,7 млн * 24 млн ячеек. Даже по 1 биту на ячейку это больше 5 террабайт (озу?) + обработка этого всего.

5 террабайт (озу?)

Azure Standard_M128m: 3.8TB RAM + 14TB SSD

EC2×1e.32xlarge: 3.8TB RAM + 3.8TB SSD

Задача параллелится: бьешь набор на 2 инстанса, в каждом находишь ТОП 25, потом сливаешь их и из получившихся 50 еще раз берешь Топ 25.

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

Сформулируйте нормально задачу

Что-то я туплю под вечер. Есть две последовательности А и Б, сгенирированы рандомом.
Допустим в них по 1000 элементов в каждой. Между ними 15% чисел совпало.
Теперь я беру только каждый десятый элемент с каждой последовательности.
Получается две последовательности А1 и Б1 по 100 элементов.
Вопрос, по теории вероятности, сколько в А1 и Б1 совпадет чисел в процентах ?

Від 0 до 100. Беріть вже по одному числу

Всё, разобрался, всё стало на свои места, 1.5%

все те же 15%, вы же берете пропорциональные размеры
но для уверености числа должны быть в рандомном порядке

Метод Монте-Карло на практиці: prntscr.com/kezfnd
ABCD — відповідник послідовності A, AEFG — послідовності B. За умовою задачки, S(ABCD ∩ AEFG) : S(ABCD) = 15 : 100, де S — площа фігури. Кидаємо випадковим чином піщинки в ABCD, щоб заповнити 10% площі. Потім зсуваємо їх всіх вліво для наочності, що не вплине на обчислення через «перпендикулярність» ABCD і AEFG. Вийде ABHI, щільно заповнений піщинками. Причому AI : AD = 1 : 10, бо з послідовності вибирали кожен 10-ий елемент. Аналогічно отримуємо AJKG. Залишилося порахувати S(ABHI ∩ AJKG) : S(ABHI). ;-)
Це буде найочікуваніший процент співпадінь.

А на питання, скільки в А1 і Б1 може співпасти чисел у процентах, відповів Vitalii Chyhirov.

Нет, есть простой краевой пример. Допустим есть две последовательности, которые совпадают
на 100%
(1,2,3)
(3,1,2)
Мы берем, и рандомом уменьшаем последовательности в три раза
Остается
(1)
(3)
Уже точно не 100%. Вероятность что совпадут оставшиися числа кратно меньше

Теория вероятности так не работает. Если вкратце, то она не о краевых примерах.
Вот обратный краевой пример.
Есть две последовательности:
1 2 2 2 2 2 2 2 2 2
3 1 3 3 3 3 3 3 3 3
Сокращаем в 10 раз и чисто случайно получаем 1 и 1, т.е. изначально последовательности совпадали на 10%, а после сокращения совпадают уже на 100%.

Если элементы повторяются, то это уже другая задача.
По условиям, элементы в последовательностях не повторяются.

Это та же задача.
Есть две последовательности:
1 2 3 4 5 6 7 8 9 0
32 1 15 56 68 89 98 4355 65 888

Сокращаем в 10 раз и чисто случайно получаем 1 и 1, т.е. изначально последовательности совпадали на 10%, а после сокращения совпадают уже на 100%.

Вспомнился анекдот, у прохожего спросили, какова вероятность встретить динозавра на красной площади. На что он ответил 50/50 либо встретишь либо нет.
В Вашем примере примерно тоже.

Пример приведен был для того, чтобы показать что

Вероятность что совпадут оставшиися числа кратно меньше

не является правильным выводом

Является, потому что прежде чем утверждать, я написал небольшой пример где высчитал как изменятся вероятностные характеристики на примере сотен тысяч таких последовательностей. Ибо в моей задаче это важно

Есть две последовательности А и Б, сгенирированы рандомом.
Допустим в них по 1000 элементов в каждой. Между ними 15% чисел совпало.
Теперь я беру только каждый десятый элемент с каждой последовательности.
Получается две последовательности А1 и Б1 по 100 элементов.
Вопрос, по теории вероятности, сколько в А1 и Б1 совпадет чисел в процентах ?
Всё, разобрался, всё стало на свои места, 1.5%

Ответ на эту задачу: 15%

вы можете дать болие подробный срез результатов если уже провели тесты?
мне кажется что такие искаженные результаты характеры только для часных случаев с маленькими массивами
точнее что проявляться они будут тем чаще чем меньшые будут массивы
а на большых размерах — %точности будет стремится к фактическому результату без приблежения

Вот, самый простой код на шарпе

var r = new Random();

           //for (int i = 0; i < 1000000; i++)
            //{
            //    var seq1 = Sequence.Generate(11, 10);
            //    var seq2 = new int[seq1.Count];

            //    seq1.CopyTo(seq2);

            //    var n1 = seq1[r.Next(0, seq1.Count - 1)];
            //    var n2 = seq2[r.Next(0, seq2.Length - 1)];

            //    if(n1 == n2)
            //    {
            //        x++;        
            //    }

            //}

            //Console.WriteLine(x);

Код Sequence.Generate

public static List<int> Generate(int maxValue, int count)
        {
            var r = new Random();

            var nums = new List<int>(count);

            HashSet<int> added = new HashSet<int>();

            for(int i=0; i<count; i++)
            {
                while (true)
                {
                    var num = r.Next(1, maxValue);

                    if (!added.Contains(num))
                    {
                        nums.Add(num);

                        added.Add(num);

                        break;
                    }
                }
            }

            nums.Sort();

            return nums;
        }
Это замер на маленьких последовательностях, уменьшенных в 10 раз. Есть другой код, который тоже меряет для больших последовательностей, он просто интегрирован в проект, его не так просто выдрать. Но результаты теже.

То ест надо — найти последовательность, которая содержит максимальную длинную под-последовательность из заданной последовательности?
Точнее найти 25 таких.
Правильно?
Че то мне кажется сие тривиальная задача.

Нет, это немного другая задача. Задача конечно тривиальная, просто считается долго ...

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

Если идентификаторы признаков — то придётся давать и вес этим признакам, не бывает так чтобы все признаки равнозначны.

PS. Невозможно решить проблему, если думать в точности так же, как тот кто её создал. Как по мне, ты неправильно создал модель данных, в результате столкнулся с избыточностью по данным.

Что-то мне подсказывает, это естественный язык — та предметная область, над которой ты собрал модель. Если так — то не переоценивай интеллект людей, которые этим пользуются, естественные языки прекрасно поддаются деградации до примитивного набора понятий, и соответственно такая у них модели и данных единицы: 0..2 селектора предметной области, шаблон, типовое наложение [или несколько], дистанция реального предмета от типовых наложений. Если так — то первое что ты должен научиться, это отделять «воду». А это значит, искать нестандартные применения шаблонов + конструкции с шаблоном агрессии, либо сомнения, либо ожидания.

Это целая наука. Чтобы понимать язык, нужно понимать саму модель жизни тех, кто им пользуется. Без этого эффективную модель — не построишь.

Но возможно у тебя цель в другом: выбросить мусор, генерируемый роботами, часто через копипасту, синонимизацию, и тому подобные некошерные вещи. Но и тут тебе не обойтись без огрубления материала, чтобы вообще классифицировать контент. Вливая в модель презумцию «от 1 до 1700000 элементов» — ты ничего не добьёшься. Разбей на классы, и анализируй сначала один (лучше максимум в нормали), а уже потом переходи к остальным.

Хочешь — дам живой пример. Зайди на DOU в мой профиль, попробуй слить все комменты (кстати, вполне боевая задача — перебор страниц по порядку, чтобы выдрать весь контент) — и попробуй что получится. Результат ты знаешь заведомо — все они писаны одним человеком, копипаста крайне редка. А что покажет твоя модель?

Мало что понял, но по предметной области, вот пример
booben.com/...​t?q=плохо хорошо&s=online
Видишь, эти графики коррелируют. И это не случайно. Даже если завтра марсиане нам пришлют много много дампов своих разговоров в курилках, то по ним можно будет почти полностью реконструировать язык и класифицировать термины, что к чему и как относится. Такова сущность нашего мира. Что в эпизоде выглядит как случайность, в обьеме больших данных выглядит как замысел.

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

не можна реконструювати мову, про яку нічого не знаєш :)

Можно конечно, тому есть много примеров. С большими данными это можно сделать почти в автоматическом режиме.

Можно конечно, тому есть много примеров

приводьте

Якщо людей, то можна. Достатньо знати що то Homo Sapiens, та історичний період (тобто умови життя, чим займалися).

От мову бюрократів реконструювати неможливо. Бо вони не роблять нічого корисного, лише ритуали.

вычисление дистанции между двумя последовательностями может быть сделано очень быстро и эффективно — берем битовую строку (200Кб длиной с границей по uint64_t), устанавливаем в 1 тот номер, который присутствует, дальше делаем битовый and по каждому 64-битному слову (с помощью SIMD). считаем количество бит в результате. Количество бит для uint16_t можно заранее вбить в таблицу в памяти и для каждого слова вызывать 4 раза.
Учитывая, что строки длинные, для каждой строки хранить адрес последнего ненулевого бита — так, чтобы оборвать цикл, когда сравнение бессмысленно.

Это мелочь, но поможет.

Вычисление дистанций между 24 миллионами последовательностьей — самая жесть, т.к. тут задача квадратичная (если решать в лоб).
Первая эвристика — отсортировать строки по количеству элементов по убыванию (а внутри по самим строкам и убрать дубликаты).
За счет этого можно оборвать квадратичный цикл раньше, когда количество элементов в строке станет меньше, чем минимальная дистанция в топ-5.
Вторая эвристика — сделать замену номеров, так, чтобы самое высокочастотное число получило номер 1, следующее — 2 и т.п.
Это даст более быстрый обрыв цикла в вычислении дистанции.

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

Альтернативное решение — свести к классическому data mining — выделить допустим через FP-grow самые длинные и частые подпоследовательности (это будет быстро) и найти все строки, где они есть, получаем lower bounds для дистанций.
Выключить найденные из общего списка и продолжить.
Там можно построить неполную матрицу дистанций, но потом ее надо будет дорабатывать напильником, там не вся информация может быть.

Имхо модифицируя FP-grow мне кажется можно получить точное решение задачи.
Память он правда жрет как не в себя...

Ну и остаются приблизительные методы — тот же LSH, HyperLogLog, Монте-Карло или почасовая оплата специалиста по HPC.
:-)

Стосовно методу HyperLogLog, маєте на увазі порівнювати множину із кожною із ≈ 24000000 решти і знаходити ним приблизну потужність об’єднання й на основі цього перетину та різниці? Чи є більш ефективний спосіб?

Як тут можна застосувати Монте-Карло?

или почасовая оплата специалиста по HPC.

Сьогодні — акція, заготовка коду без погодинної оплати ☺:

val c: BigInt = … // бітова маска послідовності, для якої треба знайти ТОП24
sc.readSequences(). // RDD[(Int, Sequence)]
  .gpu(True)
  .map { case (id, seq) => (id, seq.toBigInt) }
  .map { case (id, v) => (id, (v&c).bitCount.toDouble / (v|c).bitCount)
  .sortBy(_._2, ascending = false)
  .take(24)
  .foreach(println)

Залишилося реалізувати readSequences(), клас Sequence і toBigInt і т. п.
Код можна трошки доробити (можливо, оптимізувати сортування) й інтегрувати.
Як код запускати — www.ibm.com/...​nstances_gpu_run_app.html

Питання в тому, чи автору дійсно потрібно точний ТОП24 за < 1 сек ціною плати за Spark-кластер із GPU. І незрозуміло, чи для бізнес-проблеми, яка вирішується, так поставлена задача приведе до найкращого вирішення даної бізнес-проблеми...

HLL тут разве что для оценки дедупликации, среди 24М последовательностей будут дубликаты и если их много — то задача сильно упрощается.
Это скорее этап анализа данных.
Хотя все равно сортировать надо — и дедап можно сделать потом на отсортированных данных.
Если дубликатов мало, то лучше сначала сортировать.

Монте-Карло — тупо брать случайные пары и строить приблизительный top25 — безденежный клиент скушает.
Хотя иногда Монте-Карло дает бОльшую точность, чем найм специалиста по HPC — особенно если найм проводится методом Монте-Карло.
:-)

По коду — sortBy().take(24) сильно неэффективен — сортировка логлинейная и вообще долгая операция (даже если radix-sort для нашего случая).
А вот операция взятия top25 линейна — суем данные в хип объема 25 по очереди и достаем то, что осталось в конце.
Разница будет мягко говоря немаленькая, даже если не использовать эвристики обрыва цикла (а мы их будем использовать).
Впрочем для акционных товаров всегда так. :-)

Если автору надо терабайты ((1.7Мбит=200Кбайт)*24М = 4.8Т) считать за секунду — то тут сначала вопрос в железе с соответствующим объемом RAM, даже NVMe RAID не вытянет такой поток, а на кластере (40Ge или Infiniband) синхронизация сожрет больше, тут же задача «каждый к каждому», это не счетчик слов мап-редюсить...

PS
Большинство реальных (не синтетических) данных сильно вырождены и нет необходимости брать общие универсальные алгоритмы, частное специфичное решение ad hoc может сэкономить время.
Но для этого надо сначала смотреть данные, а эта услуга по акции не предлагается.

Уже кое-что реализовал, сборная солянка многоуровневых оптимизаций.
Во-первых, я действительно сортирую все последовательности по длине. Если последовательность на 1 тыс элементов, то я начинаю просматривать другие последовательности тоже на 1 тыс элементов, постепенно смещаясь в стороны. Таким образом сначала бью в область, которая с большой вероятностью соберет мне почти весь ТОП 25.
Во-вторых, для каждой последовательности в зависимости от ее длины, вычисляю максимальный возможный бал схожести. Если я вижу что даже в happy path я получу меньший балл чем минимальный балл из ТОП 25, то я сразу такую последовательность отбрасываю и не сканирую ибо нет смысла.
В-третьих, я добавил масштабирование последовательности (вы его называете Монте Карло, согласен чемто напоминает). Тоесть грубо говоря уменьшаю последовательность в десять раз, просто взяв из нее каждый десятый элемент. И сначала сравниваю этот черновой вариант. Баллы чернового варианта умножаю на десять (теорвер) и накидываю еще на всякий 30%-50% чтобы покрыть возможную погрешность между уменьшенным масштабом и оригиналом. Если пробация через уменьшенную копию говорит что вариант в принципе может быть годный, перехожу наконец к чистовому сканированию схожести последовательностей.
Всё вместе дало существенный прирост производительности. Пока в первом приближении на порядок, может быть даже больше, нужно дальше тюнить. Скорей всего далее пойду по пути, добавить еще пробацию на более грубом масштабе, должно помочь. Ну и возможно почищу эти 24 млн, там слишком маленькие и слишком длинные последовательности считать мало смысла по предметной области. Попробую оставить миллион, может быть больше. Такое уже более менее реально обсчитать.

Стосовно sortBy().take(24), без заглядання в source code Spark-у або проведення невеликого експерименту (не входить в акційну пропозицію ☺) не скажу, чи цей код спричинив би сортування всіх даних. Бо, наприклад, filter { case (id, v) => id % 2 == 0 }.take(24) виконується за O(1). А не лінійний час, як може здатися на перший погляд. Напр., тут про це розказують, починаючи з часу 11:32. Так працює оптимізатор у Spark. Не здивуюся, якщо розробники зробили, щоб sortBy().take(24) виконувався за лінійний час.

Крім того, не скажу без заглядання в source code або проведення невеликого експерименту, sortBy().take(24) виконувалося б на CPU чи GPU. Наприклад, Amazon здає в оренду по $14.4/год ноди p2.16xlarge з 16 графічними процесорами (NVIDIA K80 GPU) кожна, і пишуть, що 1 такий GPU має 4992 ядер. Тобто один орендований комп’ютер має ≈ 80000 ядер на графічних процесорах. 24000000 послідовностей всього — на 1 GPU припадає 300 послідовностей. Які він може швидко посортувати, якщо відповідним чином реалізований код. Злити посортовані частини можна за лінійний час. А нод у кластері може бути багато.

У найгіршому сценарії довелося б переписати sortBy().take(24).

Якщо запустити на кластері, то вмістити все в оперативну пам’ять не буде проблема. Просто треба орендувати достатньо нод. Дисковий чи мережевий I/O був би тільки:
1) readSequences() - довго, але якщо переписати це на Spark Streaming, то RDD можна 1 раз зчитати і тримати в пам’яті, і для кожного запиту (порахувати для деякої послідовності ТОП24) використовувати закешоване в RAM;
2) sortBy(_._2, ascending = false) — якщо виявилося б, що це виконувалося б довго, можна переписати, щоб з кожного partition вибиралося ТОР24 (лінійно, як Ви пропонуєте), а потім новоутворені partitions укрупнити чи взагалі зібрати на драйвер-ноді і з результату знайти глобальний ТОП24;
3) .take(24) — на драйвер передалося б зовсім мало даних.

Згоден, рішення ad hoc може бути оптимальніше. Але тут інформації по задачі недостатньо, і так, по акції таке не прийнято пропонувати ☺.

Сдается мне даже с битовой маской будет аут оф мемори. Ее просто негде хранить для длинных последовательностей. И бежать по ней тоже будет дольше. Пример
1000 чисел в диапазоне от 1 до 1.7 млн
1000 чисел займет 4 кб. А с маской 1.7млн/8 будет 212 кб. И видеокарта и всякие SIMD тут не спасет

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

Эвристика обрыва цикла будет аналогично битовой строке — если у нас счетчик общих элементов выше найденных top25 — останавливаем сравнение и переходим к следующему.

И такой момент — перенумерация элементов может дать хороший профит для такого метода сравнения. Сделать так, чтобы самая частая фича имела номер 1, следующая — 2 и т.п.
На результат это не повлияет.

PS
Вот кстати может что-то похожее:
medium.com/...​ale-datasets-450b3242e618
Там ссылка на github.

Бітову маску можна зберігати у scala.math.BigInt:

BigInteger must support values in the range −2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive) and may support values outside of that range.

Але, як зрозумів, у цій задачі (через розрідженість послідовностей) краще використовувати розріджений вектор замість бітової маски і шукати приблизний ТОП24 замість точного.

А яка середня довжина послідовності в ваших даних ? Можливо вона значно менша, ніж 1700000 / 2 ? Наприклад 100 елементів :) це сильно міняє справу

З ваших прикладів не ясно чи у ваших відсортованих послідовностях однакові числа мають мати однакові індекси чи можуть мати різні, щоб було співпадіння ? (у вас завжди однакові числа з однаковими індексами)
А = 7,10
B = 1,2,3,4,7,10
Для послідовності А в послідовності В співпадають 2 числа (7 і 10) чи нуль чисел ?

А для А і В взагалі не зрозуміло, в А 6 елементів, в В 10 елементів, як могло вийти 5 співпадінь + 4 неспівпадіння ?

Тобто поясніть краще, будь ласка, свої вимоги...
EDIT: поки писав я, написали схожий комент :)

Во-первых, непонятно, все ли последовательти возрастающие.
Во-вторых, непонятно как считаются несовпадения. A и B совпало 5, а не совпало... 1 число есть в последовательность A, которого нету в последовательности B (это 35). И есть 5 чисел в последовательности В, которых нет в А(39, 277, 302, 388, 500). Откуда взялов 4 несовпадения?

Решение напрашивается примерно такое. Во-первых, для каждой последователньости можно посчитать хеш, который бы зависел от чисел в этой последовательности. Например, это последовательность 4093 бит, бит номер i установлен в единицу если в последовательности присутствует число, являющееся кратным числа i.

Далее, для каждой последователности считаем расстояние между хешами как число различающихся бит. Потом сортируем последовательности в порядке уменьшения расстояния и начинаем рассматривать высчитывать подобие. Идея в том, что мы сможем отсечь поиск в некоторых случаях (например, если у нас несовпадают 100 элементов в битовых масках, то это гарантированных 100 несовпадений. И если уже найдены 25 последовательностей с лучшими результатами, то оставшиеся никак нам не помогут.

Также можно в хеш добавлять длину последовательности, тоже может помочь при отсечениях и оценках.

Боюсь сказать глупость.. Просто просуммировать все значения и результаты отсортировать слишком долго?

1 и 100 дадут сумму как и 50 и 51
суммы одинаковые, совпалений 0

я не поняла задачу. Есть куча последовательностей и нужно выбрать топ чего? топ похожих что на что? Что такое ТОП 1?

а, поняла, но не все — что значит похожих? (2,3) и (3,2) — похожи? в смысле порядок учитывается? Если учитывается порядок, тогда это Longest common subsequence

а если между совпадающими числами есть несовпадающее число — это похожие? например (1, 50, 2) и (1, 20, 2)?

Тут самая вишенка в том, являются ли «похожими» в терминологии автора последовательности, одна из которых является подмножеством другой. Например, «похожи» ли последовательности, одна из которых заключает все натуральные числа от трех до тысячи, другая — только нечетные числа этого диапазона, а третья — простые числа этого диапазона? Надо ли говорить, что все числа второй и третьей последовательностей входят и в первую, а все числа третьей последовательности входят во вторую?

Считается только сколько совпало чисел, сколько не совпало

В таком случае задача упрощается. Если у нас есть 2 последовательности, в которых совпало n чисел, то мы можем отбрасывать последовательности, которые состоят менее, чем из n чисел.

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

2 совпало 1 не совпало = коеф 2/(2+1) =2/3
Для абсолютно одинаковых коеф 1

Они одинаковы ибо числа отсортированы

Короче пришла в голову следующая идея. Поскольку последовательности длинные, сделать каждой последовательности более грубый масштаб. Например у нас есть списки последовательностей, в каждой по 100к элементов в среднем. 100к чисел сравнивать долго в интерации. Промасштабировать, сделать последовательность в 1к. Где первый бит будет 1 если последовательность имеет любое число из диапазона от 1 до 100, второй бит будет выставлен если последовательность имеет хоть одно число из диапазона от 101 до 200 и тд. Тоесть сравнить в таком грубом масштабе наиболее похожие последовательности. После этого масштаб увеличиваем в 10 раз для оставшейся пачки похожих последовательностей и на финальной итерации уже вычисляем конечный чистовой результат.

Ще трошки, і Ви винайдете Locality Sensitive Hashing. ;-)

Ідея методу така. Замість послідовності будемо розглядати вектор довжини 17000000, який є її бінарним представленням. Сформуємо матрицю, стовпцями якої будуть утворені вектори. Вважатимемо, що матриця складається з b прямокутник смуг, які розташовані одна під одною. Для кожної смуги придумаємо r перестановок її рядків. Для кожної з b*r перестановок визначимо хеш-функцію на стовпці: її значення буде рівне позиції найвищої одиниці у даній смузі даного стовпця. Тобто хеш — деяке число між 0 і 1700000/b. Кожна хеш-функція по своєму розбиває набір 24000000 векторів між бакетами. Кандидатами на схожість із даним вектором можна вважати ті вектори, які потраплять із ним в один бакет хоча б для однієї хеш-функції. З векторів, схожих із заданим, можна порівнянням знайти TOP24. Є ймовірність, що якийсь вектор, що мав би бути у ТОП24, туди не потрапить, але при збільшенні b i r ця ймовірність стає дуже малою, у той час як знаходження ТОП24 на порядки швидше, ніж при переборі всіх 1700000 кандидатів.

Не знаю, наскільки просто вдалося пояснити суть Locality Sensitive Hashing. Хороше пояснення (із математичною теорією) було в курсі Mining Massive Datasets на Coursera. Ще є на youtube, лекції 12-15.

Метод є ефективним, якщо матриця розріджена. Я правильно зробив припущення? Якщо не таємниця, в якій області Ви використовуєте це. Сервіси знайомств, як написав Андрюха Цибрій?

точно. только хотел про LSH написать. а автор, кстати, подбирается к идее блум фильтра, только с хардкожеными бакетами вместо хешей. у него получается такой себе фильтр с 100 коллизий на бакет и одной (псевдо-)хеш функцией. это сразу дает 99% ошибки первого рода для *каждого* элемента, если элементы ИИД. сравнивать таким образом последовательности смысла не имеет вообще. впрочем, если построить честный блум фильтр, то тоже выходит дорого (метод Стели подсказывает, что для кодирования 1.7М элементов с ошибкой 20% нужно примерно 100К памяти — экономия всего 50% по сравнению с честной битовой строкой, на которую надо ~200К). так что LSH.

Рассмотрим метрическое пространство последовательностей, в качестве расстояния — количество различающихся элементов. После чего используем стандартные алгоритмы для поиска k ближайших соседей.
en.wikipedia.org/...​arest_neighbors_algorithm

А и D => 2 числа совпало, 4 не совпало.

Не совпало 4 числа при том, что в D их всего три? А можно вообще не обсчитывать такие кейсы? Если вообще не сравнивать последовательности, чьи длины кратно отличаются (предположить, что говорить об их «похожести» в таком случае не имеет смысла), то возможно получится существенно сократить размерность задачи.

наверное это зависет от рельного контекста задачи
если представить что это алгоритм например сопоставления интересов на сайте занкомства между парами юзеров, цыфры — это просто ИД интресов
то учитывать надо все последовательности, но опираясь только на меньшую последовательность

лгоритм например сопоставления интересов на сайте занкомства между парами юзеров

bipartite graph — граф между двумя disjoint sets. Пофиг на размер каждого

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

Первое, что приходит на ум — подсчёт в лоб, но при правильном хранении данных. Под каждую последовательность выделить 200кб буфер, где каждый бит — это номер числа, 1 число есть, 0 нет. Таким образом операция AND по двум буферам и подсчет бит. Количество установленных бит — это количество совпадений.

Не подойдет. Я прикинул, на обычной машине такое решение займет 45 лет

>300Gb данных, задача раскладывается для SIMD и по процессорам максимально легко. По моим прикидкам первая итерация сравнений завершится за одну минуту на 8 ядрах. Каждая следующая итерация сравнений будет быстрее, т.к. у нас уже есть результат сравнений. Чуть больше года.

Эта задача алгоритмическая, ее проблема не в слабом оборудовании. Для меня нет разницы что год что пять что десять будет решаться, это все еще долго. Вообще SLA не больше секунды. Но я думаю просто закешировать результаты и их пересчитывать раз в месяц. Поэтому буду искать решение которое займет на имеющемся у меня оборудовании максимум неделю.

А зачем просчитывать наперёд? Просчитывай по запросу и кешируй результат вместе с возрастом этого результата, если сильно старый, пересчитываем его.

Нет, запрос должен выполняться для клиента не более секунды. А всю базу лучше заранее обсчитать. Но обсчитать, имеется ввиду за неделю хотябы.

Коэффициент корреляции Пирсона
docs.scipy.org/...​scipy.stats.pearsonr.html

Там проблема что этот метод нужно запустить 24 млн раз, на массиве из 24 млн последовательностей

Подписаться на комментарии