Swift Array Performance Issue?

No estoy seguro de si hay un problema o no, así que lo voy a escribir. Estoy desarrollando usando swift, xcode 7.2, en iphone 5s. Y calculando el time de ejecución usando NSDate.timeIntervalSinceReferenceDate()

Creé 2 matrices, una con 200,000 elementos y una con 20. y trato de tener acceso aleatorio a sus elementos. ¡El acceso a los elementos en grande es casi 55 veces más lento! Sé que es más grande pero ¿no es esto O (1)?

También probé lo mismo en Java y la velocidad de acceso es la misma para matrices grandes y pequeñas.

De CFArrayheader en la documentation de Apple, encontré esto:

El acceso a cualquier valor en un índice particular en una matriz es en el peor O (log n), pero generalmente debería ser O (1).

pero creo que esto no puede ser cierto basado en los numbers que he probado.

Sé que no hice una gran testing ni nada especial, ¡pero el hecho de que no funcione realmente está molestando mi cabeza! Necesito un poco esto para lo que estoy trabajando. y el algorithm no está funcionando en swift e iOS y está funcionando en Java y 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(ba) \\prints 0.000888049602508545 a = NSDate.timeIntervalSinceReferenceDate() print(smallArray[indexSmall]) b = NSDate.timeIntervalSinceReferenceDate() print(ba) \\prints 6.90221786499023e-05 

java: (el acceso a un elemento es tan rápido en Java y está en la PC, así que accedo a más elementos, pero el mismo número en ambas 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(ba); //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 

Si cambia el order de sus dos testings, encontrará que el performance está invertido. En resumen, la primera testing se ejecuta más lentamente que la segunda, independientemente de que sea la matriz pequeña o la grande. Este es el resultado de alguna dinámica de print . Si realiza una print antes de realizar las testings, se elimina el retraso resultante de la primera print .

Una mejor manera de probar esto sería crear una testing de unidad, que (a) repite el operador de subíndice muchas veces; y (b) usa measureBlock para repetir la testing varias veces para verificar la desviación estándar y similares.

Cuando hago eso, encuentro que el time de acceso es indistinguible, consistente con O (1). Estas fueron mis testings unitarias:

 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) } 

Es cierto, he agregado algunas operaciones matemáticas que cambian el índice (mi intención era asegurarme de que el comstackdor no hiciera alguna optimization radical que eliminara mi bash de repetir la operación de subíndice), y la sobrecarga de esa operación matemática diluiría el diferencia de performance del operador subíndice. Pero, incluso cuando simplifiqué el operador de índice, el performance entre las dos versiones era indistinguible.