473,219 Members | 1,819 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,219 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 3297
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: GujuBoy | last post by:
i want to check to see if a certain program is installed on my windows box using python. how can i do that...(ie, i want to see if "word" is installed) please help
1
by: Spockie | last post by:
I do not use linkedlist stdlibrary, vector i make my own, but i have problems with one issue, and that is checking if there are duplicates in the middle of inputing information line 294 ...
1
by: Xeno Campanoli | last post by:
I'm having a hard time checking existence of windows. The only thing I found on this is page 224 of Rhino. Why is there no function to check this? Is there a publication on this part of the...
2
by: mike | last post by:
I had a form like below that validated that a file was there before it would submit. <form name="attach" method="POST" action="run_this_pgm.cfm" enctype="multipart/form-data"...
5
by: Richard L Rosenheim | last post by:
What's the proper technique for checking for the existence of an attribute within a node? Lets say I did a SelectSingleNode which returned this element: <AnAddress city="San Francisco"...
5
by: Jermin | last post by:
Hi, I have a database composed of a single table composed of 2 columns, an auto-numbered ID column and a column which contains 30 million random numbers. All I want to Access to do is check the...
4
by: Patient Guy | last post by:
Does anyone have any coding rules they follow when doing argument checking? When arguments fail during check, do you return from the call with an ambiguous return value, or do you throw...
2
by: oaklander | last post by:
I currently have two String variables I check to find if they are duplicates: String str1 = "red"; String str2 = "yellow"; if (str1.equals(str2)){ System.out.println("Duplicate"); }...
7
by: john.cole | last post by:
I have searched all the groups I can, and I still haven't been able to come up the solution I need. I have the following problem. In my form named sbfrmSpoolList, I am entering a job, spool and...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

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.