0

I have a function f(u,v) of two variables u and v defined on a square with side of length 1.
A timer starts and for each tick of the timer I need to evaluate this function thousands of times on a discrete set of points (u,v) of this square. This points (u,v) can be different at every tick of the timer and there is no reason to suppose that they are always the same. For performance reasons, I want to sample some points of the square [f(0,0), f(0,0.1), f(0,0.2), ..., f(0.1,0),...f(1,1)] and evaluate the function only once before the timer starts and then get them as fast as possible.

Can a dictionary be a solution? Or are there better structures?

I forgot to add that obviously I don't need all the possible u, v values of the square of side 1 but those belonging to a discrete grid.

aSpagno
  • 141
  • 5
  • If the function returns the value at that point for that time step, then it sounds like you need to call the function for each point, at each time step. Sure you *could* pre-compute every value (if it's deterministic and constant), but it sounds like that's just working around whatever problem you have. – Thomas Jager Mar 01 '21 at 14:19
  • I forgot to add that obviously I don't need all the possible u, v values of the square of side 1 but those belonging to a discrete grid. – aSpagno Mar 01 '21 at 14:28
  • Should we assume the function evaluation is complex and time consuming? What is the value range for u and v? A 2D matrix, with the values encoded as integers might be very effective. You should not worry to much on a 1000x1000 matrix, With modern computers this should not be an issue. If it gets really big, it may not help you out. – RudolfJan Mar 02 '21 at 13:58
  • Yes, you can suppose that the function is time consuming. It is used to solve an equation of 4-th degree, so it contains a lot of call to Math.Sqrt for example. – aSpagno Mar 02 '21 at 15:21
  • You can also assume that the value range is [0,1] for both u and v – aSpagno Mar 02 '21 at 15:24

1 Answers1

0

If you need to samples on a regular grid, you can simply store them in a 2D array, i.e. T[11,11], just multiply your u,v coordinates with 10, or however dense your sampling is, and truncate to an int to get your indices.

A dictionary would also work, but it will probably have a larger overhead since it needs to hash the keys. For regular grids a 2D array would make more sense, while dictionaries might be more appropriate for non-regular sampling patterns.

A more complicated method could be a kd or quad-tree. These allow efficient storage of non-regular sample patterns while still allowing efficient queries of the closest point(s). But it does not sound like you need this from your description. This answer provides a great introduction to grids, quadtrees and kd trees.

JonasH
  • 28,608
  • 2
  • 10
  • 23
  • Hi Jonash, Could you be more specific about this latest kd or quad-tree method? – aSpagno Mar 02 '21 at 10:30
  • @Antonio Spagnuolo added a link to a good explanation. – JonasH Mar 02 '21 at 10:50
  • Hi Jonash, do you think that this is the most accurate way to truncate the double value to get its index? int indexU = (int) Math.Round(u /gridStep,MidpointRounding.AwayFromZero); – aSpagno Mar 03 '21 at 11:56
  • @antonio Spagnuolo If you are guaranteed to only have positive values I would just use `int indexU = (int)(u/gridStep)`. If you want to allow the 1.0 coordinate you should ensure your grid is of size `1/gridStep + 1`. Also consider what to do for values outside the 0-1 range. Exception? clamp? – JonasH Mar 03 '21 at 12:10
  • Thank you for the insight. Fortunately I have to handle only values inside the 0-1 range, so I do not worry about exceptions. – aSpagno Mar 03 '21 at 13:00