Making an algorithm more efficient

algorithmsefficiency

I have a question about the efficiency of an algorithm:

You have a list of x,y points

Now I want to get all the points that are up to 5 units away from a reference x,y point

How do you calculate it in the most efficient way?

I just go over each point and calculate distance, and if that distance is less than 5, I add it to the answer

If you know how this algorithm is called – I'd be happy if you post that too.

Best Answer

While you cannot avoid having to check every point, there are techniques you can use to check quickly or check only once.

For example, most points you can tell if they are too far away without calculating the exact distance. For example, if I have a point whose x component is 100 away from the point of reference, you don't have to calculate distance. You already know that the point is too far away. Likewise if the x and y deltas are less than 5*2*sqrt(2) away from the point of reference, you know they are close enough. See the diagram below for a visual example:

Diagram describing algorithm

If P is your point of origin and the circle represents the farthest away that a point can be from point P (in your case radius of 5 units), then A and C represents places where points are definitely out or definitely in. Therefore, you can optimize your algorithm by checking x and y deltas. Only points which lie in the gray area B should have their distance calculated because you cannot know without performing a more sophisticated calculation.

Also, it would not hurt to sort your points by distance to P. If you have to perform this calculation often, you could optimize calculation by sorting once, then finding the farthest point within 5 units from P. Unless point positions change, you know that all points after that point must be closer.

I hope that helps!

DOM only vs DOM backed by a JSON Data Model

Now, regardless of the tools, or algorithm you are going to use, if you work only with DOM elements, without having a "backend" JSON data model (please someone complete here if you see more problems):

Finding the new position of a given player will be a pain
Updating the positions of every player will be a pain

If you work with DOM elements for rendering, backed by a JSON data model, and provided you make the following changes to your individual player display, you will have a much easier time:

   <div class="player" id="player2">
        <div class="name">Player2</div>
        <div class="points" id="playerPoints2">400</div>
        <div class="position" id="playerPosition2">2</div>
   </div>

Notice that I've added an id attribute to the player <div> and to the elements displaying the points ("playerPoints2") and the position ("playerPosition2"). Doing that will allow you to quickly find the position of a player or its points, given its unique id. You could do without, but that would affect performance and you would have to use more complex queries (see JQuery's .find())

My attempt:

In short, what I try to do is moving as few DOM elements as possible, and decorrelating the data from the display.

Imagine having the following JSON data model in addition to your DOM model for displaying the players:

player (array of players)
- id
- position (you can write a custom function for sorting the array given the "position" attribute if each item of the array)
- points
- name

and the following JSON data model for performing animations later:

playerChanges (array of player changes)
- id
- deltaPosition (example: +3 = 3 ranks higher than before) . * isComputed (boolean)

After receiving data from the server, here's what I would do:

sort the list of backend players, given their respective position. The first element of the array should be the top ranked player.
loop over the data received from the server
if the points of a player change, then:
- look up the player in the array
- update its points
- move the player to the position in the array where it should fit, but don't change the "position" attribute
- create a new entry in the "playerChanges" array, storing only the id of the player (we will compute the delta only at the end)
loop on the array of backend players, and for each player in "playerChanges" (this is important) that is nit yet conputed, compute the position attribute regarding to the position of the player in the array. Since you have his "old" position, and the position in the array, you can compute the "deltaPosition". Edit: after you compute the delta, mark the "playerChange" as computed and restart looping on the array of backend players. Do that as long as there is an uncomputed ""playerChange"" in the array.

In the end you should have an array of "playerChanges". This is the list of rows that you should move, given the "deltaPosition" of each player. Notice that it could be 0, which means that the player received new points, but his position did not change. To perform the animation, I would suggest looking at this brilliant answer.

After you have done these animations, you can loop again on the list of backend players in order to update the displayed position ("playerPositionXXX" where XXX is the id of the player) of each player.

What I've attempted to do here is to decorrelate the "update and sort" from what happens on the screen, the animation that the user sees.

Edit: here is a working code sample (on Chrome at least) of an animation with JQuery and JQueryUI.

<html>
    <head>
        <title>Temp test</title>
        <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.8.0/jquery.min.js"></script>
        <script src="http://ajax.googleapis.com/ajax/libs/jqueryui/1.8.23/jquery-ui.min.js"></script>
        <style type="text/css">
            * { font-family: Calibri;}
            .player { border: 1px solid grey; background: #f0f0f0; width: 300px; 
                        padding: 10px; margin-bottom: 5px; margin-top: 5px; }
                .name { margin-left: 30px; font-size: 20px; font-weight: bold; }
                .points { float: right; color: whitesmoke; font-size: 24px; font-weight: bold; margin-top: -30px; 
                            background-color: #999; padding: 3px;}
                .position { clear: both; display: block; float: left; 
                            font-size: 20px; font-weight: bold; margin-top: -29px; padding-right: 10px; 
                            border-right: 1px solid black;}
        </style>
        <script type="text/javascript">

            function movePlayer(playerToMoveId, delta) {
                var $old = $(playerToMoveId);
                var $new = $old.clone();

                // TODO: here I don't take into account the delta
                // 
                // you need to write a simple method for determining the player
                // that will be replaced (here I hardcoded "p4"). 
                $("#p4").before($new);

                var newOffset = $new.offset();
                //Get the old position relative to document
                var oldOffset = $old.offset();
                //we also clone old to the document for the animation
                var $temp = $old.clone().appendTo('body');
                //hide new and old and move $temp to position
                //also big z-index, make sure to edit this to something that works with the page
                $temp
                  .css('position', 'absolute')
                  .css('left', oldOffset.left)
                  .css('top', oldOffset.top)
                  .css('zIndex', 1000);
                $new.hide();
                $old.hide();
                //animate the $temp to the position of the new img
                $temp.animate( {'top': newOffset.top, 'left':newOffset.left}, 'slow', function(){
                   //callback function, we remove $old and $temp and show $new
                   $new.show();
                   $old.remove();
                   $temp.remove();
                });
            }
        </script>
    </head>
    <body>
        <div class="players_list" id="plist">
           <div class="player" id ="p4">
                <div class="name" id="pName4">Player4</div>
                <div class="points" id="pPts4">800</div>
                <div class="position" id="pPos4">1</div>
           </div>
           <div class="player" id="p3">
                <div class="name" id="pName3">Player3</div>
                <div class="points" id="pPts3">500</div>
                <div class="position" id="pPos3">2</div>
           </div>

           <div class="player" id="p1">
                <div class="name" id="pName1">Player1</div>
                <div class="points" id="pPts1">300</div>
                <div class="position" id="pPos1">3</div>
           </div>     
           <div class="player" id="p2">
                <div class="name" id="pName2">Player2</div>
                <div class="points" id="pPts2">250</div>
                <div class="position" id="pPos2">4</div>
           </div>
        </div> 

        <input type="button" onclick="movePlayer($('#p2'), 3)" value="Animate"/>
    </body>
</html>

How does Jump Point Search algorithm work and why is it so efficient

The basic idea is that JPS allows to throw away many candidate paths early, therefore reducing the amount of computations required.

In many maps, multiple paths with the same cost lead to same destination, such as a game map with large open areas. JSP allows pruning those paths.

An in-depth explanation can be found here.

Best Answer

Related Solutions

JavaScript Algorithms – Efficient Algorithm to Sort HTML List of Players

DOM only vs DOM backed by a JSON Data Model

My attempt:

How does Jump Point Search algorithm work and why is it so efficient

Related Topic