Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.3k views
in Technique[技术] by (71.8m points)

java - Benefits of internal iterations

I just wanted to know, what the real benefits of Internal vs External Iterations are and why it is better to use internal operations (that's what I heard at least). Is it also possible to delete elements of a collection while internally iterating over the collection? Like in the code example:

I know that the code readability of internal iterations is better, but are there some other benefits like performance improvements?

//List with Strings of Fruit-Names
      Iterator i = aList.iterator();
      String str = "";
      while (i.hasNext()) {
         str = (String) i.next();
         if (str.equals("Orange")) {
            i.remove();
            System.out.println("
The element Orange is removed");
            break;
         }
      }
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Your condition is somewhat simplistic, as you could simply use aList.remove("Orange") resp. aList.removeAll(Collections.singleton("Orange")) instead, but there is an alternative with internal iteration which also works with more complex conditions, aList.removeIf(str -> str.equals("Orange")).

In case of ArrayList, this will immediately show the advantage of internal iteration: in case of calling remove() on an Iterator, the ArrayList has no control over the loop, hence doesn’t know when you exit it resp. abandon the Iterator. You can access the list through the List interface at any time, reading and continue iterating or writing and not iterating further.

So every time you invoke remove(), the list has to be brought into a consistent state, i.e. all subsequent elements have to be copied at the right place when removing an element. This gives iterating and removing from an ArrayList a worst case of O(n2) time complexity.

In contrast, the removeIf method only has to provide a completed state of the List when the method returns. Hence, it may postpone copying elements to the point when the final position is known, which makes it an O(n) operation. So, for large lists, there’s a significant performance advantage.

Generally, methods with internal iterations provide the possibility of being implemented optimized for the particular internal data structure, while never being worse than the external loop, as the iterator based loop is the fallback of these methods anyway.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...