Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
-
My Advice:
Start with a list of 10x10 each.
and crank up the number via an algorithm with a check. if you surpass a certain amount of milliseconds you pass or fail and then display the number.
Looks like you are looking for points that are on the same location? giving two list of 200k points
given by their x,y location (unsorted?)
sounds like a collision detection system.
perhaps you can look for information there.
because the points are just on their x/y coordinates I would just sort them with bucket sort. and then within the buckets I would find matches.
Have fun! -
Well, you went from O(N²) to O(N) in time, but from O(N) to O(N²) in space.
I would have sorted one of the lists in-place with 'x' as primary key, and 'y' as secondary. That's O(N log N). Then looping through the unsorted list, trying to look up each point in the sorted list using binary search, that's also O(N log N). -
@Fast-Nop How is it N^2 in space? It stores an additional list with a hash and an integer. This would be about double the size of one of the lists. So approx O(2N) ?
-
@Demolishun Ah I misread you'd have an NxN 2D counting array with the point x/y domain.
This is probably a standard pattern/algorithm, but I feel pretty good about myself figuring this out.
I was doing a programming challenge and found myself with 2 lists of integer points (x,y). I needed to see where the points converged and identify those locations. Of course I started with a brute force approach and did nested loops to find these locations. This was taking WAY TOO LONG. These lists were 200K each. So checking with naive looping is 200K * 200K operations. Which is a lot.
Then I thought, well I am checking equality, so I will create a third map. The index to the map will be the point, and the data will be an integer. I then go through each list once incrementing the integer for each point that exists in each respective list. Any point with a value greater than 1 is a point convergence.
Like I said, this has got to be a standard thing, so can someone tell me what algorithm this is? I am not sure how to search for this.
I am fuzzy on complexity notation but I think the complexity started at n^2 and was reduced to n. Each list is cycled over once.
rant
algorithm?