Need help for search optimization

Question

I am fairly new to programming and i need some help with optimizing. Basically a part of my method does:

for(int i = 0; i < Tiles.Length; i++)
{
    x = Tiles[i].WorldPosition.x;
    y = Tiles[i].WorldPosition.y;
    z = Tiles[i].WorldPosition.z;

    Tile topsearch = Array.Find(Tiles,
        search => search.WorldPosition == Tiles[i].WorldPosition +
            new Vector3Int(0,1,0));

    if(topsearch.isEmpty)
    {
        // DoMyThing
    }
}

So i am searching for a Tile in a position which is 1 unit above the current Tile. My problem is that for the whole method it takes 0.1 secs which results in a small hick up..Without Array.Find the method is 0.01 secs.

I tried with a for loop also, but still not great result, because i need 3 more checks for the bottom, left and right..

Can somebody help me out and point me a way of acquiring some fast results? Maybe i should go with something like threading?

If "finding" is an operation you do a lot and it needs to be fast then build a secondary storage of some sort -- a dictionary, typically -- that maps from the search key to the item. Dictionaries are optimized for fast search. — Eric Lippert, Dec 09 '13 at 14:51
@EricLippert, you know I was thinking the same thing, but then second guessed it because you're using memory just for the purposes of looking up a value. However, now that you've stated it; at least I was heading down the right school of thought. — Mike Perrenoud, Dec 09 '13 at 14:52
@MichaelPerrenoud: You can almost always trade memory for speed. It depends on which resource is cheap. On mobile devices it is usually smarter to trade lower speed for less memory usage; on desktop and server devices, particularly 64 bit, it is often a win to trade more memory usage for more speed. Of course the price you pay is not just more memory usage; it's making the data structures more complicated, possibly introducing bugs. And you are slowing down every insert in order to make every lookup faster. — Eric Lippert, Dec 09 '13 at 14:55
@EricLippert, so unless you're on a mobile device, you would justify it just like you'd justify a new index in a database. The look up speed can be orders of magnitude greater, but it can be worthless if it's a high-transaction environment. — Mike Perrenoud, Dec 09 '13 at 14:56
Can the tiles overlap ? If yes, then x, y, and z values may have duplicates, then more attention is required if a key based alternate storage is considered. — Larry, Dec 09 '13 at 15:06
@MichaelPerrenoud: Correct; an index makes the same tradeoff. All inserts become slightly slower because the index property must be maintained, and database size goes up because the index data has to be stored somewhere, but lookups become O(lg n) or O(1) instead of O(n). — Eric Lippert, Dec 09 '13 at 15:59

Roy Dictus · Accepted Answer · 2013-12-09T14:58:21.697

9

You could create a 3-dimensional array so that you can look up a tile at a specific location by just looking what's in Tiles[x, y + 1, z].

You can then iterate through your data in 2 loops: one to build up Tiles and one to do the checks you are doing in your code above, which would then just be:

for(int i = 0; i < Tiles.Length; i++)
{
    Tile toFind = Tiles[Tile[i].x, Tile[i].y + 1, Tile[i].z];
    if (toFind != null) ...
}

You would have to dimension the array so that you have 1 extra row in the y so that Tiles[x, y + 1, z] doesn't cause an index-out-of-range exception.

edited Dec 09 '13 at 14:58

answered Dec 09 '13 at 14:53

Roy Dictus

32,551
8
60
76

1

The way to go, unless x, y and z are astronomical and the grid is very sparse. – Rotem Dec 09 '13 at 14:54
3

@Rotem, and in that case, you could use sparse grid idioms. – Bathsheba Dec 09 '13 at 14:55
I think i will go and try for that.Thank you. – Mama Tate Dec 09 '13 at 15:10

score 4 · Answer 2 · edited May 23 '17 at 11:57

4

Adding to Roy's solution, if the space is not continuous, as it might be, you could put a hashcode of WorldPosition (the x, y and z coordinates) to some good use here.

I mean you could override WorldPosition's GetHashCode with your own implementation like that:

public class WorldPosition
{
    public int X;
    public int Y;
    public int Z;

    public override int GetHashCode()
    {
        int result = X.GetHashCode();
        result = (result * 397) ^ Y.GetHashCode();
        result = (result * 397) ^ Z.GetHashCode();
        return result;
    }
}

See Why is '397' used for ReSharper GetHashCode override? for explanation.

Then you can put your tiles in a Dictionary<WorldPosition, Tile>.

This would allow for quickly looking up for dict[new WorldPosition(x, y, z + 1)] etc. Dictionaries use hashcode for keys, so it would be fast.

edited May 23 '17 at 11:57

Community

1
1

answered Dec 09 '13 at 14:58

Konrad Morawski

8,307
7
53
91

The 397 thing is fascinating. – Larry Dec 09 '13 at 15:08
1

That's not the only thing I learned thanks to ReSharper :) By the way, note that there is a risk of hash collisions for really large worlds, so it should be taken into account as well. – Konrad Morawski Dec 09 '13 at 15:10
...2^32 is less than 1625^3 - in other words, if the world is 1625 x 1625 x 1625, there's not enough 32-bit integers to provide unique hashes and the probability of a hash collision reaches 100%. It looks much better with a 64-bit hash, however. – Konrad Morawski Dec 09 '13 at 15:16

score 0 · Answer 3 · answered Dec 09 '13 at 14:59

First, like @Roy suggested, try storing the values in an array so you can access them with x,y,z coordinates,

Another thing you could do is change the search to

Tile topsearch = Array.Find(Tiles,
        search => search.WorldPosition.x == Tiles[i].WorldPosition.x && 
        search.WorldPosition.y == (Tiles[i].WorldPosition.y + 1) &&
        search.WorldPosition.z == Tiles[i].WorldPosition.z)

This might be faster as well, depending on how many fields your WorldPosition has

Need help for search optimization

3 Answers3