[Starter Pitch] Introducing a `cycled` method to `Sequence`

Evolution Pitches
28

Edit 1: Added sequence(state:next:) test.
Edit 2: Added XCTAssertEqual calls.
Edit 3: Added build configuration.

The custom type was faster than the other combinations.

Average times (seconds):

Swift 4.0.3 Swift 4.1 Swift 4.2
(Xcode 9.2) (Xcode 9.3) (Xcode 9.3)
testCustom() 0.227 0.587 0.417
testRepeat() 0.320 0.685 0.501
testUnfoldFirst() 0.318 0.677 0.510
testUnfoldState() 0.273 0.632 0.471

Using:

  • Xcode 9.2 (9C40b) with Swift 4.0.3
  • Xcode 9.3 beta 4 (9Q127n) with Swift 4.1
  • Trunk Development (master) March 17, 2018 snapshot.
  • "Debug" build configuration with no optimization [-Onone].

I added methods to Collection instead of Sequence.

import XCTest

extension Collection {

  public func cycledCustom() -> CycleSequence<Self> {
    return CycleSequence(self)
  }

  public func cycledRepeat() -> FlattenSequence<Repeated<Self>> {
    return repeatElement(self, count: self.isEmpty ? 0 : .max).joined()
  }

  public func cycledUnfoldFirst() -> FlattenSequence<UnfoldFirstSequence<Self>> {
    return sequence(first: self, next: { $0.isEmpty ? nil : $0 }).joined()
  }

  public func cycledUnfoldState() -> UnfoldSequence<Element, Iterator> {
    return sequence(state: makeIterator(), next: { iterator in
      if let nextElement = iterator.next() {
        return nextElement
      }
      iterator = self.makeIterator() // NOTE: captures `self`.
      return iterator.next()
    })
  }
}

public struct CycleSequence<C: Collection> : Sequence, IteratorProtocol {

  internal let _collection: C
  internal var _iterator: C.Iterator

  internal init(_ collection: C) {
    _collection = collection
    _iterator = collection.makeIterator()
  }

  public mutating func next() -> C.Element? {
    if let nextElement = _iterator.next() {
      return nextElement
    }
    _iterator = _collection.makeIterator();
    return _iterator.next()
  }
}

class CycleBenchmark: XCTestCase {

  let _prefix = 1_000_000
  let _source = 0 ... 999

  func testCustom() {
    self.measure {
      var count = 0
      for _ in _source.cycledCustom().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }

  func testRepeat() {
    self.measure {
      var count = 0
      for _ in _source.cycledRepeat().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }

  func testUnfoldFirst() {
    self.measure {
      var count = 0
      for _ in _source.cycledUnfoldFirst().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }

  func testUnfoldState() {
    self.measure {
      var count = 0
      for _ in _source.cycledUnfoldState().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }
}
4 Likes