3

Scala コードを書いていると、要素のコレクションに対して反復的に動作する「プロセッサ」関数があり、コレクションの長さを知る必要がある場合に定期的に遭遇します。

一方、コレクションを生成する「プロバイダー」機能があるため、すでに長さを知っています。生成されたコレクションはList[T]、Array[T]またはSet[T]などですが、 の場合でもList[T]、私のジェネレーターはサイズを知っています (List型がそれを格納していなくても)。

したがって、「プロセッサ」関数は、すべてのコレクション型に適合すると思われる最も一般的な型 をパラメーターとして取るものとして自然に宣言しIterable[T]ます。ただし、その後、内部的に O(N) のコストで反復コレクション トラバーサルを介してサイズを調べる必要があり、これは望ましくありません。

したがって、私の素朴な解決策は、次のような新しい型を作成しIterableWithSize[T]、プロバイダーとプロセッサの関数にこの型を作成して取得させることです。どちらSeq[T]もIndexedSeq[T]法案に合わないようです。しかし、これは比較的一般的な使用例のように思われるので、もっと慣用的な方法があるのではないかと思います。それは何でしょう？

4

5 に答える 5

2

Scalaコレクションでは、のようなパフォーマンスに敏感なメソッドsizeは、トレイトから継承されませんが、ボトム型でオーバーライドされます。たとえば、immutable.HashSet：の実装を参照してください。

https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_0_1/src//library/scala/collection/immutable/HashSet.scala

だからあなたはそれを気にする必要はありません。Traversableまたはのような高レベルの共通特性を定義するだけでIterable完了です。

于 2011-07-05T10:23:06.837 に答える
2

実際、それを回避する慣用的な方法はありません。Scala コレクションは、他の所定の方法 (Set.containsまたは などMap.get) でトラバースまたは使用されることを実際に意図していました。サイズのチェックはそれらの一部ではなく、それらのいくつかは有限でさえありません.

これIndexedSeqは比較的安全な方法です。O(logn) サイズの場合にのみ可能な O(logn) インデックス アクセスが保証されます。また、同様の理由で、かなり安全ですSet。しかし、速度をMap保証する特性を探しているなら、そこにはありません。size

于 2011-07-05T12:06:59.537 に答える
1

これを行う慣用的な方法はないと思います。ただし、次の 2 つの方法があります。

(1) Scala の List/Set/Array コレクションを拡張し、size メソッドをオーバーライドします。これは一見したように難しいことではありません。

(2) List/Set/Array コレクションをサイズとともにラップし、次のような暗黙のアンラッパーを定義します。

class IterableWithSizeWrapper[E](private val c: Iterable[E], val size: Int)
object IterableWithSizeWrapper {
  implicit def unwrap[E](iws: IterableWithSizeWrapper[E]): Iterable[E] = iws.c
}

object ListWithSizeTest {

  def process[E](iws: IterableWithSizeWrapper[E]) {
        // iws.size uses your cached size value
        // iws.take(i) forces the unwrap to the original collect
        // so iws.take(i).size takes the calculated size
    for (i <- 0 to iws.size) assert(iws.take(i).size == i)
  }

  def main(args: Array[String]) {
    process(new IterableWithSizeWrapper(List(1,2,3), 3))
    process(new IterableWithSizeWrapper(Set(1,2,3), 3))
    process(new IterableWithSizeWrapper(Array(1,2,3), 3))
  }
}
于 2011-07-06T07:48:37.890 に答える
1

どうTraversableですか？あなたが言及するすべてのコレクションはそれから継承し（Arrayを介して間接的に）、トラバーサルのためにおよび（または）をWrappedArray提供します。sizetoIterabletoIterator

于 2011-07-05T10:34:53.240 に答える
0

プロセッサ関数は を受け入れる必要がありますSeq[T]。ASeqはまさにIterable「長さを持つ」 an です。残っている唯一の問題はlength効率化です。私の知る限り、を除くすべての場合ですでに効率的ですList。List.length効率的にするには、他の人が説明するようにします: a をラップしてその長さを格納する実装を作成しSeqますList。

于 2015-05-01T22:03:22.730 に答える