Finden Sie den Modus eines Arrays von Fließkommazahlen mit Hashing

Question

Ich habe vor kurzem gelesen, dass eine Methode mit Hashing eine gute Möglichkeit, den Modus eines Arrays von Gleitkommazahlen zu finden. Ich weiß nicht viel über Hashing oder seine Anwendungen und der Text hat nicht weiter erklärt.

Weiß jemand, was diese Methode beinhalten würde?

Answer 1

Nicht viel von einem Statistik-Typ, the mode in diesem Sinne scheint als "der Wert, der am häufigsten auftritt" definiert werden.

Aus dieser Beschreibung scheint es die offensichtliche Möglichkeit, dies unter Verwendung einer Hash-Tabelle zu implementieren, die Nummer als einen Schlüssel zu verwenden und als den gespeicherten Wert einen Frequenzzähler zu verwenden.

Dann durch jede Zahl nur Schleifen in Python Pseudo-Code wäre dies so etwas wie:

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 

Dann den größten Wert extrahieren, die Sie benötigen würden, und die entsprechende Taste finden:

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

Dies erstellt eine sortierte Liste von (Wert, Schlüssel) Paaren, sortiert nach Wert, und extrahiert dann den Schlüssel (1) aus dem letzten ([-1]) Paar.

Ich habe mich nicht mit einem defaultdict oder ähnlichem beschäftigt, zur Veranschaulichung denke ich, dass die if eher hilfreich ist.

HINWEIS: Ich kann nicht garantieren, dass dies der kanonische Weg zur Lösung des Problems ist. Das ist genau das, was ich tun würde, wenn jemand mich auffordert, das Problem zu lösen (und vielleicht angedeutet hat, dass die Verwendung eines Hashes eine gute Idee ist).

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 

ich gegen die Verwendung eines Hash raten würde, da es genaue Vergleiche geht davon aus - nie eine gute Annahme auf Gleitkommazahlen. Du willst immer eine epsilon comparison von einer Art machen. Was ist, wenn Ihr Array einige Elemente 0.2(00000000) und 0.2(00000001) enthält, die wirklich als gleichwertig betrachtet werden sollten, aber nicht, weil sie aus unterschiedlichen Berechnungen stammen?

Praktisch, J tut immer epsilon-Vergleich standardmäßig. Zu bequem, versteckte es in den /.~ da und ich muß mehr Code schreiben, um zu zeigen, wie diese wie Python in anderen Sprachen zu tun ...

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]