4 ms·
> Doing a map and then a filter is O(2N), whereas mapfilter is O(N). That’s twice as a fast! O(2N) is O(N). The function F would have to be as or more trivial
by paulgb 18y ago
> Doing a map and then a filter is O(2N), whereas mapfilter is O(N). That’s twice as a fast!
O(2N) is O(N). The function F would have to be as or more trivial than a boolean comparison for the speed to double.
> Does mapfilter exist in any programming language?
In python, you can use list comprehensions and generators to accomplish this, although it is a bit kludgy:
[fx for fx in (f(x) for x in lst) if fx]
In haskell you can just use the regular map and filter constructs and the lazyness will ensure that the list is only iterated over once.
- japerk 18y agoYes, saying it's twice as fast is a bit simplistic. And O(2N) is theoretically the same as O(N), but in practice, if you have a large list of IDs that need to be looked up in a database to do the map and the filter, mapfilter can approach "twice as fast" (how close depends on the map function). This is my general use case, and the reason I wrote a mapfilter function. It's cool that haskell can do a single iteration by being lazy. I do wish erlang could do lazy iteration and generators.