37

この質問をさらに学習する意図で、リスト（またはコレクション）が順序付けられているかどうかをチェックするアルゴリズムの明示的な再帰に代わる慣用的な代替手段に興味を持っていました。(ここでは、演算子を使用して比較し、型として Int を使用することで物事を単純にしています。そのジェネリックを掘り下げる前に、アルゴリズムを調べたいと思います)

基本的な再帰バージョンは次のようになります (@Luigi Plinge による):

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: xs => x <= xs.head && isOrdered(xs)
}

パフォーマンスの悪い慣用的な方法は次のとおりです。

def isOrdered(l: List[Int]) = l == l.sorted

フォールドを使用した代替アルゴリズム:

def isOrdered(l: List[Int]) =
  l.foldLeft((true, None:Option[Int]))((x,y) =>
    (x._1 && x._2.map(_ <= y).getOrElse(true), Some(y)))._1

最初の順不同の要素を見つけた後、早く停止できたとしても、リストのすべての n 要素を比較するという欠点があります。フォールドを「停止」して、これをより良い解決策にする方法はありますか?

他の（エレガントな）代替品はありますか？

4

9 に答える 9

63

これは、順不同の最初の要素の後に終了します。したがって、うまく機能するはずですが、私はそれをテストしていません。また、私の意見では、はるかにエレガントです。:)

def sorted(l:List[Int]) = l.view.zip(l.tail).forall(x => x._1 <= x._2)
于 2011-10-21T17:16:44.830 に答える
39

「慣用的な」とは、マクブライドとパターソンの論文Applicative Programming With Effectsの「イディオム」について話していることを前提としています。:o)

これらのイディオムを使用して、コレクションが順序付けされているかどうかを確認する方法は次のとおりです。

import scalaz._
import Scalaz._

case class Lte[A](v: A, b: Boolean)

implicit def lteSemigroup[A:Order] = new Semigroup[Lte[A]] {
  def append(a1: Lte[A], a2: => Lte[A]) = {
    lazy val b = a1.v lte a2.v
    Lte(if (!a1.b || b) a1.v else a2.v, a1.b && b && a2.b)
  }
}

def isOrdered[T[_]:Traverse, A:Order](ta: T[A]) =
  ta.foldMapDefault(x => some(Lte(x, true))).fold(_.b, true)

これがどのように機能するかは次のとおりです。

T[A]の実装が存在する任意のデータ構造は、ファンクタ、または「イディオム」、または「強力な緩いモノイド ファンクタ」Traverse[T]でトラバースできます。Applicativeたまたま、every がそのMonoidようなイディオムを無料で誘導することがあります (論文のセクション 4 を参照)。

モノイドは、ある型に対する連想二項演算であり、その演算の恒等要素です。Semigroup[Lte[A]]連想演算が 2 つの値のうち小さい方を追跡し、左の値が右の値より小さいかどうかを追跡する (セミグループはモノイドと同じですが、恒等要素がないことを除いて) を定義しています。そしてもちろんOption[Lte[A]]、半群によって自由に生成されたモノイドです。

最後に、モノイドによって誘導されたイディオムfoldMapDefaultのコレクション型をトラバースします。各値が次のすべての値より小さかった場合 (つまり、コレクションが順序付けられていた場合)、または に要素がなかった場合、T結果には true が含まれます。空は規則に従ってソートされるため、2 番目の引数として の最終引数に渡します。bNoneTTtruefoldOption

おまけとして、これはすべてのトラバース可能なコレクションで機能します。デモ:

scala> val b = isOrdered(List(1,3,5,7,123))
b: Boolean = true

scala> val b = isOrdered(Seq(5,7,2,3,6))
b: Boolean = false

scala> val b = isOrdered(Map((2 -> 22, 33 -> 3)))
b: Boolean = true

scala> val b = isOrdered(some("hello"))
b: Boolean = true

テスト：

import org.scalacheck._

scala> val p = forAll((xs: List[Int]) => (xs /== xs.sorted) ==> !isOrdered(xs))
p:org.scalacheck.Prop = Prop

scala> val q = forAll((xs: List[Int]) => isOrdered(xs.sorted))
q: org.scalacheck.Prop = Prop

scala> p && q check
+ OK, passed 100 tests.

そして、コレクションが順序付けされているかどうかを検出するために慣用的なトラバーサルを行う方法です。

于 2011-10-21T20:24:54.073 に答える
8

実際のところ、これはキム・スティーベルのものとかなり似ています。

def isOrdered(list: List[Int]): Boolean = (
  list 
  sliding 2 
  map { 
    case List(a, b) => () => a < b 
  } 
  forall (_())
)
于 2011-10-21T19:45:56.030 に答える
2

再帰バージョンは問題ありませんが、制限されてListいます（変更が制限されているため、でうまく機能しますLinearSeq）。

それが標準ライブラリに実装されている場合（意味があります）、おそらくそれはで行われIterableLike、完全に必須の実装があります（たとえばメソッドを参照find）

で中断することができますfoldLeft（returnこの場合、前の要素のみが必要であり、ブール値は必要ありません）

import Ordering.Implicits._
def isOrdered[A: Ordering](seq: Seq[A]): Boolean = {
  if (!seq.isEmpty)
    seq.tail.foldLeft(seq.head){(previous, current) => 
      if (previous > current) return false; current
    }
  true
}

しかし、命令型の実装よりも優れている、あるいは慣用的でさえあるかどうかはわかりません。私はそれを実際に命令とは呼ばないかどうかはわかりません。

別の解決策は

def isOrdered[A: Ordering](seq: Seq[A]): Boolean = 
  ! seq.sliding(2).exists{s => s.length == 2 && s(0) > s(1)}

むしろ簡潔で、おそらくそれは慣用句と呼ぶことができますが、私にはわかりません。しかし、それはあまり明確ではないと思います。さらに、これらのメソッドはすべて、命令型または末尾再帰バージョンよりもパフォーマンスが大幅に低下する可能性があり、それを購入するような追加の明確さはないと思います。

また、この質問をご覧ください。

于 2011-10-21T17:07:48.903 に答える
1

反復を停止するには、Iterateeを使用できます。

import scalaz._
import Scalaz._
import IterV._
import math.Ordering
import Ordering.Implicits._

implicit val ListEnumerator = new Enumerator[List] {
  def apply[E, A](e: List[E], i: IterV[E, A]): IterV[E, A] = e match {
    case List() => i
    case x :: xs => i.fold(done = (_, _) => i,
                           cont = k => apply(xs, k(El(x))))
  }
}

def sorted[E: Ordering] : IterV[E, Boolean] = {
  def step(is: Boolean, e: E)(s: Input[E]): IterV[E, Boolean] = 
    s(el = e2 => if (is && e < e2)
                   Cont(step(is, e2))
                 else
                   Done(false, EOF[E]),
      empty = Cont(step(is, e)),
      eof = Done(is, EOF[E]))

  def first(s: Input[E]): IterV[E, Boolean] = 
    s(el = e1 => Cont(step(true, e1)),
      empty = Cont(first),
      eof = Done(true, EOF[E]))

  Cont(first)
}


scala> val s = sorted[Int]
s: scalaz.IterV[Int,Boolean] = scalaz.IterV$Cont$$anon$2@5e9132b3

scala> s(List(1,2,3)).run
res11: Boolean = true

scala> s(List(1,2,3,0)).run
res12: Boolean = false
于 2011-10-22T06:06:27.240 に答える
0 
def isSorted[A <: Ordered[A]](sequence: List[A]): Boolean = {
  sequence match {
    case Nil        => true
    case x::Nil     => true
    case x::y::rest => (x < y) && isSorted(y::rest)
  }
}

Explain how it works.
于 2016-12-08T22:29:30.803 に答える
0

リストを 2 つの部分に分割し、最初の部分の最後が 2 番目の部分の最初よりも低いかどうかを確認します。その場合、両方の部分を並行してチェックできます。ここでは、最初に並列のない概略的なアイデアを示します。

def isOrdered (l: List [Int]): Boolean = l.size/2 match {
  case 0 => true 
  case m => {
    val  low = l.take (m)
    val high = l.drop (m)
    low.last <= high.head && isOrdered (low) && isOrdered (high) 
  }
}

そして今、並列で、splitAt代わりに使用しますtake/drop:

def isOrdered (l: List[Int]): Boolean = l.size/2 match {
  case 0 => true 
  case m => {
    val (low, high) = l.splitAt (m)
    low.last <= high.head && ! List (low, high).par.exists (x => isOrdered (x) == false) 
  }
}
于 2011-10-22T19:07:40.993 に答える