I read on some email signature something along the lines of:
“If I had a dollar for every for(int i=0; i < size; i++) { ... } I've written I'd be rich"
After coding on Android and learning about some of the tips for performance, like
"With an ArrayList, a hand-written counted loop is about 3x faster"
If you do use ArrayLists a lot you then have that tip in the back of your head and you end up with a lot of code like the following:
List; myList = ... ;
int size = myList.size();
for (int i=0; i < size; i++) {
T elem = myList.get(i);
//do something with elem
}
Eventually there was a moment when I said, I need a freaking map function, I’m sick of this little pattern, surprisingly I couldn’t find a map() function anywhere on the java collection framework. So I went and did this.
Warning: These mapping utilities are meant only for Lists with RandomAccess capabilities (.get(i) happens in constant time). Do not use with LinkedList or other lists that don’t implement RandomAccess, otherwise you’ll end up with up to O(n^2) times. Thanks to Roger Kapsi for noticing this issue. [you can now tell how much we like to use ArrayList]
//what I think would be the equivalent of a lambda or closure in Python...
public interface MapFunction {
public void map(T t);
}
And then on one of my utils classes I added a static method map that looks like this:
public static void map(List list, MapFunction mapFunction) {
int size=list.size();
for (int i=0; i < size; i++) {
mapFunction.map(list.get(i));
}
}
So now, everytime I need to iterate over a whole list and do something to each element it's a lot cleaner
//let's serialize all the messages...
List messages = ...;
Utils.map(messages, new MapFunction {
public void map(Message message) {
Engine.INSTANCE.SERIALIZER.save(message);
}
});
done deal.
Update
Here's another Map utility that let's your map() function know about the index of your current element. You may have to treat certain elements differently based on their position in the list.
This time your function takes a "IndexMapFunction
public static void map(List list, IndexedMapFunction mapFunction) {
int size = list.size();
for (int i = 0; i < size; i++) {
mapFunction.map(i, list.get(i));
}
}
The interface for IndexedMapFunction looks like this
public interface IndexedMapFunction {
public void map(int i, T obj);
}
In your implementation of "map(int i, T obj)", "i" represents the position of the element being treated. You could do different things depending on what position of the List you are. For example, you could know if you're at the beggining or end of the list, or maybe you could other data structure telling you things about some positions in the list in question.
I would change the map() function to the following because the statement is only true for some Lists, in particular ArrayList but not for all Lists. Your for loops will be crippled to an O(n**2) operation if you pass a LinkedList to it for example and that’s something you want to avoid at all cost.
public static void map(Iterable elements, MapFunction mapFunction) {
if (elements instanceof List && elements instanceof RandomAccess) {
List list = (List)elements;
int size = list.size();
for (int i = 0; i < size; i++) {
mapFunction.map(list.get(i));
}
} else {
for (T element : elements) {
mapFunction.map(element);
}
}
}
Also, the MapFunction has no clue about the context of the elements. You can therefore let the for loop run backwards and save the size variable.
for (int i = list.size()-1; i >= 0; –i) {
mapFunction.map(list.get(i));
}
You are right sir. We have been using that map function only with ArrayList which implements get() in constant time, otherwise you end up with very sucky N^2 performance.
How about this implementation?
[code]
public static <T> void map(final Collection<T> list, final MapFunction<T> mapFunction) {
final Iterator<T>it=list.iterator();
for (int index=0;it.hasNext();++index) {
mapFunction.map(index,it.next());
}
}
[/code]
I fear you may have outsmarted yourselves.
Why is old-fashioned looping through an ArrayList using an index more efficient than using an enhanced for loop in the first place? It seems to me the main reason is object allocation, not the indirection of replacing comparison and incrementation operations with function calls to the ArrayList’s Iterator’s next() and hasNext() methods.
Why is object allocation the issue? Every single time an enhanced for loop is executed a new Iterator object is created to manage the iteration. This is the real penalty since it brings in the cost of allocating a new object and later garbage-collecting it. Nested extended for loops in particular create a lot of short-lived Iterator objects.
No new object is allocated to perform an old fashioned indexed loop.
Now look at the likely performance of the map function approach.
Every execution of the loop entails the allocation of a new MapFunction object. The cost would surely be similar to using the enhanced for loop, which behind the scenes allocates an Iterator object. Does the performance of this map function approach even exceed that of the enhanced for loop in real life?
I have to say that I like the enhanced for loop best because it’s harder to get it wrong, but I’d prefer the old fashioned indexed loop (if performance is the issue) to the above alternatives. The old indexed for loop seems a fine little idiom to me. But then I too am old. Very old. (I probably have earned a dollar for each of the indexed for loops I’ve written but those dollars are mostly long since spent.)
The ArrayList.iterator() method creates a new Iterator object each time it’s called for good reasons: different iterators might be iterating through the same list at the same time and the ArrayList.iterator() function knows nothing of the context from which it was called. But if you were in a position to avoid having to create new Iterator objects all the time then you could use the enhanced for loop efficiently, e.g. by making the extended for loop’s Iterable to be at the same time its own Iterator.
You would define an economical stock of these Iterable/Iterator objects in the calling scope, wrapping your ArrayLists. Then you would use them in place of the ArrayLists they wrap as the Iterable in extended for loops, especially nested ones. No new object would be created when such an Iterable was used in an extended for loop. (An alternative to this encapsulation of ArrayList would be create a class extending ArrayList which would be its own unique Iterator.)
public class ArrayListReusableIterator implements Iterator, Iterable {
private int listIndex=0;
private ArrayList arrayList;
public ArrayListReusableIterator(ArrayList arrayList) {
this.arrayList= arrayList;
}
@Override
public Iterator iterator() {
listIndex=0;
return this;
}
@Override
public boolean hasNext() {
return listIndex<arrayList.size();
}
@Override
public T next() {
T t = arrayList.get(listIndex);
listIndex ++;
return t;
}
@Override
public void remove() {
throw new NotImplementedException();
}
}