Reputation: 83
Is there a way to rewrite this code using only one loop to increase the speed while the input is very large numbers?
The code is used to count how many integers in a list are greater than all integers to the right of it.
count = 0
for i,x in enumerate(items):
d = True
for y in items[i+1:]:
if x <= y:
d = False
if d:
count = count+1
return count
Upvotes: 1
Views: 55
Reputation: 16515
I timed some options to compare them:
The code from the question:
def f1(item_list):
count = 0
for i, x in enumerate(item_list):
d = True
for y in item_list[i+1:]:
if x <= y:
d = False
if d:
count = count+1
return count
The code from this answer from qwertyman
:
def f2(item_list):
max_elem = None
count = 0
for val in item_list[::-1]:
if max_elem is None or val > max_elem:
max_elem = val
count += 1
return count
My improved version (just used reversed()
instead of [::-1]
):
def f3(item_list):
max_elem = None
count = 0
for val in reversed(item_list):
if max_elem is None or max_elem < val:
max_elem = val
count += 1
return count
The comparison code:
if __name__ == '__main__':
func_list = [f1, f2, f3]
print('{:>8s} {:15s} {:>10s} {:>10s} {:>10s}'.format(
'n', 'items', 'f1', 'f2', 'f3'))
for n in (100, 1000, 5000):
items_1 = [random.randint(1, 1000) for _ in range(n)]
items_2 = list(sorted(items_1))
items_3 = list(sorted(items_1, reverse=True))
for label, items in [
('random', items_1),
('sorted', items_2),
('sorted-reverse', items_3),
]:
# assure that all functions return the same result
assert len(set([func(items) for func in func_list])) == 1
t_list = []
for func in func_list:
t_list.append(
timeit.timeit(
'func(items)',
'from __main__ import func, items',
number=100))
print('{:8d} {:15s} {:10.6f} {:10.6f} {:10.6f}'.format(
n, label, *t_list))
The results (using Python 3.6
on Ubuntu 18.04
):
n items f1 f2 f3
100 random 0.016022 0.000348 0.000370
100 sorted 0.015840 0.000339 0.000326
100 sorted-reverse 0.014122 0.000572 0.000505
1000 random 1.502731 0.003212 0.003077
1000 sorted 1.496299 0.003332 0.003089
1000 sorted-reverse 1.256896 0.005412 0.005196
5000 random 36.812474 0.015695 0.014762
5000 sorted 36.902378 0.015983 0.015067
5000 sorted-reverse 31.218129 0.019741 0.018419
Clearly, the proposal by qwertyman
is orders of magnitude faster than the original code, and it can be sped up a little bit by using reversed()
(obviously, for more speed one could use another language instead of Python).
Upvotes: 2
Reputation: 3038
The current value is larger than all the ones to the right if and only it is larger than the maximum one.
This code implements the above idea by iterating from right to left:
count = 0
max = None
for val in items[::-1]:
if max is None or val > max:
max = val
count += 1
return count
Upvotes: 4