8
$\begingroup$

Now I have a long number list, for example

a = {{1020, 3058}, {98, 98}, {599, 600}}; (*just a sample, the list is very very long*)

I want to replace the number with their order in the list. The number 98 is the smallest number so it should be replaced with 1 and so on. After replacement the list a should be

{{4, 5}, {1, 1}, {2, 3}};

The code I use is

a = {{1020, 3058}, {98, 98}, {599, 600}};
b = Sort@DeleteDuplicates@Flatten@a;
rule = Table[b[[i]] -> i, {i, 1, Length@b}];
a /. rule

or

a = {{1020, 3058}, {98, 98}, {599, 600}};
b = Sort@DeleteDuplicates@Flatten@a;
Cases[a, {x_Integer, y_Integer} :> {Position[b, x][[1, 1]], Position[b, y][[1, 1]]}]

With the increase of the list size, the code above is very time-consuming. I want to know if there some efficient way to realize my need?

$\endgroup$
8
$\begingroup$

I believe this is much faster:

a = {{1020, 3058}, {98, 98}, {599, 600}};
b = Sort@DeleteDuplicates@Flatten@a;
a /. Dispatch@Thread[b -> Range@Length@b]
(* {{4, 5}, {1, 1}, {2, 3}} *)

To wit:

SeedRandom[0]
a = RandomInteger[{1, 1000}, {10000, 2}];
test1 = a /. Dispatch@Thread[b -> Range@Length@b]; // AbsoluteTiming // First
test2 = a /. Thread[b -> Range@Length@b]; // AbsoluteTiming // First
test3 = Cases[a, {x_Integer, y_Integer} :> {Position[b, x][[1, 1]], Position[b, y][[1, 1]]}]; // AbsoluteTiming // First
test4 = a /. Table[b[[i]] -> i, {i, 1, Length@b}]; // AbsoluteTiming // First
(* 0.020565 *)
(* 2.091893 *)
(* 1.335496 *)
(* 1.903513 *)

Just to make sure:

test1 === test2 === test3 === test4
(* True *)

(Since I am stuck on Ver 10.0, I don't have access to RepeatedTiming, so this is the best I can do.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your great answer. I use V10.0 too. $\endgroup$ – Ice0cean Nov 29 '16 at 7:40
3
$\begingroup$

Perhaps,

With[{u = Union @@ a}, a /. Thread[u -> Range[Length@u]]]
| improve this answer | |
$\endgroup$
  • $\begingroup$ In my testing, Sort@DeleteDuplicates@Flatten@a is faster than Union @@ a, but it could be my particular choice of test list (i.e. SeedRandom[0]; a = RandomInteger[{1, 1000}, {10000, 2}];). Also, this version is not significantly faster than the OP's version. However, if instead you do Dispatch@Thread[u -> Range[Length@u]]], it is much faster. $\endgroup$ – march Nov 29 '16 at 7:22
  • $\begingroup$ @march thank you...I unfortunately did not think deeply enough...I was not sure what the "size" of the problem was but accept entirely your comments. If you post Dispatch answer i am happy to +1 :) $\endgroup$ – ubpdqn Nov 29 '16 at 7:25
  • $\begingroup$ Well, I did post it, but I was hesitant to, since the construction is exactly your answer, with the extra addition of the hash table created by Dispatch. $\endgroup$ – march Nov 29 '16 at 7:30
  • $\begingroup$ @march sorry missed that...very instructive answer rather than my off the cuff one :) $\endgroup$ – ubpdqn Nov 29 '16 at 7:32
2
$\begingroup$

Here is an incremental improvement on existing answers.

march's code as fn0 for reference.

fn1 should work on lists of any shape.

fn2 assumes that your sublists are all the same length.

fn0[a_] := With[{b = Sort@DeleteDuplicates@Flatten@a},
  a /. Dispatch@Thread[b -> Range@Length@b]]

fn1[a_] :=
  a /. AssociationThread[Ordering[#], #] & @ DeleteDuplicates @ Flatten @ a;

fn2[a_] :=
  Module[{flat, asc},
    flat = Flatten@a;
    asc = AssociationThread[Ordering[#], #] & @ DeleteDuplicates @ flat;
    asc ~Lookup~ flat ~Partition~ Length[First @ a]
  ]

a = RandomInteger[1*^6, {500000, 2}];

fn0[a] // RepeatedTiming // First
fn1[a] // RepeatedTiming // First
fn2[a] // RepeatedTiming // First
1.53

1.33

1.09
| improve this answer | |
$\endgroup$
  • $\begingroup$ It's a big improvement. Thanks. Is the reason that AssociationThread is faster than Dispatch? $\endgroup$ – Ice0cean Dec 21 '16 at 4:57
  • $\begingroup$ @Ice0cean If AssociationThread is faster I think (you should check) it is because we eliminate the separate Thread operation. I'll try to remember to check it myself later but I'll probably forget. $\endgroup$ – Mr.Wizard Dec 21 '16 at 5:00
  • $\begingroup$ ♦ I will check it. $\endgroup$ – Ice0cean Dec 21 '16 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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