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

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

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

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

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

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

Точно ли это имело бы смысл для java.util.Random implements Iterator<Double>?

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


java performance iterator
person polygenelubricants    schedule 23.03.2010    source источник
comment
нет, нет, да / нет (я думаю), нет, мне нравится, нет, поскольку random может возвращать множество следующих типов - какой из них вы выберете? и, наконец: если у вас есть что-то, что удобно использовало бы итератор этого типа и не нуждалось в remove / hasNext, конечно, мне нравится   -  person Carl    schedule 23.03.2010

Ответы (5)


arrow_upward
7
arrow_downward

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

person bmargulies    schedule 23.03.2010

arrow_upward
3
arrow_downward

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

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

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

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

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

person Joachim Sauer    schedule 23.03.2010

arrow_upward
1
arrow_downward

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

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

person Rex Kerr    schedule 23.03.2010

arrow_upward
1
arrow_downward

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

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

person Steve B.    schedule 23.03.2010

arrow_upward
0
arrow_downward

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

for(long prime : new PrimeGenerator()){
    //do stuff
    if(condition){
        break;
    }
}
person Enno Shioji    schedule 23.03.2010
comment
не говоря уже о том, что if (condition) мог быть представлен в hasNext в любом случае - просто может быть удобнее закодировать его, как вы. - person Carl; 23.03.2010