CODEWITHSUNDEEP
c#integerrange
Eli-ne
Eli-ne

Reputation: 11

Checking against a changing set of integer ranges using C#

When filling in a form, the user needs to specify an amount. This amount is then checked against approximately 4 to 6 ranges. The selected range is then saved in the database. The original amount will not be stored (for non-technical reasons). There will be no overlay between the ranges, e.g.:

The tricky part is that these ranges are not fixed in stone. There can be alterations and additional ranges can be added to further specify the '10000 and higher' range. These changes will occur a couple of times and can't be prevented. The old ranges will need to be stored since the specific amount can not be saved to the database.

What would be the most efficient C# data structure for checking against a changing set of ranges?

For my research I included:

Upvotes: 1

Views: 254

Answers (3)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

You can sort low bounds, e.g.

// or decimal instead of double if values are money
double[] lowBounds = new double[] {
      0, // 0th group:  (-Inf ..     0)
   1000, // 1st group:     [0 ..  1000)
   2000, // 2nd group:  [1000 ..  2000)
   5000, // 3d  group:  [2000 ..  5000)
  10000, // 4th group:  [5000 .. 10000)
         // 5th group: [10000 ..  +Inf)
};

and then find the correct group (0-based)

   int index = Array.BinarySearch(lowBounds, value);

   index = index < 0 ? index = -index - 1 : index + 1;

Demo:

  double[] tests = new double[] {
      -10,
        0,
       45,
      999,
     1000,
     1997,
     5123,
    10000,
    20000,
  };

  var result = tests
    .Select(value => {
      int index = Array.BinarySearch(lowBounds, value);

      index = index < 0 ? index = -index - 1 : index + 1;

      return $"{value,6} : {index}";
    });

  Console.Write(string.Join(Environment.NewLine, result));

Outcome:

   -10 : 0
     0 : 1
    45 : 1
   999 : 1
  1000 : 2
  1997 : 2
  5123 : 4
 10000 : 5
 20000 : 5

Upvotes: 1

Fildor
Fildor

Reputation: 16084

Since there are already great answers regarding how to find the correct range, I'd like to address the persistence issue.

What do we have here?

  1. You cannot persist the exact value. ( Not allowed )
  2. Values will be "blurred" by fitting them into a range.
  3. Those ranges can (and will) change over time in bounds and number.

So, what I would probably do would be to persist lower and upper bound explicitly in the db. That way, if ranges change, old data is still correct. You cannot "transform" to the new ranges, because you cannot know if it would be correct. So you need to keep the old values. Any new entries after the change will reflect the new ranges.

One could think of normalization, but honestly, I think that would be overcomplicating the problem. I'd only consider that if the benefit (less storage space) would greatly outweigh the complexity issues.

Upvotes: 0

Matthew Watson
Matthew Watson

Reputation: 109567

A simple approach here is to store the lower band values in an array, and pass it to a FindBand() method which returns an integer representing the index of the band containing the value.

For example:

public static int FindBand(double value, double[] bandLowerValues)
{
    for (int i = 0; i < bandLowerValues.Length; ++i)
        if (value < bandLowerValues[i])
            return Math.Max(0, i-1);

    return bandLowerValues.Length;
}

Test code:

double[] bandLowerValues = {0, 1, 2, 5, 10};

Console.WriteLine(FindBand(-1, bandLowerValues));
Console.WriteLine(FindBand(0, bandLowerValues));
Console.WriteLine(FindBand(0.5, bandLowerValues));
Console.WriteLine(FindBand(1, bandLowerValues));
Console.WriteLine(FindBand(1.5, bandLowerValues));
Console.WriteLine(FindBand(2.5, bandLowerValues));
Console.WriteLine(FindBand(5, bandLowerValues));
Console.WriteLine(FindBand(8, bandLowerValues));
Console.WriteLine(FindBand(9.9, bandLowerValues));
Console.WriteLine(FindBand(10, bandLowerValues));
Console.WriteLine(FindBand(11, bandLowerValues));

This isn't the fastest approach if there are a LOT of bands, but if there are just a few bands this is likely to be sufficiently fast.

(If there were a lot of bands, you could use a binary search to find the appropriate band, but that would be overkill for this in my opinion.)

Upvotes: 1

Related Questions