4
\$\begingroup\$

Here is my program to find the largest number(s) in a list of elements, possibly non-unique (in Python):

item_no = [5, 6, 7, 8, 8]
max_no = 0 
for i in item_no:
    if i > max_no:
        max_no = i
        high = [i]
    elif i == max_no:
        high.append(i)

Example input: [5, 6, 7, 8, 8]

Example output: [8, 8]

How can I make this program more effective and shorter?

Any help would be highly appreciated.

This code is based on help received on Stack Overflow.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's pretty much as efficient as it gets. If you sorted the list first and got the last element it would be fewer lines of code, but take more computational resources and be less efficient. \$\endgroup\$ – Slothario May 6 at 17:02
  • 2
    \$\begingroup\$ I have added the [performance] tag, if you mean in big-O time, then please change it to the [complexity] tag. \$\endgroup\$ – Peilonrayz May 6 at 18:21
  • 1
    \$\begingroup\$ @Slothario Please see my answer to see how your assumption that sorting the list "take more computational resources" is incorrect. Unless you mean sorted rather than list.sort. \$\endgroup\$ – Peilonrayz May 6 at 19:33
8
\$\begingroup\$

Note: After posting my answer I found out that the question is a duplicate of this question.

Readability

  1. If you have no values then your code will error when you try to interact with high. You should define high outside the loop.
  2. You should use a function so it's easier to test your code.
  3. You should use full words for variable names.
def largest_orig_pretty(values):
    max_no = 0
    highest = []
    for value in values:
        if value > max_no:
            max_no = value
            highest = [value]
        elif value == max_no:
            highest.append(value)
    return highest

Performance

This however isn't shorter or faster than your code.

When optimizing Python it's almost guaranteed that all C functions are faster than the Python equivalent. And so we can test some changes out:

  • Remove max_no to make your code smaller.
  • Remove max_no and use iter to not incur \$O(n)\$ memory.
  • Try using collections.Counter, in the hopes it's written in C.
  • Use list.sort to sort the input so we can just take the first elements that are the same.

    I did this in multiple ways:

    • Using a for loop. largest_sort.
    • Using a functional/iterator approach, but using lambda. largest_sort_semifunctional.
    • Using a functional/iterator approach, using functools.partial and operator.eq. largest_sort_functional.
  • Using sorted to not mutate the input list. And otherwise using the same code as largest_sort.
  • Using max and build a new list using list.count.

    Most of the answers in the duplicate question derive from this method.

    • Allan's answer is the same as my original one. largest_max_count.
    • Ev.Kounis's answer suggests using a comprehension to build the output list.
    • Daweo's answer suggested not using list.count and instead use a list comprehension. There are two varients one when they use max once and one where it's used on every iteration.
  • Grijesh Chauhan's answer suggested storing only the value and a count, rather than building a list.

I have not tested the output of these functions, only the timings. The sample data is also uniform, and so may not accurately describe the expected timings if this assumption is not true.

Disclaimer, graphtimer was written and is maintained by me. It is only to produce the graph.

import collections
import itertools
import operator
import functools

import matplotlib.pyplot as plt
import numpy as np

from graphtimer import Plotter, MultiTimer


def largest_orig(values):
    max_no = 0
    for i in values:
        if i > max_no:
            max_no = i
            high = [i]
        elif i == max_no:
            high.append(i)
    return high


def largest_orig_pretty(values):
    max_no = 0
    highest = []
    for value in values:
        if value > max_no:
            max_no = value
            highest = [value]
        elif value == max_no:
            highest.append(value)
    return highest


def largest_no_max(values):
    if not values:
        return []
    highest = [values[0]]
    for value in values[1:]:
        if value > highest[0]:
            highest = [value]
        elif value == highest[0]:
            highest.append(value)
    return highest


def largest_no_max_iter(values):
    values = iter(values)
    highest = [next(values)]
    for value in values:
        if value > highest[0]:
            highest = [value]
        elif value == highest[0]:
            highest.append(value)
    return highest


def largest_counter(values):
    if not values:
        return []
    c = collections.Counter(values)
    k = max(c)
    return [k] * c[k]


def largest_sort(values):
    if not values:
        return []
    values.sort(reverse=True)
    value = values[0]
    for i, v in enumerate(values):
        if value != v:
            return [value] * i
    return values


def largest_sort_semifunctional(values):
    if not values:
        return []
    values.sort(reverse=True)
    value = values[0]
    return list(itertools.takewhile(lambda i: i == value, values))


def largest_sort_functional(values):
    if not values:
        return []
    values.sort(reverse=True)
    value = values[0]
    return list(itertools.takewhile(functools.partial(operator.eq, value), values))


def largest_sorted(values):
    if not values:
        return []
    values = sorted(values, reverse=True)
    value = values[0]
    for i, v in enumerate(values):
        if value != v:
            return [value] * i
    return values


# Same as https://stackoverflow.com/a/55216417
def largest_max_count(values):
    if not values:
        return []
    maximum = max(values)
    return [maximum] * values.count(maximum)


# Derived from Ev. Kounis' answer: https://stackoverflow.com/a/55216309
def largest_max_count_comprehension(values):
    if not values:
        return []
    maximum = max(values)
    return [maximum for _ in range(values.count(maximum))]


# Derived from Daweo's answer: https://stackoverflow.com/a/55216401
def largest_max_comprehension(values):
    if not values:
        return []
    return [value for value in values if value == max(values)]


# Derived from Daweo's answer: https://stackoverflow.com/a/55216401
def largest_max_comprehension_once(values):
    if not values:
        return []
    maximum = max(values)
    return [value for value in values if value == maximum]


# Grijesh Chauhan's answer: https://stackoverflow.com/a/55254044
def largest_grijesh_chauhan(iterable):
    max = None
    count = 0
    for index, value in enumerate(iterable):
        if index == 0 or value >= max:
            if value != max:
                count = 0
            max = value
            count += 1
    return count * [max]


def main():
    fig, axs = plt.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    (
        Plotter(MultiTimer([
            largest_orig,
            largest_orig_pretty,
            largest_no_max,
            largest_no_max_iter,
            largest_counter,
            largest_sort,
            largest_sort_semifunctional,
            largest_sort_functional,
            largest_sorted,
            largest_max_count,
        ]))
            .repeat(10, 10, np.logspace(0, 5), args_conv=lambda n: list(np.random.rand(int(n))))
            .min()
            .plot(axs, title='Maximums')
    )
    fig.show()

    fig, axs = plt.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    (
        Plotter(MultiTimer([
            largest_orig_pretty,
            largest_sort,
            largest_max_count,
            largest_max_count_comprehension,
            largest_max_comprehension,
            largest_max_comprehension_once,
            largest_grijesh_chauhan,
        ]))
            .repeat(10, 10, np.logspace(0, 3), args_conv=lambda n: list(np.random.rand(int(n))))
            .min()
            .plot(axs, title='Maximums max count derived')
    )
    fig.show()


if __name__ == '__main__':
    main()

Resulting in the following timings:

Timings of the functions

The following is a comparison of the SO answers:

Comparison of SO answers

Conclusion

  • [Performance] sort is the fastest method when there are ~10 or more elements in the list. Despite the \$O(n\log{n})\$ big-O time complexity it's the fastest as it's written in C.

    It mutates the input which may not be desirable, and using sorted destroys the performance gain.

    Using a plain for loop is faster than itertools.

  • [Performance] Using max and list.count is the fastest method if you are not allowed to mutate the list.
  • [Size] Using max and list.count results in the smallest amount of lines of code.

And so depending on your need I'd use either largest_max_count or largest_sort.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hmm, my answer flying up with input size. Indeed, Cookbook says "The nlargest() and nsmallest() functions are most appropriate if you are trying to find a relatively small number of items. If you are simply trying to find the single smallest or largest item (N=1), it is faster to use min() and max() Similarly, if N is about the same size as the collection itself, it is usually faster to sort it first and take a slice (i.e., use sorted(items)[: N] or sorted(items)[-N:]" ... Thanks for the simulation \$\endgroup\$ – Grijesh Chauhan May 7 at 4:27
  • 1
    \$\begingroup\$ @GrijeshChauhan In case you have misread the graph, your function isn't the worst, but the second worst in the "Maximums SO comparison". For the most part it shouldn't matter what you use, unless you pick Daweo's answer which calls max every iteration. \$\endgroup\$ – Peilonrayz May 7 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.