filter list fast

[lars_woetmann]

I have a list I filter using another list and I would like this to be
as fast as possible
right now I do like this:

[x for x in list1 if x not in list2]

i tried using the method filter:

filter(lambda x: x not in list2, list1)

but it didn't make much difference, because of lambda I guess
is there any way I can speed this up

[Ben Cartwright]

Re: filter list fast

lars_woetmann wrote:[color=blue]
> I have a list I filter using another list and I would like this to be
> as fast as possible
> right now I do like this:
>
> [x for x in list1 if x not in list2]
>
> i tried using the method filter:
>
> filter(lambda x: x not in list2, list1)
>
> but it didn't make much difference, because of lambda I guess
> is there any way I can speed this up[/color]

Both of these techniques are O(n^2). You can reduce it to O(n log n)
by using sets:
[color=blue][color=green][color=darkred]
>>> set2 = set(list2)
>>> [x for x in list1 if x not in set2][/color][/color][/color]

Checking to see if an item is in a set is much more efficient than a
list.

--Ben

[Fredrik Lundh]

Re: filter list fast

lars_woetmann wrote:
[color=blue]
> I have a list I filter using another list and I would like this to be
> as fast as possible right now I do like this:
>
> [x for x in list1 if x not in list2]
>
> i tried using the method filter:
>
> filter(lambda x: x not in list2, list1)
>
> but it didn't make much difference, because of lambda I guess
> is there any way I can speed this up[/color]

if list2 is a list object, "not in list2" is an O(N) operation.

maybe you should use sets instead ? does the following work
better ?

set2 = set(list2)
result = [x for x in list1 if x not in set2]

?

</F>

[Klaus Alexander Seistrup]

Re: filter list fast

Lars Woetmann wrote:
[color=blue]
> I have a list I filter using another list and I would like
> this to be as fast as possible
> right now I do like this:
>
> [x for x in list1 if x not in list2]
>
> i tried using the method filter:
>
> filter(lambda x: x not in list2, list1)
>
> but it didn't make much difference, because of lambda I guess
> is there any way I can speed this up[/color]

If you use a reasonably new python version, you could use sets:

#v+
[color=blue][color=green][color=darkred]
>>> a = set(range(10))
>>> a[/color][/color][/color]
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])[color=blue][color=green][color=darkred]
>>> b = set(range(5, 15))
>>> b[/color][/color][/color]
set([5, 6, 7, 8, 9, 10, 11, 12, 13, 14])[color=blue][color=green][color=darkred]
>>> a.difference(b)[/color][/color][/color]
set([0, 1, 2, 3, 4])[color=blue][color=green][color=darkred]
>>> a-b[/color][/color][/color]
set([0, 1, 2, 3, 4])[color=blue][color=green][color=darkred]
>>> list(a-b)[/color][/color][/color]
[0, 1, 2, 3, 4][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

#v-

Cheers,

--
Klaus Alexander Seistrup
SubZeroNet, Copenhagen, Denmark

http://magnetic-ink.dk/

[Diez B. Roggisch]

Re: filter list fast

> Both of these techniques are O(n^2). You can reduce it to O(n log n)[color=blue]
> by using sets:
>[color=green][color=darkred]
>>>> set2 = set(list2)
>>>> [x for x in list1 if x not in set2][/color][/color]
>
> Checking to see if an item is in a set is much more efficient than a
> list.[/color]

Is the set-lookup reliably O(log n)? I was under the impression that it is
hash-based, and this should be O(1) usually, but couldbve O(n) worst-case
(hash the same for _all_ entries).

Regards,

Diez

[Peter Hansen]

Re: filter list fast

Diez B. Roggisch wrote:[color=blue][color=green]
>>Both of these techniques are O(n^2). You can reduce it to O(n log n)
>>by using sets:
>>[color=darkred]
>>>>>set2 = set(list2)
>>>>>[x for x in list1 if x not in set2][/color]
>>
>>Checking to see if an item is in a set is much more efficient than a
>>list.[/color]
>
> Is the set-lookup reliably O(log n)? I was under the impression that it is
> hash-based, and this should be O(1) usually, but couldbve O(n) worst-case
> (hash the same for _all_ entries).[/color]

That's largely a theoretical concern. Google for something like

'''dict worst-case performance "tim peters"'''

to learn more. (The third article there (no doubt obsolete in some
ways, given that it was in 2000) says that Python "keeps at least 1/3 of
the internal hash table entries unused, making collisions very rarely a
problem... It's possible to contrive keys that will cause collisions
systematically ... but unlikely to happen by accident in 2.0")

-Peter

[lars_woetmann]

Re: filter list fast

Thanks all, sets work like i charm

[Paddy]

Re: filter list fast

What was the speed-up ?

[lars_woetmann]

Re: filter list fast

comparing
[x for x in list1 if x not in list2]
with
set1, set2 = set(list1), set(list2)
list(set1-set2)

gives something like
len(list2) speedup
------------------------------
100 10
1000 100
10000 1000

the speedup is constant for different len(list1)

[Paddy]

Re: filter list fast

Thanks.