It's not that I don't like debating, but it's useless in this case 
You're pointing out a non-problem: you deduce your conclusion from *your* imaginary implementation, which is not *mine*.
To show you that iterator filtering has theoretically no disadvantages, lets examine this example:
collection of natural numbers, in random order, from 1 to n=1'000'000. You have to extract the even items that are divisible by 3. You've 3 filtering functions (evenF, divF, andF) that does respectively the following: returns true if the passed argument is even, returns true if the passed argument is divisible by 3, and returns true if both the arguments are true. These are my tools: I've to use them in my solution.
A trivial but fast solution, without inferring anything about the data structure, is this:
foreach (int n, collection) {
if (andF(evenF(n), divF())
matching << n;
}
QList matching;
foreach (int n, collection) {
if (andF(evenF(n), divF())
matching << n;
}
To copy to clipboard, switch view to plain text mode
This takes O(n). Which is pretty fast. Actually, I think, is the best result when it comes to random order.
The solution involving iterations is like this:
struct Iterator {
Iterator(Collection c): _iter(c.iterator()) {}
bool hasNext() {
while (_iter.hasNext()) {
if (andF(evenF(_iter.peek()), divF(_iter.peek()))
return true; // Found next, is current iterator
return _iter.next(); // Filtered items, try next one
}
return false;
}
int next() {
return _iter.next(); // Next one is valid
}
private:
CollectionIter _iter;
};
Iterator i(collection);
while (i.hasNext()) matching << i.next();
struct Iterator {
Iterator(Collection c): _iter(c.iterator()) {}
bool hasNext() {
while (_iter.hasNext()) {
if (andF(evenF(_iter.peek()), divF(_iter.peek()))
return true; // Found next, is current iterator
return _iter.next(); // Filtered items, try next one
}
return false;
}
int next() {
return _iter.next(); // Next one is valid
}
private:
CollectionIter _iter;
};
QList matching;
Iterator i(collection);
while (i.hasNext()) matching << i.next();
To copy to clipboard, switch view to plain text mode
(I hope you get the idea, the code is written on-the-fly and may be wrong)
Since hasNext always advance the hidden _iter, the iterator does EXACTLY the same number of iteration over the sequence. The outer while is necessary because of the iterator nature, but doesn't make the performances worst over larger collections. This takes O(n), too.
Of course, it's OBVIOUS that the simpler implementation above requires less steps, less calls, and thus is more efficient, but both solution has the same time complexity.
Clearly, the advantages in this solutions are architectural. For example, in the first example, your're REQUIRED to execute the check in the foreach loop. If you have multiple filtering steps, you must use functors, or the advantage will vanish.
On the other hand, in the iterator example, you can use ANOTHER iterator type as CollectionIter, thus you can compose iterators, without using functors, without strict requirements when it comes to function apply order. You can't compose while loops, that's why immediate filtering is necessary in the first example.
And if you say: "yeah but the first is calculated once", while the second is not and iteration is repeated every time you need to access this, I reply with, "yes, but"
1. the first is calculated once ONLY if you don't have to change the filtering function often (as I do)
2. it's easy to cache the second example using a QList when you access the data in the second while loop. But in my program, since data and filtering functions are mutable, cache is a minor advantage. Data is asked almost once when it's needed, and the next call is almost sure to access to new data, hence requiring a caching refresh.
I hope this answers your points.
To clarify again: the point is not the speed, but the style. I hope this example is clear enough to show that speed is not compromised by extra-loops and that style (architecture?) benefits a lot from such pattern.
There are many real-life example and languages/libraries that use this approach, I'm sure they have discussed this topic (not only style, but also efficiency) enough.
Filtering iterators
Reply With Quote
Originally Posted by high_flyer
Bookmarks