MathGroup Archive 2005

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

Search the Archive

Re: Complement replacement

  • To: mathgroup at
  • Subject: [mg58640] Re: [mg58608] Complement replacement
  • From: "Carl K. Woll" <carl at>
  • Date: Mon, 11 Jul 2005 04:19:25 -0400 (EDT)
  • References: <>
  • Sender: owner-wri-mathgroup at

----- Original Message ----- 
From: <konstantpi at>
To: mathgroup at
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:


{1.594 Second,Null}

{0.625 Second,Null}


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;
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 

  • Prev by Date: Re: FrameTicks bug
  • Next by Date: Re: FrameTicks bug
  • Previous by thread: Re: Complement replacement
  • Next by thread: Re: Complement replacement