10
$\begingroup$

Recently I had to solve a problem similar to this:

Let's say I have a list of list of rules

Clear[a, b, c, d] l = {{a -> 2, b -> 1, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, {c -> 3, a -> 1, b -> 2}};

What is the best way to sort the values of {a, b, c} in each sublist without touching the rest of the sublist. So the first sublist should be:

{a -> 1, b -> 2, c -> 3, d -> 2}

and the whole result should be

{{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, {c -> 3, a -> 1, b -> 2}}

There are no duplicates in the subsists (so a -> _ appears only once). The order of rules in the sublist does not matter.

In an effort to expand my pattern matching skills I would like to know: What's the best way to achieve this? Here "best" means elegant code, but still efficient enough to work ~10^5 subsists. 

testdata = Table[MapThread[ Rule, {RandomSample[{a, b, c, d, e, f, g, h, i, j, k}, 10], RandomReal[{-1, 1}, 10]}], {ii, 10^5}];

I'm posting my answer below, so that I won't get accused of not showing any effort:)

Improve this question
$\endgroup$
0

5 Answers 5

Reset to default
6
$\begingroup$

I cannot think of a better approach than your own method therefore I shall recast it in a generalized fashion.

With[{T = Thread}, normRls[l_, pat_] := l /. T[T[pat -> _] -> T[pat -> Sort[pat /. l]]] ] normRls[#, {a, b, c}] & /@ testdata // Timing // First 
1.31

This is however a bit slower than your hard-coded method:

normalize /@ testdata // Timing // First 
1.045

Okay, let's try a little meta-programming:

genRule[x_, {y_}] := (x -> _) :> (x -> Slot[y]) genNorm[pat_List] := With[{body = MapIndexed[genRule, pat]}, # /. (body &) @@ Sort[pat /. #] & ] genNorm[{a, b, c}] /@ testdata // Timing // First 
0.889

Ah, that's more like it!

Explanation

A request for explanation of the code was made. The first method is fairly straightforward after understanding the behavior of Thread:

Thread[{a, b, c} -> {1, 2, 3}] 
{a -> 1, b -> 2, c -> 3} 
Thread[{a, b, c} -> nonlist] 
{a -> nonlist, b -> nonlist, c -> nonlist}

This is used three separate times, to generate e.g.: {a -> _, b -> _, c -> _}
then {a -> 1, b -> 2, c -> 3}, and then to combine them into:
{(a -> _) -> a -> 1, (b -> _) -> b -> 2, (c -> _) -> c -> 3}.

The "meta-programming" method is a bit more involved.

First let's look at the result, then how we get there:

genNorm[{q, r, s}] 
#1 /. ({(q -> _) :> q -> #1, (r -> _) :> r -> #2, (s -> _) :> s -> #3} &) @@ Sort[{q, r, s} /. #1] &

We see that the output is a Function (&). This function takes a single argument, the (sub)list of rules to be modified. Upon it a replacement will eventually be done (#1 /. ...). The rules for that replacement are constructed by an internal Function:

({(q -> _) :> q -> #1, (r -> _) :> r -> #2, (s -> _) :> s -> #3} &)

the parameters (#1, #2, #3) of which are filled by applying (@@) to Sort[{q, r, s} /. #1] wherein #1 is the original (sub)list of rules. Sort[{q, r, s} /. #1] itself is hopefully self-explanatory. This internal function pulls the needed parts from the sorted list. For example, with the input:

{q -> 21, r -> 11, s -> 31, t -> 21}

The output is:

{(q -> _) :> q -> 11, (r -> _) :> r -> 21, (s -> _) :> s -> 31}

Which when applied yields:

{q -> 11, r -> 21, s -> 31, t -> 21}

Okay, so how is that function constructed?

The auxiliary function genRule is MapIndexed over the pattern list:

MapIndexed[genRule, {a, b, c}] 
{(a -> _) :> a -> #1, (b -> _) :> b -> #2, (c -> _) :> c -> #3}

This expression is then named body (using With) and injected into: # /. (body &) @ Sort[pat /. #] & which you should recognize as the (nested) function detailed above.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer (+1). Some wonderful ideas. But, I think this answer would be much better if you could ad a line or two explaining what the code does (for those who don't have MMA at hand or are not so proficient -- actually I'm still deciphering the meta-programming trick:). $\endgroup$ Commented Feb 14, 2013 at 21:43
  • $\begingroup$ @Ajasja Done. Please tell me if my explanation is satisfactory. I never know what to include and what to leave out I'm afraid. $\endgroup$ Commented Feb 14, 2013 at 22:07
  • $\begingroup$ @Ajasja I realize that this can be made faster by using genNorm[pat_List] := With[{body = MapIndexed[genRule, pat]}, Replace[#, body & @@ Sort[pat /. #], {1}] &] -- that is replace at level one. $\endgroup$ Commented Feb 20, 2013 at 21:12
5
$\begingroup$

Here is my solution: I first retrieve the values, sort them and then use rule replacement to apply the changes.

Clear@normalize normalize[l_] := Block[{av, bv, cv}, (*Get sorted values*) {av, bv, cv} = Sort[{a, b, c} /. l]; (*Modify the original lis*) l /. {Rule[a, _] -> Rule[a, av], Rule[b, _] -> Rule[b, bv], Rule[c, _] -> Rule[c, cv]} ] normalize /@ l (* out => {{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, {c -> 3, a -> 1, b -> 2}} *)

This takes about 2 seconds on my computer

AbsoluteTiming[result = normalize /@ testdata;] (*=> {2.319133, Null}*)
Improve this answer
$\endgroup$
3
$\begingroup$

Here is an alternative:

Clear@sortKeys sortKeys[list_, keys_] := Module[{keysInList, values, rules}, {keysInList, values} = (rules = FilterRules[#, keys]) /. Rule -> List // Transpose; # /. MapThread[RuleDelayed, {Sort@rules, Thread[Sort@keysInList -> Sort@values]}] ] & /@ list

This first filters the rules in a sublist corresponding to the input keys ({a, b, c}) we wish to sort by and then keeps a separate list of keys that actually appear in the sublist (keysInList) and their values (this is to handle missing keys). Then it sorts the values and replaces a -> original value with a -> sorted value (the MapThread is used to construct a rule list).

Usage:

sortKeys[l, {a, b, c}] (* {{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, {c -> 3, a -> 1, b -> 2}} *)

This can be simplified if it can be guaranteed that all the sublists will have all the keys.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I think a short sentence explaining what the code does would make this a much better answer. $\endgroup$ Commented Feb 14, 2013 at 10:19
  • $\begingroup$ @Ajasja Explanation added :) $\endgroup$ Commented Feb 14, 2013 at 14:54
  • $\begingroup$ Thanks +1. Why is RuleDelayed needed? (Instead of a normal Rule) $\endgroup$ Commented Feb 14, 2013 at 15:06
  • 1
    $\begingroup$ Probably not needed in this case, but I do it out of habit, when the RHS is a named pattern (or more generally, when it's not something of the form HeadA -> HeadB or SymbolA -> SymbolB) $\endgroup$ Commented Feb 14, 2013 at 16:11
2
$\begingroup$

In a comment elsewhere, @Mr.Wizard suggested that associations might be useful for this question. Here is my attempt:

normalizeAssoc[keys_][l_] := <| l, AssociationThread[keys -> Sort @ Lookup[l, keys, 0]] |>

... and here it is in action:

Take[testdata, 2] (* {{h->0.074356,i->0.756409,f->0.456624,b->-0.0342208,c->0.634687, d->0.0939196,e->-0.527057,g->-0.62371,k->-0.41238,a->0.0599702}, {a->-0.665407,g->0.414135,i->-0.909054,e->-0.727194,c->-0.872878, b->-0.125237,j->0.829395,k->-0.416614,h->-0.819966,f->0.815137}} *) normalizeAssoc[{a, b, c}] /@ Take[testdata, 2] (* {<|h->0.074356,i->0.756409,f->0.456624,b->0.0599702,c->0.634687, d->0.0939196,e->-0.527057,g->-0.62371,k->-0.41238,a->-0.0342208|>, <|a->-0.872878,g->0.414135,i->-0.909054,e->-0.727194,c->-0.125237, b->-0.665407,j->0.829395,k->-0.416614,h->-0.819966,f->0.815137|>} *)

This function operates equally well when the original rules are in list form or in associations.

The question's construction of testdata will generate some sublists in which a, b, or c is missing. The problem statement is silent on how to handle such cases, so I have arbitrarily decided to treat the values of missing keys as zero. If a different value is appropriate, simply adjust the expression Lookup[..., 0]. It is left as an exercise for the reader if some other strategy is required.

Note that the result contains associations instead of sublists. If this is unacceptable, then we can use:

normalizeAssoc2[keys_][l_] := normalizeAssoc[keys][l] // Normal

Naturally, this takes a little longer to run. Speaking of run time, here are some timings on my machine:

 normalizeAssoc : 1.39s normalizeAssoc2 : 2.07s normalize (from Ajasja) : 5.92s normRls (#1 from Mr.Wizard): 4.26s genNorm (#2 from Mr.Wizard): 3.56s

Like all microbenchmarks, these timings should be taken with a grain of salt. I found that the running times of all functions changed radically as new random variations of testdata were generated, presumably due to the randomized key order. However, repeated runs showed that the relative performance of the functions remained reasonably consistent.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. That is cleaner than what I had. $\endgroup$ Commented Feb 14, 2015 at 10:50
0
$\begingroup$

edit: this is actually not doing what you want, i sorted the order of the rules without changing the rules. 

rulelist = {a -> 1, b -> 2, cc -> 4, c -> -1}; sortpos = Position[ rulelist , r_Rule /; MemberQ[{a, b, c}, r[[1]]]]; sorted = Sort[ Take[rulelist, #][[1]] & /@ (sortpos) , #1[[2]] < #2[[2]] &]; (rulelist[[sortpos[[#]]]] = sorted[[#]]) & /@ Range[Length[sortpos]]; rulelist {c -> -1, a -> 1, cc -> 4, b -> 2}

Take 2, I think this is what you want, changine the rules so that a-> min value, etc and reordering the rules.. I think it does basically what you did, except I didnt "hard code" the a,b,c into the algotithm. If performace suffers a tad that might be a fair trade.

rulelist = {a -> 1, b -> 2, cc -> 4, c -> -1}; desiredorder = {a, b, c}; values = Sort[ desiredorder /. rulelist]; rulelist = rulelist /. (x_ -> y_) /; MemberQ[desiredorder, x] :> (x ->values[[First[Position[desiredorder, x]][[1]]]]); sortpos = Position[ rulelist , r_Rule /; MemberQ[desiredorder, r[[1]]]]; (rulelist[[sortpos[[#]]]] = desiredorder[[#]] -> values[[#]]) & /@ Range[Length[desiredorder]]; rulelist -> {a -> -1, b -> 1, cc -> 4, c -> 2}

(If you dont care about the order of the rules, drop the last two lines)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer. I think a short sentence explaining what the code does would make this a much better answer. $\endgroup$ Commented Feb 14, 2013 at 10:20

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.