Increase speed using only one loop?

Question

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

Answer 1

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).

Answer 2

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