Was ist ein schneller Weg, um eine Zeichenfolge von zwei Zeichen in ein Array von Booleans zu konvertieren?

Question

Ich habe eine lange Zeichenfolge (manchmal über 1000 Zeichen), die ich in ein Array von booleschen Werten konvertieren möchte. Und das muss es viele Male sehr schnell tun.

let input: String = "001" 
let output: [Bool] = [false, false, true] 

Mein naiver Versuch war:

input.characters.map { $0 == "1" } 

Das ist aber viel langsamer als Ich mag würde. Mein Profiling hat mir gezeigt, dass die map wo die Verlangsamung ist, aber ich bin mir nicht sicher, wie viel einfacher ich das machen kann.

Ich fühle mich wie dies schnell ohne Swift/ObjC Overhead wäre. In C denke ich, das ist eine einfache for Schleife, wo ein Byte des Speichers mit einer Konstante verglichen wird, aber ich bin mir nicht sicher, was die Funktionen oder die Syntax ist, die ich betrachten sollte.

Gibt es eine Möglichkeit, dies viel schneller zu tun?

UPDATE:

Ich habe auch versucht eine

output = [] 
for char in input.characters { 
    output.append(char == "1") 
} 

Und es geht um 15% schneller. Ich hoffe auf viel mehr als das.

Answer 1

Dies ist schneller:

// Algorithm 'A' 
let input = "0101010110010101010" 
var output = Array<Bool>(count: input.characters.count, repeatedValue: false) 
for (index, char) in input.characters.enumerate() where char == "1" { 
    output[index] = true 
} 

Update: unter input = "010101011010101001000100000011010101010101010101"

0,0741/0,0087, wo dieser Ansatz schneller ist, dass Autor in 8,46 mal. Bei größerer Datenkorrelation positiver.

Auch bei der Verwendung von nulTerminatedUTF8 Geschwindigkeit ein wenig erhöht, aber nicht immer der Geschwindigkeit höher als Algorithmus A:

// Algorithm 'B' 
let input = "10101010101011111110101000010100101001010101" 
var output = Array<Bool>(count: input.nulTerminatedUTF8.count, repeatedValue: false) 
for (index, code) in input.nulTerminatedUTF8.enumerate() where code == 49 { 
    output[index] = true 
} 

In Ergebnisgrafik angezeigt wird, mit Eingabelänge , wo ersten und letzten 0. .1, A - Sekunde, B - dritter Punkt. A: 0.311sec, B: 0.304sec

Answer 2

Ein weiterer Schritt sollte das noch mehr beschleunigen. Wenn Sie reserveCapacity verwenden, ändert sich die Größe des Arrays vor dem Start der Schleifen, anstatt es zu versuchen, während die Schleife ausgeführt wird.

var output = [Bool]() 
output.reserveCapacity(input.characters.count) 
for char in input.characters { 
    output.append(char == "1") 
} 

Answer 3

Verwenden withCString(_:) ein rohes UnsafePointer<Int8> abzurufen. Iterate darüber und vergleiche mit 49 (ascii Wert von "1").

Answer 4

import Foundation 

let input:String = "010101011001010101001010101100101010100101010110010101010101011001010101001010101100101010100101010101011001010101001010101100101010100101010" 
var start = clock() 
var output = Array<Bool>(count: input.nulTerminatedUTF8.count, repeatedValue: false) 
var index = 0 
for val in input.nulTerminatedUTF8 { 
    if val != 49 { 
     output[index] = true 
    } 
    index+=1 
} 
var diff = clock() - start; 
var msec = diff * 1000/UInt(CLOCKS_PER_SEC); 
print("Time taken \(Double(msec)/1000.0) seconds \(msec%1000) milliseconds"); 

Dies sollte wirklich schnell sein. Versuch es. Für 010101011010101001000100000011010101010101010101 dauert es 0,039 Sekunden.

Answer 5

Dies sollte ein wenig schneller sein als die enumerate() where char == "1" Version (0.557s für 500_000 Einsen und Nullen vs. 1.159s Algorithmus 'A' von diampiax abwechselnd)

let input = inputStr.utf8 
let n = input.count 
var output = [Bool](count: n, repeatedValue: false) 
let one = UInt8(49) // 1 
for (idx, char) in input.enumerate() { 
    if char == one { output[idx] = true } 
} 

aber es ist auch viel weniger lesbar ;-p

edit: beide Versionen sind langsamer als die Karte Variante, vielleicht hast du vergessen, mit Optimierungen zu kompilieren?

Answer 6

Was ist mit einem funktionalen Stil? Es ist nicht am schnellsten (47 ms), heute, sicher ...

import Cocoa 

let start = clock() 

let bools = [Bool](([Character] ("010101011001010101001010101100101010100101010110010101010101011001010101001010101100101010100101010101011001010101001010101100101010100101010".characters)).map({$0 == "1"})) 

let msec = (clock() - start) * 1000/UInt(CLOCKS_PER_SEC); 
print("Time taken \(Double(msec)/1000.0) seconds \(msec%1000) milliseconds"); 

Answer 7

ich zu einigen Tests müssen sicher sein, aber ich denke, ein Problem mit vielen Ansätzen, einschließlich der Originalkarte angegeben ist, dass sie über zu durchlaufen müssen die Zeichenfolge, um die Zeichen zu zählen und dann ein zweites Mal, um die Zeichen tatsächlich zu verarbeiten.

Haben Sie versucht:

let output = [Bool](input.characters.lazy.map { $0 == "1" }) 

Dies könnte nur eine einzige Iteration tun. Die andere Sache, die Dinge beschleunigen könnte, ist, wenn Sie die Verwendung von Zeichenketten vermeiden können, stattdessen Arrays von Zeichen mit einer geeigneten Codierung verwenden (besonders wenn es festere Einheiten (zB UTF16 oder ASCII) gibt. Dann wird die Längensuche durchgeführt O (1) anstelle von O (n) und die Iteration kann auch schneller sein

BTW immer testen Leistung mit dem Optimierer aktiviert und nie auf dem Spielplatz, weil die Leistungsmerkmale völlig unterschiedlich sind, manchmal um den Faktor 100.

Answer 8

Ich würde vermuten, dass dies so schnell wie möglich ist:

let targ = Character("1") 
let input: String = "001" // your real string goes here 
let inputchars = Array(input.characters) 
var output:[Bool] = Array.init(count: inputchars.count, repeatedValue: false) 
inputchars.withUnsafeBufferPointer { 
    inputbuf in 
    output.withUnsafeMutableBufferPointer { 
     outputbuf in 
     var ptr1 = inputbuf.baseAddress 
     var ptr2 = outputbuf.baseAddress 
     for _ in 0..<inputbuf.count { 
      ptr2.memory = ptr1.memory == targ 
      ptr1 = ptr1.successor() 
      ptr2 = ptr2.successor() 
     } 
    } 
} 
// output now contains the result 

Der Grund ist, dass wir, dank der Verwendung von Pufferzeigern, einfach durch den zusammenhängenden Speicher wechseln, genau so, wie Sie durch ein C-Array durch Inkrementieren seines Zeigers zyklieren. Somit kann, sobald wir an der Ersteinrichtung zu erhalten, soll dies so schnell sein, wie es in C.

EDIT In einem aktuellen Test wäre, die Zeitdifferenz zwischen der ursprünglichen Verfahren der OP und dieser ist der Unterschied zwischen

13.3660290241241 

und

0.219357967376709 

, der ein ziemlich dramatisches Speed-up ist. Ich beeile mich jedoch hinzuzufügen, dass ich die ursprüngliche Einrichtung vom Timing-Test ausgeschlossen habe. Diese Zeile:

let inputchars = Array(input.characters) 

... ist besonders teuer.