1

以下は、Scala で記述された選択ソートの実装です。

行 ss.sort(arr) により、次のエラーが発生します: type mismatch; 見つかった: 配列[文字列] 必須: 配列[順序付けられた[任意]]

タイプ Ordered は StringOps によって継承されるため、このタイプは推論されるべきではありませんか? 文字列の配列を sort() メソッドに追加するにはどうすればよいですか?

完全なコードは次のとおりです。

object SelectionSortTest {

  def main(args: Array[String]){

    val arr = Array("Hello","World")

    val ss = new SelectionSort()
    ss.sort(arr)
  }

}

class SelectionSort {

  def sort(a : Array[Ordered[Any]]) = {
    var N = a.length

    for (i <- 0 until N) {
        var min = i

        for(j <- i + 1 until N){
            if( less(a(j) , a(min))){
              min = j
            }
        exchange(a , i , min)
        }
    }

  }

  def less(v : Ordered[Any] , w : Ordered[Any]) = {
    v.compareTo(w) < 0
  }

  def exchange(a : Array[Ordered[Any]] , i : Integer , j : Integer) = {
    var swap : Ordered[Any] = a(i)
    a(i) = a(j)
    a(j) = swap
  }
}
4

3 に答える 3

3

配列は不変です。が のサブタイプであっても、Array[A]を として使用することはできません。こちらの理由を参照してください:なぜ配列は不変ですが、リストは共変なのですか?Array[B]AB

どちらでもないOrderedので、less の実装も機能しません。

次の方法で実装をジェネリックにする必要があります。

object SelectionSortTest {

  def main(args: Array[String]){

    val arr = Array("Hello","World")

    val ss = new SelectionSort()
    ss.sort(arr)
  }

}

class SelectionSort {

  def sort[T <% Ordered[T]](a : Array[T]) = {
    var N = a.length

    for (i <- 0 until N) {
        var min = i

        for(j <- i + 1 until N){
            if(a(j) < a(min)){ // call less directly on Ordered[T]
              min = j
            }
        exchange(a , i , min)
        }
    }

  }

  def exchange[T](a : Array[T] , i : Integer , j : Integer) = {
    var swap = a(i)
    a(i) = a(j)
    a(j) = swap
  }
}

やや奇妙なステートメントは、「暗黙的に変換できるT <% Ordered[T]任意の型」を意味します。これにより、小なり演算子を引き続き使用できます。TOrdered[T]

詳細については、これを参照してください: Scala コンテキストとビューの境界とは?

于 2013-04-24T21:57:16.233 に答える
1

@gzm0による回答（いくつかの非常に素晴らしいリンクを含む）は、Ordered. をカバーする回答で補足しOrderingます。これは、クラスにそれほど負担をかけずに同等の機能を提供します。

Ordering暗黙的なインスタンスが定義されている「T」型の配列を受け入れるように sort メソッドを調整しましょう。

def sort[T : Ordering](a: Array[T]) = {
  val ord = implicitly[Ordering[T]]
  import ord._ // now comparison operations such as '<' are available for 'T'
  // ...
  if (a(j) < a(min))
  // ...
}

[T : Ordering]andのimplicitly[Ordering[T]]組み合わせは、 type の暗黙のパラメーターと同等ですOrdering[T]。

def sort[T](a: Array[T])(implicit ord: Ordering[T]) = {
  import ord._
  // ...
}

なぜこれが役立つのですか？case class Account(balance: Int)第三者から提供されていると想像してください。Ordering次のように for を追加できます。

// somewhere in scope
implicit val accountOrdering = new Ordering[Account] {
  def compare(x: Account, y: Account) = x.balance - y.balance
}

// or, more simply
implicit val accountOrdering: Ordering[Account] = Ordering by (_.balance)

そのインスタンスがスコープ内にある限り、使用できるはずですsort(accounts)。
別の順序付けを使用したい場合は、次のように明示的に指定することもできますsort(accounts)(otherOrdering)。

Orderingこれは、 (少なくともこの質問のコンテキスト内では)への暗黙的な変換を提供することとあまり変わらないことに注意してください。

于 2013-04-25T23:14:34.247 に答える
0

Scala をコーディングするとき、私は関数型プログラミング スタイル (コンビネータまたは再帰を使用) を命令型スタイル (変数と反復を使用) よりも好むことに慣れていますが、今回は、この特定の問題については、古い学校の命令型のネストされたループがよりシンプルでパフォーマンスの高い結果になりますコード。

命令型スタイルにフォールバックすることは、新しいソートされたコレクションになるのではなく、通常は入力バッファーを変換するソートアルゴリズム (プロシージャのようなもの) など、特定のクラスの問題では間違いではないと思います。

ここに私の解決策があります：

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

ご覧のとおり、パラメトリック ポリモーフィズムを実現するには、 を使用するのではなく、Upper Bounds ではなく Scala View Boundsjava.lang.Comparableを優先しました。scala.math.Orderedプリミティブ型からリッチ ラッパーへの Scala Implicit Conversions のおかげで、これは確かに機能します。

クライアント プログラムは次のように記述できます。

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))
于 2014-04-27T21:52:57.320 に答える