4
\$\begingroup\$

I am looking for a more efficient way than bruteforcing my way through in the following problem in python 3.

Problem statement:

Input:

  • An array of n integers, scores, where each score is denoted by scores_j

  • An array of q integers, lowerLimits, where each lowerLimits_i denotes the lowerLimit for score range i.

  • An array of q integers, upperLimits, where each upperLimits_i denotes the upperLimit for score range i.

Output: A function that returns an array of Q integers where the value at each index i denotes the number of integers that are in the inclusive range [lowerLimits_i, upperLimits_i].

Constraints:

  • 1 ≤ n ≤ 1e5
  • 1 ≤ scores_j ≤ 1e9
  • 1 ≤ q ≤ 1e5
  • 1 ≤ lowerLimits_i ≤ upperLimits_i ≤ 1e9

Example: Given scores= [5, 8, 7], lowerLimits = [3, 7], and upperLimits = [9, 7] I want to check how many of the integers are contained in each interval (inclusive). In this examples: intervals are [3,9] and [7,7], and the result would be [3, 1].

My code looks like this:

def check(scores, lowerLimits, upperLimits): res = [] for l, u in zip(lowerLimits, upperLimits): res.append(sum([l <= y <= u for y in scores])) return res if __name__ == "__main__": scores= [5, 8, 7] lowerLimits = [3, 7] upperLimits = [9, 7] print(check(scores, lowerLimits, upperLimits))
\$\endgroup\$
10
  • \$\begingroup\$ This has all hardcoded values. What's your actual problem statement? \$\endgroup\$ Commented Sep 23, 2018 at 10:42
  • \$\begingroup\$ Thanks for the feedback @Mast. I reformulated the question in a more general way. \$\endgroup\$ Commented Sep 23, 2018 at 10:46
  • \$\begingroup\$ Please take a look at the help center. I don't know what you're doing, why you're doing it and what the problem is, but it doesn't look like something we cover here. \$\endgroup\$ Commented Sep 23, 2018 at 10:47
  • \$\begingroup\$ You're not doing anything with N or Q, nor are you asking for them. You're only printing the values for the example provided, not for the real problem. \$\endgroup\$ Commented Sep 23, 2018 at 10:49
  • 1
    \$\begingroup\$ @Graipher You're right. I've cast the first re-open vote, so it should be in the queue now. Thanks! \$\endgroup\$ Commented Sep 24, 2018 at 6:10

1 Answer 1

Reset to default
6
\$\begingroup\$

If you sort your values, you can then make an iterator on the sorted list, forward it to the lower limit, count until the first value is reached that is larger than the upper limit and discard all further values.

The sorting will add \$\mathcal{O}(n\log n)\$ time complexity, but if you have a lot of values larger than (all) your upper bounds, you could get this back.

An implementation using itertools could be:

from itertools import dropwhile, takewhile def graipher(scores, lower, upper): scores = sorted(scores) for l, u in zip(lower, upper): s = iter(scores) yield sum(1 for _ in takewhile(lambda x: x <= u, dropwhile(lambda x: x < l, s)))

Since the scores are now already sorted, you could even use bisect to find the right indices to insert the upper and lower limits. The difference between the two indices will give you the number of values in range:

from bisect import bisect_left, bisect_right def graipher2(scores, lower, upper): scores = sorted(scores) for l, u in zip(lower, upper): yield bisect_right(scores, u) - bisect_left(scores, l)

Both functions are generators. You can just call list() on them to consume them into a list, giving the same result as your code:

if __name__ == "__main__": scores= [5, 8, 7] lowerLimits = [3, 7] upperLimits = [9, 7] print(check(scores, lowerLimits, upperLimits)) print(list(graipher(scores, lowerLimits, upperLimits))) print(list(graipher2(scores, lowerLimits, upperLimits)))

Finally, Python has an official style-guide, PEP8, which recommends using lower_case for variables and functions.

When running your function and my two functions on an input of the maximum defined size for scores and a single pair of limits, I get the following timings:

  • check: 249 ms ± 3.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  • graipher: 77.3 ms ± 950 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
  • graipher2: 53.9 ms ± 772 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

When using a scores of length 10 and the maximum defined size for the lengths of the limits, I get:

  • check: 2.8 s ± 112 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  • graipher: 246 ms ± 2.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  • graipher2: 73.1 ms ± 612 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

And finally, when using the maximum defined size for both scores and the limits, only graipher2 finishes in a reasonable time (I stopped the other ones after a few minutes):

  • graipher2: 247 ms ± 4.94 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

So, to summarize, sort your scores and use bisection.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.