Is there an efficient way to filter the maximum numbers in a list

user_15072704 0
Viewed 122

I'm just curious to know if there is a better way to find all the maximum numbers in a list.

As an example, i have a list of dictionaries. which has a key ("info") with corresponding value of dictionary as shown below. I want to find the maximum numbers ("count") from that list. once the maximum numbers are found, the corresponding "code" for that element has to be determined.

I am able to do it as below, but for a really large list, the execution time will be high.

codes = [{"code": 1, "info": {"status": "running", "count": 4}},
         {"code": 2, "info": {"status": "running", "count": 1}},
         {"code": 3, "info": {"status": "running", "count": 2}},
         {"code": 4, "info": {"status": "running", "count": 4}},
         {"code": 5, "info": {"status": "running", "count": 4}}
         ]
count_max = 0
filtered_codes = []
for i in range(len(codes)):
    if codes[i]['info']['count'] == count_max:
        filtered_codes.append(codes[i]['code'])
    if codes[i]['info']['count'] > count_max:
        filtered_codes.clear()
        filtered_codes.append(codes[i]['code'])
        count_max = codes[i]['info']['count']
print(filtered_codes)

output : [1, 4, 5] #1,4,5 are the code for dictionary with count == 4 (max amongst all the count)

so, is there any better way to do this? may be using like filter, lambda, max ?

Edit : Someone had posted the below code as answer, later got deleted

max_count = max(info["info"]["count"] for info in codes)
filtered_codes = [val["code"] for val in filter(lambda x: x["info"]["count"] == max_count, codes)]

So i ran both the code on a list of length 1000000

The first approach posted by me took : 1.4539954662322998s

Second approach took : 0.4440000057220459s

So is the second approach best solution?

python-3.x
1 Answers

Your code is the most asymptotically efficient way to do this. Also your code is good because it can operate on a stream -- using max and then filter would require multiple passes. The advantage of using these builtins would be readability.

If you really need performance though, you probably want to use a library like numpy or write your code in C.

Updated question: Yeah I mean they are both linear time asymptotically. Which one is faster in the real world depends on which kinds of input you see, as well as cache and interpreter quirks. For example, the second one will definitely be way faster for specific datasets like count = [1,1,1,1,1,1,...,1,2]. The first example would be way faster streaming a 10TiB random input list from a remote service over a slow network. To do a true comparison you would need to define what space of datasets you want to test over.

Is solution 2 the "best" for the input data you generated? Well I mean there are more ways to optimize -- for example you can spin up threads and partition the input list for the filtering once you determine the max. Depends on how far you want to go.

Personally I would prefer to write (and read) the second example. Because it works and is easy to understand. Going even further it's probably more idiomatic to use if rather than filter in a comprehension, i.e.

max_count = max(info["info"]["count"] for info in codes)
filtered_codes = [val["code"] for val in codes if val["info"]["count"] == max_count]

Like I said before though if you actually care about super high performance on large data you obviously don't want to be using pure Python.

user_88873130
Related