如何在固定时间内返回下标？ [英] How to Return subscript in Constant Time?

问题描述

根据 Swift文档，当符合时集合协议：

符合Collection的类型应提供startIndex和endIndex属性以及对下标的访问元素作为O（1）运算。

Types that conform to Collection are expected to provide the startIndex and endIndex properties and subscript access to elements as O(1) operations.

如何在恒定时间内返回下标？它不需要遍历集合，直到正确的索引，然后返回该值吗？

How can subscript be returned in constant time? Wouldn't it need to iterate through the collection, up to the correct index, and then return that value?

这是我用来遵循的LinkedList Collection ：

This is the LinkedList that I'm using to conform to Collection:

indirect enum LinkedList<T> {
    case value(element: T, next: LinkedList<T>)
    case end
}

extension LinkedList: Sequence {
    func makeIterator() -> LinkedListIterator<T> {
        return LinkedListIterator(current: self)
    }
    var underestimatedCount: Int {
        var count = 0
        for _ in self {
            count += 1
        }
        return count
    }
}

struct LinkedListIterator<T>: IteratorProtocol {
    var current: LinkedList<T>
    mutating func next() -> T? {
        switch current {
        case let .value(element, next):
            current = next
            return element
        case .end:
            return nil
        }
    }
}

这是我在这里的地方确实符合协议：

And here is this is where I actually conform to the protocol:

extension LinkedList: Collection {

    typealias Index = Int
    typealias Element = T

    var startIndex: Index {
        return 0
    }
    var endIndex: Index {
        return underestimatedCount
    }
    func index(after i: Index) -> Index {
        return (i < endIndex) ? i + 1 : endIndex
    }
    subscript (position: Index) -> Element {
        precondition(position < endIndex && position >= startIndex)
        var iterator = makeIterator()
        for i in 0 ..< position {
            iterator.next()
            if i + 1 == position {
                return iterator.next()!
            }
        }
        var zero = makeIterator()
        return zero.next()!
    }

}

let test = LinkedList<Int>.value(element: 2, next: LinkedList<Int>.value(element: 4, next: LinkedList<Int>.value(element: 7, next: LinkedList<Int>.value(element: 9, next: LinkedList<Int>.end))))

推荐答案

集合的 Index 不必是 Int 。一种可能的方法
是使用自定义索引类型，该类型对相应的
元素具有 reference 。但这要求列表节点是类的实例。

The collection's Index does not have to be an Int. One possible approach is to use a custom index type which has a reference to the corresponding element. However this requires the list nodes to be instances of a class.

这是我想出的东西。
可能可以改进它，但希望能证明这一想法。

Here is something that I came up with. It can probably be improved, but hopefully demonstrates the idea.

ListNode类存储
元素和指向下一个节点的指针，另外还有一个递增的
整数 ordinal ，该整数用于创建 struct ListIndex
采用 Comparable 协议。

class ListNode stores the element and a pointer to the next node, and in addition, an increasing integer ordinal, which is used to make struct ListIndex adopt the Comparable protocol.

struct ListIndex 包含对列表节点的引用，或 nil
表示 endIndex 。

struct ListIndex contains a reference to the list node, or nil for endIndex.

struct LinkedListCollection<T>: Collection {

    class ListNode {
        let element: T
        let next: ListNode?
        let ordinal: Int

        init(element: T, next: ListNode?, ordinal: Int) {
            self.element = element
            self.next = next
            self.ordinal = ordinal
        }

        // Create ListNode as the head of a linked list with elements from an iterator.
        convenience init?<I: IteratorProtocol>(it: inout I, ordinal: Int = 0) where I.Element == T {
            if let el = it.next() {
                self.init(element: el, next: ListNode(it: &it, ordinal: ordinal + 1), ordinal: ordinal)
            } else {
                return nil
            }
        }
    }

    struct ListIndex: Comparable {
        let node: ListNode?

        static func <(lhs: ListIndex, rhs: ListIndex) -> Bool {
            // Compare indices according to the ordinal of the referenced
            // node. `nil` (corresponding to `endIndex`) is ordered last.

            switch (lhs.node?.ordinal, rhs.node?.ordinal) {
            case let (r?, l?):
                return r < l
            case (_?, nil):
                return true
            default:
                return false
            }
        }

        static func ==(lhs: ListIndex, rhs: ListIndex) -> Bool {
            return lhs.node?.ordinal == rhs.node?.ordinal
        }
    }

    let startIndex: ListIndex
    let endIndex: ListIndex

    // Create collection as a linked list from the given elements.
    init<S: Sequence>(elements: S) where S.Iterator.Element == T {
        var it = elements.makeIterator()
        startIndex = ListIndex(node: ListNode(it: &it))
        endIndex = ListIndex(node: nil)
    }

    func index(after i: ListIndex) -> ListIndex {
        guard let next = i.node?.next else {
            return endIndex
        }
        return ListIndex(node: next)
    }

    subscript (position: ListIndex) -> T {
        guard let node = position.node else {
            fatalError("index out of bounds")
        }
        return node.element
    }
}

示例用法：

let coll = LinkedListCollection(elements: [1, 1, 2, 3, 5, 8, 13])
for idx in coll.indices {
    print(coll[idx])
}

这篇关于如何在固定时间内返回下标？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！