473,583 Members | 3,097 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Slow comparison between two lists

I have rather simple 'Address' object that contains streetname,
number, my own status and x,y coordinates for it. I have two lists
both containing approximately 30000 addresses.

I've defined __eq__ method in my class like this:

def __eq__(self, other):
return self.xcoord == other.xcoord and \
self.ycoord == other.ycoord and \
self.streetname == other.streetnam e and \
self.streetno == other.streetno

But it turns out to be very, very slow.

Then I setup two lists:

list_external = getexternal()
list_internal = getinternal()

Now I need get all all addresses from 'list_external' that are not in
'list_internal' , and mark them as "new".

I did it like this:

for addr in list_external:
if addr not in list_internal:
addr.status = 1 # New address

But in my case running that loop takes about 10 minutes. What I am
doing wrong?

--

Jani Tiainen
Oct 23 '08 #1
7 1216
Jani Tiainen <re*****@gmail. comwrites:
for addr in list_external:
if addr not in list_internal:
addr.status = 1 # New address

But in my case running that loop takes about 10 minutes. What I am
doing wrong?
The nested loop takes time proportional to the product of the number
of elements in the loops. To avoid it, convert the inner loop to a
set, which can be looked up in constant time:

internal = set(list_intern al)
for addr in list_external:
if addr in internal:
addr.status = 1
Oct 23 '08 #2
Jani Tiainen wrote:
I have rather simple 'Address' object that contains streetname,
number, my own status and x,y coordinates for it. I have two lists
both containing approximately 30000 addresses.

I've defined __eq__ method in my class like this:

def __eq__(self, other):
return self.xcoord == other.xcoord and \
self.ycoord == other.ycoord and \
self.streetname == other.streetnam e and \
self.streetno == other.streetno

But it turns out to be very, very slow.

Then I setup two lists:

list_external = getexternal()
list_internal = getinternal()

Now I need get all all addresses from 'list_external' that are not in
'list_internal' , and mark them as "new".

I did it like this:

for addr in list_external:
if addr not in list_internal:
addr.status = 1 # New address

But in my case running that loop takes about 10 minutes. What I am
doing wrong?
Even if list_external and list_internal contain the same items you need
about len(list_extern al)*(len(list_i nternal)/2), or 45 million comparisons.
You can bring that down to 30000*some_smal l_factor if you make your
addresses hashable and put the internal ones into a dict or set

def __hash__(self):
return hash((self.xcoo rd, self.yccord, self.streetname , self.streetno))
def __eq__(self, other):
# as above

Then

set_internal = set(list_intern al)
for addr in list_external:
if addr not in set_internal:
addr.status = 1

Note that the attributes relevant for hash and equality must not change
during this process.

Peter
Oct 23 '08 #3
Hrvoje Niksic:
internal = set(list_intern al)
....

To do that the original poster may have to define a __hash__ and
__eq__ methods in his/her class.

Bye,
bearophile
Oct 23 '08 #4
Jani Tiainen a écrit :
I have rather simple 'Address' object that contains streetname,
number, my own status and x,y coordinates for it. I have two lists
both containing approximately 30000 addresses.

I've defined __eq__ method in my class like this:

def __eq__(self, other):
return self.xcoord == other.xcoord and \
self.ycoord == other.ycoord and \
self.streetname == other.streetnam e and \
self.streetno == other.streetno

But it turns out to be very, very slow.

Then I setup two lists:

list_external = getexternal()
list_internal = getinternal()

Now I need get all all addresses from 'list_external' that are not in
'list_internal' , and mark them as "new".

I did it like this:

for addr in list_external:
if addr not in list_internal:
addr.status = 1 # New address

But in my case running that loop takes about 10 minutes. What I am
doing wrong?
mmm... not using sets ?
Oct 23 '08 #5
On 23 loka, 15:24, Peter Otten <__pete...@web. dewrote:
Jani Tiainen wrote:
I have rather simple 'Address' object that contains streetname,
number, my own status and x,y coordinates for it. I have two lists
both containing approximately 30000 addresses.
I've defined __eq__ method in my class like this:
* * def __eq__(self, other):
* * * * return self.xcoord == other.xcoord and \
* * * * * * self.ycoord == other.ycoord and \
* * * * * * self.streetname == other.streetnam e and \
* * * * * * self.streetno == other.streetno
But it turns out to be very, very slow.
Then I setup two lists:
list_external = getexternal()
list_internal = getinternal()
Now I need get all all addresses from 'list_external' that are not in
'list_internal' , and mark them as "new".
I did it like this:
for addr in list_external:
* * if addr not in list_internal:
* * * * addr.status = 1 # New address
But in my case running that loop takes about 10 minutes. What I am
doing wrong?

Even if list_external and list_internal contain the same items you need
about len(list_extern al)*(len(list_i nternal)/2), or 45 million comparisons.
You can bring that down to 30000*some_smal l_factor if you make your
addresses hashable and put the internal ones into a dict or set

def __hash__(self):
* *return hash((self.xcoo rd, self.yccord, self.streetname , self.streetno))
def __eq__(self, other):
* *# as above

Then

set_internal = set(list_intern al)
for addr in list_external:
* * if addr not in set_internal:
* * * * addr.status = 1

Note that the attributes relevant for hash and equality must not change
during this process.
Very complete answer, thank you very much.

I tried that hash approach and sets but it seemed to get wrong results
first time and it was all due my hash method.

Now it takes like 2-3 seconds to do all that stuff and result seem to
be correct. Apparently I have lot to learn about Python... :)

--

Jani Tiainen
Oct 23 '08 #6
be************@ lycos.com writes:
>internal = set(list_intern al)
...

To do that the original poster may have to define a __hash__ and
__eq__ methods in his/her class.
You're right. The OP states he implements __eq__, so he also needs a
matching __hash__, such as:

def __hash__(self, other):
return (hash(self.xcoo rd) ^ hash(self.ycoor d) ^
hash(self.stree tname) ^ hash(self.stree tno))
Oct 23 '08 #7
On Thu, 23 Oct 2008 05:03:26 -0700, Jani Tiainen wrote:
But in my case running that loop takes about 10 minutes. What I am doing
wrong?
Others have already suggested you have a O(N**2) algorithm. Here's an
excellent article that explains more about them:

http://www.joelonsoftware.com/articl...000000319.html
The article is biased towards low-level languages like C. In Python the
way to avoid them is to use sets or dicts, or to keep the list sorted and
use the bisect module.
--
Steven
Oct 23 '08 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
3076
by: Craig Keightley | last post by:
is it possible to compare acomma separated list aginst another eg comma list 1 => 1,2,3,4,5 comma list 2 => 3,5 can you check that 3 is in both, and 5 is in both, therfore they match??? the comparison is to check that if product a who supplies products 1,2,3,4,5 can be used instead of product b who supplies 3,5 as product a already...
5
3132
by: Shay | last post by:
essentially I am trying to do some counts based on some assumptions in the recordset. So I get the RS back, put the values into a variable, move to the next record in the RS and compare what is in the variable to the value in the next record in the recordset and do a count. Then overwrite the value in the variables and do the same for the...
2
5340
by: Tim Fountain | last post by:
We've recently enabled slow query logging on a server and it's proving interesting seeing which queries are bogging things down. This one is puzzling me a little: SELECT articleid, type, authorid, authorname, text, posted FROM comments WHERE status = 'normal' ORDER BY posted DESC LIMIT 5; The purpose of this query is to list the five...
50
5682
by: diffuser78 | last post by:
I have just started to learn python. Some said that its slow. Can somebody pin point the issue. Thans
0
7896
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7828
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8186
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7936
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8197
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6583
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
3821
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1436
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1160
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

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.