2

私はSeqと関数Int=>Intを持っています。私が達成する必要があるのは、元のSeqから、結果のシーケンスの最大値に等しい要素のみを取得することです（1つは、特定の関数を適用した後に取得します）。

def mapper:Int=>Int= x=>x*x
val s= Seq( -2,-2,2,2 )
val themax= s.map(mapper).max
s.filter( mapper(_)==themax)

ただし、これは2回マップする必要があるため（フィルター用に1回、最大用に1回）、無駄に思えます。これを行うためのより良い方法はありますか？（サイクルを使用せずに、うまくいけば）

編集 その後、コードは編集されました。オリジナルでは、これはフィルターラインでした：s.filter( mapper(_)==s.map(mapper).max)。om-nom-nomが指摘しているように、これは各（フィルター）反復で `s.map（mapper）.maxを評価し、2次の複雑さをもたらします。

4

1 に答える 1

3

マッピングを1回だけ行い、`foldLeft'関数を使用するソリューションは次のとおりです。

原則は、seqを調べ、マップされた要素ごとに、それが以前にマップされたすべてよりも大きい場合は、それを使用して新しいシーケンスを開始します。それ以外の場合は、すべての最大値と新しいマップされた最大値のリストを返します。最後に、それよりも小さい場合は、以前に計算された最大値のSeqを返します。

def getMaxElems1(s:Seq[Int])(mapper:Int=>Int):Seq[Int] = s.foldLeft(Seq[(Int,Int)]())((res, elem) => {
  val e2 = mapper(elem)
  if(res.isEmpty || e2>res.head._2) 
    Seq((elem,e2)) 
  else if (e2==res.head._2) 
    res++Seq((elem,e2)) 
  else res 
}).map(_._1) // keep only original elements

// test with your list
scala> getMaxElems1(s)(mapper)
res14: Seq[Int] = List(-2, -2, 2, 2)

//test with a list containing also non maximal elements
scala> getMaxElems1(Seq(-1, 2,0, -2, 1,-2))(mapper)
res15: Seq[Int] = List(2, -2, -2)

備考：複雑さについて

上で示したアルゴリズムは、N個の要素を持つリストに対してO（N）の複雑さを持っています。でも：

  • すべての要素をマッピングする操作は複雑ですO（N）
  • 最大値を計算する操作は複雑ですO（N）
  • zipの操作は複雑ですO（N）
  • 最大値に従ってリストをフィルタリングする操作も複雑ですO（N）
  • すべての要素をマッピングする操作は複雑さO（M）であり、Mは最終要素の数です。

したがって、最後に、質問で提示したアルゴリズムは、私の回答のアルゴリズムと同じ複雑さ（品質）を持ち、さらに、提示したソリューションは私のものよりも明確です。したがって、「foldLeft」がより強力な場合でも、この操作にはあなたのアイデアをお勧めしますが、元のリストを圧縮してマップを1回だけ計算します（特に、マップが単純な正方形よりも複雑な場合）。これは、question / chat/commentsの*scala_newbie*を使用して計算されたソリューションです。

def getMaxElems2(s:Seq[Int])(mapper:Int=>Int):Seq[Int] = {
  val mappedS = s.map(mapper) //map done only once 
  val m = mappedS.max         // find the max
  s.zip(mappedS).filter(_._2==themax).unzip._1
}

// test with your list
scala> getMaxElems2(s)(mapper)
res16: Seq[Int] = List(-2, -2, 2, 2)

//test with a list containing also non maximal elements
scala> getMaxElems2(Seq(-1, 2,0, -2, 1,-2))(mapper)
res17: Seq[Int] = List(2, -2, -2)
于 2012-11-24T19:15:47.673 に答える