Re: Complement replacement
- To: mathgroup at smc.vnet.net
- Subject: [mg58640] Re: [mg58608] Complement replacement
- From: "Carl K. Woll" <carl at woll2woll.com>
- Date: Mon, 11 Jul 2005 04:19:25 -0400 (EDT)
- References: <200507100912.FAA06500@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
----- Original Message -----
From: <konstantpi at mail15.com>
To: mathgroup at smc.vnet.net
Subject: [mg58640] [mg58608] Complement replacement
> hi
> in the list:
> pp=Table[Random[Integer, {1, 1000}], {i, 1000}];
> how could i know which numbers from 1 to 1000 does not exist in the
> pp List.
> but without using:
> Complement[Table[i,{i,1000}],pp]
> regards
>
Here is a possibility that is faster than Complement on my machine for this
particular problem:
missing[list_] := Module[{len = Length[list], a},
a = Range[len];
a[[list]] = 0;
DeleteCases[a, 0]]
The above function scales as O(n), and Complement scales as O(n log n) due
to sorting, so for large enough input my function ought to be faster. For
example, with the data:
n = 10^6;
pp = Table[Random[Integer, {1, n}], {n}];
We have the following comparison:
In[26]:=
c1=Complement[Range[Length[pp]],pp];//Timing
c2=missing[pp];//Timing
c1===c2
Out[26]=
{1.594 Second,Null}
Out[27]=
{0.625 Second,Null}
Out[28]=
True
A further slight increase in speed ought to be possible if you compile
DeleteCases[a,0] since a is a list of integers. For example, define
deletezeros as:
deletezeros = Compile[{{a, _Integer, 1}},
Module[{b, len, j},
len = Length[a];
b = a;
j = 0;
Do[
If[a[[i]] =!= 0, b[[++j]] = a[[i]]], {i, len}];
Take[b, j]]]
Then, replacing DeleteCases[a,0] with deletezeros[a] approximately doubles
the speed.
Carl Woll
Wolfram Research
- References:
- Complement replacement
- From: konstantpi@mail15.com
- Complement replacement