Re: Unique Elements in a List

aahz@xxxxxxxxxxxxxxx (Aahz) writes:

>>[x for x in data if data.count(x) == 1]
>>
>>suffice? it is also "stable" preserving order of items. Lemme demo:
>
> Only for small datasets -- this is an O(N^2) algorithm.

I realized that, but maybe I should've pointed it out too. For the OP if
he/she is unaware - notation O(N^2) (big O n squared) means the computing time
of the algorithm increases exponentially (where exponent is 2) relative to the
size of the input.

Eg. if the input size is i and it takes p seconds to compute it, then given
input size 10*i, the computing time would be 100*p. These notions can apply
for memory usage as well, but the problem in here is the computing time:
list.count() must iterate through the list each time, and as such the loop

[x for x in data if data.count(x) == 1]

iterates through each item in data (x for x in data), and for each item it
will again iterate through each item in data to see how many times it
occurred. If data contains 200 items, this idiom would iterate the structure
40 000 times. With today's computers one wouldn't notice it, unless each item
requires heavy processing (eg. launching a separate process per item
etc). However, if the length of the data can be thousands or even tens of
thousands, this idiom would become unusable. If data contained 75 000 items,
the loop would do 25 625 000 000 iterations, effectively bringing cpu to
halt..

So, generally one should avoid using exponential O(n^k) (where k > 1)
algorithms, unless faster O(n) or O(n*lg(n)) solution is either impossible (or
too complex, and inputs are known to be small etc).

Wikipedia has good resources and pointers to related things, see
http://en.wikipedia.org/wiki/Analysis_of_algorithms

--
#!/usr/bin/perl -w
$h={23,69,28,'6e',2,64,3,76,7,20,13,61,8,'4d',24,73,10,'6a',12,'6b',21,68,14,
72,16,'2c',17,20,9,61,11,61,25,74,4,61,1,45,29,20,5,72,18,61,15,69,20,43,26,
69,19,20,6,64,27,61,22,72};$_=join'',map{chr hex $h->{$_}}sort{$a<=>$b}
keys%$h;m/(\w).*\s(\w+)/x;$_.=uc substr(crypt(join('',60,28,14,49),join'',
map{lc}($1,substr $2,4,1)),2,4)."\n"; print;
.

Relevant Pages

  • Implementing data flow analysis in single pass parser
    ... pointers in the C program. ... I read the chapter 10.8 in dragon book ... I have written a parser to parse the CFG version of the C code dumped ... I previously implemented algorithm for finding ...
    (comp.compilers)
  • Re: string combination script?
    ... this thread I had recently wanted an algorithm that would iterate ... My initial algorithm wasn't very efficient, ... unique partition and vice versa. ...
    (microsoft.public.scripting.vbscript)
  • Re: Code for finding the 1000th prime
    ... Also I am not a mathematician. ... Can some one give me pointers for ... all that's left to do is write a prime number generator (a random ... That reminds me of the only algorithm I really invented myself: ...
    (comp.lang.python)
  • Re: Whats the position of pointers
    ... people to write a program to sort some data, where the intent is for them ... understand the *importance* of pointers (remember it is the importance ... he will come up with an algorithm which probably can be any of the ... algorithm with complexity Osuch as merge sort, ...
    (comp.lang.c)
  • Re: Pointer equality and dereferencing
    ... int main{ ... there is no semantic meaning to the struct twoptrs. ... The pointers have meaningless names and serve no useful purpose in this particular program other than to illustrate my point; but that's because any real-life example would be a lot bigger and more complicated and nobody would bother to read it. ... That's how a lot of compression or encryption algorithm works. ...
    (comp.std.c)