4

Edit: Due to errors in my code i updated with my oldest, but working code

I get a list of speed recordings from a database, and I want to find the max speed in that list. Sounds easy enough, but I got some requirements for any max speed to count:

If the max speed is over a certain level, it has to have more than a certain number of records to be recognized as maximum speed. The reason for this logic is that I want the max speed under normal conditions, not just an error or one time occurrence. I also have a constraint that a speed has to be over a certain limit to be counted, for the same reason.

Here is the example on a speed array:

v = [8.0, 1.3, 0.7, 0.8, 0.9, 1.1, 14.9, 14.0, 14.1, 14.2, 14.3, 13.8, 13.9, 13.7, 13.6, 13.5, 13.4, 15.7, 15.8, 15.0, 15.3, 15.4, 15.5, 15.6, 15.2, 12.8, 12.7, 12.6, 8.7, 8.8, 8.6, 9.0, 8.5, 8.4, 8.3, 0.1, 0.0, 16.4, 16.5, 16.7, 16.8, 17.0, 17.1, 17.8, 17.7, 17.6, 17.4, 17.5, 17.3, 17.9, 18.2, 18.3, 18.1, 18.0, 18.4, 18.5, 18.6, 19.0, 19.1, 18.9, 19.2, 19.3, 19.9, 20.1, 19.8, 20.0, 19.7, 19.6, 19.5, 20.2, 20.3, 18.7, 18.8, 17.2, 16.9, 11.5, 11.2, 11.3, 11.4, 7.1, 12.9, 14.4, 13.1, 13.2, 12.5, 12.1, 12.2, 13.0, 0.2, 3.6, 7.4, 4.6, 4.5, 4.3, 4.0, 9.4, 9.6, 9.7, 5.8, 5.7, 7.3, 2.1, 0.4, 0.3, 16.1, 11.9, 12.0, 11.7, 11.8, 10.0, 10.1, 9.8, 15.1, 14.7, 14.8, 10.2, 10.3, 1.2, 9.9, 1.9, 3.4, 14.6, 0.6, 5.1, 5.2, 7.5, 19.4, 10.7, 10.8, 10.9, 0.5, 16.3, 16.2, 16.0, 16.6, 12.4, 11.0, 1.7, 1.6, 2.4, 11.6, 3.9, 3.8, 14.5, 11.1]

This is my code to find what I define as the true maximum speed:

from collections import Counter
while max(speeds)>30:
    speeds.remove(max(speeds))
nwsp = []
for s in speeds:
    nwsp.append(np.floor(s))
count = Counter(nwsp)
while speeds and max(speeds)>14 and count[np.floor(max(speeds))]<10:
    speeds.remove(max(speeds))
while speeds and max(speeds)<5:
    speeds.remove(max(speeds))
if speeds:
    print max(speeds)
    return max(speeds)
else:
    return False

Result with v as shown over: 19.9

The reason that i make the nwsp is that it doesn't matter for me if f.ex 19.6 is only found 9 times - if any number inside the same integer, f.ex 19.7 is found 3 times as well, then 19.6 will be valid.

How can I rewrite/optimize this code so the selection process is quicker? I already removed the max(speeds) and instead sorted the list and referenced the largest element using speeds[-1].

Sorry for not adding any unit to my speeds.

11
  • 1
    'while speeds is list', this line is incorrect. Assuming you are testing for whether speeds still has members, the correct way would be, 'while speeds'. 'speeds is list' will always return False.
    – Totem
    Apr 28, 2015 at 18:34
  • 1
    Also, 'speeds.remove(len(speeds)-1)' will remove whatever the value of len(speeds)-1 is from speeds, and not whatever happens to be at speeds[len(speeds)-1]. Sorry if you knew that.
    – Totem
    Apr 28, 2015 at 18:38
  • 1
    what is the correct answer for what you have provided? speeds.remove(len(speeds)-1) nor speeds[len(speeds)-1]. is going to work with your current code Apr 28, 2015 at 18:49
  • 1
    @bjornasm, yes that is what I used locally, what is the correct answer for your list v? Apr 28, 2015 at 18:54
  • 1
    @bjornasm At you interactive python interpreter, try typing '[1,2,3,4,5] is list' see what happens, you get False. That condition still needs to go
    – Totem
    Apr 28, 2015 at 18:59

3 Answers 3

2

Your code is just slow because you call max and remove over and over and over again and each of those calls costs time proportional to the length of the list. Any reasonable solution will be much faster.

If you know that False can't happen, then this suffices:

speeds = [8.0, 1.3, 0.7, 0.8, 0.9, 1.1, 14.9, 14.0, 14.1, 14.2, 14.3, 13.8, 13.9, 13.7, 13.6, 13.5, 13.4, 15.7, 15.8, 15.0, 15.3, 15.4, 15.5, 15.6, 15.2, 12.8, 12.7, 12.6, 8.7, 8.8, 8.6, 9.0, 8.5, 8.4, 8.3, 0.1, 0.0, 16.4, 16.5, 16.7, 16.8, 17.0, 17.1, 17.8, 17.7, 17.6, 17.4, 17.5, 17.3, 17.9, 18.2, 18.3, 18.1, 18.0, 18.4, 18.5, 18.6, 19.0, 19.1, 18.9, 19.2, 19.3, 19.9, 20.1, 19.8, 20.0, 19.7, 19.6, 19.5, 20.2, 20.3, 18.7, 18.8, 17.2, 16.9, 11.5, 11.2, 11.3, 11.4, 7.1, 12.9, 14.4, 13.1, 13.2, 12.5, 12.1, 12.2, 13.0, 0.2, 3.6, 7.4, 4.6, 4.5, 4.3, 4.0, 9.4, 9.6, 9.7, 5.8, 5.7, 7.3, 2.1, 0.4, 0.3, 16.1, 11.9, 12.0, 11.7, 11.8, 10.0, 10.1, 9.8, 15.1, 14.7, 14.8, 10.2, 10.3, 1.2, 9.9, 1.9, 3.4, 14.6, 0.6, 5.1, 5.2, 7.5, 19.4, 10.7, 10.8, 10.9, 0.5, 16.3, 16.2, 16.0, 16.6, 12.4, 11.0, 1.7, 1.6, 2.4, 11.6, 3.9, 3.8, 14.5, 11.1]

from collections import Counter
count = Counter(map(int, speeds))
print max(s for s in speeds
          if 5 <= s <= 30 and (s <= 14 or count[int(s)] >= 10))

If the False case can happen, this would be one way:

speeds = [8.0, 1.3, 0.7, 0.8, 0.9, 1.1, 14.9, 14.0, 14.1, 14.2, 14.3, 13.8, 13.9, 13.7, 13.6, 13.5, 13.4, 15.7, 15.8, 15.0, 15.3, 15.4, 15.5, 15.6, 15.2, 12.8, 12.7, 12.6, 8.7, 8.8, 8.6, 9.0, 8.5, 8.4, 8.3, 0.1, 0.0, 16.4, 16.5, 16.7, 16.8, 17.0, 17.1, 17.8, 17.7, 17.6, 17.4, 17.5, 17.3, 17.9, 18.2, 18.3, 18.1, 18.0, 18.4, 18.5, 18.6, 19.0, 19.1, 18.9, 19.2, 19.3, 19.9, 20.1, 19.8, 20.0, 19.7, 19.6, 19.5, 20.2, 20.3, 18.7, 18.8, 17.2, 16.9, 11.5, 11.2, 11.3, 11.4, 7.1, 12.9, 14.4, 13.1, 13.2, 12.5, 12.1, 12.2, 13.0, 0.2, 3.6, 7.4, 4.6, 4.5, 4.3, 4.0, 9.4, 9.6, 9.7, 5.8, 5.7, 7.3, 2.1, 0.4, 0.3, 16.1, 11.9, 12.0, 11.7, 11.8, 10.0, 10.1, 9.8, 15.1, 14.7, 14.8, 10.2, 10.3, 1.2, 9.9, 1.9, 3.4, 14.6, 0.6, 5.1, 5.2, 7.5, 19.4, 10.7, 10.8, 10.9, 0.5, 16.3, 16.2, 16.0, 16.6, 12.4, 11.0, 1.7, 1.6, 2.4, 11.6, 3.9, 3.8, 14.5, 11.1]

from collections import Counter
count = Counter(map(int, speeds))
valids = [s for s in speeds
         if 5 <= s <= 30 and (s <= 14 or count[int(s)] >= 10)]
print max(valids) if valids else False

Or sort and use next, which can take your False as default:

speeds = [8.0, 1.3, 0.7, 0.8, 0.9, 1.1, 14.9, 14.0, 14.1, 14.2, 14.3, 13.8, 13.9, 13.7, 13.6, 13.5, 13.4, 15.7, 15.8, 15.0, 15.3, 15.4, 15.5, 15.6, 15.2, 12.8, 12.7, 12.6, 8.7, 8.8, 8.6, 9.0, 8.5, 8.4, 8.3, 0.1, 0.0, 16.4, 16.5, 16.7, 16.8, 17.0, 17.1, 17.8, 17.7, 17.6, 17.4, 17.5, 17.3, 17.9, 18.2, 18.3, 18.1, 18.0, 18.4, 18.5, 18.6, 19.0, 19.1, 18.9, 19.2, 19.3, 19.9, 20.1, 19.8, 20.0, 19.7, 19.6, 19.5, 20.2, 20.3, 18.7, 18.8, 17.2, 16.9, 11.5, 11.2, 11.3, 11.4, 7.1, 12.9, 14.4, 13.1, 13.2, 12.5, 12.1, 12.2, 13.0, 0.2, 3.6, 7.4, 4.6, 4.5, 4.3, 4.0, 9.4, 9.6, 9.7, 5.8, 5.7, 7.3, 2.1, 0.4, 0.3, 16.1, 11.9, 12.0, 11.7, 11.8, 10.0, 10.1, 9.8, 15.1, 14.7, 14.8, 10.2, 10.3, 1.2, 9.9, 1.9, 3.4, 14.6, 0.6, 5.1, 5.2, 7.5, 19.4, 10.7, 10.8, 10.9, 0.5, 16.3, 16.2, 16.0, 16.6, 12.4, 11.0, 1.7, 1.6, 2.4, 11.6, 3.9, 3.8, 14.5, 11.1]

count = Counter(map(int, speeds))
print next((s for s in reversed(sorted(speeds))
            if 5 <= s <= 30 and (s <= 14 or count[int(s)] >= 10)),
           False)

Instead of Counter, you could also use groupby:

speeds = [8.0, 1.3, 0.7, 0.8, 0.9, 1.1, 14.9, 14.0, 14.1, 14.2, 14.3, 13.8, 13.9, 13.7, 13.6, 13.5, 13.4, 15.7, 15.8, 15.0, 15.3, 15.4, 15.5, 15.6, 15.2, 12.8, 12.7, 12.6, 8.7, 8.8, 8.6, 9.0, 8.5, 8.4, 8.3, 0.1, 0.0, 16.4, 16.5, 16.7, 16.8, 17.0, 17.1, 17.8, 17.7, 17.6, 17.4, 17.5, 17.3, 17.9, 18.2, 18.3, 18.1, 18.0, 18.4, 18.5, 18.6, 19.0, 19.1, 18.9, 19.2, 19.3, 19.9, 20.1, 19.8, 20.0, 19.7, 19.6, 19.5, 20.2, 20.3, 18.7, 18.8, 17.2, 16.9, 11.5, 11.2, 11.3, 11.4, 7.1, 12.9, 14.4, 13.1, 13.2, 12.5, 12.1, 12.2, 13.0, 0.2, 3.6, 7.4, 4.6, 4.5, 4.3, 4.0, 9.4, 9.6, 9.7, 5.8, 5.7, 7.3, 2.1, 0.4, 0.3, 16.1, 11.9, 12.0, 11.7, 11.8, 10.0, 10.1, 9.8, 15.1, 14.7, 14.8, 10.2, 10.3, 1.2, 9.9, 1.9, 3.4, 14.6, 0.6, 5.1, 5.2, 7.5, 19.4, 10.7, 10.8, 10.9, 0.5, 16.3, 16.2, 16.0, 16.6, 12.4, 11.0, 1.7, 1.6, 2.4, 11.6, 3.9, 3.8, 14.5, 11.1]

from itertools import *
groups = (list(group) for _, group in groupby(reversed(sorted(speeds)), int))
print next((s[0] for s in groups
            if 5 <= s[0] <= 30 and (s[0] <= 14 or len(s) >= 10)),
           False)

Just in case all of these look odd to you, here's one close to your original. Just looking at the speeds from fastest to slowest and returning the first that matches the requirements:

def f(speeds):
    count = Counter(map(int, speeds))
    for speed in reversed(sorted(speeds)):
        if 5 <= speed <= 30 and (speed <= 14 or count[int(speed)] >= 10):
            return speed
    return False

Btw, your definition of "the true maximum speed" seems rather odd to me. How about just looking at a certain percentile? Maybe like this:

print sorted(speeds)[len(speeds) * 9 // 10]
1

I'm not sure if this is faster, but it is shorter, and I think it achieves your requirements. It uses Counter.

from collections import Counter
import math

def valid(item):
  speed,count = item
  return speed <= 30 and (speed <= 13 or count >= 10)

speeds = [4,3,1,3,4,5,6,7,14,16,18,19,20,34,5,4,3,2,12,58,14,14,14]

speeds = map(math.floor,speeds)
counts = Counter(speeds)
max_valid_speed = max(filter(valid,counts.items()))

Result: max_valid_speed == (12,1)

5
  • 1
    Thanks, didn't know about Counter yet.
    – user2124834
    Apr 28, 2015 at 18:58
  • Thank you for our answer @Marein , I am sorry for not providing you with additional info - if f.ex 12.3 is recorded 9 times and 12.5 is recorded 1 time I still think of 12.5 as the max speed.
    – bjornasm
    Apr 28, 2015 at 19:20
  • 1
    I've now added flooring to account for that.
    – user2124834
    Apr 28, 2015 at 19:45
  • 1
    I agree on your first point (returning the original value), but I feel my condition is correct. It says, an item is valid if the speed is less than or equal to 30, and if it is over 13, its count needs to be over 10. Is that not the requirement?
    – user2124834
    Apr 28, 2015 at 19:52
  • 1
    The acknowledged flooring issue aside, they return the same.
    – user2124834
    Apr 28, 2015 at 19:55
1

Using your sort idea we can start at the end of the list at the numbers less than 30, returning on the first number that matched the criteria or returning False:

from collections import Counter

def f(speeds):
    # get speeds that satisfy the range
    rev = [speed for speed in speeds if 5 <= speed < 30]
    rev.sort(reverse=True)
    c = Counter((int(v) for v in rev))
    for speed in rev:
        # will hit highest numbers first
        # so return first that matches
        if speed > 14 and c[int(speed)] > 9 or speed < 15:
            return speed
    # we did not find any speed that matched our requirement
    return False

Output for your list v:

In [70]: f(v)
Out[70]: 19.9

Without sorting you could use a dict, depending on your what your data is like will decide which is best, it will work for all cases including an empty list:

 def f_dict(speeds):
    d = defaultdict(lambda: defaultdict(lambda: 0, {}))
    for speed in speeds:
        key = int(speed)
        d[key]["count"] += 1
        if speed > d[key]["speed"]:
            d[key]["speed"] = speed
    filt = max(filter(lambda x: (15 <= x[0] < 30 and
                                 x[1]["count"] > 9 or x[0] < 15), d.items()), default=False)
    return filt[1]["speed"] if filt else False

Output:

In [95]: f_dict(v)
Out[95]: 19.9

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.