MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Element Extraction

  • To: mathgroup at smc.vnet.net
  • Subject: [mg19326] Re: [mg19240] Element Extraction
  • From: "Allan Hayes" <hay at haystack.demon.co.uk>
  • Date: Mon, 16 Aug 1999 02:14:56 -0400
  • References: <199908110606.CAA01017@smc.vnet.net.> <37B47049.33AB607@fermi.phys.washington.edu> <37B54909.973D6F5E@hixnet.co.za> <37B53F8E.B16E04A2@fermi.phys.washington.edu>
  • Sender: owner-wri-mathgroup at wolfram.com

Carl:
Another approach, using Inner:

hamming[1.1][lis_, tar_, dist_] :=
  lis[[
      Flatten[Position[Inner[SameQ, lis, tar
            , (Count[{##}, False] <= dist) &], True]]]]

This is considerbly faster on your test than my original hamming[1]:

hamming[1][lis_, tar_, dist_] :=
  Cases[lis, x_ /; Count[MapThread[SameQ, {tar, x}], False] <= dist]

testlist = Table[Random[Integer, {0, 2}], {10000}, {10}];
target = Table[Random[Integer, {0, 2}], {10}];
dist = 2;

hamming[1.1][testlist, target, dist]; // Timing // First

3.73 Second

hamming[1][testlist, target, dist]; // Timing // First

6.37 Second

Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565



----- Original Message -----
From: Carl K.Woll <carlw at fermi.phys.washington.edu>
To: mathgroup at smc.vnet.net
Andrzej Kozlowski <andrzej at tuins.ac.jp>; Bob Hanlon <BobHanlon at aol.com>;
<mathgroup at smc.vnet.net>
Subject: [mg19326] Re: [mg19240] Element Extraction


Below Kew complains about the lack of generality of the fastest solution to
his problem. I should have given some words of
explanation about how the fastest solution worked.

Basically, for my hamming[5] function, I took Allan Hayes solution, and
tried to speed it up. There were two things that I
did.

1. He used MapThread to thread SameQ over his two vectors. I temporarily
gave SameQ the attribute Listable to achieve the
same thing. This gave a 20-30% improvement in speed. I modified my previous
hamming[5] function to do just this single
change.

2. Rather than counting the number of false entries and seeing if it was
less than some prescribed number, given the
shortness of the vector I instead hardcoded the close enough possibilities
(alternatively, I could have hardcoded the far
enough away possibilities). This provided another 100% improvement in speed
at the sacrifice of generality.

For the hamming[6] function, I tried to attack the problem from a different
angle. Since Position and Part are such
extremely quick functions, I massaged the whole testlist function instead of
each element individually. I also used the two
things I noted above.

If we want a general hamming function, then approach 2 above is obviously
not the way to go. However, for the approach taken
in hamming[6], I was able to come up with a similar method, which was still
general enough. In this approach I used the ever
useful Sequence[] function. At any rate, here is a revised version of my
previous notebook with the above changes using your
new syntax hamming[list,target,distance] (I also had to change David Park's
solution a little bit more than the others to
make it work, and in the process speeded it up a bit).

In[1]:=
(* Hayes *)
hamming[1][lis_,tar_,dist_]:=
  Cases[lis,x_/;Count[MapThread[SameQ,{target,x}],False]<=dist]

(* Park revised *)
hamming[2][lis_,tar_,dist_]:=Select[lis,Count[#-tar,0]>Length[tar]-dist-1&]

(* Kozlowski *)
distance[a_, b_] := If[a === b, 0, 1]
SetAttributes[distance, Listable]

hamming[3][lis_,tar_,dist_]:=
  Select[lis, Apply[Plus, distance[tar, #]] <= dist &]

(* Hanlon *)
hammingDistance[x_?VectorQ, y_?VectorQ] /; Length[x] == Length[y] :=
    Plus @@ MapThread[If[#1 == #2, 0, 1] &, {x, y}];

hamming[4][lis_,tar_,dist_]:=Select[lis, hammingDistance[tar, #] < dist+1&]

(* Woll #1 *)hamming[5][lis_,tar_,dist_]:=Module[{ans},
  SetAttributes[SameQ,{Listable}];
  ans=Cases[lis,x_/;Count[SameQ[x,tar],False]<=dist];
  ClearAttributes[SameQ,{Listable}];
  ans]

(* Woll #2 *)
hamming[6][lis_,tar_,dist_]:=Module[{ans,t,len=Length[lis]},
  SetAttributes[SameQ,{Listable}];
  t=SameQ[testlist,Table[tar,{len}]];
  ans=lis[[
          Flatten[Position[Length/@(t/.True->Sequence[]),
              Alternatives@@Range[0,dist]]]]];
  ClearAttributes[SameQ,{Listable}];
  ans]
In[27]:=
target = Table[Random[Integer,{0,2}],{10}];
In[28]:=
testlist =
    Table[Random[Integer, {0, 2}], {10000},{10}];
In[29]:=
Do[Print[Timing[r[i]=hamming[i][testlist,target,2];]],{i,1,6}]

r[1]==r[2]==r[3]==r[4]==r[5]==r[6]
{3.734 Second,Null}
{4.547 Second,Null}
{9.281 Second,Null}
{9.109 Second,Null}
{3.063 Second,Null}
{2.187 Second,Null}
Out[30]=
True

Carl Woll
Dept of Physics
U of Washington


Kew Joinery wrote:

> Hello,
> I'd like to thank to all replies again.
> Only to add few words:
> To define universal Humming function it should be of the form :
> Hamming[someList , target , distance]
> Obviously all solutions from the different authors (excluding the
"fastest" solution
> of Mr.K.Woll )could be easy adapted to this form (they are at the moment
of the form
> hamming[someList ,target] .
> What about the fastest solution? At the moment it detects only lists with
elements of
> length=3 and distance <=1. Consider example when testing
>
someList={{0,1,2,3,4,5,6,7,8,9},{0,0,1,2,3,4,5,6,7,8},{0,0,0,1,2,3,4,5,6,7},
{0,0,0,0,1,2,3,4,5,6}.{0,0,0,0,0,0,0,0,0,0}}
>
> According to Mr.Woll I should define all 10! "success[.]=0 " in advance to
detect
> someList in Hamming Distance <=9 for example.I thing this solution is
inpractical .
> Regards,
> Eugene
>
> Carl K.Woll wrote:
>
> > Hi all,
> >
> > I thought I would give a comparison of the various solutions provided,
along with
> > a couple of new ones by yours truly.
> >
> > (* Hayes *)
> > hamming[1][lis_,tar_]:=
> >   Cases[lis,x_/;Count[MapThread[SameQ,{target,x}],False]<=1]
> >
> > (* Park *)
> > hammtest[p : {_, _, _}, t : {_, _, _}] := Count[Abs[t - p], 0] > 1;
> >
> > hamming[2][lis_,tar_]:=Select[lis,hammtest[#,tar]&]
> >
> > (* Kozlowski *)
> > dist[a_, b_] := If[a === b, 0, 1]
> > SetAttributes[dist, Listable]
> >
> > hamming[3][lis_,tar_]:=Select[lis, Apply[Plus, dist[tar, #]] <= 1 &]
> >
> > (* Hanlon *)
> > hammingDistance[x_?VectorQ, y_?VectorQ] /; Length[x] == Length[y] :=
> >     Plus @@ MapThread[If[#1 == #2, 0, 1] &, {x, y}];
> >
> > hamming[4][lis_,tar_]:=Select[lis, hammingDistance[tar, #] < 2 &]
> >
> > (* Woll #1 *)
> > Clear[closeEnough];
> > closeEnough[{True,True,True}]=True;
> > closeEnough[{True,True,False}]=True;
> > closeEnough[{True,False,True}]=True;
> > closeEnough[{False,True,True}]=True;
> >
> > hamming[5][lis_,tar_]:=Module[{ans},
> >   SetAttributes[SameQ,{Listable}];
> >   ans=Select[lis,closeEnough[SameQ[#,tar]]&];
> >   ClearAttributes[SameQ,{Listable}];
> >   ans]
> >
> > (* Woll #2 *)
> > Clear[success]
> > success[True,True,True]=0;
> > success[True,True,False]=0;
> > success[True,False,True]=0;
> > success[False,True,True]=0;
> >
> > hamming[6][lis_,tar_]:=Module[{ans,t,len=Length[lis]},
> >   SetAttributes[SameQ,{Listable}];
> >   t=SameQ[testlist,Table[tar,{len}]];
> >   ans=lis[[Flatten[Position[Apply[success,t,1],0]]]];
> >   ClearAttributes[SameQ,{Listable}];
> >   ans]
> > In[22]:=
> > target = {0, 0, 1};
> > In[263]:=
> > testlist =
> >     Table[{Random[Integer, {0, 2}], Random[Integer, {0, 2}],
> >         Random[Integer, {0, 2}]}, {10000}];
> > In[381]:=
> > Do[Print[Timing[r[i]=hamming[i][testlist,target];]],{i,1,6}]
> >
> > r[1]==r[2]==r[3]==r[4]==r[5]==r[6]
> > {2.703 Second,Null}
> > {3.937 Second,Null}
> > {3.969 Second,Null}
> > {5.234 Second,Null}
> > {1.125 Second,Null}
> > {0.969 Second,Null}
> > Out[382]=
> > True
> >
> > Carl Woll
> > Dept of Physics
> > U of Washington
> >
> > Kew Joinery wrote:
> >
> > > Hello everyone,
> > > I have a problem extracting list of list.
> > > Given some list, consisting of elements (not all of them distinct)
with
> > > the same length and some target list of the same length, for example:
> > > In[26]:=
> > >
someList={{0,0,0},{0,0,1},{0,0,2},{0,1,0},{0,1,1},{0,1,2},{0,2,0},{0,2,1},{0
,
> > >
> > >
2,2},{1,0,0},{1,0,1},{1,0,2},{1,1,0},{1,1,1},{1,1,2},{1,2,0},{1,2,1},{1,
> > >
> > >
2,2},{2,0,0},{2,0,1},{2,0,2},{2,1,0},{2,1,1},{2,1,2},{2,2,0},{2,2,1},{2,
> > >
> > >       2,2}};
> > >
> > > In[27]:=
> > > target={0,0,1};
> > >
> > > Hamming distance between two bit strings means the number of bit
> > > positions in which they differ. For example consecutive elements of
the
> > > Gray code list have Hamming distance = 1.
> > > I need to extract these cases(elements of someList) which differ from
> > > target in one coordinate (Hamming distance = 1) or less (the
> > > element===target itself//Hamming distance=0), so the answer should be:
> > >
> > > In[33]:=
> > > answer={{0,0,0},{0,0,1},{0,0,2},{0,1,1},{0,2,1},{1,0,1},{2,0,1}};
> > >
> > > How could I achieve the extraction efficiently?
> > > Thank you in advance for any suggestions.
> > > Eugene




  • Prev by Date: Re: Simple edit ...
  • Next by Date: Simulation
  • Previous by thread: Re: Element Extraction
  • Next by thread: Re: Element Extraction