ListIteratorを最初のN個の要素に制限する（最適化）

StackOverflow https://stackoverflow.com/questions/1618759

質問

List の先頭から最大でN個の要素を返すイテレータを取得する簡単で高速な方法は何ですか？

思いつく最も簡単なバージョンは次のとおりです。

＃1：

import com.google.common.collect.Iterators;

// ...

public static <E> Iterator<E> lengthLimitedIterator(Iterable<E> source, int maxLen) {
    return Iterators.partition(source.iterator(), maxLen).next().iterator();
}

＃2：

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    return source.subList(0, Math.min(source.size(), maxLen)).iterator();
}

残念ながら、どちらのバージョンも一時的な List を作成します。これは、このメソッドを何百万回もタイトなループで呼び出しているため、パフォーマンスに大きく影響します。

これに使用できる他のライブラリ関数はありますか？

注：イテレータを引数として取るメソッドにリストを渡すため、リストの繰り返しを避けることはできず、そのクラスを変更することはできません。

役に立ちましたか？

解決

機能は、現在（r06現在）ベータでグアバに追加されます：

public static <T> Iterator<T> limit(Iterator<T> iterator, int limitSize)

他のヒント

リストであることは既にわかっているので、 List.subList（int fromIndex、int toIndex）メソッドを呼び出すだけです。仕様によると、subListは元のリストに支えられているため、実際には完全な List を作成するのではなく、何らかの種類のプロキシオブジェクトを作成するだけです。

これは、デコレーターが非常にうまく機能する場所です。デコレーターはカウントを保持しますが、 next（）によってインクリメントされ、コントロール hasNext（）によって使用されます。

例（意図的に不完全）：

public class LengthLimitedIterator<T>
implements Iterator<T>
{
    private Iterator<T> _wrapped;
    private int _length;
    private int _count;

    public LengthLimitedIterator(Iterator<T> wrapped, int length)
    {
        _wrapped = wrapped;
        _length = length;
    }


    public boolean hasNext()
    {
        if (_count < _length)
            return _wrapped.hasNext();
        return false;
    }

    public T next()
    {
        // FIXME - add exception if count >= length
        _count++;
        return _wrapped.next();
    }

なぜ単純ではない

list.subList(0, 42).iterator();

その一時的なリストの作成を気にする理由がわかりません。高価だと思うものは何もしません。実際、このリストを作成するのは、繰り返し処理するよりもはるかに安価です。

ArrayList.sublist（int、int）メソッドは、元のリストのコピーを作成しません。代わりに、元のArrayListをラップするSubListインスタンスを返します。 Arrayから派生したサブリストによって返される反復子もコピーを作成しません。

したがって、私のアドバイスは、ベースリストタイプとして ArrayList と sublist メソッドを使用することです。それで十分でない場合は、 limitedLengthIterator メソッドを実装する ArrayList の独自のバリアントを実装します。たとえば、同時変更をチェックするコードを取り除くことができるはずです。

パフォーマンスが心配な場合は、イテレーターを使用せず、配列のインデックスを使用します。これにより、パフォーマンスが大幅に向上します。配列の最初のN個の要素を取得するのは簡単です。

このバージョンは、他のどの例よりも高速であることがわかりました。

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    maxLen = Math.min(maxLen, source.size());
    ArrayList<E> tempList = new ArrayList<E>(maxLen);
    for (int i = 0; i < maxLen; ++ i) {
       tempList.add(source.get(i));
    }
    return tempList.iterator();
}

一時リストを作成する必要がある場合、 ArrayList は、他のライブラリメソッドによって返される装飾リストよりも高速です。

推測では、 ArrayList はVM内で特別な扱いを受けています。

これは非常に長いリストに対しては非効率かもしれませんが、私のリストは短いです（ほぼ常に50未満の要素です）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top