Re: Element Extraction
- To: mathgroup at smc.vnet.net
- Subject: [mg19316] Re: [mg19240] Element Extraction
- From: "Carl K.Woll" <carlw at fermi.phys.washington.edu>
- Date: Sat, 14 Aug 1999 23:42:48 -0400
- Organization: Department of Physics
- References: <199908110606.CAA01017@smc.vnet.net.> <37B47049.33AB607@fermi.phys.washington.edu> <37B54909.973D6F5E@hixnet.co.za>
- Sender: owner-wri-mathgroup at wolfram.com
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 farstest 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 inn advance to detect
> someList in Hamming Distance <= 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
- References:
- Element Extraction
- From: kewjoi@hixnet.co.za (Kew Joinery)
- Element Extraction