How can I find the most frequent largest element in list faster?-CodePudding

The task is to find the most frequent largest element in given list

# for example we have list a
a = ['1', '3', '3', '2', '1', '1', '4', '3', '3', '1', '6', '6', '3','6', '6', '6']
a.sort(reverse=True)
print(max(a, key=a.count))

how can I make this simple script work faster?

CodePudding user response：

Why do you sort at all?

You got n*log(n) for sorting which does nothing for you here - you still need to go over complete a for the max(...) statement and for EACH ELEMENT go through the whole list again to count() its occurences - even if all emements are the same.

So for

["a","a","a","a","a"]

this uses 5 passes and counts the whole lists for each wich leads to O(n²) on top of O(n*log(n)) for sorting - asymptomatically this is bound by O(n²).

The basic approach for this kind is to use collections.Counter:

from collections import Counter

a = ['1', '3', '3', '2', '1', '1', '4', '3', '3', '1',
     '6', '6', '3','6', '6', '6']
 
c = Counter(a) 

# "3" and "6" occure 5 times, "3" is first in source so it is 
# reported first - to get the max value of all those that occure
# max_times, see below
print(c.most_common(1))[0][0]

which up to a certain list-size may still be outperformed by list counting - as you remove the need to create a dictionary from your data to begin with - wich also costs time.

For slightly bigger list Counter wins hands down:

from collections import Counter

# larger sample - for short samples list iteration may outperform Counter
data = list('1332114331663666')

# 6 times your data   1 times "6" so "6" occures the most
a1 = [*data, *data, *data, *data, *data, *data, "6"]
a2 = sorted(a1, reverse=True)
c = Counter(a1)

def yours():
    return max(a1, key=a1.count)

def yours_sorted():
    return max(a2, key=a2.count)

def counter():
    c = Counter(a1)
    mx = c.most_common(1)[0][1]  # get maximal count amount
    # get max value for same highest count
    return max(v for v,cnt in c.most_common() if cnt==mx) 

def counter_nc():        
    mx = c.most_common(1)[0][1] # get maximal count amount
    # get max value for same highest count
    return max(v for v,cnt in c.most_common() if cnt==mx) 

import timeit

print("Yours:   ", timeit.timeit(stmt=yours, setup=globals, number=10000))
print("Sorted:  ", timeit.timeit(stmt=yours, setup=globals, number=10000))
print("Counter: ", timeit.timeit(stmt=counter, setup=globals, number=10000))
print("NoCreat: ", timeit.timeit(stmt=counter_nc, setup=globals, number=10000))

gives you (roughly):

Yours:    0.558837399999902
Sorted:   0.557338600001458 # for 10k executions saves 2/1000s == noise
Counter:  0.170493399999031 # 3.1 times faster including counter creation
NoCreat:  0.117090099998677 # 5 times faster no counter creation

Even including the creation of the Counter inside the function its time outperforms the O(n²) approach.

CodePudding user response：

If you use pure python, collections.Counter may be the best choice.

from collections import Counter

counter = Counter(a)
mode = counter.most_common(1)[0][0]

Of course, it is not difficult to realize it by yourself.

counter = {}
counter_get = counter.get
for elem in a:
    counter[elem] = counter_get(elem, 0)   1
mode = max(counter, key=counter_get)   # or key=counter.__getitem__

For large list, using numpy's array may be faster.

import numpy as np

ar = np.array(a, dtype=str)
vals, counts = np.unique(ar, return_counts=True)
mode = vals[counts.argmax()]

EDIT

I'm sorry I didn't notice the 'largest' requirement.

If you choose Counter:

max_count = max(counter.values())
largest_mode = max(val for val, count in counter.items() if count == max_count)

# One step in place, a little faster.
largest_mode = max(zip(counter.values(), counter))[1]

Or numpy:

largest_mode = vals[counts == counts.max()].max()
# even vals[counts == counts.max()][-1]
# because vals is sorted.

CodePudding user response：

A from scratch solution would be something likes this:


elem_dict = dict()

max_key_el = [0,0]
for el in a:
  if el not in elem_dict:
    elem_dict[el] = 1
  else:
    elem_dict[el]  = 1

  if elem_dict[el] >= max_key_el[1]:
     if int(el) > int(max_key_el[0]):
        max_key_el[0] = el
        max_key_el[1] = elem_dict[el] 

print(max_key_el[0])

I use a dictionary elem_dict to store the counters. I store in max_key_el the max [key, value]. In the first if statement I sum the occurrences of the element and in the second if statement I update the max element, while in the last if I compare also the keys.

Using a list with 20000 elements I obtain:

For your solution 3.08 s,
For this solution 16 ms!