2
\$\begingroup\$

This is an algorithm to find the item with the minimal value in a sequence. I've written a function called minimal to implement this algorithm.

Here is my script:

def minimal(*args):
    """Returns the item with the minimal value in a sequence. """
    if len(args) == 1:
        sequence = args[0]
    else:    
        sequence = args

    index = 0
    successor = index + 1

    while successor < len(sequence):
        if sequence[index] > sequence[successor]:
            index = successor 
        successor += 1

    return sequence[index]
\$\endgroup\$
  • 1
    \$\begingroup\$ What's wrong with min? Or did you do it for the fun of it? In that case add the tag reinventing-the-wheel \$\endgroup\$ – Graipher Aug 25 '16 at 18:55
  • \$\begingroup\$ Oh! I didn't know of that tag. I know min, I'm just practicing for fun! \$\endgroup\$ – Mahmood Muhammad Nageeb Aug 25 '16 at 18:58
4
\$\begingroup\$

Redundant use of indexing

Since you only need value, not index, you could store current minimal value instead of its index. This would allow for for loop, like

for item in sequence:
    if item < current_minimum:
        current_minimum = item

You both ditch overhead for array access, for tracking the index and - most important - code looks cleaner. (although that's subjective)

No support for generators

Generators provide items one at a time, instead of wasting memory on all of them at once. Your code would force generation of all items before first of them is processed. This is not really good.

Well, if you don't use indexing then you don't need len and generators would work just fine, your if len(args) == 1: clause is good in this regard.

Confusing behaviour with single argument

However, special treatment for a lone argument is not obvious from signature, that's not really good. If one does not know about this behaviour, one can easily use stuff like min_element = minimal(*some_list) which would generally work but will do an unexpected thing if some_list had only one element.

Yes, it seems extremely useful, but also confusing. Maybe limiting to one argument only and expecting users to do stuff like minimal((1,2))? I'm really not sure. It seems useful enough that built-in min works like that, but generally speaking decisions like this should not be taken lightly.

Also, take a closer look at what min does - there's also an option of using a key function and providing default value.

\$\endgroup\$
  • \$\begingroup\$ Thank you! I've, just, implemented that! It's much better. \$\endgroup\$ – Mahmood Muhammad Nageeb Aug 25 '16 at 19:23
  • \$\begingroup\$ It's also important to set current_minimum to sequence[0], and you can also splice the list to ignore the first element on the first recursion. \$\endgroup\$ – Joshua Klein Aug 25 '16 at 21:57
0
\$\begingroup\$

Here are five different ways to find the min

from functools import reduce

#Min
def find_min1(iterable_obj):
    return min(iterable_obj)

#Iteration
def find_min2(iterable_obj):
    current_minimum = iterable_obj[0]
    for item in iterable_obj[1:]:
        if item < current_minimum:
            current_minimum = item
    return current_minimum

#Reduce
def find_min3(iterable_obj):
    return reduce(lambda x, y: x if x<y else y, iterable_obj)

#Sorted
def find_min4(iterable_obj):
    return sorted(iterable_obj)[0]

#Recursion
def find_min5(iterable_obj):
    if(len(iterable_obj) == 1):
        return iterable_obj[0]
    else:
        return min(iterable_obj[0],find_min4(iterable_obj[1:]))

Listen in approximate speed order based on profiling by cProfile Recursion crashed before list size 10,000. Build in was usually fastest, but all were within ~.001 seconds except for recursion which quickly tanked due to system overhead function calls.

\$\endgroup\$
  • 1
    \$\begingroup\$ In resursive solution, you are calling find_min4 - sorted one. Is it a typo? (also, there are actually 2 ways to do it recursively - right fold and left fold - but both are not really suitable for Python) \$\endgroup\$ – Daerdemandt Aug 26 '16 at 0:49

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.