Share
Embed
Transcript
19 slides
-
Profile - Ryo Aoyama - CyberAgent/FRESH! 2016~ - GitHub: @ra1028
- Twitter: @ra1028fe5 -
Sample public struct Bag0<Element> { public struct Key: Equatable {
fileprivate let value: UInt64 fileprivate init(value: UInt64) { self.value = value } public static func == (lhs: Key, rhs: Key) -> Bool { return lhs.value == rhs.value } } private var buffer = [(key: Key, element: Element)]() private var nextKey = Key(value: 0) public init() {} @discardableResult public mutating func add(_ element: Element) -> Key { let key = nextKey nextKey = Key(value: key.value &+ 1) buffer.append((key: key, element: element)) return key } @discardableResult public mutating func remove(for key: Key) -> Element? { if let index = buffer.indices.reversed().first(where: { buffer[$0].key == key }) { return buffer.remove(at: index).element } return nil } } -
Sample extension Bag0: RandomAccessCollection { public var startIndex: Int {
return buffer.startIndex } public var endIndex: Int { return buffer.endIndex } public func index(after i: Int) -> Int { return i + 1 } public subscript(position: Int) -> Element { return buffer[position].element } } -
Element͕Class͔@objcͷͱ͖ʹϝϞϦͷ࿈ଓͨ͠ྖҬʹ֨ ೲ͠ɺΠςϨʔγϣϯΛߴԽͰ͖Δ ͜ͷಛੑΛ׆͔ͨ͢ΊɺElementͱKeyͰผʑͷྻΛ֬อ public struct Bag1<Element> { private var elements
= ContiguousArray<Element>() private var keys = ContiguousArray<Key>() private var buffer = [(key: Key, element: Element)]() -
public struct Bag2<Element> { private var elements = ContiguousArray<Element>() private
var keyRawValues = ContiguousArray<UInt64>() private var nextKey = Key(value: 0) @discardableResult public mutating func remove(for key: Key) -> Element? { if let index = elements.indices.reversed().first(where: { keyRawValues[$0] == key.value }) { keyRawValues.remove(at: index) return elements.remove(at: index) } return nil } ࠷దԽࡁΈͷstdlibΛͦͷ··ར༻͢Δ͜ͱͰࣗલ࣮ΑΓ ߴԽͰ͖Δ߹͕͋Δ KeyͷΘΓʹ࣮ମͷUInt64Λ֨ೲ͢Δ ͜ͱͰൺֱʹUInt64.==Λ͏ -
extension Bag3: RandomAccessCollection { public var startIndex: Int { return
elements.startIndex } public var endIndex: Int { return elements.endIndex } public subscript(index: Int) -> Element { return elements[index] } public func makeIterator() -> ContiguousArray<Element>.Iterator { return elements.makeIterator() } } σϑΥϧτͰ࣮͞ΕΔIndexingIterator<Bag>෦Ͱɺؔݺͼग़͠ʹίε τ͕͔͔Δ߹͕͋ΔͨΊContiguousArray<Element>.IteratorΛެ։͢Δ @_versioned, @_inlineable͕privateଐੑͰͳ͘ͳΕΑΓదʹ࠷దԽ͞Ε Δ࣮͕Ͱ͖Δ͕... extension Bag0: RandomAccessCollection { public var startIndex: Int { return buffer.startIndex } public var endIndex: Int { return buffer.endIndex } public func index(after i: Int) -> Int { return i + 1 } public subscript(position: Int) -> Element { return buffer[position].element } } -
@discardableResult public mutating func remove(for key: Key) -> Element? {
if let index = elements.indices.reversed().first(where: { keyRawValues[$0] == key.value }) { keyRawValues.remove(at: index) return elements.remove(at: index) } return nil } ReactiveSwiftͰɺ͋ͱ͔ΒՃ͞Εͨͷͷํ͕remove(for:)͞Ε͍͢ ͱ͍͏ߟ͑Ͱٯॱʹࡧ͍ͯͨ͠ͷΛݱࡏͷ༻్ʹ߹ΘͤͯΊΔ ͜ͷΑ͏ʹɺར༻ํ๏ʹ͚ͩ͢͜͠าΈدΔͷ༗ޮ @discardableResult public mutating func remove(for key: Key) -> Element? { if let index = elements.indices.first(where: { keyRawValues[$0] == key.value }) { keyRawValues.remove(at: index) return elements.remove(at: index) } return nil } -
Iteration 1,000,000 elements func testBag0() { typealias Bag = Bag0
let count = 1000_000 var bag = Bag<Object>() for _ in 0..<count { let object = Object() bag.add(object) } measure { var trash = [Object]() trash.reserveCapacity(count) for object in bag { trash.append(object) } XCTAssertEqual(trash.count, count) } } -
Add, Iteration, Remove 10,000 elements func testBag0() { typealias Bag
= Bag0 let count = 10_000 measure { var bag = Bag<Object>() var keys = [Bag<Object>.Key]() for _ in 0..<count { let object = Object() let key = bag.add(object) keys.append(key) } var trash = [Object]() trash.reserveCapacity(count) for object in bag { trash.append(object) } for key in keys { bag.remove(for: key) } XCTAssertEqual(trash.count, count) XCTAssertEqual(bag.count, 0) } }