search

carsonfarmer / fastpair

FastPair: Data-structure for the dynamic closest-pair problem.
MIT License
12 stars 4 forks source link

Use python set instead of python list for maintaining points #13

Open CMCDragonkai opened 6 years ago

CMCDragonkai commented 6 years ago

I noticed that point removal is O(n) as it uses list remove function. Instead one can switch to using sets, which would make it close to O(1) for removal. All other operations don't really change by switching to sets as far as I can see.

carsonfarmer commented 6 years ago

Ah nice find, I'm hoping to find a few spare moments this weekend to get this fix in a push to pypi. I'l report back here when those are done.

CMCDragonkai commented 6 years ago

Note that if you use sets, points cannot be lists, since lists are unhashable. But if they are lists, they can be converted to tuples. Ultimately one can just say that input points must be hashable objects.

CMCDragonkai commented 5 years ago

@carsonfarmer Any update on this?

carsonfarmer commented 5 years ago

I don't have much time to spend on this library these days. I'd be happy to accept a quick PR with this change if you're interested?

CMCDragonkai commented 3 years ago

@Rakesh4G tried to do this recently but it didn't work... maybe there's some trick here we need.

carsonfarmer commented 3 years ago

Hmmm, ok. I can take a look at this. Can @Rakesh4G elaborate on what "didn't work" in this context means?