Контракт производительности итератора (и использование на не-коллекциях)

Question

Если все, что вы делаете, - это простая однопроходная итерация (т. Е. Только hasNext() и next(), не remove()), гарантируете ли вы линейное время и / или амортизируемые постоянные затраты на операцию? 1004 *

Указано ли это где-нибудь в Iterator контракте?

Существуют ли структуры данных / Java Collection, которые не могут быть повторены за линейное время?

java.util.Scanner implements Iterator<String>. A Scanner вряд ли является структурой данных (например, remove() не имеет абсолютно никакого смысла). Это считается ошибкой дизайна?

Что-то вроде PrimeGenerator implements Iterator<Integer> считается плохим дизайном, или это именно то, для чего Iterator? (hasNext() всегда возвращает true, next() вычисляет следующее число по требованию, remove() не имеет смысла).

Аналогично, имело бы смысл java.util.Random implements Iterator<Double>?

Должен ли тип действительно реализовывать Iterator, если он эффективно использует только одну треть своего API? (т.е. нет remove(), всегда hasNext())

Answer 1

Такой гарантии нет. Как вы указали, любой может моделировать что угодно в качестве итератора. Отдельные производители итераторов должны будут указать свою индивидуальную производительность.

Answer 2

Ничто в документе Iterator не содержит упоминаний о каких-либо гарантиях производительности, поэтому нет никакой гарантии.

Также не имеет смысла требовать такого ограничения для такого универсального инструмента.

Гораздо более полезным ограничением будет документ iterator() метод для указания временных ограничений, которые этот Iterator экземпляр выполняет (например, Iterator по общему назначению Collection будет скорее всего сможет гарантировать линейное время работы).

Точно так же ничто в документации не требует, чтобы hasNext() когда-либо возвращал false, поэтому бесконечный Iterator был бы совершенно действительным.

Однако существует общее предположение, что все Iterator экземпляры ведут себя как "нормальные" Iterator экземпляры, возвращаемые Collection.iterator(), в том смысле, что они возвращают некоторое количество значений и end в некоторый момент , Это не требуется в документации, и, строго говоря, любой код, зависящий от этого факта, будет слегка нарушен.

Answer 3

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

В этом смысле поток простых чисел или объектов списка имеет смысл, и модель не подразумевает ничего о конечности источника данных.

Answer 4

Все ваши предложения звучат разумно для Iterator. Документы API в явном виде говорят, что remove не нужно поддерживать, и предлагают не использовать более старый Enumeration, который работает так же, как Iterator, только без удаления.

Кроме того, потоки бесконечной длины являются очень полезной концепцией в функциональном программировании и могут быть реализованы с Iterator, который всегда hasNext. Это функция, которая может обрабатывать любой случай.

Answer 5

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

for(long prime : new PrimeGenerator()){
    //do stuff
    if(condition){
        break;
    }
}