Ограничить ListIterator первыми 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

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

Answer 2

Похоже, что функция будет добавлена ​​в гуаву, в настоящее время (с r06) в бета-версии:

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

Answer 3

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

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

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

Answer 4

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

Метод ArrayList.sublist(int,int) не создает копию исходного списка. Вместо этого он возвращает экземпляр SubList, который оборачивает исходный 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 элементов.)