这与 this question 有点相关，假设使用生成器(迭代器)遍历嵌套数组对于遍历元素是最佳的，只要你不需要存储结果，而如果你只是想使用重复数组连接是最好的展平数组。

但是，我决定做一些测试，并实现这个函数(将包含 Int 或 [Int]< 的数组="">[Any] 展平s) 在惰性形式和存储形式中，事实证明存储形式更快，即使只是用于遍历元素!这意味着不知何故，遍历生成器比在内存中构造一个新数组和然后遍历那个花费更多的时间。

令人难以置信的是，它甚至比同一程序的 python 实现慢大约 5-70%，输入越小，情况越糟。 Swift 是使用 -O 标志构建的。

这是三个测试用例 1. 小输入，混合； 2. 大输入，[Int] 显性，3. 大输入，Int 显性:

swift

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)

python

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

生成器和数组生成器:

swift

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
}

python

def chain(L):
    for i in L:
        if type(i) is int:
            yield i
        elif type(i) is list:
            yield from i


def 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 次):

swift

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 *

python

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   s

test 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   s

test 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 程序员)会认为，如果我们试图合成一个不可变对象(immutable对象)(如字符串)，我们应该首先将源提供给生成函数以展开它，然后将输出关闭到 joined() 方法，该方法适用于单个浅序列。相反，看起来最有效的策略是通过数组进行序列化；将源展开为一个中间数组，然后从该数组构造输出。

构建一个全新的数组然后遍历它是否比在原始数组上进行惰性迭代更快？为什么？

( Possibly related javascript question )

编辑

测试代码如下:

swift

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

python

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, ΔE2, ΔG1, ΔG2

print(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 在这方面非常有效。与此同时，围棋做得更糟。我向您表明，Swift 迭代器的效率可能不是理想的，但它们可能是原始 C 代码可能实现的效率的两倍之内。性能差距可能与 Swift 中的函数内联不足有关。

我看到您正在使用 AnyIterator。我建议从 IteratorProtocol 派生一个 struct 而不是它的好处是确保不需要任何动态调度。这是一个相对有效的可能性:

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 ms
Filling an array, and looping through it : 0.0069870000000000002 ms
Looping 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  ms

test case 2 (large input, [Int] s)
Filling an array                         : 2.125931            ms
Filling an array, and looping through it : 2.1169820000000001  ms
Looping through a generator              : 15.064767           ms 
Materializing the generator to an array  : 15.45152            ms 
Looping through a fast iterator          : 1.572919            ms
Materializing the fast iterator          : 1.964912            ms 

test case 3 (large input, Int s)
Filling an array                         : 2.9140269999999999  ms
Filling an array, and looping through it : 2.9064290000000002  ms
Looping through a generator              : 9.8297640000000008  ms
Materializing 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

关于arrays - 为什么 Swift 迭代器比数组构建慢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40689128/