Ограничьте список первыми N элементами (оптимизировано)

Question

Каков простой и быстрый способ получить итератор, который возвращает не более 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 что существенно влияет на производительность, поскольку я вызываю этот метод миллионы раз в замкнутом цикле.

Есть ли какие-либо другие библиотечные функции, которые я мог бы использовать для этого?

---

Примечание:Я не могу избежать повторения списка, поскольку я передаю его методу, который принимает итератор в качестве своего аргумента, и я не могу изменить этот класс.

Answer 1

Кажется, как будто особенность будет добавлен в guava, в настоящее время (начиная с r06) находится в бета-версии:

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

Answer 2

Вы уже знаете, что это список, так что вы можете просто вызвать List.subList(int fromIndex, int toIndex) способ.Согласно спецификации, подсписок поддерживается исходным списком, так что на самом деле это не создает полноценного List, просто какой-то прокси-объект.

Answer 3

Это место, где Декоратор работает очень хорошо:ваш декоратор ведет подсчет, который увеличивается на 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();
    }

Answer 4

Почему бы просто не

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

Я не уверен, почему вы возражаете против создания этого временного списка.Это не делает ничего такого, что я бы счел дорогостоящим.На самом деле, создание этого списка намного дешевле, чем повторение по нему, что, я предполагаю, вы и делаете.

Answer 5

В ArrayList.sublist(int,int) метод не создает копию исходного списка.Вместо этого он возвращает экземпляр подсписка, который оборачивает исходный ArrayList .Итератор, возвращаемый подсписком, производным от Array, также не создает копию.

Поэтому мой совет - попробовать использовать ArrayList в качестве вашего базового типа списка и sublist способ.Если это недостаточно быстро, реализуйте свой собственный вариант ArrayList который реализует limitedLengthIterator способ.Например, вы должны быть в состоянии избавиться от кода, который проверяет наличие одновременных изменений.

Answer 6

Если вас беспокоит производительность, не используйте итератор, используйте индекс в массиве.Это даст намного лучшую производительность.Получение первых N элементов массива тривиально.

Answer 7

Эта версия оказывается быстрее, чем любой из других примеров:

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 получает какое-то особое отношение внутри виртуальной машины.

Возможно, это было бы неэффективно для очень длинных списков, но мои списки короткие (почти всегда менее 50 элементов).)