Swift数组性能问题？

Question

Swift数组性能问题？

iosarraysswiftperformance

9

我不确定是否存在问题，所以我要将其写下来。我使用Swift和Xcode 7.2，在iPhone 5s上开发。使用NSDate.timeIntervalSinceReferenceDate()计算执行时间。

我创建了两个数组，一个有200,000个元素，另一个只有20个元素，并尝试随机访问它们的元素。访问大数组的元素几乎慢了55倍！我知道它更大，但这不是O(1)吗？

我在Java上也尝试了相同的操作，大数组和小数组的访问速度是相同的。

从苹果文档的CFArrayheader中，我发现了这个：

在数组中访问特定索引处的任何值最坏情况下是O(log n)，但通常应该是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上，访问一个元素非常快，并且在电脑上也是如此，因此我可以访问更多的元素，但是两个数组上的元素数量相同。

    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

- Vahid

我也检查了NSArray和NSMutableArray，没有增强。 - Vahid

1

你能给我们提供一些用于基准测试的样例代码吗？ - Cristik

@Cristik 我刚刚做了 :D - Vahid

1

另外，请告诉我们您使用了哪些优化设置。它可能会影响数组性能。 - Rob

通常情况下不应该这样做，但你能否禁用安全检查并重新测量呢？ - HAS

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob · Accepted Answer

如果您更改两个测试的顺序，您会发现性能会翻转。简而言之，第一个测试比第二个测试运行更慢，无论是小数组还是大数组。这是由于“打印”的某些动态影响。如果在执行测试之前先进行“打印”，则消除了第一次“打印”产生的延迟。

更好的测试方法是创建一个单元测试，该测试(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)
}

可以承认的是，我添加了一些数学运算来改变索引（我的意图是确保编译器没有进行一些激进的优化，删除了我尝试重复订阅操作），这个数学运算的开销将会削弱下标运算符的性能差异。但即使在我简化索引操作时，这两种表现之间的性能也是无法区分的。