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