Effizientes Mapping von 2^24 Werten auf einen 2^7 Index

Question

Ich habe eine Datenstruktur, die unter anderem einen 24 Bit breiten Wert speichert. Ich habe viel dieser Objekte.

Um die Speicherkosten zu minimieren, berechnete ich die 2^7 wichtigsten Werte aus den 2^24 möglichen Werten und speicherte sie in einem statischen Array. Daher muss ich nur einen 7-Bit-Index für dieses Array in meiner Datenstruktur speichern.

Das Problem ist: Ich bekomme diese 24-Bit-Werte und muss sie im laufenden Betrieb in meinen 7-Bit-Index umwandeln (keine Vorverarbeitung möglich). Die Berechnung ist im Grunde eine Suche, bei der einer von 2^7 Werten am besten passt. Offensichtlich braucht dies einige Zeit für eine große Anzahl von Objekten.

Eine naheliegende Lösung wäre, ein einfaches Mapping Array von Bytes mit der Länge 2^24 zu erstellen. Aber das würde 16 MB RAM benötigen. Zu viel.

Eine Beobachtung des 16 MB-Arrays: Im Durchschnitt sind 31 aufeinanderfolgende Werte gleich. Leider gibt es auch eine Anzahl von aufeinanderfolgenden Werten, die unterschiedlich sind.

---

Wie würden Sie diese Umwandlung von einem Wert von 24-Bit-Implementierung auf einen 7-Bit-Indices wie viel CPU und Speicher wie möglich zu speichern?

Answer 1

Eine andere Idee wäre, Ihre wichtigen Werte in ein anderes Array zu setzen, dann suchen Sie einfach zuerst. Wenn Sie dort keine akzeptable Antwort finden, dann können Sie, shudder, das größere Array suchen.

Answer 2

Wie viele 2^24 haben Sie? Können Sie diese Werte sortieren und sie zählen, indem Sie die Anzahl der aufeinander folgenden Werte zählen.

Answer 3

Schwer zu sagen, ohne zu wissen, was die Definition von "am besten passt". Vielleicht würde eine kd-tree eine geeignete Suche basierend auf der Nähe von einigen metrischen oder anderen erlauben, so dass Sie schnell die meisten Kandidaten ausschließen, und nur einige der 2^7 tatsächlich testen müssen, um zu sehen, welche die beste ist?

Das klingt ähnlich wie das Problem, das ein Bildprozessor beim Reduzieren auf eine kleinere Farbpalette hat. Ich weiß eigentlich nicht, welche Algorithmen/Strukturen dafür verwendet werden, aber ich bin mir sicher, dass sie nachschlagefähig sind und helfen könnten.

Answer 4

Als eine Idee ... Die Indextabelle auf 8 Bits auf, dann xor oder alle 3 Bytes des 24-Bit-Wortes hinein. dann würde Ihre Tabelle aus diesem 8-Bit-Hash-Wert plus dem Index zurück zu dem ursprünglichen 24-Bit-Wert bestehen.

Da Ihre Daten RGB-ähnlich sind, kann eine komplexere Hash-Methode erforderlich sein.

---

bit24var  & 0x000f gives you the right hand most char. 
(bit24var >> 8) & 0x000f gives you the one beside it. 
(bit24var >> 16) & 0x000f gives you the one beside that. 

---

Ja, Sie denken richtig. Es ist sehr wahrscheinlich, dass einer oder mehrere der 24-Bit-Werte aufgrund der pigeon hole principal auf denselben Index hashen.

Eine Methode zum Auflösen eines Hash-Konflikts besteht darin, eine Art Verkettung zu verwenden.

Answer 5

Da Sie bereits wissen, welchen der 2^24 Werte Sie behalten müssen (dh die 2^7 Werte, die Sie als wichtig erachtet haben), können wir einfach nur eingehende Daten filtern und einen Wert zuweisen, beginnend mit 0 und bis zu 2^7-1, zu diesen Werten, wenn wir ihnen begegnen. Natürlich würden wir einen Weg brauchen, um zu verfolgen, welche der wichtigen Werte wir bereits gesehen und in [0,2^7] bereits vergeben haben. Dafür können wir eine Art von Baum- oder Haschtabellen-basierter Wörterbuchimplementierung verwenden (z. B. std::map in C++, HashMap oder TreeMap in Java oder dict in Python).

Der Code könnte wie folgt aussehen (ich einen viel kleineren Bereich von Werten):

import random 

def make_mapping(data, important): 
    mapping=dict() # dictionary to hold the final mapping 
    next_index=0 # the next free label that can be assigned to an incoming value 
    for elem in data: 
     if elem in important: #check that the element is important 
      if elem not in mapping: # check that this element hasn't been assigned a label yet 
       mapping[elem]=next_index 
       next_index+=1 # this label is assigned, the next new important value will get the next label 
    return mapping 

if __name__=='__main__': 
    important_values=[1,5,200000,6,24,33] 
    data=range(0,300000) 
    random.shuffle(data) 
    answer=make_mapping(data,important_values) 
    print answer 

Sie die Suche viel schneller machen können für den Satz Hash/Baum basierten Set-Datenstruktur unter Verwendung von von wichtigen Werten. Das würde die gesamte Prozedur O(n*log(k)) (oder O(n), wenn es eine Hashtabelle ist) machen, wobei n die Größe der Eingabe und k die Menge wichtiger Werte ist.

Answer 6

Eine weitere Idee besteht darin, das 24BitValue-Array in einer Bitmap darzustellen. Ein nettes Zeichen ohne Vorzeichen kann 8 Bits enthalten, also benötigt man 2^16 Array-Elemente. Das ist 65536. Wenn das entsprechende Bit gesetzt ist, dann wissen Sie, dass dieser spezifische 24BitValue im Array vorhanden ist und überprüft werden muss.

Man benötigt einen Iterator, um durch das Array zu gehen und das nächste gesetzte Bit zu finden. Einige Maschinen bieten tatsächlich eine Operation "erstes Bit finden" in ihrem Befehlssatz.

Viel Glück auf Ihrer Suche. Lassen Sie uns wissen, wie sich die Dinge entwickeln.

Böse.