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

Я пытаюсь написать простую реализацию терпеливой сортировки, используя 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.
Редактировать2: я ожидал, что returnVal будет содержать наименьший -к наибольшему порядку элементов, найденному путем взятия наименьшего элемента из головок всех стеков. Даниэль указал, что мой порядок будет упорядочивать мои стеки от самого большого к самому маленькому (сами стеки уже упорядочены правильно, с наименьшим элементом сверху), что, по-видимому, является проблемой.


scala priority-queue
person owst    schedule 29.11.2010    source источник
comment
Пожалуйста, предоставьте компилируемый код. Этот не скомпилируется, потому что оба A и count неизвестны.   -  person Daniel C. Sobral    schedule 29.11.2010
comment
Да, ты прав. Я предполагаю, что проблема в том, чтобы задавать вопросы ранним утром. Меня сейчас нет дома, но я отредактирую вопрос позже, когда буду.   -  person owst    schedule 29.11.2010
comment
Уточните, пожалуйста, что должен делать код в returnVal, иначе будет сложно понять, неправильный ваш код или нет. :-)   -  person Daniel C. Sobral    schedule 29.11.2010

Ответы (2)


arrow_upward
1
arrow_downward

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

person Daniel C. Sobral    schedule 29.11.2010
comment
Я подозреваю, что вы правы; Мне нужно будет проверить конкретные значения, которые я использовал дома, но да, я так думаю. - person owst; 29.11.2010

arrow_upward
0
arrow_downward

Немного сложно ответить, что происходит, потому что вы не включили всю программу с входными и выходными данными. Я предполагаю, что это связано со старой реализацией 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
person axel22    schedule 29.11.2010
comment
Да, опубликовать пример определенно было бы разумно... Мне нужно будет проверить, что происходит с моим конкретным примером, когда я вернусь домой, но запуск вашего примера (на 2.8.1) дает мне это: Stack(8, 15) Stack(4, 3, 2, 1, 45) Stack(3, 2, 1) Stack(-1, 0, 9, 4, 3) Что, казалось бы, просто показывает, что init. порядок стека изменился. Вполне возможно, что я неправильно интерпретировал вывод, который я получил ранее - Дэниел указал, что код, который я вставил, даже не скомпилируется, у меня явно не было ясного ума в то время утра! Спасибо за ответ! - person owst; 29.11.2010