 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / December 2005Difference between Java iterator and iterator in Gang of Four
Hi, I just read through the Design Patterns book of Gamma et al., also known as the GoF, and noticed that they define a method Start in their iterator, which does nothing but set the index to zero. I would find this possibility rather useful, as I want to recycle some iterators. Right now I have to recreate them at the end of the loop every time. This seems rather inefficient to me. Why didn´t Sun include this method in the Iterator interface? Do they have good reasons for this? H.  SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > I just read through the Design Patterns book of Gamma et al., also known > as the GoF, and noticed that they define a method Start in their [quoted text clipped - 5 lines] > Why didn=3Ft Sun include this method in the Iterator interface? Do they > have good reasons for this? If this seems rather inefficient, I'd suggest you re-evaluate your ideas of performance. It could be nice if iterators had some kind of a reset method... but recreating an iterator from an existing collection is hardly expensive. My best guess as to why it wasn't included is that Iterator is intended for any Collection... not necessarily one that's in memory all the time or that even has a defined order; I can conceive of such a structure for which there is not easy way to start over without performing a significant amount of work... or for which it's not even possible at all. (Of course, in the world of optional methods -- the Collections API -- it almost seems unusual that something would be omitted just because it may not apply.) Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation >If this seems rather inefficient, I'd suggest you re-evaluate your ideas >of performance. It could be nice if iterators had some kind of a reset >method... but recreating an iterator from an existing collection is >hardly expensive. You can write an iterator to process records coming in over a socket, e.g. the stock quotes for a company. One problem with allowing an iterator to be reusable is defining whether it has to give the same answers the second time. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. Chris Smith uitte de volgende tekst op 19/12/2005 18:15: >>I just read through the Design Patterns book of Gamma et al., also known >>as the GoF, and noticed that they define a method Start in their [quoted text clipped - 19 lines] > API -- it almost seems unusual that something would be omitted just > because it may not apply.) Thanks all for the different answers, they shed some light on the problem. I see that you can conceive structures which are hard to restart iterating /in the same order/, but I merely want the option to say: start your iteration again, for example, in (Hash)Set, there is no order guarantee at all. But as indeed they are only a lightweight wrapper of indexes, and with what I read about the differences in object creating between Java and C++, I can see why they left this out. H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > I see that you can conceive structures which are hard to restart > iterating /in the same order/, but I merely want the option to say: > start your iteration again, for example, in (Hash)Set, there is no order > guarantee at all. But as indeed they are only a lightweight wrapper of > indexes, and with what I read about the differences in object creating > between Java and C++, I can see why they left this out. See Roedy's reply. It may be that the iteration can't be repeated at all, in any order. (Again, there's no consistent justification, though, for leaving this out while including other optional operations... except that someone didn't think this was as useful.) Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation > > I see that you can conceive structures which are hard to restart > > iterating /in the same order/, but I merely want the option to say: [quoted text clipped - 7 lines] > for leaving this out while including other optional operations... except > that someone didn't think this was as useful.) Yes. I don't understand why remove() is part of the Iterator interface, while being optional. Wouldn't it be better design to have a separate interface, say, RemovableIterator, for those times when you also want to support remove()? Moveover, the remove() method mutates the underlying collection, whereas the simpler interface without remove() could guarantee never to change it. Any insight into why remove() is part of Iterator? >Yes. I don't understand why remove() is part of the Iterator >interface, while being optional. Wouldn't it be better design >to have a separate interface, say, RemovableIterator, for >those times when you also want to support remove()? I agree. I think that was just an error. They did not realise until it was too late that forcing you to support remove was too onerous and the code would likely never be used. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > I agree. I think that was just an error. They did not realise until it > was too late that forcing you to support remove was too onerous and > the code would likely never be used. Au contraire. From the beginning, it was very carefully considered and decided that remove() should be provided and made into an optional operation. Optional operations were quite deliberately designed into the collections API. The goal was to reduce the number of public interfaces. Careful before you dismiss this. Mutable versus immutable is only one possible distinction. Arrays.asList creates a List implementation that supports only that mutation which does not change the length. The danger was that different operations might be legal in different contexts, and there might be a combinatoric explosion of superinterfaces if the API walked that road. Whether this was a good idea or not is another matter. I believe that it was not. However, it was a deliberate decision made in response to real challenges. It was a conscious decision for simplicity over safety. (How that decision meshes with the later decision to add generics to the type system is a question for a different thread. Clearly, these value judgements are made differently by different people at Sun.) Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation >Au contraire. From the beginning, it was very carefully considered and >decided that remove() should be provided and made into an optional >operation. How do you know this? SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > >Au contraire. From the beginning, it was very carefully considered and > >decided that remove() should be provided and made into an optional > >operation. > > How do you know this? Mostly I deduced this from common sense. Though I hardly think Sun is immune from making mistakes, the level of mistake which you suggest -- to forget about the possibility of immutable collections when designing a general-purpose collections API -- would be phenomenally negligent and require that they employ only complete morons. That's clearly not true. Incidentally, Google confirms my thoughts on the matter. This information is out there for the finding. See, for example: http://java.sun.com/j2se/1.4.2/docs/guide/collections/designfaq.html Of course, no one wrote that text to defend against this specific outrageous charge of idiocy, but "We would have supported it if we believed it were feasible" implies that, in fact, they thought about it and decided it wasn't feasible... not that they forgot and then never bothered to fix it. You'll also probably recall that the design team at Sun went out of their way to ask Doug Lea for input based on the experience he had with his then-popular third-party collections framework. Since Doug's framework did provide compile-time checking for immutable iterators and collections via interface hierarchies, it's doubly unlikely that the idea never occurred to Sun's design team even while they read his existing code to implement it. Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation > Yes. I don't understand why remove() is part of the Iterator > interface, while being optional. Wouldn't it be better design [quoted text clipped - 3 lines] > collection, whereas the simpler interface without remove() > could guarantee never to change it. Alpha versions of 1.5 had a SimpleIterator (or ReadOnlyIterator). Iterator extended SimpleIterator. Iterable.iterator returned an SimpleIterator. As now, Collection extended Iterable. Unfortunately having bridging botched by javac rather than implemented by the JVM gives slightly different semantics. (In class files, methods override if name, parameters and return type match, and the overridden method is accessible. Bridge methods override the old method, forwarding to the new, narrower typed method.) Old classes directly implementing Collection did not have the bridge method, so would throw an AbstractMethodError if used through the Iterable interface (e.g. in the enhanced for loop). Tom Hawtin SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ Hendrik Maryns sez: [ iterators ] > start your iteration again, for example, in (Hash)Set, there is no order > guarantee at all. But as indeed they are only a lightweight wrapper of > indexes, and with what I read about the differences in object creating > between Java and C++, I can see why they left this out. Errm, they aren't lightweight wrappers for indexes. Recall that Java has no separate RandomAccess and SequentialAccess lists, there's only one List and it's implicitly sequential access. Which means that rewinding an iterator is O(n) -- creating a new one will be much faster in most cases. Also, every index-based access is O(n), giving you O(n) for for( Iterator i = l.iterator(); i.hasNext(); ) e = i.next(); and O(n^2) for for( int i = 0; i < l.size(); i++ ) e = l.get( i ); What's beyond me is why they didn't make Iterator.next() return a boolean or void, and Iterator.get() for getting to the element: either while( i.next() ) or for( Iterator i = l.iterator(); i.hasNext(); i.next() ) would be much better than what we have now. Dima SignatureSufficiently advanced incompetence is indistinguishable from malice. Dimitri Maziuk wrote On 12/20/05 12:20,: > Hendrik Maryns sez: > [ iterators ] [quoted text clipped - 7 lines] > Java has no separate RandomAccess and SequentialAccess lists, > there's only one List and it's implicitly sequential access. There is only one java.util.List, but there's no implication of an access pattern. Various methods of List take a position argument, and there is no requirement or even suggestion that successive calls to the methods should use adjacent indices. True, some particular implementations of List cannot provide efficient random access -- but that's not a characteristic of List, but of (for example) LinkedList. Implementations like ArrayList most definitely do support efficient random access. > Which means that rewinding an iterator is O(n) -- creating a > new one will be much faster in most cases. Even a half-clever programmer can do better than that. If there's an efficient way to start a brand-new Iterator at the beginning of the List, a hypothetical Iterator.rewind() method could use it. > Also, every index-based access is O(n), giving you O(n) for > for( Iterator i = l.iterator(); i.hasNext(); ) > e = i.next(); > and O(n^2) for > for( int i = 0; i < l.size(); i++ ) > e = l.get( i ); True for LinkedList, but not true for ArrayList or Vector. > What's beyond me is why they didn't make Iterator.next() > return a boolean or void, and Iterator.get() for getting > to the element: Ah, but "they" did exactly what you ask! They used different names: hasNext() for your next() and next() for your get(), but the same[*] functionality is provided. Is it just the choice of names that bothers you? [*] "The same" for "return a boolean." I confess I do not understand what you mean by "return a [...] void," since the only use of `void' in Java is to indicate that a method returns nothing at all, not ever. > either > while( i.next() ) > or > for( Iterator i = l.iterator(); i.hasNext(); i.next() ) > would be much better than what we have now. The first is "what we have now," with a change of name. The second is *exactly* "what we have how," so I don't see how it "would be much better" than what it already is ...? SignatureEric.Sosman@sun.com Eric Sosman sez: > Dimitri Maziuk wrote On 12/20/05 12:20,: ... > There is only one java.util.List, but there's no implication > of an access pattern. Various methods of List take a position > argument, and there is no requirement or even suggestion that > successive calls to the methods should use adjacent indices. RTF Javadoc for java.util.List, spec. where it says "Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation." > True, some particular implementations of List cannot provide > efficient random access -- but that's not a characteristic of > List, but of (for example) LinkedList. Implementations like > ArrayList most definitely do support efficient random access. Again, RTFM. Iterator is part of Collection that does not guarantee anything, esp. wrt. underlying storage -- so there *is* no guarantee of efficient random access. Cf. java.util.Iterator<foo> Vector::iterator<foo> -- the latter form is "iterator over random access container", the former is "iterator over any collection". Besides, it's not "some particular implementations", it's 50% of existing implementations of List that don't provide efficient random access. > Even a half-clever programmer can do better than that. If > there's an efficient way to start a brand-new Iterator at the > beginning of the List, a hypothetical Iterator.rewind() method > could use it. Sure, if it could repoint "this" to the brand-new iterator. ... > [*] "The same" for "return a boolean." I confess I > do not understand what you mean by "return a [...] void," > since the only use of `void' in Java is to indicate that > a method returns nothing at all, not ever. You don't seem to understand much, do you? Cf. while( i.hasNext() ) { name = i.next().getName(); num = i.next().getNumber(); } // boolean next() while( i.next() ) { name = i.get().getName(); num = i.get().getNumber(); } // void next() for( i = l.iterator(); i.hasNext(); i.next() ) { name = i.get().getName(); num = i.get().getNumber(); } RTF JLS # 8.4 where it says "void" is a method result type. Dima SignatureWe're part of that admittedly-too-small group that is trying to save the human race from itself. With any luck, we'll fail abjectly and the cockroaches will win out. -- Mike Andrews Dimitri Maziuk wrote On 12/20/05 19:07,: > Eric Sosman sez: > [quoted text clipped - 14 lines] > typically preferable to indexing through it if the caller does not > know the implementation." I draw your attention to the word "may" and to the phrase "some implementations." In your earlier posting you stated as fact that every List required O(n) time to access the n'th element. This is true only of some List implementations, definitely not of all. >> True, some particular implementations of List cannot provide >>efficient random access -- but that's not a characteristic of [quoted text clipped - 8 lines] > -- the latter form is "iterator over random access container", > the former is "iterator over any collection". Iterator has nothing to do with random access, and Iterator is not "part of Collection." There seems to be a communication problem here. > Besides, it's not "some particular implementations", it's 50% > of existing implementations of List that don't provide efficient [quoted text clipped - 7 lines] > Sure, if it could repoint "this" to the brand-new iterator. > ... No such magic (and it would indeed need to be magical) is needed. My claim is that if List.iterator() has an efficient way to initialize a new Iterator properly, then the same initialization technique is available to the hypothetical Iterator.rewind(). >> [*] "The same" for "return a boolean." I confess I >>do not understand what you mean by "return a [...] void," >>since the only use of `void' in Java is to indicate that >>a method returns nothing at all, not ever. > > You don't seem to understand much, do you? Cf. Was that called for? > while( i.hasNext() ) { > name = i.next().getName(); [quoted text clipped - 12 lines] > num = i.get().getNumber(); > } Aha! Now I see what you were after; it certainly wasn't apparent in your earlier posting. You want a get() method that does not advance the "current position" of the Iterator. I'm not sure why you want such a thing, but if you really want it you can easily wrap the Iterator in a helper class. > RTF JLS # 8.4 where it says "void" is a method result type. I'm aware that `void' is a method result type, but you expressed a desire for Iterator.next to "return a boolean or void." Not even a `void' method can "return a void." SignatureEric.Sosman@sun.com Eric Sosman sez: > Dimitri Maziuk wrote On 12/20/05 19:07,: ... >> "Note that these operations may execute in time proportional to >> the index value for some implementations (the LinkedList class, >> for example). Thus, iterating over the elements in a list is >> typically preferable to indexing through it if the caller does not >> know the implementation." I love how they phrased it: "some implementations". Until they come up with quantum subspace memory, there's only two and half of them is sequential access. > I draw your attention to the word "may" and to the > phrase "some implementations." In your earlier posting > you stated as fact that every List required O(n) time to > access the n'th element. This is true only of some List > implementations, definitely not of all. I draw you attention to "does not know the implementation". If all you have is "a List" then it's O(n). Similarly, if all you have is "a Collection", then it's O(n) -- see below. >> Iterator is part of Collection that does not >> guarantee anything, esp. wrt. underlying storage ... > Iterator has nothing to do with random access, and > Iterator is not "part of Collection." There seems to be > a communication problem here. Riight. Let me try this again in words of one syllable or less: Iterator is part of Collections API, it's an iterator over "a Collection". Since "a Collection" has no guarantees wrt underlying storage (unlike c++ Containers), designers of iterator must assume the worst case scenario where cost of rewinding the iterator is proportional to number of elements in the collection. Creating a new iterator, on the other hand, is presumed to be O(1). Again, note how Java Iterator is "an iterator", not c++-style "ArrayList::Iterator" or "LinkedList::Iterator". >> Sure, if it could repoint "this" to the brand-new iterator. >> ... [quoted text clipped - 4 lines] > the same initialization technique is available to the > hypothetical Iterator.rewind(). Que? Iterator foo = bar.iterator(); while( foo.hasNext() ) { do stuff } foo.rewind(); while( foo.hasNext() ) { do more stuff } Explain to me how this works if foo.rewind() initializes a new bar.iterator() "properly". > I'm aware that `void' is a method result type, but you > expressed a desire for Iterator.next to "return a boolean > or void." Not even a `void' method can "return a void." "(return a boolean) or void". Get it now? Dima SignatureRelativity, Uncertainty, Incompleteness, Undecidability: choose any four > Riight. Let me try this again in words of one syllable or less: Must you be such a jackhole? Do you really think you look clever or admirable by putting down other people? > Iterator is part of Collections API, it's an iterator over "a > Collection". Since "a Collection" has no guarantees wrt underlying > storage (unlike c++ Containers), designers of iterator must assume > the worst case scenario where cost of rewinding the iterator is > proportional to number of elements in the collection. Creating a new > iterator, on the other hand, is presumed to be O(1). PS you're not very good at counting, are you? Signaturemonique Ask smart questions, get good answers: http://www.catb.org/~esr/faqs/smart-questions.html Monique Y. Mudama sez: >> Riight. Let me try this again in words of one syllable or less: > > Must you be such a jackhole? Do you really think you look clever or > admirable by putting down other people? public boolean giveafuck() { return false; } >> Iterator is part of Collections API, it's an iterator over "a >> Collection". Since "a Collection" has no guarantees wrt underlying [quoted text clipped - 4 lines] > > PS you're not very good at counting, are you? Nah, I've computers for that. HTH,HAND Dima SignatureDouble d = new Double(2.0); d = new Double(d.doubleValue() * d.doubleValue()); I regard Double variables as mutable, considering this one started as 2.0 and ended up as 4.0. -- Brendan Guild Dimitri, Here is a list you can use in all of your code that will give you that great sequential access you want. import java.util.*; public class MyList<T> extends ArrayList<T> { Random rand = new Random(); public T get(int index) { while (rand.nextInt(index+1) != index) { System.out.println("Damn! where did I put that thing again?"); } return super.get(index); } } > What's beyond me is why they didn't make Iterator.next() > return a boolean or void, and Iterator.get() for getting [quoted text clipped - 3 lines] > for( Iterator i = l.iterator(); i.hasNext(); i.next() ) > would be much better than what we have now. Quite. Try writing an iterator filter with strong exception guarantees. It ain't pretty. You can't quite do it if removes are permitted. Tom Hawtin SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ > I want to recycle some iterators. >Right now I have to recreate them at the end of the loop every time. >This seems rather inefficient to me. An Iterator is extremely light weight, it is nothing more than a reference structure for pointing at the original collection, but I guess you know that if you've read GOF. Take a look at the sun source (eg AbstractList) for their various implementations they have just a couple of int index/cursor attributes. It is very normal to create them on any whim. It is the choice method to access collections, so much so there's now the for/each language augmentation to support it. -- Mike W It's better to keep the interface as minimal as possible, to keep the limitations on where it can be used to a minimum, and to keep the effort required in implementing it to a minimum. Creating another Iterator is very cheap, for all collections I've known about. Use a profiler to examine performance, don't guess. Oh, when you reimplement List, feel free to make your own RestartableIterator for these purposes. Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.