1

I am trying to create a mapping, where we are given an integer n, and also a bunch of intervals that map to random numbers.

e.g. n = 55, and say we have intervals: [1:3]->-2,[4:10]->-3,[11:25]->-4,[26:44]->-5,[45:66]->-6, etc.

Is it possible/how can I create a mapping that is constant time, so that for any given n, I can find the corresponding interval, then the correct mapping to the negative number?

My thoughts are to create a dictionary, with keys as the intervals, and the values as the negative number- however would this be constant time lookup for any given n?

Patrick_Chong
  • 434
  • 2
  • 12
  • what do you know about n? what do you know about the intervals? – Eyal D Nov 14 '21 at 10:35
  • What do you mean by "the correct mapping to the negative number"? You want to take an integer and then lookup the value where the integer is in a range? – Iain Shelvington Nov 14 '21 at 10:35
  • Sorry if I wasn't the clearest, n is an integer that falls inside exactly one of the intervals – Patrick_Chong Nov 14 '21 at 10:37
  • So following the example, if n=27, I want the function to return -5. Is n=2 then I want the function to return -2 – Patrick_Chong Nov 14 '21 at 10:37
  • If `n` is restricted to a finite number of values and it's convenient to store them in memory, then a dict with each value would be constant time lookup. Or if up at 66 you have the mapping above and for n > 66 you have, say, -7. That would also work with a dict by using a default value for any missing keys. A list can achieve all that where you first check that `n < len(list_of_values)` and then fetch by index. If it's not practical to store the whole mapping, then you can use bisect thresholds, but with O(logn) complexity. – Reti43 Nov 14 '21 at 10:39
  • I know the intervals above don't quite work in coding terms either, like [1:3] is meaningless, but I think it is clear what I meant! In my code I would do [I for I in range(1,4)] – Patrick_Chong Nov 14 '21 at 10:39
  • What do you know about the NUMBER of intervals? – Eyal D Nov 14 '21 at 10:41
  • @Reti43 n can be huge 10^5, so storing each number won't be practical- sorry should have mentioned this too! – Patrick_Chong Nov 14 '21 at 10:42
  • @Eyal, the number of intervals will be say around 100 – Patrick_Chong Nov 14 '21 at 10:43
  • @user15877202 you will probably have to loop over the intervals and run a comparison to see if n contained in the interval – Iain Shelvington Nov 14 '21 at 10:44
  • Thanks Lain, that's what I thought. But if the intervals were sorted, is there a faster was to look up then? – Patrick_Chong Nov 14 '21 at 10:45
  • I don't think 10**5 is really that big of a deal. Do you have any memory restrictions? If your intervals are sorted, you can use bisect like I mentioned above. Check [here](https://stackoverflow.com/questions/66762595/efficient-way-to-sort-by-number-thresholds-in-python). – Reti43 Nov 14 '21 at 10:47
  • Even if you define your map with something like `d = {i: -i for i in range(10000)}` so that all numbers are different and you need that many objects in memory, they still don't take up more than [1 MB](https://stackoverflow.com/a/30316760/2243104). – Reti43 Nov 14 '21 at 10:50
  • And a numpy array would be even more memory efficient, assuming the list/array approach is practical. – Reti43 Nov 14 '21 at 10:52
  • Thanks Reti- this does seem to work. I am coding on CodeChef, a competitive website, so conscious about time and space! But this does work so thank you :) – Patrick_Chong Nov 14 '21 at 11:29

2 Answers2

1

(Disclaimer: I'm the maintainer of the portion library)

There's a Python library named portion that explicitly supports this use case. portion has an IntervalDict class that allows you to map intervals with data and that has an API close to the built-in dict.

Based on the provided example:

>>> import portion as P
>>> d = P.IntervalDict()
>>> d[P.closed(1, 3)] = -2
>>> d[P.closed(4, 10)] = -3
>>> d[P.closed(11, 25)] = -4
>>> # ... and so on
>>> d[16]
-4
>>> d[2]
-2
>>> # ... and so on

Lookups are in O(n) where n is the number of distinct values in the mapping (i.e. number of distinct integers in your case). A O(log(n)) implementation is currently in progress (where n is the number of disjoint intervals).

Link to the documentation: https://github.com/AlexandreDecan/portion (look for "Map intervals to data").

Guybrush
  • 2,680
  • 1
  • 10
  • 17
0

A naive solution would be to create an array of size n, and for each index, initialize it with the target value. This is wasteful (for example if n is really big, and you have just one interval). Constructing the array is done in O(n) time, but accessing an array by index is O(1).

EDIT: If the number of given intervals is a constant and not a function of n, then iterating the intervals to find the right one can be done in O(1) time. In this case you don't need any dict or array.

Eyal D
  • 169
  • 1
  • 15