10

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

私が思いつくことができる最も単純なバージョンは次のとおりです。

#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パフォーマンスに大きな影響を与える一時的なものを作成します。これは、このメソッドをタイトなループで何百万回も呼び出しているためです。

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

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

4

7 に答える 7

15

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

于 2009-10-24T19:16:05.267 に答える
8

現在（r06現在）ベータ版のguavaに機能が追加されるようです：

public static <T> Iterator<T> limit(Iterator<T> iterator, int limitSize)
于 2010-08-05T01:29:10.357 に答える
5

なぜ単純に

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

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

于 2009-10-24T19:14:20.543 に答える
5

これは、デコレータが非常にうまく機能する場所です。デコレータはカウントを保持し、それは によってインクリメントされ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();
    }
于 2009-10-24T18:59:17.183 に答える
2

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

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

于 2009-10-25T14:27:57.957 に答える
1

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

于 2009-10-25T14:01:22.710 に答える
0

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

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 未満です)。

于 2009-10-25T12:17:20.140 に答える