美文网首页iOS学习笔记swift
【译】Swift算法俱乐部-有界优先队列

【译】Swift算法俱乐部-有界优先队列

作者: Andy_Ron | 来源:发表于2019-07-13 15:12 被阅读3次
    Swift算法俱乐部

    本文是对 Swift Algorithm Club 翻译的一篇文章。
    Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
    🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
    本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Bounded Priority Queue


    有界优先队列(Bounded Priority queue)

    有界优先级队列类似于常规优先队列,除了可以存储的元素数量有固定的上限。在队列处于满容量时,将新元素添加到队列时,具有最高优先级值的元素将从队列中弹出。

    例子

    假设我们有一个最大大小为5的有界优先级队列,它具有以下值和优先级:

    Value:    [ A,   B,   C,    D,    E   ]
    Priority: [ 4.6, 3.2, 1.33, 0.25, 0.1 ]
    

    在这里,我们认为具有最高优先级值的对象是最重要的(因此这是max-priority队列)。 优先级值越大,我们关注的对象就越多。 所以AB更重要,BC更重要,依此类推。

    现在我们要将优先级为0.4的元素F插入到这个有界优先级队列中。 因为队列大小最大为5,所以这将插入元素F,然后逐出最低优先级元素(E),产生更新的队列:

    Value:    [ A,   B,   C,    F,   D    ]
    Priority: [ 4.6, 3.2, 1.33, 0.4, 0.25 ]
    

    由于其优先级值,在CD之间插入F。它不如C重要,但比D更重要。

    假设我们希望将优先级为0.1的元素G插入到此BPQ中。因为G的优先级值小于队列中的最小优先级元素,所以在插入G时它将立即被驱逐。换句话说,将元素插入优先级小于BPQ的最小优先级元素的BPQ中没有任何效果。

    实施

    虽然heap可能是优先级队列的一个非常简单的实现,但排序的链表允许 O(k) 插入和 O(1) 删除,其中 k 是元素的边界数。

    以下是在Swift中的实现:

    public class BoundedPriorityQueue<T: Comparable> {
      private typealias Node = LinkedListNode<T>
    
      private(set) public var count = 0
      fileprivate var head: Node?
      private var tail: Node?
      private var maxElements: Int
    
      public init(maxElements: Int) {
        self.maxElements = maxElements
      }
    
      public var isEmpty: Bool {
        return count == 0
      }
    
      public func peek() -> T? {
        return head?.value
      }
    

    BoundedPriorityQueue类包含LinkedListNode对象的双向链表。 这里没什么特别的。 有趣的东西发生在enqueue()方法中:

    public func enqueue(_ value: T) {
      if let node = insert(value, after: findInsertionPoint(value)) {
        // If the newly inserted node is the last one in the list, then update
        // the tail pointer.
        if node.next == nil {
          tail = node
        }
    
        // If the queue is full, then remove an element from the back.
        count += 1
        if count > maxElements {
          removeLeastImportantElement()
        }
      }
    }
    
    private func insert(_ value: T, after: Node?) -> Node? {
      if let previous = after {
    
        // If the queue is full and we have to insert at the end of the list,
        // then there's no reason to insert the new value.
        if count == maxElements && previous.next == nil {
          print("Queue is full and priority of new object is too small")
          return nil
        }
    
        // Put the new node in between previous and previous.next (if exists).
        let node = Node(value: value)
        node.next = previous.next
        previous.next?.previous = node
        previous.next = node
        node.previous = previous
        return node
    
      } else if let first = head {
        // Have to insert at the head, so shift the existing head up once place.
        head = Node(value: value)
        head!.next = first
        first.previous = head
        return head
    
      } else {
        // This is the very first item in the queue.
        head = Node(value: value)
        return head
      }
    }
    
    /* Find the node after which to insert the new value. If this returns nil,
       the new value should be inserted at the head of the list. */
    private func findInsertionPoint(_ value: T) -> Node? {
      var node = head
      var prev: Node? = nil
    
      while let current = node where value < current.value {
        prev = node
        node = current.next
      }
      return prev
    }
    
    private func removeLeastImportantElement() {
      if let last = tail {
        tail = last.previous
        tail?.next = nil
        count -= 1
      }
    
      // Note: Instead of using a tail pointer, we could just scan from the new
      // node until the end. Then nodes also don't need a previous pointer. But
      // this is much slower on large lists.
    }
    

    我们首先检查队列是否已经具有最大元素数。 如果是这样,并且新的优先级值小于tail元素的优先级值,那么这个新元素没有空间,我们返回时不插入它。

    如果新值是可接受的,那么我们搜索列表以找到正确的插入位置并更新nextprevious指针。

    最后,如果队列现在已达到最大元素数,那么我们dequeue()具有最大优先级值。

    通过将最重要的元素保留在列表的前面,它使得出列非常容易:

    public func dequeue() -> T? {
      if let first = head {
        count -= 1
        if count == 0 {
          head = nil
          tail = nil
        } else {
          head = first.next
          head!.previous = nil
        }
        return first.value
      } else {
        return nil
      }
    }
    

    这只是从列表中删除head元素并返回它。

    作者:John Gill, Matthijs Hollemans
    翻译:Andy Ron
    校对:Andy Ron

    相关文章

      网友评论

        本文标题:【译】Swift算法俱乐部-有界优先队列

        本文链接:https://www.haomeiwen.com/subject/ebkpkctx.html