Improvement on O(N*N) solution

Question

I am having a list of object which gets modified. Modification is either removal of object from list or addition of object to list.

Logic to check removal is some what not good that is what I feel as it is O(N*N). It actually checks one with all other. Can I improve this logic?

Refer code below for more clarity:

https://code.sololearn.com/cyyYiGLuJ7BO

I just need to improve checkCollosion() function. Any thoughts?

P.s. : I forgot to add my thoughts and confusion on same...

I thought to add map instead of list ...key will be position and value will be object... But will map work on dynamic additional object creation when iterator is iterating over in update function ? That's why I thought to raise the query... If used map, just check with few only as it is sorted data... Plus map insertion and deletion is costly compared to corresponding operation on list

Answer 1

Deepak Singh the outer array size is 10 for the original question and code that Ketan Lalcheta is asking, however the OP changed the question again to ask about 800 * 800 boundary collision which should have been in a separate question thread instead to give less confusion to the original question asked. i already answered the solution to that above, which is to use octree or quadtree for collision checking. that's what algorithms physics engine uses for their collision detection

Answer 2

One way to speed is to write a custom quicksort algorithm which sorts your lsthuman according to position. Then you can go through the list and remove consecutive values with same position. The complexity should be O(nlog(n) + n).

You can also use map by creating a map for each check call. Update value by position(like you mentioned) and then remake a new list.

Answer 3

You should always consider a structure that you process as immutable for the duration that it is being processed.

Speed is usually bought with space. Depending on where you are going with this, addition of bookkeeping structures (space consumption) may help to boost performance. But you should evaluate space requirements, and how it scales to your targeted size.

Answer 4

With the new information, I think sorting will not solve your problem. Even using maps will be difficult since collison is not happening at the position but at a distance. So, you will need to check each existing key for evey insretion. How many humans do you have in this code? Is the region in which they exist fixed?

Answer 5

Your requirement is that on the grid any circle with a radius of 5 should have only 1 point in it. The solution should account for all the overlapping circles. Sorting with a base point will place 0,200 and 200,0 next to each other. To be honest, i am unable to think of a solution better than O(N*N) right now.

Answer 6

just use a 2d vector instead of a list, the outer array index would have 10 size which represents each position. and then each position would contain another vector.

when checkCollision() is called, it would simply loop through the outer vector and check if there is more than 2 humans in that vector, clear the vector.

giving it an O(10) time complexity.

if you're askig about how to check collision of each objects on a 2d plane, there's already a lot of documentation of algorithms used to solve this. you can check about octree, quadtree and aabb collision algorithms for that.

Answer 7

If I am not wrong, Shen missed my comment regarding boundary of 800*800...

He just refered code having 10 unique position in 1-D due to below line

double ipos = rand() % 10;

Answer 8

Thanks Deepak Singh and Ani Jona 🕊

When I thought to sort it , I got more confused

The code here is very basic code I created for the question.. my actual code where I am trying to optimise is complex

I forgot to mention that pos here is int only and collision happen when both humans are having same pos value

in actual , I have pos as array of size 2 storing x and y co ordinates... collision occurs when distance between two humans sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) is less than 5

how to sort in this case as distance is relative to all humans and not absolute value

Answer 9

How to keep in sync is the issue .... If we can have sorted data or by somehow have index , all set

But how to sort or how to have index as it is not absolute and it is relative

Distance is relative to other human. so how to sort as two objects are considered for finding the distance

Answer 10

My boundary is -400,-400 to 400,400.

Does below method work ?

Base point is -400,-400
Does all human calculate distance between own position and base point ? Based on this distance, can we sort all human ?

Answer 11

Shen can you please elaborate on why the outer array index would have 10 size which represents each position? Can you provide one or two example of the position on the 800x800 grid. I mean if you start from -395,-395. What will be the next position?

Answer 12

Oh… that makes a lot of sense…