Существует ли эвристический алгоритм для подсчета groupBy +? - PullRequest
Новая
       11

Существует ли эвристический алгоритм для подсчета groupBy +?

0 голосов
/ 14 ноября 2018

Я получил список целых чисел, и я хочу подсчитать, сколько раз каждое целое число появляется в списке.

Например: [0,5,0,1,3,3,1,1,1] дает (0 -> 2), (1 -> 4), (3 -> 2), (5 -> 1).Мне нужен только счет, а не значение (цель состоит в том, чтобы получить гистограмму отсчетов).

Обычным подходом было бы группировать по значению, а затем считать количество элементов каждого набора.В SQL: SELECT count(*) FROM myTable GROUPBY theColumnContainingIntegers.

Есть ли более быстрый способ сделать это?Эвристический или вероятностный подход - это хорошо, так как я вычисляю большой набор данных и жертвую точностью ради скорости.

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

1 Ответ

0 голосов
/ 02 декабря 2018

Давайте возьмем ваш набор, содержащий 9 элементов [0,5,0,1,3,3,1,1,1], и сделаем его большим, но с одинаковыми частотами элементов: 

> bigarray = [0,5,0,1,3,3,1,1,1] * 200
 => [0, 5, 0, 1, 3, 3, 1, 1, 1, 0, 5, 0, 1, 3, 3, 1, ...

Теперь размер биг-массива равен 1800, поэтому давайте попробуем с ним поработать.

Возьмите выборку из 180 элементов (случайных 180 элементов из этого набора)

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

{5=>19, 3=>45, 1=>76, 0=>40}

Нормализовано: 

{5=>1.0, 3=>2.3684210526315788, 1=>4.0, 0=>2.1052631578947367}

ИзКонечно, для разных случайных подмножеств результаты будут разными: 

{5=>21, 3=>38, 1=>86, 0=>35}

Нормализовано 

{5=>1.0, 3=>1.8095238095238095, 1=>4.095238095238095, 0=>1.6666666666666667}

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

Теперь выполните такой же тест для bigarray (размер 1000) с 50% от 0 и 50% от 1 

 > bigarray = [0,1] * 500
 => [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  ...

С выборкой из 100 элементов: 

{0=>50, 1=>50}

Нормализовано 

{0=>1.0, 1=>1.0}

Второй образец: 

{0=>49, 1=>51}

Нормализовано 

{0=>1.0, 1=>1.0408163265306123}

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

Особенно Выборка из резервуара - это может бытьОчень полезно, если в вашем случае данные заполнены «вживую» или слишком велики, чтобы обрабатывать все значения одновременно.

edit

Относительно комментария: Конечно, если выЕсли у вас большой набор, и какой-то элемент появляется там очень редко, тогда вы можете потерять его, и вхождение будет равно 0.

Тогда вы можете использовать вид функции сглаживания (отметьте аддитивное сглаживание ).Просто предположим, что каждый возможный элемент 1 больше времени, чем он был на самом деле.

Например, допустим, мы установили: 

1000 elements 1
100 elements 2
10 elements 3
1 elements 4

Допустим, наше подмножество содержит {1 => 100,2 => 10,3 => 1, 4 => 0}

Параметр сглаживания = 0,05, поэтому мы добавляем 0,05 к каждому вхождению

{1 => 100,05,2 => 10,05,3 =>1,05, 4 => 0,05}

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

...