Home » forums » LtU Forum

Optimal map API

This has just crossed my mind:

Functional APIs and imperative ones often differ in the way that functional ones make use of function-passing as a way to manipulate data. For example, in Haskell, there's filter:

 filter :: (a -> Bool) -> [a] -> [a]

Used like this:

 filter somecondition oldlist

For lists, this can be simulated in say, Java by using:

ListIterator<E> it = list.listIterator();
while(it.hasNext()) {
  if(!somecondition(it.next())) {
    it.remove();
  }
}

While it is possible to implement this and other operations on lists equally fast, it doesn't seem to be the case for maps. Consider the following task:
You have a map from strings to int. You get a string "str" and an int "n". If the value at the position "str" is smaller than "n", you delete it, otherwise you overwrite it with "n" plus the old value(if there was no entry, the old one is assumed 0). In Haskell I would implement this using alter:

 alter :: (Maybe a -> Maybe a) -> k -> Map k a -> Map k a

In this case:

alter (\x -> case x of
             Just v  -> if v < n
                        then Nothing
                        else Just (v+n)
             Nothing -> Just n) str oldmap

This traverses the tree exactly once, while my Java implementation

Integer value = map.get(str);
if(value==null) {
  map.put(str,n);
}
else {
  if(value<n) {
    map.remove(str);
  }
  else {
    map.put(str,n+value);
  }
}

traverses the map twice(once for retrieval, once for insertion/deletion).
Is this (or equivalent performance issues) relevant for API design? Can every such problem be solved using iterators?

By Henning G at 2006-12-11 00:15 | LtU Forum | previous forum topic | next forum topic | other blogs | 6117 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Even simpler problem

Java's ConcurrentMap.putIfAbsent is an even simpler example. It tries to replace the {"get", check-for-null, "put"} idiom but doesn't do it perfectly.

map.putIfAbsent("key", new Window())

The problem here is that the "new Window()" operation will execute even if its result isn't needed.

I do think the most elegant way to solve these problems is by passing in a function but there's probably always a way to do things using persistent cursors (though supporting persistent cursors makes the implementation of the collection more complex). For example, I think the operation you describe could be implemented without redundant traversals by using java.util.TreeMap's "subMap" feature.

By Kannan Goundan at Mon, 2006-12-11 12:03 | login or register to post comments

Change the list?

Why don't you return a new list/map instead of modifying the existing list? I would expect that adding a value would not incur a traversal, if I understand the term properly.

By Denis Bredelet -jido at Mon, 2006-12-11 14:33 | login or register to post comments

Java map iterators can both update and remove


import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class OptimalMap {
    public static void main(String[] x) {
        Map<String,Integer> m = new TreeMap<String,Integer>();
        m.put("a", 0);
        m.put("b", 1);
        m.put("c", 2);
        m.put("d", 3);
        m.put("e", 4);
        m.put("f", 5);
        m.put("g", null);
        int n = 3;
        Iterator<Map.Entry<String,Integer>> it = m.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String,Integer> e = it.next();
            String k = e.getKey();
            Integer value = e.getValue();
            if (value == null) {
                e.setValue(n);
            } else if (value < n) {
                it.remove();
            } else {
                e.setValue(n + value);
            }
        }
        System.out.println(m);
    }
}

=>

{d=6, e=7, f=8, g=3}

with only one traversal of the map.

By jglick at Wed, 2006-12-13 00:05 | login or register to post comments