3

関数構造 (map、foreach、flatMap など) を使用してコレクションをループする方が良いですか? ダミーの問題として、文字列のリストがあり、さまざまな基準で文字列をフィルタリングし、それらをマップして値を取得したいと考えています。以下のコードを検討してください。

val x1 = list.filter(criteria1).map(do_something)
val x2 = list.filter(criteria2).map(do_something)

このような異なるフィルター基準が 5 つあるとすると、このようにして、リスト (大きい場合があります) を 10 回 (フィルターで 1 回、マップで 1 回) ループします。

ただし、これをすべて 1 つの for ループにグループ化し、1 回の繰り返しで 5 つの新しいリストを返したり入力したりしてから、それぞれをマップして合計 10 回ではなく 6 回のループにすることもできます。

for(i<- 0 to list.length-1){
  if(criteria1) //filter
  if(criteria2) //filter
}

このコードにより、変更可能なリストを使用せざるを得なくなる場合がありますが、厳密にはパフォーマンスの観点から、そのような状況で関数構造を使用することは理にかなっています。どちらがより良いアプローチでしょうか?

注: 上記のコード/問題は単なる例であり、私が言及している状況の種類を説明してくれることを願っています

4

6 に答える 6

7

フィルター処理とマップを行う場合は、withFilter代わりに を使用できますfilter。これにより、フィルターが遅延するため、リストを複数回走査する必要がなくなります。for-式は効率のために使用withFilterします。view他の操作に同様の遅延を提供する s を調べることもできます。

あなたが何をしようとしているのかという質問からは完全には明らかではありませんが、異なるフィルターとマップ操作に基づいて 5 つの新しいリストを出力したいと考えています。あなたが提案するようにループと可変ビルダーを使用することは、パフォーマンスが最重要である場合に合理的なアプローチであり、これがプログラムされているコレクションメソッドの数です(ソースコードを確認してください)。5 つのリストにフィルター処理してから、それぞれをトラバースしてマッピングを行う必要があると考える理由がわかりません。関数を各要素に適用して、新しいリストを作成すると同時にマップを実行しないのはなぜですか? ? 例えば

  def split[T](xs: Seq[T])(ops: (T => Boolean, T => T)*): Seq[Seq[T]] = {
    val (filters, maps) = ops.unzip
    val buffers = IndexedSeq.fill(ops.size)(ListBuffer.empty[T])
    for {
      x <- xs
      i <- buffers.indices
      if filters(i)(x)
    } buffers(i) += maps(i)(x)  
    buffers.map(_.toSeq)  // return to immutable-land
  }

  // demo: 
  val res = split(1 to 10)(
    (_ < 5, _ * 100),     // multiply everything under 5 by 100
    (_ % 2 == 1, 0 - _),  // negate all odd numbers
    (_ % 3 == 0, _ + 5)   // add 5 to numbers divisible by 3
  )

  println(res) 
  //Vector(List(100, 200, 300, 400), List(-1, -3, -5, -7, -9), List(8, 11, 14))

あなたがやりたいこと(私が思うに)をするための組み込みの方法はないと思います。再帰を使用する場合、可変状態なしでビルダー メソッドを定義できることに注意してください。

あなたの質問は本当にパフォーマンスにかかっており、時期尚早に最適化するのは簡単です。真のパフォーマンスの問題がある場合にのみ、上記を実行することをお勧めします。慣用的/単純では不十分な場合は、特定のユースケースを最適化するために調整できる場合があります。やりたいことすべてに最適化された組み込みメソッドが存在しないという事実に帰着します。

于 2012-08-23T07:01:53.180 に答える
5

次の方法でも実行できます。

val x1 = for(x <- list if criteria1) yield do_something(x)

コンパイラは実際にこれをval x1 = list.filter(criteria1).map(do_something)上記のように変換します。内包表記は、forいくつかのシーケンスに対する操作の複雑な集約をより読みやすいものに変えることができる、優れた構文糖衣です。詳細については、 Oderskyの本の関連する章を参照してください。

ただし、質問に戻ります。異なるフィルターとマップに基づいて 5 つの異なるリストを作成しようとしている場合は、代わりにリストのリストを作成する必要があります。内包表記を使用forして、変換関数の各ペアの入力リストをループできます。

これはコードを少し単純にするのに役立ちますが、問題のアルゴリズムの複雑さを実際に軽減することはできません (つまり、リストを 5 回反復する必要があります)。

この状況では、命令型のループを使用する方がはるかに効率的であるという点で、あなたは正しいと思います。リストを構築するための推奨されるデータ構造はListBuffer、要素をいずれかの端に一定時間で追加できるためです。リストの構築が完了したら、(これも一定時間で) 不変リストに変えることができます。Odersky の本には、ListBuffer の使用に関する小さなセクションもあります。これが私がそれを行う方法です:

import scala.collection.mutable.ListBuffer

val b1 = new ListBuffer[Int]
val b2 = new ListBuffer[Int]
// ... b3, b4, b5

for (x <- list) {
  val y = do_something(x)
  if (criteria1(x)) b1 += y
  if (criteria2(x)) b2 += y
  // ... criteria3, criteria4, criteria5
}

val x1 = b1.toList
val x2 = b2.toList
// ... x3, x4, x5

ミュータブルを使用しているため、ListBufferこのコードはもはや「純粋」ではありませんが、リスト全体を 5 回トラバースする必要がなくなるため、長いリストの場合は高速化する価値があるかもしれません。

この場合、ある方法が他の方法よりもはるかに優れているとは言えません。このListBuffer方法ではミューテーションを使用します。これは高速ですが、コードの保守が難しくなる可能性があります。対照的に、より機能的なバージョンは、元のリストへの繰り返し呼び出しを使用するだけfiltermapあり、おそらく読みやすく (読者が慣用的な Scala に精通していると仮定して)、保守も容易ですが、実行が少し遅くなる可能性があります。選択は本当にあなたの目標が何であるかに依存します.

于 2012-08-23T04:14:56.257 に答える
1

反復部分は本当にあなたのパフォーマンスに関係していますか? ほとんどの場合、私はそれを疑います。これが当てはまる場合にのみ、単一の for ループが高速になります。

しかし、変更可能なデータ型を使用する必要がある場合、複数のコアで実行するのははるかに難しくなり、これが実際にパフォーマンスが重要な状況にある場合、これを 8 ~ 800 コアで実行することから得られる利益は、ループの反復を 1 回節約することで得られるものはほとんどありません。

for 内包表記は多くのクロージャ インスタンスを作成する必要があるため、パフォーマンスにとって最適ではないことが多いことに注意してください。

于 2012-08-23T04:24:48.580 に答える
1

リストを何度も確認すると遅くなるかどうかはわかりません。長さのリストから長さのmリストを作成する必要があります。したがって、いずれかの方法でそれぞれを比較する必要があります。遅い場合は、一定の要因によるものです。その要因が小さいか大きいかはわかりません。knm*kn

本当にワンパスでやりたいのなら、それは間違いなく可能です。リストに対するすべての操作は、フォールドを使用して 1 回のパスで実行できます。少し複雑になる可能性があり、これ以上高速にならない理由が浮き彫りになります。確かに読みにくい:

val cs = List((criteria1, f1), (criteria2, f2))
val xs = list.foldRight(cs.map(_ => Nil)) { (x, rs) =>
  (cs zip rs).map { case ((p, f), r) =>
    if (p(x)) f(x) :: r else r
  }
}

ここで示したよりも多くの型注釈が必要になる場合があります。

ここで怠惰を有利に利用することもできます。

list.toStream.filter(???).map(???)

これは、リストをゼロ回トラバースします。結果の要素を要求するまで、要素は実際にはフィルタリングおよびマップされません。明らかに、代わりに実際のコードを使用してください???

于 2012-08-23T04:17:16.813 に答える
1

私の理解が正しければ、さまざまな基準に応じて、単一のリストから複数のリストを作成したいと考えています。groupBy目的にかなうと思います〜

val grouped = list.groupBy{ item => {
    val c1 = criteria1(item)
    val c2 = criteria2(item)
    if (c1 && c2) 12
    else if (c1) 1
    else if (c2) 2
    else 0
}}
val excluded0 = grouped - 0
val result = excluded0 mapValues do_something
val x1 = result(1) ++ result(12)
val x2 = result(2) ++ result(12)

Apocalisp が述べたように、次のように使用viewして怠惰を利用することもできます。force

val grouped = list.view.groupBy{ ...
...
val x1 = (result(1) ++ result(12)).force
于 2012-08-23T04:34:19.247 に答える
0

前に言及されていないので、 と の組み合わせがfilter経由mapで短い形式で利用可能であることも考慮する必要がありますcollect。したがって、次のようなことができます。

list.collect {
  case x if criteria1(x) => ...
  case x if criteria2(x) => ....
  case _ => ...
}

criteria1ただし、これは、 と の両方を満たすリスト要素のセマンティクスがわずかに変更されていcriteria2ます。クリスが提案したものと同様に、最初の を作成することもできますがcase x if criteria1(x) && criteria2(x)、もちろん、そのような複数の基準に拡張することはできません。

ただし、不明な点は、実際の結果リストを作成するか (最初の例のように)、または単にいくつかの副作用を実行するか (2 番目の例のように) です。後者は、次の例に示すように、わずかに異なるアプローチでも実現できます。

// A list of criteria and corresponding effects
val criteriaEffects = List( 
  ( (x : Int) => x == 0, (x : Int) => { println("Effect 1: " + x) } ),
  ( (x : Int) => x == 1, (x : Int) => { println("Effect 2: " + x) } ) )

// now run through your values list
List(0,1,2).map(x => criteriaEffects.map( p => if (p._1(x)) p._2(x) ) )
于 2012-08-23T05:43:53.113 に答える