ListIterator를 첫 번째 N 요소로 제한합니다 (최적화)
-
06-07-2019 - |
문제
시작부터 대부분의 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 개 미만의 요소입니다.)