Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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 



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