Vergleichen Float-Array als int-Array

Question

Ich brauche einen optimierten binären Suchalgorithmus auf einem Array von sortierten Zahlen. Ich tat dies und stellte fest, dass zum Speichern von Zahlen mit Schwimmer ist schneller als ganze Zahl verwenden, weil am Ende i

(frameNumber-this->frameNumber[imin])/(this->frameNumber[imax]-this->frameNumber[imin]) 

this->frameNumber[imin] berechnen muss, ist der größte framenumber weniger gleich, dass frameNumber und this->frameNumber[imax] ist die kleinste größer gleich als Das. Dieser Code soll den Fortschritt zwischen diesen beiden Keyframes berechnen. Das frameNumber-Array ist statisch. Ich muss es nur einmal sortieren. Aber greifen Sie mehrmals darauf mit einer binären Suche und dem obigen Code zu, um den Fortschritt zu berechnen.

Die Konvertierung von int nach float verbrachte einige Zyklen. Dann entdeckte ich, dass in der asm eine Menge von fpu Anweisungen. Ich mache mir Sorgen, dass sie langsamer als Integer sind.

Also hier ist die Frage. Kann ich ein Array von sortierten Fließkommazahlen in ein int * umwandeln und eine binäre Suche darauf ausführen?

Das heißt:

void binary_search(float key,float* array,...) 
{ 
    int key_integer=*(int*)&key; 
    int* array_intege(int*)array; 
    binary_search_for_integers(key_integer,array_integer,...); 
} 

Oder meine obige Schlussfolgerung falsch sind? (Wie Gießen int zu schwimmen ist nicht so costy oder Vergleich zwischen floating Punkten ist das gleiche schnell wie ganze Zahlen?

Vielen Dank!

Answer 1

Diese wie eine schlechte Idee zu sein scheint. Integer Mit vergleicht auf float Daten tatsächlich führt in einer richtig geordneten Anordnung von Schwimmern, wie @rlbond hinweist. (Siehe http://www.h-schmidt.net/FloatConverter/IEEE754.html mit den binären Darstellungen von Schwimmern zu spielen.), dass sizeof(int32_t) == sizeof(float) überprüfen Sie vor diesem.

ein Hack wie das ist nicht wirklich nötig. float Vergleich ist nicht viel teurer als int Vergleich, auf moderner Hardware. (Intel Haswell: ucomiss ist 1 Up, mit 1 pro Zyklus Durchsatz. Vergleichen mit einem Speicheroperanden ist 2 Ups, keine Mikro-Fusion, obwohl. Und es kann nicht Makro-Fuse wie cmp/jcc) FP add/sub und FP mul haben höhere Latenzen als ihre Integer-Äquivalente und weniger Durchsatz. Es scheint albern zu sein, ein ganzes Array in float umzuwandeln, während du es schreibst, nur weil du am Ende eine FP-Mathematik mit den Min- und Max-Werten machen willst.

Ein Befehl load-and-convert-int-float (x86 cvtsi2ss (signed-integer 2 skalare single)) ist ungefähr so ​​schnell und benötigt den gleichen Coderaum wie eine normale Ladung (movss).

Wenn Ihre Daten ursprünglich Integer waren und Sie nur einen Teil davon verwenden, verwenden Sie int (vermeiden Sie die Konvertierung für Werte, die Sie später nicht benötigen). Wenn Sie auf alles zugreifen und Ihre Daten nur als Floats verwenden, speichern Sie sie unter float. Wenn Sie es als beides verwenden, ist es wahrscheinlich am besten, es als int zu speichern, also ist es schneller, wenn Sie es als Integer verwenden, und ungefähr die gleiche Geschwindigkeit, wenn Sie es als float verwenden.

Aus Ihrem Codebeispiel verwenden Sie nur die Werte an den Min- und Max-Positionen? Es ist viel schneller, die Min- und Max-Werte in einem Array zu finden, als das gesamte Array zu sortieren. min/max vektorisiert sogar mit gepackten min Anweisungen.

Viele Plattformen haben nicht so schnelle Fließkommazahl wie moderne Intel-CPUs, also sollten Sie nicht mit Floating Point über Bord gehen.