我不确定是否存在问题,所以我只想把它写下来.
我正在 iphone 5s上使用swift,xcode 7.2开发.
并使用计算执行时间
NSDate.timeIntervalSinceReferenceDate()
我正在 iphone 5s上使用swift,xcode 7.2开发.
并使用计算执行时间
NSDate.timeIntervalSinceReferenceDate()
我创建了2个数组,一个有200,000个元素,另一个有20个.
并尝试随机访问其元素.访问大元素的元素几乎慢了55倍！我知道它更大但不是这个O(1)？
我也尝试过相同的java和大小数组的访问速度相同.
从苹果文档中的CFArrayheader,我发现了这个：
Accessing any value at a particular index in an array is at worst O(log n),but should usually be O(1).
但它认为根据我测试的数字,这是不可能的.
我知道我没有做过大的测试或任何特别的事情,但事实上它不起作用的确是在弄乱我的脑袋！
我有点需要这个我正在做的事情.并且该算法不适用于swift和iOS及其在java和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：
(访问一个元素在java及其在PC上是如此之快,所以我访问更多元素,但两个数组上的数字相同)
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
解决方法
如果您更改两个测试的顺序,您将发现性能被翻转.简而言之,第一次测试比第二次测试运行得慢,无论是小阵列还是大阵列.这是一些印刷动态的结果.如果在执行测试之前进行打印,则会消除第一次打印导致的延迟.
测试这个的更好方法是创建一个单元测试,它(a)多次重复下标操作符; (b)使用measureBlock重复测试几次以检查标准偏差等.
当我这样做时,我发现访问时间难以区分,与O(1)一致.这是我的单元测试：
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)
}
不可否认,我添加了一些改变索引的数学运算(我的目的是确保编译器没有进行一些彻底的优化,这些优化消除了我重复下标操作的尝试),并且该数学运算的开销将稀释下标运算符性能差异.但是,即使我简化了索引运算符,两个表达之间的性能也难以区分.
