Отдельные элементы в очереди приоритетов - PullRequest
Новая
       22

Отдельные элементы в очереди приоритетов

0 голосов
/ 10 марта 2019

Я использую эту реализацию очереди с ограниченным приоритетом, https://gist.github.com/ryanlecompte/5746241,, и она отлично работает. Однако я хочу, чтобы эта очередь не содержала никаких элементов с таким же порядком 'ord'. Как мне этого добиться?

Я попытался обновить функцию MaybeReplaceLowest, задав функцию lteq вместо lt. 

private def maybeReplaceLowest(a: A) {
    if (ord.lteq(a, head)) {
      dequeue()
      super.+=(a)
    }
  }

Но я думаю, что это не работает, потому что элемент, который имеет ту же функцию, что и новый элемент, может не быть во главе. Что может быть быстрым решением этой проблемы?

Большое спасибо.

1 Ответ

0 голосов
/ 10 марта 2019

Scala PriorityQueue реализовано с использованием Array.Что очень неэффективно для операции поиска, которую нужно делать для каждой вставки (чтобы проверить, существует ли элемент в очереди.

Для TreeSet идеально подходит для поиска и упорядоченного хранения.Но так как это закрытый класс (scala-2.12.8), я создал составной класс 

import scala.collection.mutable

class PrioritySet[A](val maxSize:Int)(implicit ordering:Ordering[A]) {
    var set = mutable.TreeSet[A]()(ordering)

    private def removeAdditional(): this.type = {
        val additionalElements = set.size - maxSize
        if( additionalElements > 0) { set = set.drop(additionalElements) }
        this
    }

    def +(elem: A): this.type = {
        set += elem
        removeAdditional()
    }

    def ++=(elem: A, elements: A*) : this.type = {
        set += elem ++= elements 
        removeAdditional()
    }

    override def toString = this.getClass.getName + set.mkString("(", ", ", ")")
}

. Это можно использовать как 

>>> val set = new PrioritySet[Int](4)
>>> set ++=(1000,3,42,2,5, 1,2,4, 100)
>>> println(set)
PrioritySet(5, 42, 100, 1000)
.
...