Konstante Zeit Binning von Werten

Question

Angenommen, ich habe einen Vektor von Werten, die die oberen Grenzen von Klassen zu klassifizieren (bin) Werte in. Also z.B. Der Vektor {1, 3, 5, 10} repräsentiert Bins [0, 1 [, [1, 3 [, [3, 5 [und [5,10 [. Wie implementiere ich die Klassifikation eines Zufallswertes V in einer dieser Klassen (0,1,2,3) in konstanter Zeit? Es ist trivial, die Liste der Grenzen zu gehen und zu stoppen, sobald V die obere Grenze des Behälters überschreitet; aber das ist O (n) bezüglich der Anzahl von Behältern; Ich versuche, dies in konstanter Zeit zu tun.

Ich dachte, es war trivial, bevor ich tatsächlich den Code eintippte, indem ich eine Nachschlagetabelle aufstellte, jedes V durch einen bestimmten Wert in Abhängigkeit von den Klassengrenzen dividierte und dann das (gerundete) Ergebnis der Division verwendete Fachnummer in der Nachschlagetabelle. Aber ich finde es viel schwieriger, als ich gedacht habe, dies auf eine allgemeine Art und Weise zu machen, die die Größe der Nachschlagetabelle minimiert, während sie immer noch genau ist, ungeachtet des proportionalen Abstandes zwischen Fachgrenzen; und in einer Weise, die für alle realen Werte funktioniert. Mit Google finde ich nur Algorithmen, die die Grenzen der Bins bestimmen, zumindest unter Verwendung der Begriffe, die ich gemacht habe.

Answer 1

Ich bezweifle, dass es einen Weg gibt, dies in streng konstanter Zeit zu tun (und keinen unendlichen Raum zu erfordern), ohne irgendeine Eigenschaft der gegebenen Zahlen auszunutzen.

---

Eine Nachschlagetabelle ist eine vernünftige Idee, aber Gleitkommawerte macht dies schwierig. Wenn die Anzahl der Stellen endlich ist, können Sie die Lookup-Tabelle als im Wesentlichen eine trie (eine Struktur, bei der jede Ebene eine Ziffer darstellt) darstellen.

Also für {1, 2.5, 5, 9}, würde Ihr Baum in etwa so aussehen:

       root 
//  /  /| \ \ \ \ \ 
0 1   2   3 4 5 6 7 8 9 
     / |  \ 
     2.0 ... 2.5 ... 2.9 

Jeder Blattknoten einen Wert enthalten würde angibt, der es gehört zu Intervall, so
0 wird auf 0 gesetzt werden,
1 , 2,0-2,4 werden alle auf 1 gesetzt werden,
2,5 bis 2,9, von 3 bis 4 wird auf 2 gesetzt werden,
5 bis 9 wird eine Abfrage würde nur involv bis 3

eingestellt werden Wir beginnen mit der Wurzel und gehen wiederholt zum Kind-Knoten, der der nächsten Ziffer in der Nummer entspricht, die wir suchen. Wenn Sie 2,65 im obigen Baum nachschlagen, gehen Sie zuerst zu 2, dann zu 2,6, denn es ist ein Blatt, du hörst auf und gibst es zurück, was 1 ist. Die Zeitkomplexität für eine Abfrage wäre O(d), wobei d die Anzahl der signifikanten Stellen in Ihrem Vektor und die Komplexität des Platzes O(nd) ist

Das ist nicht besonders effizient klingen mag, aber denken Sie daran, dass d die Anzahl der Ziffern ist - zum Beispiel, dass d = log m mit m wäre der maximal mögliche Wert sein, wenn wir über positive ganze Zahlen sprechen sind.

---

O(log n) ist ziemlich trivial, wenn man nur einrichten ein binary search tree (BST) alle Werte in dem Vektor in ihren ursprünglichen Indizes abgebildet enthält.

Ein Lookup würde sehr ähnlich aussehen, wie Sie eine BST suchen würden - beginnen Sie von der Wurzel aus und gehen Sie entweder nach links oder rechts, bis Sie den Wert finden, außer in diesem Fall notieren Sie jeden von Ihnen besuchten Knoten und geben den zugeordneten Index zurück der nächstliegende Wert, der nicht größer ist. Einige APIs haben Methoden, die das für Sie tun (wie std::map in C++).

Answer 2

Ich denke, der einzige Weg, um O (1) zu erhalten, ist eine Nachschlagetabelle zu erstellen, so dass Sie alle Werte direkt nachschlagen können.

Dies ist nur machbar, wenn die Grenzen gut verhalten:

1. Die erwarteten Zahlen ganze Zahlen sind oder die Grenzen sind ganze Zahlen oder haben eine begrenzte Genauigkeit. Auf diese Weise können Sie die Nummer abrunden (flood), bevor Sie sie mit der Nachschlagetabelle vergleichen, und die erforderlichen Einträge für die Tabelle drastisch reduzieren.

2. Der Unterschied zwischen der Max- und Min-Grenze darf nicht zu groß sein. Nehmen wir an, wir wissen, dass die Genauigkeit der Grenzen 0,5 ist und das Minimum ist 1 und das Maximum ist 10, dann benötigt die Nachschlagetabelle (10-1)/0,5 = 18 Einträge.

Die Kontrollen für die erste und die letzte Gruppe (kleiner als min und mehr als max) mit einfacher gemacht, wenn überprüft, welche nicht der Komplexität beeinflussen.