CODEWITHSUNDEEP
c#.netperformancelinq
Adam Knights
Adam Knights

Reputation: 2151

C# Data Structure to allow fast finding of objects in a large dataset with a property between two given doubles

I have a list of large number of objects of the following form:

public class Point
{
    public double X {get; set;}
    public double Y {get; set;}
    public double Z {get; set;}
    public double DistanceFromStart {get; set;}
}

List<Point> points = GetPointList();

In a given calculation I can narrow down the ones to consider to within a range of DistanceFromStart. So DistanceFromStart is effectively an index. I know I will repeatedly call code similar to this:

points.Where(p => p.DistanceFromStart < lowestDistance &&
 p.DistanceFromStart > highestDistance).someothercals

hundreds of times.

DistanceFromStart is not necessarily unique so not sure how I would use a dictionary and I thought about ToLookup and Lookup but that seems to be for specific values, rather than a range of doubles. What is going to be the most efficient way to use DistanceFromStart in a similar way to an index for best performance?

Upvotes: 1

Views: 116

Answers (2)

Adam Knights
Adam Knights

Reputation: 2151

I went with Ewan's suggestion in the comments to use a dictionary but of the form

Dictionary<double, _LIST_<Point>>

The idea is that when building up the dictionary initially if the DistanceFromStart is already in the dictionary then you add to the point list of that entry. When going through the dictionary to find results you then just handle a list of points rather than a single point.

Tim's answer could well be quicker, however, it would have need much more thought to implement. In this instance using the dictionary that Ewan suggested gave seamless calculations to the end user so the extra complication for any speed improvements associated with Tim's answer were not required.

Upvotes: 0

Tim
Tim

Reputation: 2912

I think using lookup is going to be your best bet. If you need to use it for ranges you could pretty easily add another property that was a distanceFromStart copy with reduced resolution. For example, round to the nearest ten and store based on that value.

So if the distance is 5, maybe it has another index property of 0 that indicates it is in the 0-9 range. Another with a distance of 11 would use 10 because it was 10-19.

Using this technique you should be able to effectively index your results, and by adjusting the sizes of the indexes you should be able to tune the algorithm.

Note that you do not have to actually store the value to use it as the key, however doing so may prove more performent than doing the calculation repeatedly. Again, as always measure before micro-optimizing like that.

Upvotes: 1

Related Questions