Есть два множества с парами ключ-значение, где ключ неуникален, а значение числовое.
Если оба множества объединить в одно, посчитать среднее арифметическое по ключу, отсортировать получившиеся ключи по среднему арифметическому и взять первые 100 строк, то мы получим 100 ключей с максимальным средним.
Вопрос: как найти эти ключи или хотя бы кандидатоов на эти ключи, не считая среднее по всем ключам?
Здравствуйте, scf, Вы писали:
scf>Есть два множества с парами ключ-значение, где ключ неуникален, а значение числовое.
scf>Если оба множества объединить в одно, посчитать среднее арифметическое по ключу, отсортировать получившиеся ключи по среднему арифметическому и взять первые 100 строк, то мы получим 100 ключей с максимальным средним.
scf>Вопрос: как найти эти ключи или хотя бы кандидатоов на эти ключи, не считая среднее по всем ключам?
Во-первых, два множества лишние; и средние арифметические тоже лишние.
Есть множестово чисел (сколько, кстати? миллион? миллиард?). Из них нужно выбрать 100 самых больших, не читая всех чисел.
Это невозможно, в смысле, невозможно получить точное решение. В общем случае нельзя точно найти 100 максимальных элементов массива (несортированного массива), не прочитав всего массива.
Если сгодится приближенное, можно пересмотреть, скажем, случайно выбранные каждое десятое число; выбрать из них 10 маскимальных, и взять их по 10 копий каждого, чтобы получить 100 приблизительых результатов. При этом не гарантируется, что в исходном массиве на самом деле есть эти числа, но, смотря какая задача, может и подойдёт.
Здравствуйте, Sharowarsheg, Вы писали:
S>Здравствуйте, scf, Вы писали: S>Во-первых, два множества лишние; и средние арифметические тоже лишние.
S>Есть множестово чисел (сколько, кстати? миллион? миллиард?). Из них нужно выбрать 100 самых больших, не читая всех чисел.
Наверное, я неудачно объяснил. Это распределенная СУБД, и минимизировать нужно трафик между нодами кластера. Например, для суммы достаточно с каждой ноды скачать 100 самых больших строк плюс ключи, полученные с остальных нод. Итого 100*node_count строчек с каждой ноды. Вопрос, как оптимизировать расчет среднего.
Здравствуйте, scf, Вы писали:
scf>Наверное, я неудачно объяснил.
А можешь на примере
Есть две ноды, на первой есть пары {1K1 1V1} {1K2 1V2} {1K3 1V3}, а на второй есть пары {2K1 2V1} {2K2 2V2} {2K3 2V3}.
имена я сделал из номер-ноды ключ-или-значение 1-based-индекс-массива.
Пусть нужно найти не сто значений, а два всего. Что надо сделать?
Здравствуйте, Sharowarsheg, Вы писали:
S>А можешь на примере
S>Есть две ноды, на первой есть пары {1K1 1V1} {1K2 1V2} {1K3 1V3}, а на второй есть пары {2K1 2V1} {2K2 2V2} {2K3 2V3}. S>имена я сделал из номер-ноды ключ-или-значение 1-based-индекс-массива.
S>Пусть нужно найти не сто значений, а два всего. Что надо сделать?
В этом примере ключи уникальны, поэтому поиск арифметического среднего тривиален)
Вот мой пример (буква ключ, цифра значение):
node1 A1 A2 B1 C3
node2 A6 B1 C1 D4
Если посчитать арифметическое среднее и отсортировать, получится D4 A3 C2 B1, итого результат — D4 A3. Вопрос — как получить этот результат, не перекачивая всё содержимое второй ноды на первую.
Здравствуйте, scf, Вы писали:
scf>node1 A1 A2 B1 C3 scf>node2 A6 B1 C1 D4
scf>Если посчитать арифметическое среднее и отсортировать, получится D4 A3 C2 B1, итого результат — D4 A3. Вопрос — как получить этот результат, не перекачивая всё содержимое второй ноды на первую.
О, вот так понятно.
Я бы думал что-то о том, что нужно посчитать сначала ноды отдельно
Получим
C = 3; 1
A = 1.5; 2
B = 1; 1
и
A = 6; 1
D = 4; 1
B = 1; 1
C = 1; 1
нужно ещё отслеживать количество элементов, чтобы можно было среднее по двум нодам считать
После этого будем брать по одной с паре каждой стороны (берем первый ключ с первой ноды, и соответствующее ему данное со второй, а потом наоборот, а потом второй ключ с первой, и так далее) и обсчитывать её (на практике, конечно, пачками, чтобы число пересылок уменьшить, но пока по одной), и складывать в массив с результатами (а в результатах количество элементов уже не нужно)
C = 2; пусто
потом
A = 3; C = 2
потом
D = 4; A = 3
и тут бы остановиться, но я не понимаю, какой критерий остановки.
критерий остановки в этом случае может быть такой, что на каждой стороне следующее значение (1) меньше, чем минимальное среднее из результата (что означает, что гарантированно не будет новых победителей), но насколько это позволит сэкономить пересылки, сильно зависит от данных.
Здравствуйте, Sharowarsheg, Вы писали:
S>Я бы думал что-то о том, что нужно посчитать сначала ноды отдельно
Это было бы идеально — если бы мы могли заранее предсказать в рамках одной ноды, какие ключи попадут в результат и вытягивать из базы только их. Но так не получится — если взять два максимальных средних с каждой ноды, то объединенное среднее вовсе не обязательно будет максимальным. Я пробовал исследовать это явление математически, но там всплывают квадратичные системы неравенств с кучей переменных, а я не умею их решать.
Здравствуйте, scf, Вы писали:
scf>Здравствуйте, Sharowarsheg, Вы писали:
S>>Я бы думал что-то о том, что нужно посчитать сначала ноды отдельно
scf>Это было бы идеально — если бы мы могли заранее предсказать в рамках одной ноды, какие ключи попадут в результат и вытягивать из базы только их. Но так не получится — если взять два максимальных средних с каждой ноды, то объединенное среднее вовсе не обязательно будет максимальным.
Это зависит от конкретных данных. Объединённое среднее не обязательно будет максимальным, но нам и не нужно, чтобы оно было максимальное. Нам только нужно заметно уменьшить число пересылок. Насколько его получится уменьшить, будет зависеть от того, сколько пересекающихся ключей между нодами, сколько чисел на каждой стороне, насколько отличаются средние между собой, насколько отличаются средние по одному ключу между двумя нодами и так далее.
Здравствуйте, Sharowarsheg, Вы писали:
S>Это зависит от конкретных данных. Объединённое среднее не обязательно будет максимальным, но нам и не нужно, чтобы оно было максимальное. Нам только нужно заметно уменьшить число пересылок. Насколько его получится уменьшить, будет зависеть от того, сколько пересекающихся ключей между нодами, сколько чисел на каждой стороне, насколько отличаются средние между собой, насколько отличаются средние по одному ключу между двумя нодами и так далее.
Все ключи пересекаются, ключей сотни миллионов (иначе зачем алгоритмы городить), по каждому ключу несколько тысяч значений, поэтому средние могут быть любыми.
Здравствуйте, scf, Вы писали:
scf>Все ключи пересекаются, ключей сотни миллионов (иначе зачем алгоритмы городить), по каждому ключу несколько тысяч значений, поэтому средние могут быть любыми.
Тогда тестировать надо. Скачать себе все ноды, и прогнать тест на них, сколько пересылок получится до остановки. И распределения неплохо бы построить, типа, как выглядят средние на каждой ноде после сортировки, в зависимости от порядкового номера в отсортированном массиве. Чем больше наклон, тем меньше пересылок нужно.
scf>Наверное, я неудачно объяснил. Это распределенная СУБД, и минимизировать нужно трафик между нодами кластера. Например, для суммы достаточно с каждой ноды скачать 100 самых больших строк плюс ключи, полученные с остальных нод. Итого 100*node_count строчек с каждой ноды. Вопрос, как оптимизировать расчет среднего.
Вообще, обычно для таких случаев оптимизируют структуру базы — хранят все значения для ключа на одном узле. В графовых базах обычно так делают, для вершины A хранят все ребра вида A --> B на том же узле. В общем случае тяжело подсчитать — среднее же нерегулярная вещь, по локальной выборке конечное значение не предскажешь. Если бы было известно распределение значений для ключей, то можно было вероятностные методы использовать. Для нормального распределения считать доверительные интервалы и т.п. А так map/reduce и никуда не денешься.
Здравствуйте, scf, Вы писали:
scf>Есть два множества с парами ключ-значение, где ключ неуникален, а значение числовое. scf>Если оба множества объединить в одно, посчитать среднее арифметическое по ключу, отсортировать получившиеся ключи по среднему арифметическому и взять первые 100 строк, то мы получим 100 ключей с максимальным средним. scf>Вопрос: как найти эти ключи или хотя бы кандидатоов на эти ключи, не считая среднее по всем ключам?
Вам быстро или точно?
Для A { k=>v } и B { k=>v }
Строим третье множество C k=>{ n,m }
Для пробегаем по всем элементам A и B
для не существующих ключей k=>value пишем { n=1, m=value } иначе { n=n+1, m=(m*n+value)/(n+1) }
Затем делаем вычисляем nth_element(100) по m эти полученные 100 элементов можно отсортировать.
Если надо не по всем то делаем тоже самое, но для случайной выборки.
Здравствуйте, scf, Вы писали:
scf>Есть два множества с парами ключ-значение, где ключ неуникален, а значение числовое.
scf>Если оба множества объединить в одно, посчитать среднее арифметическое по ключу, отсортировать получившиеся ключи по среднему арифметическому и взять первые 100 строк, то мы получим 100 ключей с максимальным средним.
scf>Вопрос: как найти эти ключи или хотя бы кандидатоов на эти ключи, не считая среднее по всем ключам?
Никак в общем случае, потому что чтобы не считать среднее по всем ключам, нужно хранить ограниченный набор данных. Например, когда мы решаем задачу top-N, мы храним N лучших значений, а остальные вытесняем. Но тут так не сработает, потому что в начале прохода может быть ключ с очень маленьким значением, а в конце — этот же ключ, но с очень большим значением, и он обязан будет присутствовать в результативной выборке. Нужно смотреть на контекст задачи и оптимизировать по месту.
scf>>Вопрос: как найти эти ключи или хотя бы кандидатоов на эти ключи, не считая среднее по всем ключам?
C>Никак в общем случае,
при решении подобной задачи применил инкрементальный пересчет 1 раз в сутки по новым значением и объединение по определенной схеме с предыдущими результатами.
при этом получается только 1 тяжелый прогон (первый, начальный) по всем значениям, далее уже быстро и мало только по новым.
Здравствуйте, paradok, Вы писали:
P>при решении подобной задачи применил инкрементальный пересчет 1 раз в сутки по новым значением и объединение по определенной схеме с предыдущими результатами. P>при этом получается только 1 тяжелый прогон (первый, начальный) по всем значениям, далее уже быстро и мало только по новым.
Это же работает только для конкретной агрегации? А у меня композитный ключ из 3 иерархических классификаторов с набором уровней в каждом.
Здравствуйте, scf, Вы писали:
scf>Здравствуйте, paradok, Вы писали:
P>>при решении подобной задачи применил инкрементальный пересчет 1 раз в сутки по новым значением и объединение по определенной схеме с предыдущими результатами. P>>при этом получается только 1 тяжелый прогон (первый, начальный) по всем значениям, далее уже быстро и мало только по новым.
scf>Это же работает только для конкретной агрегации? А у меня композитный ключ из 3 иерархических классификаторов с набором уровней в каждом.
я про ваш первый пост.
Вы сделайте модель вашей проблемы вот тут например dbfiddle.uk
и сформулируйте ваш новый вопрос с новыми вводными данным...
пока непонятно почему в вашем случае с вашими новыми вводными данными инкрементальность невозможна?
Здравствуйте, scf, Вы писали:
scf>Здравствуйте, Sharowarsheg, Вы писали:
S>>Я бы думал что-то о том, что нужно посчитать сначала ноды отдельно
scf>Это было бы идеально — если бы мы могли заранее предсказать в рамках одной ноды, какие ключи попадут в результат и вытягивать из базы только их. Но так не получится — если взять два максимальных средних с каждой ноды, то объединенное среднее вовсе не обязательно будет максимальным. Я пробовал исследовать это явление математически, но там всплывают квадратичные системы неравенств с кучей переменных, а я не умею их решать.
Вероятно, вы пытались найти критерий для точного решения. Но, ключ дающий максиму для суммарного множества, может быть средним в каждом отдельном множестве. Например:
Т.е. вам нужно обменяться, минимму, половиной данных с одной ноды, чтобы правильно найти максимум.
Можно обмениваться не сырыми, а сводными данными (число и сумма значений для каждого ключа), это сократит объем пересылки в 10^3 раз, но он останется большим.
Поможет только знание статистических закономерностей исходных данных, и переход от поиска гарантированно точного решения, к решению с найденному с высокой вероятностью.
Например:
Если число значений для заданного ключа =N (~10^3), и его значения распределены нормально, с дисперсией D, то среднее посчитанное по половине случайно выбранных точек, отличается от общего среднего на D * (N/2)^(-0.5) (среднеквадратичное отклонение).
Т.е. можно собрать статистику для каждого ключа (по множествам отдельно), найти top100 по средним. Пусть 100й член (по данным node1) имеет среднее =q.
Тогда со второго узла достаточно запросить статистику только по ключам, для которых S[node2,i]+3*D[node2,i]*N[node2,i]^(-0.5) >= q. (А также, для ключей, которые входят в top100 node1.)
Проблемы могут быть только с узлами, для которых слишком мало точек или статистика распределена неравномерно.
Можно отдельно передать все ключи для которых число точек мало N[node2,i]<10. (Конкретное число нужно подбирать по конкретной статистике, поскольку они могут не подчиняться нормальному распределению).
Здравствуйте, Chorkov, Вы писали:
C>Вероятно, вы пытались найти критерий для точного решения. Но, ключ дающий максиму для суммарного множества, может быть средним в каждом отдельном множестве. Например:
