数组 – 为什么Swift迭代器比数组构建慢？

概述这与 this question有关,假设使用生成器(迭代器)遍历嵌套数组将是迭代元素的最佳选择,只要您不需要存储结果,同时使用重复数组连接如果你只想平整阵列是最好的. 但是,我决定进行一些测试,并实现这个函数(以懒惰和存储形式展平包含Ints或[Int] s的数组[Any]),结果表明存储的形式更快,即使刚刚使用迭代元素！这意味着,不知何故,迭代生成器比在内存中构造新数组花费更多的时间,然后迭代 这与 this question有关,假设使用生成器(迭代器)遍历嵌套数组将是迭代元素的最佳选择,只要您不需要存储结果,同时使用重复数组连接如果你只想平整阵列是最好的.

但是,我决定进行一些测试,并实现这个函数(以懒惰和存储形式展平包含Ints或[Int] s的数组[Any]),结果表明存储的形式更快,即使刚刚使用迭代元素！这意味着,不知何故,迭代生成器比在内存中构造新数组花费更多的时间,然后迭代它.

令人难以置信的是,它甚至比同一程序的python实现慢约5-70％,随着输入的减少而恶化. Swift是用-O标志构建的.

这里有三个测试用例1.小输入,混合; 2.大输入,[Int]显性,3.大输入,Int显性：

迅速

let array1: [Any] = [Array(1...100),Array(101...105),106,Array(107...111),112,113,114,Array(115...125)]let array2: [Any] = Array(repeating: Array(1...5),count: 2000)let array3: [Any] = Array(repeating: 31,count: 10000)

蟒蛇

A1 = [List(range(1,101)),List(range(101,106)),List(range(107,112)),List(range(115,126))]A2 = List(range(1,6)) * 2000A3 = [31] * 10000

生成器和数组构建器：

迅速

func chain(_ segments: [Any]) -> AnyIterator<Int>{    var i = 0    var j = 0    return AnyIterator<Int> {        while i < segments.count {            switch segments[i] {                case let e as Int:                    i += 1                    return e                case let E as [Int]:                    if j < E.count {                        let val = E[j]                        j += 1                        return val                    }                    j = 0                    i += 1                default:                    return nil            }        }        return nil    }}func flatten_array(_ segments: [Any]) -> [Int] {    var result = [Int]()    for segment in segments {        switch segment {            case let segment as Int:                result.append(segment)            case let segment as [Int]:                result.append(contentsOf: segment)            default:                break        }    }    return result}

蟒蛇

def chain(L):    for i in L:        if type(i) is int:            yIEld i        elif type(i) is List:            yIEld from idef flatten_List(L):    result = []    for i in L:        if type(i) is int:            result.append(i)        elif type(i) is List:            result.extend(i)    return result

基准测试结果(第一个测试用例为100000个循环,其他测试用例为1000个)：

迅速

test case 1 (small mixed input)    Filling an array                         : 0.068221092224121094 s    Filling an array,and looPing through it : 0.074559926986694336 s    LooPing through a generator              : 1.5902719497680664   s *    Materializing the generator to an array  : 1.759943962097168    s *test case 2 (large input,[Int] s)    Filling an array                         : 0.20634698867797852  s    Filling an array,and looPing through it : 0.21031379699707031  s    LooPing through a generator              : 1.3505551815032959   s *    Materializing the generator to an array  : 1.4733860492706299   s *test case 3 (large input,Int s)    Filling an array                         : 0.27392101287841797  s    Filling an array,and looPing through it : 0.27670192718505859  s    LooPing through a generator              : 0.85304021835327148  s    Materializing the generator to an array  : 1.0027849674224854   s *

蟒蛇

test case 1 (small mixed input)    Filling an array                         : 0.1622014045715332   s    Filling an array,and looPing through it : 0.4312894344329834   s    LooPing through a generator              : 0.6839139461517334   s    Materializing the generator to an array  : 0.5300459861755371   stest case 2 (large input,[int] s)    Filling an array                         : 1.029205083847046    s    Filling an array,and looPing through it : 1.2195289134979248   s    LooPing through a generator              : 1.0876803398132324   s    Materializing the generator to an array  : 0.8958714008331299   stest case 3 (large input,int s)    Filling an array                         : 1.0181667804718018   s    Filling an array,and looPing through it : 1.244570255279541    s    LooPing through a generator              : 1.1220412254333496   s    Materializing the generator to an array  : 0.9486079216003418   s

显然,Swift非常非常擅长构建数组.但是为什么它的发生器在某些情况下如此慢,甚至比Python慢​​？ (在表格中标有*.)使用极大的输入(> 100,000,000个元素,几乎崩溃Swift)进行测试表明,即使在极限情况下,发生器也会比阵列填充速度慢至少3.25倍在最好的情况下.

如果这是该语言的内在特征,那么它有一些有趣的含义.例如,常识(对我来说无论如何都是python程序员)会有这样的情况：如果我们试图合成一个不可变对象(比如一个字符串),我们首先应该将源提供给一个生成函数来展开它,然后手将输出关闭到一个join()方法,该方法适用于单个浅序列.相反,看起来最有效的策略是通过数组进行序列化;将源展开到中间数组,然后构造数组的输出.

是构建一个完整的新数组,然后通过它迭代它比原始数组上的延迟迭代更快？为什么？

(Possibly related javascript question)

编辑

这是测试代码：

迅速

func time(test_array: [Any],cycles: Int = 1000000) -> (array_iterate: Double,array_store  : Double,generate_iterate: Double,generate_store: Double) {    func start() -> Double { return Date().timeIntervalSince1970 }    func lap(_ t0: Double) -> Double {        return Date().timeIntervalSince1970 - t0    }    var t0 = start()    for _ in 0..<cycles {        for e in flatten_array(test_array) { e + 1 }    }    let ΔE1 = lap(t0)    t0 = start()    for _ in 0..<cycles {        let array: [Int] = flatten_array(test_array)    }    let ΔE2 = lap(t0)    t0 = start()    for _ in 0..<cycles {        let G = chain(test_array)        while let g = G.next() { g + 1 }    }    let ΔG1 = lap(t0)    t0 = start()    for _ in 0..<cycles {        let array: [Int] = Array(chain(test_array))    }    let ΔG2 = lap(t0)    return (ΔE1,ΔE2,ΔG1,ΔG2)}print(time(test_array: array1,cycles: 100000))print(time(test_array: array2,cycles: 1000))print(time(test_array: array3,cycles: 1000))

蟒蛇

def time_f(test_array,cycles = 1000000):    lap = lambda t0: time() - t0    t0 = time()    for _ in range(cycles):        for e in flatten_List(test_array):            e + 1    ΔE1 = lap(t0)    t0 = time()    for _ in range(cycles):        array = flatten_List(test_array)    ΔE2 = lap(t0)    t0 = time()    for _ in range(cycles):        for g in chain(test_array):            g + 1    ΔG1 = lap(t0)    t0 = time()    for _ in range(cycles):        array = List(chain(test_array))    ΔG2 = lap(t0)    return ΔE1,ΔG2print(time_f(A1,cycles=100000))print(time_f(A3,cycles=1000))print(time_f(A2,cycles=1000))

你问“为什么它的[Swift]生成器在某些情况下如此慢,甚至比Python慢​​？”

我的答案是,我不认为它们几乎和你的结果一样慢.特别是,我将尝试证明循环遍历迭代器应该比为所有测试用例构造数组更快.

在早期的工作中(参见http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/的相关博客文章),我发现在使用bitset类时,Swift迭代器的速度大约是Java中等效函数的一半.这不是很好,但Java在这方面非常有效.与此同时,Go更糟糕.我向你提出,Swift迭代器可能效率不高,但它们可能只是原始C代码可能的两倍.性能差距可能与Swift中功能内联不足有关.

我看到你正在使用AnyIterator.我建议从IteratorProtocol派生一个结构,它的好处是确保不必进行任何动态调度.这是一个相对有效的可能性：

public struct FastFlattenIterator: IteratorProtocol {   let segments: [Any]    var i = 0 // top-level index    var j = 0 // second-level index    var jmax = 0 // essentially,this is currentarray.count,but we buffer it    var currentarray : [Int]! // quick reference to an int array to be flatten   init(_ segments: [Any]) {       self.segments = segments   }   public mutating func next() -> Int? {     if j > 0 { // we handle the case where we iterate within an array separately       let val = currentarray[j]       j += 1       if j == jmax {         j = 0         i += 1       }       return val     }     while i < segments.count {        switch segments[i] {          case let e as Int: // found an integer value            i += 1            return e          case let E as [Int]: // first encounter with an array            jmax = E.count            currentarray = E            if jmax > 0 {              j = 1              return E[0]            }            i += 1          default:            return nil        }     }     return nil   }}

通过这门课,我得到以下数字.对于每个测试用例,前四个方法取自您的代码示例,而后两个(快速迭代器)是使用新结构构建的.请注意,“通过快速迭代器循环”总是最快的.

test case 1 (small mixed input)Filling an array                         : 0.0073099999999999997 msFilling an array,and looPing through it : 0.0069870000000000002 msLooPing through a generator              : 0.18385799999999999   ms Materializing the generator to an array  : 0.18745700000000001   ms LooPing through a fast iterator          : 0.005372              ms Materializing the fast iterator          : 0.015883999999999999  mstest case 2 (large input,[Int] s)Filling an array                         : 2.125931            msFilling an array,and looPing through it : 2.1169820000000001  msLooPing through a generator              : 15.064767           ms Materializing the generator to an array  : 15.45152            ms LooPing through a fast iterator          : 1.572919            msMaterializing the fast iterator          : 1.964912            ms test case 3 (large input,Int s)Filling an array                         : 2.9140269999999999  msFilling an array,and looPing through it : 2.9064290000000002  msLooPing through a generator              : 9.8297640000000008  msMaterializing the generator to an array  : 9.8297640000000008  ms LooPing through a fast iterator          : 1.978038            ms Materializing the fast iterator          : 2.2565339999999998  ms

您将在GitHub上找到我的完整代码示例：https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/swift/iterators

总结

以上是内存溢出为你收集整理的数组 – 为什么Swift迭代器比数组构建慢？全部内容，希望文章能够帮你解决数组 – 为什么Swift迭代器比数组构建慢？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。