471,330 Members | 1,835 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,330 software developers and data experts.

Checking for the existence of Duplicates

I have found a lot of material on removing duplicates from a list, but I
am trying to find the most efficient way to just check for the existence
of duplicates in a list. Here is the best I have come up with so far:

CheckList = [x[ValIndex] for x in self.__XRList[z]]
FilteredList = filter((lambda x:x != 0),CheckList)
if len(FilteredList) len(sets.Set(FilteredList)): return
False

The first statement pulls the slice out of a matrix I need to check.
The filter statement gets rid of zeroes (they don't count as duplicates).
The if statement is the actual duplicates check

This is in a program that generates random numbers to do a brute force
solve on a sudoku-like puzzle. Once a certain level of difficulty in
the puzzle is reached, performance goes off a cliff because the
duplicate checking code, although fast, is executed so many times.
Sep 28 '07 #1
1 3165
On Sep 28, 10:27 pm, AndyB <andrewblakes...@gmail.comwrote:
...
This is in a program that generates random numbers to do a brute force
solve on a sudoku-like puzzle. Once a certain level of difficulty in
the puzzle is reached, performance goes off a cliff because the
duplicate checking code, although fast, is executed so many times.
For a sudoku solver, you may be better dodging the problem, and
maintaining a set per row, column and box saying which numbers have
been placed already - and thus avoiding adding duplicates in the first
place. It may be better to use a bitfield instead (ie use bits 1..9 of
an int to represent these sets). You should also check out Donald
Knuth's 'Dancing Links' algorithm as a clever implementation of a
brute-force search that works perfectly for sudoku solving. (It uses
linked lists, but the idea still works in python).

But to answer your actual question:
I have found a lot of material on removing duplicates from a list, but I
am trying to find the most efficient way to just check for the existence
of duplicates in a list. Here is the best I have come up with so far:

CheckList = [x[ValIndex] for x in self.__XRList[z]]
FilteredList = filter((lambda x:x != 0),CheckList)
if len(FilteredList) len(sets.Set(FilteredList)): return
In general, the natural way to test for duplicates is as you have it,
except that set is now built-in, so you can write
def has_no_duplicates(x):
return len(x) == len(set(x))

But in your case, you're having to construct the list and filter, so
it's better just to loop and do everything at once:

found = set()
for x in self.__XRList[z]:
cell = x[ValIndex]
if cell != 0 and cell in found:
return False
found.add(cell)

Since your elements are probably numbers 1 to 9 (or 0), you might use
bitfields. I'd expect this to be faster, but you should check:

found = 0
for x in self.__XRList[z]:
cellbit = 1 << x[ValIndex]
if cellbit != 1 and (cellbit & found):
return False
found |= cellbit

--
Paul Hankin

Sep 28 '07 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by GujuBoy | last post: by
1 post views Thread by Spockie | last post: by
1 post views Thread by Xeno Campanoli | last post: by
2 posts views Thread by mike | last post: by
5 posts views Thread by Richard L Rosenheim | last post: by
4 posts views Thread by Patient Guy | last post: by
2 posts views Thread by oaklander | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.