ListIterator를 첫 번째 N 요소로 제한합니다 (최적화)

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

문제

시작부터 대부분의 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 이 방법을 단단한 루프로 수백만 번 호출 할 때 성능에 크게 영향을 미칩니다.

이것에 사용할 수있는 다른 라이브러리 기능이 있습니까?

참고 : 반복자를 인수로 취하는 메소드로 전달할 때 목록을 반복하는 것을 피할 수 없으며 해당 클래스를 수정할 수 없습니다.

도움이 되었습니까?

해결책

마치 마치 마치 특징 베타에서 현재 (R06 기준) Guava에 추가됩니다.

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

다른 팁

이미 목록이라는 것을 알고 있으므로 List.subList(int fromIndex, int toIndex) 방법. 사양에 따라 Subrist는 원래 목록에 의해 뒷받침되므로 실제로 완전히 날아가는 것은 아닙니다. List, 단지 어떤 종류의 프록시 객체.

이곳은 a 데코레이터 매우 잘 작동합니다 : 데코레이터는 카운트를 유지하며 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를 감싸는 Subrist 인스턴스를 반환합니다. 배열에서 파생 된 Subrist에 의해 반환 된 반복자도 사본을 만들지 않습니다.

그래서 제 조언은 사용을 시도하는 것입니다 ArrayList 기본 목록 유형 및 sublist 방법. 충분히 빠르지 않으면 자신의 변형을 구현하십시오. ArrayList 그것은 a limitedLengthIterator 방법. 예를 들어, 동시 수정을 확인하는 코드를 제거 할 수 있어야합니다.

성능이 우려되는 경우 반복기를 사용하지 말고 배열에서 색인을 사용하십시오. 이것은 훨씬 더 나은 성능을 제공 할 것입니다. 배열의 첫 번째 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