Ruby: die Anzahl der 1 ist eine binäre Zahl,

Habe ich eine binäre Zahl (52 bits) als Zeichenfolge dargestellt "01100011...."

Was wäre der Schnellste Weg, um die Anzahl der 1 ist?

"01100011....".count("1")

offensichtlich funktioniert, ist aber sehr zeitaufwendig, wenn diese Arbeit getan werden muss, um Tausende Male.

ok, ein paar mehr Infos. Ich bin versucht zu erstellen-bit-Vektoren für die Worte wie folgt

def bit_vec(str)
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    bv = ""
    alphabet.each_char do |a|
        if str.include?(a)
            bv += "1"
        else
            bv += "0"
        end
    end
        bv
end

Den bit_vec Methode aufgerufen wird, wird über 170K Zeiten. Ich speichern die bit-Vektoren in einer hash-und nutzen Sie, um zu finden, die ähnliche Wörter zu einem gegebenen Wort von XOR ' Ing des bit-Vektoren und zählen der Anzahl von 1 (mehr 1 == weniger ähnlichkeit). Wenn die count-Methode verwenden, die nicht mit String#scan die was anderes nutzen könnte?

Ich weiß, Ruby ist langsamer als beispielsweise C oder Java. Ich bin gerade auf der Suche zur Verbesserung der Algorithmus, die beste, die ich kann. Ich bin nicht auf der Suche für roh-Geschwindigkeit.

Vielleicht ist das enthalten? Methode ist der Engpass?

  • Anstelle der bit-Vektoren, könnte ich versuchen, die Speicherung der strings, die als array von Buchstaben und tun so etwas wie dieses (["a", "b", "c"] & ["x","b","x"]).Größe
InformationsquelleAutor Maulin | 2009-10-28
  1. 9

    Beachten Sie, dass das problem der Zählung der 1-bits bezeichnet man als "population count".

    Zumindest in Ruby, bleiben Sie bei Umgang mit diesen als string über die count Methode, es sei denn, Sie haben einen zwingenden Grund für die Verwendung von Ganzzahlen.

    count:

    Benchmark: 78.60 s für zu 10.000.000 Iterationen (127,225.63 Iterationen pro Sekunde)

    Bei integer-math,

    Wenn Sie kümmern sich nicht um die oben genannten Werte 2**32,

    def popcount(x)
  m1 = 0x55555555
  m2 = 0x33333333
  m4 = 0x0f0f0f0f
  x -= (x >> 1) & m1
  x = (x & m2) + ((x >> 2) & m2)
  x = (x + (x >> 4)) & m4
  x += x >> 8
  return (x + (x >> 16)) & 0x3f
end

    Benchmark: 105.73 s für zu 10.000.000 Iterationen (94,579.03 Iterationen pro Sekunde)

    Wenn Sie kümmern sich um Werte, die über 2**32,

    def popcount(x)
  b = 0
  while x > 0
    x &= x - 1
    b += 1
  end
  return b
end

    Benchmark: 365.59 s für zu 10.000.000 Iterationen (27,353.27 Iterationen pro Sekunde)

    Nachtrag:

    Code:

    Benchmark: 78.25 s für 1.000.000 Iterationen (12,779.56 Iterationen pro Sekunde)

    Diesem code:

    def bit_vec(str)
  # alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  bv = "0" * 52
  str.each_char do |c|
    ord = c.ord
    next unless (ord >= 65 && ord <= 90) || (ord >= 97 && ord <= 122)
    index = ord - 65
    index -= 6 if index > 25
    bv[index] = "1"
    break if bv == "1111111111111111111111111111111111111111111111111111"
  end
  bv
end

    Hinweis: Sie sagte, dass Sie es mit einem 52-bit-Zahl, also bin ich davon ausgegangen, dass Sie kümmerte sich um die beiden groß-und Kleinbuchstaben (26 + 26 = 52). Entschied ich mich zu prüfen, für die Großbuchstaben zuerst, weil das ist, wie Sie erscheinen in so ziemlich jeden Zeichensatz immer, die Berechnung ein wenig einfacher.

    Benchmark: 24.86 s für 1.000.000 Iterationen (40,231.60 Iterationen pro Sekunde)

    3.14 x speed-up.

    • Vielen Dank für die ausführliche Antwort. Das half!
    InformationsquelleAutor Bob Aman
  2. 10

    Sind Sie gehen zu müssen O(n) Leistung, egal was. Versuchen Sie, diese einfache ruby-Befehl. Messen, ob es wirklich ein problem.

    Dieses einfache Skript, gemessen mit time ruby test.rb nahm 0.058 CPU-Sekunden. Dies ist auf eine alte 1,25 Ghz Prozessor. Sind Sie wirklich sicher, dass dieser Vorgang zu langsam?

    10000.times do
  "0100010000100001111101101000111110000001101001010".count("1")
end

    Wenn das nicht schnell genug schreiben Sie eine C-Erweiterung. Versuchen Sie zu vermeiden, mit Bedingungen. Schreiben Sie es wie folgt:

    count = 0;
for (i = stringLength; i; i++) {
    count += string[i] - '0';     // no conditional used.
}

    Aber ehrlich gesagt, wenn Sie müssen diese Art von Geschwindigkeit ruby ist die falsche Sprache für dich. Es gibt so viele verschiedene Dinge in ruby, die nehmen viel mehr Zeit als eine einfache .count("1").

    • Ich lief mein Programm mit rprofile und es zeigte sich, dass 38% der Zeit aufgewendet wird mittels String#scan (170K Anrufe). Ich dachte, dass wenn es eine clevere Art und Weise zu zählen, die 1, ich könnte in der Lage sein, die Dinge zu beschleunigen ein wenig.
    • Ich glaube nicht, dass .count() verwendet String#scan intern. Vielleicht ist dein Flaschenhals woanders ist.
    • Wie finde ich heraus, welche Methoden verwenden Sie String#scan-intern?
    • Verwenden Sie einen profiler, der Euch sagt, oder einen Blick auf die Quelle. ruby-lang.org/en/downloads
    • Für die Uneingeweihten, der Grund, Sie nicht zu Bedingungen ist die CPU-branch prediction findet, die in der Regel Abfall CPU-Zeit in einen sogenannten "pipeline stall": hat die CPU zu stoppen, die Annahme neuer Anweisungen in einer pipeline / reservation-station Weg, bis die pipeline ist klar, um zu berechnen die richtige (nicht vorhergesagte) Ergebnis. Insgesamt, obwohl, verwenden Sie ein anständiges profiler zu sein, dass die Reifen-Optimierung sorgt für eine messbare Verbesserung.
    InformationsquelleAutor Georg Schölly
  3. 3

    vom http://www.bergek.com/2009/03/11/count-number-of-bits-in-a-ruby-integer/

    yourString.scan(/1/).size

    vom http://snippets.dzone.com/posts/show/4233

    count = 0
count += byte & 1 and byte >>= 1 until byte == 0

    Hier ist ein post mit verschiedenen Schleifen (in c) für die Zählung der auf die Dichte von 0 vs. 1

    http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

    • scan(/1/).size ist mehr als 10 mal langsamer als count("1").
    • Ich getestet es und es ist wahr. String#count ist schnell!
    InformationsquelleAutor willoller
  4. 3

    Hier ist ein weiterer benchmark: https://gist.github.com/knugie/3865903

    Einfach führen Sie es auf Ihrem Computer, wenn Sie in Zweifel.

    Ruby sollte nicht verwendet werden, für die maximale Optimierung, aber die überprüfung für Engpässe in Ihrem code ist immer sinnvoll. Ein Algorithmus, der funktioniert gut in einem Bereich nicht notwendigerweise auch in einem anderen. Versuchen Sie, verwenden Sie echte Daten von Ihrer Anwendung für die Optimierung.

    Beispiel-AUSGABE:

    $ ruby bit_count_benchmark.rb 
CPU : Intel(R) Core(TM)2 Duo CPU P8400 @ 2.26 GHz 
MEM : 3083288 kB 
RUBY : ruby-1.9.2-p320 

"NORM": 
TEST... OK 
BENCHMARK (2000000): 
VORBEREITEN... OK 
LAUFEN... 
user system total real 
scan_string 227.770000 0.250000 228.020000 (227.912435) 
scan_regex 214.500000 0.220000 214.720000 (214.635405) 
progressive_right_shift 43.420000 0.030000 43.450000 ( 43.412643) 
continuous_right_shift 39.340000 0.010000 39.350000 ( 39.345163) 
count_string 19.910000 0.030000 19.940000 ( 19.932677) 
access_bit_fast 18.310000 0.040000 18.350000 ( 18.345740) 
bit_elimination_for 16.400000 0.010000 16.410000 ( 16.388461) 
bit_elimination_until 14.650000 0.000000 14.650000 ( 14.650187) 
bit_elimination_while 14.610000 0.000000 14.610000 ( 14.604845) 
pre_compute_16 4.370000 0.000000 4.370000 ( 4.371228) 

"NORM" FERTIG 


"LOTTO": 
TEST... OK 
BENCHMARK (2000000): 
VORBEREITEN... OK 
LAUFEN... 
user system total real 
scan_string 92.900000 0.100000 93.000000 ( 92.947647) 
scan_regex 79.500000 0.230000 79.730000 ( 79.671581) 
progressive_right_shift 43.430000 0.010000 43.440000 ( 43.424880) 
continuous_right_shift 35.360000 0.020000 35.380000 ( 35.360854) 
count_string 19.210000 0.020000 19.230000 ( 19.215173) 
access_bit_fast 17.890000 0.000000 17.890000 ( 17.890401) 
bit_elimination_for 5.680000 0.010000 5.690000 ( 5.680348) 
bit_elimination_until 5.040000 0.010000 5.050000 ( 5.054189) 
bit_elimination_while 5.080000 0.020000 5.100000 ( 5.093165) 
pre_compute_16 4.360000 0.010000 4.370000 ( 4.364988) 

"LOTTO" FERTIG 


GETAN
    InformationsquelleAutor knugie
  5. 1

    Split den string in 8, schauen Sie jeden Eintrag in einer 128-Eintrag lookup-Tabelle und summieren Sie?

    Ich weiß.. das ist lächerlich... nur teilen einige Ideen 😉

    • +1 - das kann die Schnellste Ansatz, so lächerlich wie es klingt. Selbst wenn Sie wurden gruppiert in Gruppen von 4, es ist vielleicht ein bisschen langsamer, aber die lookup-Tabelle wäre so viel kleiner.
    • Hashing 8 bytes nehmen wird, mehr als nur das zählen der vorkommen von 1s.
    • Wenn Sie split um 8, würde nicht benötigen Sie 256 Einträge in der lookup-Tabelle?
    • Diese werden langsamer als count in Rubinrot, fast garantiert.
    InformationsquelleAutor JRL
Schreibe einen Kommentar