11
$\begingroup$

I am interested in mapping a function, f over a (long) list which contains duplicates. Since this function takes a while to evaluate I would like to make use of this duplication to speed up the mapping.

Attempt

Let us say my list is 

list = {a, a, b, a, c, b}

my purpose is to map f over list efficiently. I have defined a function 

MapDuplicate[f_, list_] := Module[{ff, list1, ulist},
list1 = ff /@ list; (* ff is dummy f *) 
ulist = Union[list]; (* the reduced list *)
rr = Dispatch[Thread[(ff /@ ulist) -> (f /@ ulist)]];
list1 /. rr]

which does the trick, 

MapDuplicate[f1, list]

(* {f1(a),f1(a),f1(b),f1(a),f1(c),f1(b)} *)

but I strongly suspect there is a more elegant (using Ordering? SparseArray?) of doing this.

Question

Any idea on how to do this more efficiently (e.g. without duplicating the list) My apologies in advance if the answer turns out to be trivial.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Considered memoization? I.e., f[x_]:=f[x]= your definition used with Map: f/@list $\endgroup$
    – kglr
    Commented Aug 19, 2012 at 13:03
  • $\begingroup$ No I had not! I tend to think of memorization as attached to the function rather than to lists. I guess it would do the trick. $\endgroup$
    – chris
    Commented Aug 19, 2012 at 13:04
  • $\begingroup$ Though if I want to parallelize the mapping I suspect it won't work cf mathematica.stackexchange.com/questions/9186/… $\endgroup$
    – chris
    Commented Aug 19, 2012 at 13:07
  • 4
    $\begingroup$ Keep in mind that both memoization or other hash-based approaches (rules, Dispatch, etc) may actually make things slower for numerical lists when your function is compilable, since Map auto-compiles and switching to memoization etc you will lose that advantage (not to detract from the suggestions to use memoization etc, since those are the right things to do generically). $\endgroup$
    – Leonid Shifrin
    Commented Aug 19, 2012 at 19:52

1 Answer 1

Reset to default
14
$\begingroup$ 
dispatchTable = Dispatch[ # -> g[#] & /@ DeleteDuplicates[list]]
(* {a -> g[a], b -> g[b], c -> g[c]}  *)
list/.dispatchTable
(* {g[a], g[a], g[b], g[a], g[c], g[b]} *)

or memoization:

f[x_]:=f[x]= 3 x (* say *)

with Map

f/@list
(*  {3 a, 3 a, 3 b, 3 a, 3 c, 3 b} *)

or with ParallelMap:

ParallelMap[f, list]
Improve this answer
$\endgroup$
5
  • $\begingroup$ it seems to me the last option, ParallelMap will not be as efficient as it should be because sub-kernels will not know about what other kernels have already memorized. $\endgroup$
    – chris
    Commented Aug 19, 2012 at 13:16
  • $\begingroup$ @chris, good point. I have not done any testing with ParallelMap; and just saw your related question. Parallelization versus memoization (in case the choice is one of either/or) would make a great question: pros/cons, trade-offs involved etc. $\endgroup$
    – kglr
    Commented Aug 19, 2012 at 13:23
  • 2
    $\begingroup$ I suggest modifying your answer to dispatchTable =Dispatch[ # -> g[#] & /@ DeleteDuplicates[list]] which will makes it more efficient if the dispatch table is long $\endgroup$
    – chris
    Commented Aug 19, 2012 at 13:23
  • $\begingroup$ @chris, another great point. I actually did mean to use Dispatch:) $\endgroup$
    – kglr
    Commented Aug 19, 2012 at 13:25
  • $\begingroup$ first option (dispatch) seems about 30 % faster. $\endgroup$
    – chris
    Commented Aug 19, 2012 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.