0

アプリケーション サーバーを作成していますが、メッセージ送信ループがあります。メッセージはフィールドで構成されているため、フィールドを反復処理する反復子と見なすことができます。また、メッセージ ループによって処理されるメッセージ キューがありますが、ループはいつでも中断でき (たとえば、ソケット バッファーがいっぱいになった場合)、後で再開できます。現在の実装は次のようになります。

private val messageQueue: Queue[Iterator[Field]]

sent = 0
breakable {
  for (iterator <- messageQueue) {
    for (field <- iterator) {
      ... breakable ...
    }
    sent += 1
  }
} finally messageQueue.trimStart(sent)

これは機能し、悪くはありませんが、++ 演算子を使用して反復子を連結する反復子でキューを置き換えることができれば、コードを少しきれいにできると思いました。言う：

private val messageQueue: Iterator[Field] = message1.iterator ++ message2.iterator ++ ...

breakable {
  for (field <- messageQueue) {
    ... breakable ...
  }
}

コードはよりきれいに見えますが、パフォーマンスの問題があります。連結された反復子は内部で (不均衡な) ツリーを形成するため、next() 操作には O(n) の時間がかかります。したがって、反復には全体で O(n^2) の時間がかかります。

要約すると、メッセージは 1 回だけ処理する必要があるため、キューを Traversable にする必要はありません。Iterator (TraversableOnce) で十分です。メッセージ キューを連続した反復子のコレクションとして表示したいのですが、++ にはパフォーマンスの問題があります。コードをよりクリーンにすると同時に効率的な優れたソリューションはありますか?

4

2 に答える 2

2

Streamと を使用し#:::てメッセージを遅延連結することを考えたことはありますか?

private val messageQueue: Stream[Field] = message1.toStream #::: message2.toStream #::: ...

breakable {
  for (field <- messageQueue) {
    ... breakable ...
  }
}

ここでの時間の複雑さについては、連結している反復子の数が O(n) になると思います (toStream各反復子と#:::それらを一緒に呼び出す必要があります)。ただし、個人toStreamと#:::操作は怠け者であるため、O(1) にする必要があります。のtoStream実装は次のIteratorとおりです。

def toStream: Stream[A] =
    if (self.hasNext) Stream.cons(self.next, self.toStream)
    else Stream.empty[A]

Stream.cons の 2 番目の引数は名前による呼び出しであるため、これには一定の時間がかかります。そのため、実際にテールにアクセスするまで評価されません。

ただし、Stream への変換では、要素アクセスごとに一定のオーバーヘッド要素がnext追加されます。つまり、イテレータを呼び出すだけでなく、ストリームのレイジー テールを強制して含まれる値にアクセスするために、いくつかの追加のメソッド呼び出しを行う必要があります。

于 2013-02-28T04:11:14.410 に答える
2

それらを平らにするとどうなりますか？

def flattenIterator[T](l: List[Iterator[T]]): Iterator[T] = l.iterator.flatten
于 2013-02-28T04:14:45.417 に答える