Проблема Scala с использованием приоритета приоритета не по умолчанию для стека [A] - PullRequest
Новая
       13

Проблема Scala с использованием приоритета приоритета не по умолчанию для стека [A]

1 голос
/ 29 ноября 2010

Я пытаюсь написать простую реализацию вида терпения, используя Scala.
Мне правильно удалось создать начальные сваи; однако мое использование очереди приоритетов для упрощения генерации списка вывода вызывает у меня головную боль.

Похоже, что моя реализация заказа неверна или игнорируется: 

def PileOrdering = new Ordering[Stack[A]] {
    def compare(a : Stack[A], b : Stack[A]) = a.head.compare(b.head)
}

// Use a priority queue, ordering on stack heads (smallest stack elems)
val pq = new PriorityQueue[Stack[A]]()(PileOrdering)

// piles is a List[Stack[A]]
pq ++= piles

// Extract an ordered list of elements
val returnVal = (0 until count) map (_ => {
    val smallestList = pq.dequeue
    val smallestVal = smallestList.pop

    if (smallestList.length > 0){
        pq.enqueue(smallestList)
    }

    smallestVal
})

Кажется, что PriorityQueue упорядочен (а я полагаю, по умолчанию в стеке), а не в моем порядке.

Что-нибудь выскакивает как явно неправильное? Любая помощь будет принята.
Спасибо,

Редактировать: Я не ясно дал понять в исходном вопросе: я использую Scala 2.8.1.
Edit2: Я ожидал, что returnVal будет содержать порядок элементов от наименьшего к наибольшему, найденный путем взятия наименьшего элемента из голов всех стеков. Дэниел указал, что мой порядок упорядочит мои стеки от самого большого к маленькому (сами стеки уже упорядочены правильно, с наименьшим элементом сверху), что, похоже, является проблемой.

Ответы [ 2 ]

1 голос
/ 29 ноября 2010

Вас не смущает тот факт, что первый элемент в очереди с приоритетами - это элемент со значением наибольшее , согласно порядку? Кажется, код ожидает, что первый элемент будет с наименьшим значением.

0 голосов
/ 29 ноября 2010

Немного трудно ответить, что происходит, потому что вы не включили всю программу с входами и выходами. Я предполагаю, что это связано со старой реализацией PriorityQueue в 2.8.1. Следующая программа использует пользовательский порядок и заполняет очередь приоритетов списком стеков: 

import collection._                                                                                                 
import collection.mutable.PriorityQueue                                                                             
import collection.mutable.Stack                                                                                     



class Test[A](piles: Traversable[Stack[A]])(implicit ord: Ordering[A]) {                                            

  def PileOrdering = new Ordering[Stack[A]] {                                                                       
    def compare(a : Stack[A], b : Stack[A]) = ord.compare(a.head, b.head)                                           
  }                                                                                                                 

  // Use a priority queue, ordering on stack heads (smallest stack elems)                                           
  val pq = new PriorityQueue[Stack[A]]()(PileOrdering)                                                              

  // piles is a List[Stack[A]]                                                                                      
  pq ++= piles                                                                                                      

}                                                                                                                   

object Main {                                                                                                       
  def main(args: Array[String]) {                                                                                   
    val t = new Test(Seq(Stack(1, 2, 3), Stack(15, 8), Stack(3, 4, 9, 0, -1), Stack(45, 1, 2, 3, 4)))               
    while (t.pq.nonEmpty) {                                                                                         
      println(t.pq.dequeue)                                                                                         
    }                                                                                                               
  }                                                                                                                 
}

Программа выводит: 

Stack(45, 1, 2, 3, 4)                                                                                               
Stack(15, 8)                                                                                                        
Stack(3, 4, 9, 0, -1)                                                                                               
Stack(1, 2, 3)

со стволом Scala, что представляется правильным. Следует отметить, что PriorityQueue претерпел некоторые изменения, которые не были включены в 2.8.1 по причинам двоичной совместимости, но будут доступны в 2.9:

  • Раньше это была последовательность, и она больше не является последовательностью - apply и update не могут быть реализованы осмысленно
  • вызов toString или итерации по элементам не приведут к порядку кучи - единственный способ получить его - использовать dequeue
...