4
\$\begingroup\$

What is the most efficient way to use a look-up table in C# that works like a range? For a given number, I want to increment it by another number.

I have a look-up table like so

1 1
5 6
10 60

So if the number is 1-4, increment them by 1, if the number is 5-9, increment them by 6, if the number is 10 or more, increment them by 60.

Currently, I've got a working solution by doing the following but I was wondering if there's a better way to achieve the same thing?

public int GetNewValue(int input)
{
    var range = "1,1;2,1;3,1;4,1;5,6;6,6;7,6;8,6;9,6;10,60";
    Dictionary<int, int> dic = ParseRanges(range);

    int increment;
    int total;
    
    if (dic.TryGetValue(input, out increment))
    {
        total = input + increment;
    } 
    else 
    {
        dic.TryGetValue(10, out increment);         
        total = input + increment;
    };
    
    return total;
}

private static Dictionary<int, int> ParseRanges(string rangeString)
{
    if (string.IsNullOrWhiteSpace(rangeString))
    {
        return null;
    }

    try
    {
        var newRange = new Dictionary<int, int>();

        var ranges = rangeString.Split(';');

        foreach (var range in ranges)
        {
            var minMax = range.Split(',');

            if (minMax.Length != 2)
            {
                continue;
            }

            newRange.Add(Convert.ToInt16(minMax[0]), Convert.ToInt16(minMax[1]));
        }

        return newRange;

    }
    catch (Exception e)
    {
    }

    return null;
}
}
\$\endgroup\$
2
  • \$\begingroup\$ Are you allow to use other data structure than Dictionary<int, int>? Is it guaranteed that your input data is ordered by first number of the pairs? \$\endgroup\$ Feb 20 at 13:14
  • 1
    \$\begingroup\$ Yes and yes. The input data doesn't have to be in this format "1,1;2,1;3,1;4,1;5,6;6,6;7,6;8,6;9,6;10,60" but that's what I went with for the given scenario. \$\endgroup\$
    – Bhav
    Feb 20 at 13:25

3 Answers 3

6
\$\begingroup\$

Since you have consecutive numbers as input starting at 1, storing the increments in an array where the array index is the input will be faster than a dictionary.

//                          index  =  0  1  2  3  4  5  6  7  8  9  10
private readonly int[] _increments = [0, 1, 1, 1, 1, 6, 6, 6, 6, 6, 60];

public int GetNewValue(int input)
{
    if (input < 1) throw new ArgumentOutOfRangeException("Must be > 0", nameof(input));
    // OR, alternatively:
    // if (input < 1) return input;   // I.e., add increment 0

    int increment = input >= _increments.Length
        ? _increments[^1]
        : _increments[input];
    return input + increment;
}

Since array indexes are 0-based, we add a dummy entry 0 to the array.

_increments[^1] is equivalent to _increments[_increments.Length - 1].

Both, the dictionary and the array have an O(1) access time; however, dictionary operations have quite and overhead associated with them.


If you want to create an increment array from a string, I suggest using your original (non-expanded) representation like "1 1;5 6;10 60" and to use the following method to expand the ranges into an array:

private static int[] ExpandRanges(string rangeString)
{
    string[] parts = rangeString.Split([' ', ';']);
    if (parts.Length % 2 != 0) {
        throw new ArgumentException("Must contain an even number of integers", nameof(rangeString));
    }
    var numbers = parts
        .Select(s => Int32.Parse(s))
        .ToList();
    int lastRangeStart = numbers[^2]; // Used to calculate the array length
    int[] expanded = new int[lastRangeStart + 1];

    // Range and increments alternate in the numbers list.
    // Therefore, we step by 2 (i += 2)
    for (int i = 0; i < numbers.Count - 1; i += 2) {
        int rangeMin = numbers[i];
        int rangeMax = i < numbers.Count - 3 ? numbers[i + 2] - 1 : rangeMin;
        int increment = numbers[i + 1];
        for (int j = rangeMin; j <= rangeMax; j++) {
            expanded[j] = increment;
        }
    }
    return expanded;
}

Note that like in the first example, I would store the array in a field and create it once instead of repeating this at each call of GetNewValue.


The increments could also be expanded from tuples of range/increment-pairs:

private static int[] ExpandRanges(params (int range, int increment)[] ranges)
{
    int lastRangeStart = ranges[^1].range;
    int[] expanded = new int[lastRangeStart + 1];
    for (int i = 0; i < ranges.Length; i++) {
        var (rangeMin, increment) = ranges[i];
        int rangeMax = i < ranges.Length - 1 ? ranges[i + 1].range - 1 : rangeMin;
        for (int j = rangeMin; j <= rangeMax; j++) {
            expanded[j] = increment;
        }
    }
    return expanded;
}

like this:

private readonly int[] _increments = ExpandRanges((1, 1), (5, 6), (10, 60));
\$\endgroup\$
4
  • 2
    \$\begingroup\$ The OP's version treats inputs less than 1 as if they were 10. I guess you're assuming that was a bug? You should maybe mention that in text or at least a comment in the code. The OP's problem statement in words implies that nothing should be added to inputs < 1 (since it doesn't fall into any of the cases for something being added), which isn't what their code does, so yeah maybe we can assume (or assert) that doesn't happen. \$\endgroup\$ Feb 21 at 3:20
  • \$\begingroup\$ @PeterCordes: I followed what the OP states in the text and didn't look at what the code does exactly. The OP says: "So if the number is 1-4, increment them by 1, if the number is 5-9, increment them by 6, if the number is 10 or more, increment them by 60." and doesn't mention values less than 1. \$\endgroup\$ Feb 21 at 14:40
  • \$\begingroup\$ @PeterCordes: If the input is not in the domain of definition it is probably better to throw an exception. If inputs < 1 are okay adding 0 (or something else) will be better. We need a specification in order to decide. \$\endgroup\$ Feb 21 at 14:49
  • 1
    \$\begingroup\$ Exactly: in the description in words, none of the if conditions are true so no increment should happen (for integers that's the same as adding 0). But since that's not what their code does, a more complete / explicit spec is necessary. \$\endgroup\$ Feb 21 at 16:25
8
\$\begingroup\$

What is the most efficient way to use a look-up table in C# that works like a range?

You asked for the "most efficient" without saying what "efficiency" means. Efficiency is work divided by cost, so in order to answer the question we need to know how you measure work and cost.

You've proposed a "toy problem" -- two ranges bounded below by 1 and above by 10, and "everything else". This is an utterly trivial problem, so any solution will certainly be "efficient enough". You will run into unacceptable inefficiencies when the problem ceases to be a toy problem:

  • Suppose you have two bounded ranges, 1-1234567, 1234568-9999998. I hope you would not dream of making a 9999999-element array and filling it in with ones and sixes. That would not be memory-efficient.

  • Suppose you have a million ranges. I hope you would not use Peter Csala's solution of making a sequence of ranges and then doing a linear search on it. That would not be time-efficient.

To solve this problem efficiently in both time and memory at scale you need a better algorithm. Here are some thoughts:

Number your ranges 0, 1, 2, 3, ... n and create a dictionary from range number to increment. This reduces the problem to "given a query value, what is the number of the range the query falls into?". Now attack that problem.

If you have an n-element list that has the first value of every range then binary-searching that array using the standard binary search implementation that comes with the base class library solves your problem. (If the search item is in the list then you get the index; if not, you get the bitwise complement of the next larger index. From this information you can compute the index you need.)

This reduces the asymptotic complexity of the solution from O(n) to O(lg n), which is probably good enough. But you didn't ask for good enough, you asked for MOST EFFICIENT. (Perhaps now you see why asking for "most efficient" is a bad idea. You don't need most efficient. You need good enough.)

Suppose O(lg n) was not efficient enough. How could we do better? It depends on the specific ranges and the statistical distribution of queries. Suppose the distribution of queries is uniform across all possible values, which seems like a plausible prior. What does this imply for some pathological cases?

Suppose the ranges are 1-2, 3-4, 5-6, .... 999-1000, 1001-2000. We have 500 ranges, but if the queries are uniformly distributed from 1-2000 then 50% of the queries will need to find the last element in your list of ranges, which is the worst case for binary search. How can we make this more efficient?

If you know ahead of time what the query likelihood is for each range then instead of building an array and binary searching it, instead build a binary search tree of ranges, and then run a balanced tree optimization algorithm on it to move the likely ranges towards the root and the unlikely ranges towards the leaves while maintaining a balance property to ensure worst case continues to be O(lg n). You can do this ahead of time; there's a quadratic algorithm for generating the optimal tree. Do a web search for optimal binary search trees and you'll find it.

If you don't know the query distribution ahead of time, or it changes dynamically, then you'll want to go with a self-tuning solution such as a splay tree. Dynamically alter the tree so that it becomes more optimal for common searches; again, remember that you need to maintain a balance property.

You can obtain dramatically better results than O(lg n) for average searches using these techniques while still using O(n) memory for the tables.

\$\endgroup\$
3
  • \$\begingroup\$ so any solution will certainly be "efficient enough" - Depends how fast you're hoping to go for that special case. e.g. you could vectorize it with SIMD, such as x86 Sse2.CompareGreaterThan (learn.microsoft.com/en-us/dotnet/api/…) and Sse2.Add to count how many thresholds it was greater than, or that were greater than it. Then use that as an index for a shuffle like vpermilps (which uses 32-bit indices so is more convenient than pshufb). With AVX2, you could process 8 ints per maybe 2 clock cycles. \$\endgroup\$ Feb 21 at 2:46
  • \$\begingroup\$ Scalar code with a lookup table goes at best 1 int per clock cycle, maybe a bit faster on Alder Lake (3 loads + 2 stores per cycle, so with some loop unrolling maybe more than 1 iteration of work can get through the 6-wide pipeline per cycle). That's unimpressive vs. SIMD speeds for data hot in L1d or L2 cache where you actually can go much faster without hitting bandwidth bottlenecks. \$\endgroup\$ Feb 21 at 2:50
  • \$\begingroup\$ We don't know which problem the OP is trying to solve. Therefore, this might be a XY problem. The ideal case would be to have a math formula for the increment with an O(1) time complexity and which would require no memory. \$\endgroup\$ Feb 21 at 15:01
2
\$\begingroup\$

With Linq it is straightforward to achieve the desired goal:

Parsing the input

var rawImplicitRules ="1,1;5,6;10,60";

var parsedImplicitRules = rawImplicitRules.Split(";")
    .Select(item => { 
        var pair = item.Split(","); 
        return (rangeBound: int.Parse(pair[0]), increment: int.Parse(pair[1])); 
    });
  1. Split the input by semicolons
  2. Split the previously split inputs by colons
  3. Create a named ValueTuple for the converted values

The entire solution assumed that the input data is in the right format.

[
   (1, 1)
   ,
   (5, 6)
   ,
   (10, 60)
]

Adding one more rule

var extendedImplicitRules = parsedImplicitRules
    .Union([(rangeBound: int.MaxValue, increment: parsedImplicitRules.Last().increment)]);
  1. Add one more rule (Union) about the last range
[
   (1, 1)
   ,
   (5, 6)
   ,
   (10, 60)
   ,
   (2147483647, 60)
]

Creating the rules

var rules = extendedImplicitRules
    .Zip(extendedImplicitRules.Skip(1), 
         (lower, upper) => (lowerBound: lower.rangeBound, upperBound: upper.rangeBound, increment: lower.increment))
    .ToList();
  1. Self-join (Zip) the parsed input by shifting one of the sequence with one (Skip)
  2. Create the appropriate data structure which includes both lower and upper bounds
[
   (1, 5, 1)
   ,
   (5, 10, 6)
   ,
   (10, 2147483647, 60)
]

Finding the right increment

var incrementBy = rules
    .First(r => r.lowerBound <= number && r.upperBound >= number)
    .increment;

Please make sure that you calculate the rules only once not at every method call.

Here you can find a dotnet fiddle to play with the solution: https://dotnetfiddle.net/2BkjBl

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.