13
$\begingroup$

I have two lists as the following:

ab = {1, -1, -1, -1, 1, 1};
ac = {1, -1, -1,  1, 1, 1};

How I can find the difference (more precisely, the edit distance) between them? In this case the result should be 1, since there is one item difference between ab and ac.

Note: in my case, the list elements only take the values 1 and -1, and both lists are one-dimensional of the same length, but it is always nice to see more general solutions (elements are of Reals, lists are matrices, etc.).

Thank you.

$\endgroup$
4
  • 1
    $\begingroup$ Will you always deal in integers only? $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 12:28
  • 1
    $\begingroup$ ... or even only 1 and -1? $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 12:38
  • $\begingroup$ values are only 1 and -1 $\endgroup$
    – sky-light
    Sep 6, 2013 at 13:48
  • $\begingroup$ Then you are in for a treat (see answers)! Please edit your question to include the 1/-1 information. $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 14:03

6 Answers 6

22
$\begingroup$

There is an appropriate metrics:

HammingDistance[ab, ac]
1

one could use also (but in general it yields different results since it counts transpositions, deletions etc.)

DamerauLevenshteinDistance[ab, ac]
1
$\endgroup$
4
  • $\begingroup$ Strangely HammingDistance doesn't work for mixed data i.e having both Integer and Symbols. $\endgroup$ Sep 6, 2013 at 16:20
  • 1
    $\begingroup$ @Blackbird What problems have you encountered? How many should it be HammingDistance[{3, 2, a, 10, b, 5, 11, c}, {3, 2, a, 11, b, Pi, 11, 3}] ? 3, shouldn't it? $\endgroup$
    – Artes
    Sep 6, 2013 at 16:50
  • $\begingroup$ I am sorry for reading the definition in wrong way.My bad, you are correct. $\endgroup$ Sep 6, 2013 at 18:05
  • 1
    $\begingroup$ @Blackbird Note that HammingDistance works also for strings (there is useful the IgnoreCase option) unlike the other methods. $\endgroup$
    – Artes
    Sep 6, 2013 at 18:31
16
$\begingroup$

For Integer data we also could write:

 Tr @ Unitize @ BitXor[ab, ac]
1

For Real data we can use the slightly slower but also shorter:

Tr @ Unitize[ab - ac]

Blackbird challenged me to provide a method that works on all input types. My approach is to select between methods depending on data.

diff[a__?(VectorQ[#, IntegerQ] &)] := Tr @ Unitize @ BitXor @ a
diff[a__?(VectorQ[#, NumericQ] &)] := Tr @ Unitize @ Subtract @ a
diff[a_, b_] := HammingDistance[a, b]

Timings for some of the methods posted so far (search the site for timeAvg):

{ab, ac} = List @@ RandomInteger[2, {2, 250000}];  (* List @@ to prevent unpacking *)

HammingDistance[ab, ac]                  // timeAvg
Count[MapThread[Equal, {ab, ac}], False] // timeAvg
Tr @ Unitize @ BitXor[ab, ac]            // timeAvg
diff[ab, ac]                             // timeAvg

0.009984

0.05428

0.0005488

0.0005744

Now with Real data:

{ab, ac} = N /@ {ab, ac};

HammingDistance[ab, ac]                  // timeAvg
Count[MapThread[Equal, {ab, ac}], False] // timeAvg
Tr @ Unitize[ab - ac]                    // timeAvg
diff[ab, ac]                             // timeAvg

0.01872

0.0748

0.00312

0.0021728

(I learned something from this test: Subtract[a,b] is faster than a-b on packed reals.)

Now something unpackable:

{ab, ac} = RandomChoice[CharacterRange["a", "z"], {2, 250000}];

HammingDistance[ab, ac]                  // timeAvg
Count[MapThread[Equal, {ab, ac}], False] // timeAvg
diff[ab, ac]                             // timeAvg

0.005488

0.0524

0.005496

$\endgroup$
15
  • 3
    $\begingroup$ I knew this was one of those explode-in-your-face threads ;P $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 12:25
  • $\begingroup$ @Yves Please define that. $\endgroup$
    – Mr.Wizard
    Sep 6, 2013 at 12:30
  • $\begingroup$ Simple/trivial question, one gazillion possible (and sometimes surprising and/or creative) answers. Oh, and my timings are usually abysmal... $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 12:31
  • $\begingroup$ @Yves Ah, one of those. $\endgroup$
    – Mr.Wizard
    Sep 6, 2013 at 12:35
  • $\begingroup$ Is the term unsuitable / lost in translation? $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 12:38
9
$\begingroup$

You could do this

ab = {1, -1, -1, -1, 1, 1};
ac = {1, -1, -1, 1, 1, 1};

EditDistance[ab, ac]

which would give a result even if the lists had different lengths (or whatever).

The documentation says:

EditDistance[u, v] gives the number of one-element deletions, insertions, and substitutions required to transform u to v.

$\endgroup$
3
  • $\begingroup$ I'm sorry, I have to down-vote this. EditDistance is not the same thing. Incidentally it is a far more complex measure and will be unusably slow on long vectors. $\endgroup$
    – Mr.Wizard
    Sep 6, 2013 at 17:03
  • 1
    $\begingroup$ The OP said “How I can find the difference between them? Now in our case the result should be 1, since there is one item difference between ab and ac.”, which is such a loose definition of “difference” that EditDistance is a feasible candidate. Though I agree with your comment about complexity. $\endgroup$ Sep 7, 2013 at 11:40
  • 1
    $\begingroup$ Okay, I have to admit you're right. My impression of the question didn't allow for that but I was wrong. I removed my down-vote (I had to edit to do this). $\endgroup$
    – Mr.Wizard
    Sep 7, 2013 at 11:45
8
$\begingroup$

A very basic approach:

Count[Equal @@@ Thread[{ab, ac}], False]

1

or perhaps:

Count[MapThread[Equal, {ab, ac}], False]

1

Now if there is only 1 and -1 to watch out for, this will also do (thanks to Aky for pointing out a glaring error):

Plus @@ Abs[ab - ac]/2
$\endgroup$
11
  • 2
    $\begingroup$ You don't need Thread in the last one: Tr[ab-ac]/-2 $\endgroup$
    – Mr.Wizard
    Sep 6, 2013 at 12:43
  • 1
    $\begingroup$ It is too short for the answer so maybe you can add Count[ab ac, -1] somewhere for 1/-1 data case. $\endgroup$
    – Kuba
    Sep 6, 2013 at 12:59
  • 1
    $\begingroup$ @Kuba good one! You sure you do not want to answer yourself? $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 13:01
  • 1
    $\begingroup$ @Kuba Short is the best kind of answer. I encourage you to post it. :-) $\endgroup$
    – Mr.Wizard
    Sep 6, 2013 at 13:07
  • 2
    $\begingroup$ @Mr.Wizard now you see what I meant by "explode in your face" :-) $\endgroup$
    – Yves Klett
    Sep 6, 2013 at 13:42
7
$\begingroup$

These results are specific to the case where the data are 1|-1, and may be specific to v6.

<<Developer`
n = 10^7
PackedArrayQ[ a = RandomInteger[1,n]*2 - 1 ]
PackedArrayQ[ b = RandomInteger[1,n]*2 - 1 ]
(* 10000000
   True
   True *)

AbsoluteTiming[ (Length@a - a.b)/2  ]
(* {0.435134, 4998582} *)

AbsoluteTiming[ Tr@Unitize@Subtract[a,b] ]
(* {0.792662, 4998582} *)

AbsoluteTiming[ Tr@Unitize@BitXor[a,b] ]
(* {0.883002, 4998582} *)

aa = FromPackedArray@a;
bb = FromPackedArray@b;

AbsoluteTiming[ (Length@aa - aa.bb)/2  ]
(* {1.373384, 4998582} *)

AbsoluteTiming[ Tr@Unitize@Subtract[aa,bb] ]
(* {1.366143, 4998582} *)

AbsoluteTiming[ Tr@Unitize@BitXor[aa,bb] ]
(* {2.590419, 4998582} *)
$\endgroup$
2
  • $\begingroup$ I get the same rankings in v7. I hadn't realized that Subtract was faster than BitXor. $\endgroup$
    – Mr.Wizard
    Sep 7, 2013 at 11:50
  • $\begingroup$ Ah, I see now that it's only faster on this data, not general Integer data. Nevertheless +1 well earned for teaching me something. $\endgroup$
    – Mr.Wizard
    Sep 7, 2013 at 11:58
6
$\begingroup$

I will abuse the fact that OP hasn't said if it is more general question.

This is my solution fo 1/-1 data case:

Count[ab ac, -1]
$\endgroup$
3
  • $\begingroup$ @YvesKlett Here is another fun one for -1/1: Tr@Log[ab ac]/I/Pi $\endgroup$
    – Mr.Wizard
    Sep 6, 2013 at 13:16
  • 1
    $\begingroup$ @Mr.Wizard If we a priori know the Length then this one is shorter: (n - ab.ac)/2 $\endgroup$
    – Kuba
    Sep 6, 2013 at 13:20
  • $\begingroup$ @Mr.Wizard, you could save one character with Tr@Log[-1, ab ac] $\endgroup$ Sep 7, 2013 at 12:25

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.