Als ich mir vorstellte, was ich implementieren wollte, wurde es notwendig, "die Bits mit der ganzen Zahl 1 zu zählen". Ich bemerkte jedoch, dass die Implementierung in Ruby ziemlich langsam war, und entschied mich daher, sie in C-Sprache usw. zu implementieren (jkr2255 / bit_counter).
Vor kurzem wurde es zu einem CPU-Befehl namens "POPCNT" (später beschrieben), und als ich dachte, dass jemand ihn implementiert hatte, stellte ich überraschenderweise fest, dass "Bignum" fast unberührt blieb.
"Wenn du keine hast, kannst du es selbst machen!"
Im Fall von Ruby erlaubt die Ganzzahl (konzeptionell) unendliche Ziffern, und die negative Zahl ist eine Komplementdarstellung von 2, so dass das Vorzeichenbit 1 ** unendlich ** ist. Wie erwartet ist das Zählen der Anzahl von Einsen in diesem Zustand "unendlich" und bedeutungslos. Wenn es sich also um eine negative Zahl handelt, "Zählen Sie die Anzahl von Nullen und geben Sie sie als Minus zurück". [^ 1].
Wenn Sie eine Erweiterung in C-Sprache vornehmen, wird JRuby nicht unterstützt. In diesem Fall gab es jedoch Methoden wie "Long.bitCount ()" und "BigInteger # bitCount ()" auf der Java-Seite, also Call this. jkr_2255 / items / 33b1eb1b2d4099ca1c67) war fast fertig.
Wenn der Build der C-Erweiterung jedoch mit JRuby beginnt, tritt ein Fehler auf. Fügen Sie daher einen bedingten Zweig hinzu, um festzustellen, ob es sich um JRuby mit "Rakefile" oder "gemspec" handelt, und generieren Sie ein separates Gem für JRuby zu RubyGems. Ich musste pushen.
Ruby-Ganzzahlen sind unterteilt in "Fixnum" und "Bignum", aber "Fixnum" kann leicht eine Ganzzahl in C-Sprache sein, daher sollten Sie dies tun. Das ist
Bignum in ein Bit-ArrayDiese zwei.
Überprüfen Sie zunächst mit CPUID, ob der in SSE 4.2 eingeführte Befehl POPCNT verwendet werden kann, und zählen Sie mit POPCNT [^ 2], wenn er gültig ist. Wenn nicht, verwenden Sie das in GCC integrierte "__builtin_popcountl ()", andernfalls verwenden Sie eine handschriftliche Version der Zählfunktion.
Wenn Sie den Vorgang mit "Bignum" fortsetzen, wird jedes Mal ein Objekt erstellt, und die Geschwindigkeit wird überhaupt nicht ausgegeben. Sobald Sie also von "Bignum" in ein numerisches Array konvertieren, gibt es zwei Funktionen, "rb_big_pack" und "rb_integer_pack", abhängig von der Version von Ruby, und welche gültig ist, kann unterschiedlich sein. Wenn die Kapazität des Konvertierungspuffers klein ist, wird "ALLOCA" anstelle von "ALLOC" verwendet, um Overhead für den Stapel zu vermeiden (tatsächlich ist dies allein für kleine Zahlen 30% schneller).
Wenn Sie das Array eingeben, zählt der Rest, aber in der Windows x64-Umgebung ist "long" 32 Bit breit, sodass der Zeiger gelesen wird, damit der 64-Bit-Befehl "POPCNT" verwendet werden kann.
Im Vergleich zu den häufig verwendeten "num.to_s (2) .count (" 1 ")" war es 5 bis 20 Mal schneller (auf Maschinen mit POPCNT-Anweisungen).
Ichiou Rubinius funktioniert auch, aber es wird nicht viel schneller, also denke ich über etwas nach, das nicht getan werden kann.
[^ 1]: Javas "BigInteger # bitCount ()" gibt die Anzahl der Bits zurück, die "vom Vorzeichenbit verschieden" sind. Das heißt, es wird auch ein positiver Wert für negative Zahlen zurückgegeben. [^ 2]: Es scheint, dass es etwas schneller sein wird, wenn Sie AVX usw. verwenden, um begeistert zu werden, aber ich habe nicht so viel getan.
Recommended Posts