Swift Array Performance-Problem?

Question

Ich bin mir nicht sicher, ob es ein Problem gibt oder nicht, also schreibe ich es einfach auf. Ich entwickle mit swift, xcode 7.2, auf dem iPhone 5s. und die Ausführungszeit der Berechnung mit NSDate.timeIntervalSinceReferenceDate()

Ich habe 2 Arrays, eines mit 200.000 Elementen und einem mit 20 und versuchen zufälligen Zugriff auf ihre Elemente zu haben. Zugriff auf Elemente auf großen ist fast 55 mal langsamer! Ich weiß, es ist größer, aber ist das nicht O (1)?

Ich habe auch das gleiche auf Java versucht und die Zugriffsgeschwindigkeit ist die gleiche für große und kleine Array.

Von CFArrayheader in Apfel Dokumentation, fand ich dies:

in einem Array einen beliebigen Wert an einem bestimmten Index Zugriff wird im schlimmsten Fall O (log n), sollte aber in der Regel O (1) sein.

aber ich denke, das kann nicht stimmen, basierend auf den Zahlen, die ich getestet habe.

Ich weiß, ich habe keinen großen Test gemacht oder etwas besonderes, aber die Tatsache, dass es nicht funktioniert, ist wirklich mit meinem Kopf durcheinander! Ich brauche das irgendwie, woran ich gerade arbeite. und der Algorithmus arbeitet nicht an swift und iOS und seine Arbeit an Java und Android.

let bigSize:Int = 200000 
    var bigArray = [Int](count:bigSize,repeatedValue:0) 

    let smallSize:Int = 20 
    var smallArray = [Int](count:smallSize,repeatedValue:0) 

    for i in 0..<bigSize 
    { 
     bigArray[i] = i + 8 * i 
    } 
    for i in 0..<smallSize 
    { 
     smallArray[i] = i + 9 * i 
    } 
    let indexBig = Int(arc4random_uniform(UInt32(bigSize)) % UInt32(bigSize)) 
    let indexSmall = Int(arc4random_uniform(UInt32(smallSize)) % UInt32(smallSize)) 

    var a = NSDate.timeIntervalSinceReferenceDate() 
    print(bigArray[indexBig]) 
    var b = NSDate.timeIntervalSinceReferenceDate() 
    print(b-a) \\prints 0.000888049602508545 
    a = NSDate.timeIntervalSinceReferenceDate() 
    print(smallArray[indexSmall]) 
    b = NSDate.timeIntervalSinceReferenceDate() 
    print(b-a) \\prints 6.90221786499023e-05 

java: (ein Element ist der Zugriff so schnell auf Java und seine auf dem PC, so dass ich mehr Elemente zuzugreifen, aber die gleiche Anzahl auf beiden Arrays)

int bigSize = 200000; 
    int[] bigArray = new int[bigSize]; 
    Random rand = new Random(); 
    int smallSize = 20; 
    int[] smallArray = new int[smallSize]; 
    for(int i = 0;i < bigSize;i++) 
     bigArray[i] = i + i * 8; 
    for(int i = 0;i < smallSize;i++) 
     smallArray[i] = i + i * 8; 
    int smallIndex = rand.nextInt(smallSize); 
    int bigIndex = rand.nextInt(bigSize); 
    int sum = 0; 
    long a = System.currentTimeMillis(); 
    for(int i = 0;i < 10000;i++) 
    { 
     sum += bigArray[rand.nextInt(bigSize)]; 
    } 
    System.out.println(sum); 
    long b = System.currentTimeMillis(); 
    System.out.println(b-a); //prints 2 
    a = System.currentTimeMillis(); 
    sum = 0; 
    for(int i = 0; i < 10000;i++) 
    { 
     sum += smallArray[rand.nextInt(smallSize)]; 
    } 
    System.out.println(sum);  
    b = System.currentTimeMillis(); 
    System.out.println(b - a); //prints 1 

Answer 1

Wenn Sie die Reihenfolge der ändern Ihre zwei Tests werden Sie feststellen, dass die Leistung umgedreht wird. Kurz gesagt, der erste Test läuft langsamer als der zweite, unabhängig davon, ob es sich um das kleine oder das große Array handelt. Dies ist ein Ergebnis einiger Dynamiken von print. Wenn Sie eine print vor der Durchführung der Tests machen, ist die Verzögerung von der ersten print beseitigt.

Eine bessere Möglichkeit, dies zu testen, wäre, einen Komponententest zu erstellen, der (a) den tiefgestellten Operator mehrmals wiederholt; und (b) verwendet measureBlock, um den Test einige Male zu wiederholen, um auf Standardabweichung und dergleichen zu prüfen.

Wenn ich das tue, finde ich die Zugriffszeit ist nicht unterscheidbar, im Einklang mit O (1). Das ist meine Unit-Tests waren:

let bigSize: Int = 200_000 
let smallSize: Int = 20 

func testBigArrayPerformance() { 
    let size = bigSize 

    let array = Array(0 ..< size).map { $0 + 8 * $0 } 

    var value = 0 

    measureBlock { 
     let baseIndex = Int(arc4random_uniform(UInt32(size))) 
     for index in 0 ..< 1_000_000 { 
      value += array[(baseIndex + index) % size] 
     } 
    } 

    print(value) 
    print(array.count) 
} 

func testSmallArrayPerformance() { 
    let size = smallSize 

    let array = Array(0 ..< size).map { $0 + 8 * $0 } 

    var value = 0 

    measureBlock { 
     let baseIndex = Int(arc4random_uniform(UInt32(size))) 
     for index in 0 ..< 1_000_000 { 
      value += array[(baseIndex + index) % size] 
     } 
    } 

    print(value) 
    print(array.count) 
} 

Zwar habe ich einige mathematische Operationen hinzugefügt, die den Index (meine Absicht verändern sollte sicherstellen, dass der Compiler nicht einige radikale Optimierung tun, dass mein Versuch entfernt, um den Index zu wiederholen Operation), und der Overhead dieser mathematischen Operation wird die Leistungsdifferenz des tiefgestellten Operators verdünnen. Aber selbst wenn ich den Indexoperator vereinfachte, war die Leistung zwischen den beiden Darstellungen nicht unterscheidbar.