Найти режим массива чисел с плавающей точкой, используя хеширование

Question

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

Кто-нибудь знает, что подразумевается под этим методом?

Answer 1

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

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

Затем просто переберите каждое число, в псевдокоде Python это будет примерно так:

array = [1.0, 1.2, 0.4, ...] # A bunch of numbers
counts = {}
for a in array:
  if a in counts:
    counts[a] += 1
  else:
    counts[a] = 1

Тогда вам нужно извлечь наибольшее значение и найти соответствующий ему ключ:

sorted([(v, k) for k, v in counts.items()])[-1][1]

Это создает отсортированный список пар (значение, ключ), отсортированных по значению, а затем извлекает ключ (<a href="http://en.wikipedia.org/wiki/Mode_%28statistics%29" rel="nofollow noreferrer">1</a>) из последней ([-1]) пары.

Я не удосужился использовать defaultdict или эквивалент, для иллюстрации я думаю, что if довольно полезен.

ПРИМЕЧАНИЕ: Я не даю никаких гарантий, что это канонический способ решения проблемы. Это то, что я сделал бы, если бы кто-то попросил меня решить проблему (и, возможно, намекнул, что использование хэша - хорошая идея).

Answer 2

J

   NB. random array of floating-point numbers
   ] y =: 10 (?@$%]) 5
0 0.6 0.2 0.4 0.4 0.8 0.6 0.6 0.8 0
   NB. count occurrences
   ({:,#)/.~ y
  0 2
0.6 3
0.2 1
0.4 2
0.8 2
   NB. order by occurrences
   (\:{:"1)({:,#)/.~ y
0.6 3
  0 2
0.4 2
0.8 2
0.2 1
   NB. pick the most frequent
   {.{.(\:{:"1)({:,#)/.~ y
0.6

Я бы посоветовал не использовать хеш, поскольку он предполагает точное сравнение - никогда не хорошее предположение для чисел с плавающей запятой. Вы всегда хотите сделать сравнение эпсилон в некотором роде. Что если в вашем массиве есть некоторые элементы 0.2(00000000) и 0.2(00000001), которые на самом деле следует считать равными, но не потому, что они получены из разных вычислений?

Удобно, J всегда выполняет эпсилон-сравнение по умолчанию. Слишком удобно, поскольку он скрыт в /.~, и мне нужно написать больше кода, чтобы продемонстрировать, как это сделать на других языках, таких как Python ...

epsilon = 0.0001
def almost_equal(a, b):
    return -epsilon <= a-b <= epsilon

array = [0.0, 0.6, 0.2, 0.4, 0.4, 0.8, 0.6, 0.6, 0.8, 0.0]

# more efficient would be to keep this in sorted order,
# and use binary search to determine where to insert,
# but this is just a simple demo
counts = []
for a in array:
    for i, (b, c) in enumerate(counts):
        if almost_equal(a, b):
            counts[i] = (b, c + 1)
            break
    else:
        counts.append((a, 1))

# sort by frequency, extract key of most frequent
print "Mode is %f" % sorted(counts, key = lambda(a, b): b)[-1][0]