2

I was wondering which data structure would offer me better performance for my scenario.... My requirements are: Possible Huge DataSet several million of records, I am going to write it only once and I am not going to change it any more during the execution lifetime, I don't need that it is stored in a sorted way.... I was thinking to go with List but if I use a Linq query and in the where condition call InRange performance are very bad... if I do a foreach, performance are not so great.... I am pretty sure that there is a best way to do it ( I was thinking to use a struct and or implement IEquatable but performance are not improving... witch is the quickest data structure in C# for querying in my range with optimal performances? What I want is a data structure to store several million of instances of the class Rnage

class Range
{
    public int Low {get; set;}
    public int High {get; set;}    
    public bool InRange(int val) { return val >= Low && val <= High; }
}

A logic example would be List but I am afraid that List class is not optimized for my requirements... since it is sorted and I don't need sorting and it affect a lot on performances...

thanks for the help!

Conrad Frix
  • 51,984
  • 12
  • 96
  • 155
yamini
  • 41
  • 3
  • What exactly are you trying to achieve? What kind of data is stored in the dataset? And what kind of operations are you doing with the dataset? Also I don't really understand what you're Range class has to do with the question, perhaps you could explain you're code a little more. – Tiddo Jan 13 '12 at 01:22
  • 1
    You should reword your question, it's not very clear what you're trying to do. From what I understand, you have a collection of Range objects, and you want to find the ones for which InRange returns true, right? – Thomas Levesque Jan 13 '12 at 01:23
  • yes Thomas you are correct... I was thinking to use a List to store several millions of Ranges but when it comes to performances, it perform very bad... so I need an other way to store my class (or eventually change it in a struct) more optimized for my requirement: – yamini Jan 13 '12 at 01:44
  • 1
    Is there anything special about the type of data that can help optimize the algorithm? For example, if it was ranges of ages, knowing that the numbers are between 0 and 130 can help. – bryanmac Jan 13 '12 at 02:09
  • unfortunately I cannot think about nothing to optimize it... – yamini Jan 13 '12 at 08:45
  • Low is smaller than High and the operation that I have to do is to check how many times my items are contained in the range... – yamini Jan 13 '12 at 08:46

1 Answers1

1

I think you may want an interval tree. Stackoverflow user alan2here has recently asked several questions regarding a project he's working on; Eric Lippert pointed him towards the interval tree structure in one of them.

Community
  • 1
  • 1
phoog
  • 42,068
  • 6
  • 79
  • 117