Получение и сравнение алгоритмов суммирования максимального суммарного массива

Это упражнение в реализации проблемы с максимальной суммой массива .

Он запрашивает несколько решений сложности:

  • \ $ O (п) \ $
  • \ $ O (n \ log n) \ $
  • \ $ O (N ^ 2) \ $
  • \ $ O (N ^ 3) \ $

Для дополнительной задачи я завершил ее с помощью Python .

import random
import timeit

#random array generator
def generate_array(item_count, lower_bound, upper_bound):
    number_list = []
    for x in range(1, item_count):
        number_list.append(random.randint(lower_bound, upper_bound))
    return number_list


#cubic brute force O(n^3)
def max_subarray_cubic(array):
    maximum = float('-inf')
    for i in range(1, len(array)):
        for j in range(i, len(array)):
            current_sum = 0
            for k in range(i, j):
                current_sum += array[k]
            maximum = max(maximum, current_sum)
    return maximum


#quadratic brute force O(n^2)
def max_subarray_quadratic(array):
  maximum = float('-inf')
  for i in range(0, len(array)):
    current = 0
    for j in range(i, len(array)):
       current += array[j]
       maximum = max(current, maximum)
  return maximum


#divide and conquer O(n*lg(n))
def max_cross_sum(array, low, mid, high):
  left_sum = float('-inf')
  sum_ = 0
  for i in range(mid, low, -1):
    sum_ += array[i]
    left_sum = max(left_sum, sum_)

  right_sum = float('-inf')
  sum_ = 0
  for i in range(mid + 1, high):
    sum_ += array[i]
    right_sum = max(right_sum, sum_)
  return left_sum + right_sum


def max_subarray_div_conquer(array, low, high):
  if low == high:
    return array[low]
  else:
    mid = (low + high) / 2
    return max(max_subarray_div_conquer(array, low, mid), 
               max_subarray_div_conquer(array, mid + 1, high),
               max_cross_sum(array, low, mid, high))


#Kadane's algorithm O(n)
def max_subarray_kadane(array):
    current = maximum = array[0]
    for x in array[1:]:
        current = max(x, current + x)
        maximum = max(maximum, current)
    return maximum

#to facilitate timing each algorithm
def function_timer(function, array, policy):
    start_time = timeit.default_timer()
    if policy == "divide and conquer":
        print("Maximum sub sum for the %s algorithm: %s" 
            % (policy, function(array, 0, len(array) - 1)))
    else:
        print("Maximum sub sum for the %s algorithm: %s" % (policy, function(array)))
    print("Running Time: %s seconds.\n" % (timeit.default_timer() - start_time))



magnitude = input('enter vector size: ')
number_list = generate_array(magnitude, -10, 10)

function_timer(max_subarray_cubic, number_list, "cubic")
function_timer(max_subarray_quadratic, number_list, "quadratic")
function_timer(max_subarray_div_conquer, number_list, "divide and conquer")
function_timer(max_subarray_kadane, number_list, "kadane")

Я бы хотел:

  1. Чтобы узнать, является ли это Pythonic? Я точно следую соглашениям?
  2. Общий обзор точности алгоритмов. Насколько я знаю, я выполнил требования, но на всякий случай. Сосредоточившись на алгоритме разделения и покорения, поскольку он сильно отличается и кубическом решении, на удивление сложно думать о том, как что-то решить плохо.
  3. Обратная связь о том, как я измеряю время работы. Я дал мне средства для запуска тестов, но насколько они эффективны? Насколько надежны результаты?
11 голосов | спросил Legato 24 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 24 Sep 2015 04:15:49 +0300 2015, 04:15:49

3 ответа


11

tl; dr: Это очень хорошо! Несколько ошибок и странных крайних случаев, и вы можете быть более Pythonic - никакой код не идеален, но мне нравится то, что вы сделали.


Является ли это Pythonic?

Есть несколько вещей, которые вы могли бы сделать, чтобы сделать это более Pythonic:

  • Вместо описания функций с использованием комментария выше определения используйте docstring - это предпочтительный способ документировать функции в Python.

  • Вместо того, чтобы перебирать индексы массива, лучше перебирать элементы. Это разница между (плохим):

    for index in range(len(myarray)):
        element = myarray[index]
        do_stuff_with_element()
    

    и (хорошо):

    for element in myarray:
        do_stuff_with_element()
    

    Если вам нужен как индекс, так и элемент, то вы должны использовать перечислить () .

  • Отступ должен состоять из четырех пробелов, а не из двух.

  • Посмотрите на список понятий; они очень полезны. Например, они могут уменьшить вашу функцию generate_array () до одной строки:

    def generate_array(count, lower_bound, upper_bound):
        """
        Generates a random array of integers.
        """
        return [random.randint(lower_bound, upper_bound) for _ in range(count)]
    


Являются ли эти точные реализации алгоритмов?

max_subarray_cubic ()

  • Поскольку все ваши диапазоны начинаются с 1, но индексы Python перечисляются в 0, эта функция, похоже, не включает первый элемент в массиве. Например:

    >>> max_subarray_cubic([1, 2, 3, -100])
    5
    

    , но взятие первых трех элементов дает большую сумму 6. Скорректируйте диапазон до range(len(array)).

max_subarray_quadratic ()

  • Я не заметил в нем никаких ошибок; это, кажется, работает правильно.

  • Как я объяснил выше, вы можете сделать внутренний цикл более Pythonic, итерации по элементам, например:

    for elem in array[i:]:
        current += elem
        maximum = max(current, maximum)
    

max_cross_sum ()

  • В docstring должно быть что-то, чтобы объяснить, как использовать аргументы low /mid /high; Я должен был догадаться, и я думаю, что я ошибся. [Я не понимал, что это была вспомогательная функция для max_subarray_div_conquer, когда я впервые ее прочитал.]

  • Необычно видеть имя переменной с завершающим подчеркиванием в программах Python. Хорошая работа не для переопределения встроенной функции (распространенная ошибка среди новых программистов) , но вы должны попытаться выбрать лучшее имя переменной, а не просто добавить подчеркивание.

  • Когда последний аргумент range () равен -1, я предпочитаю использовать reverse (), потому что, по-моему, его легче читать. Объединившись с моим советом выше, ваш первый цикл будет выглядеть следующим образом:

    for elem in reversed(array[low:mid]):
        sum += elem
        # do stuff with elem
    

max_subarray_div_conquer ()

  • Когда эта функция сначала вызывается, я должен передать длину массива в качестве аргументов, что может вызвать проблему, если я передаю неправильные значения. Я повторяю информацию, предоставленную первым аргументом.

    Было бы лучше проверить, проходит ли пользователь в любых значениях, а если нет, вычислить их на основе длины массива:

    def max_subarray_div_conquer(array, low=None, high=None):
        if low is None:
            low = 0
        if high is None:
            high = len(array)
    

    Я использую аргумент по умолчанию для None, чтобы проверить, что пользователь передал что-либо; если бы они этого не сделали, я сам все поработаю.

max_subarray_kadane ()

  • Если я передаю этой функции пустой список, она попадает в исключение в первой строке:

     Traceback (most recent call last):
      File "tmp/subarrays.py", line 89, in <module>
        function_timer(max_subarray_kadane, [], "kadane")
      File "tmp/subarrays.py", line 76, in function_timer
        print("Maximum sub sum for the %s algorithm: %s" % (policy, function(array)))
      File "tmp/subarrays.py", line 63, in max_subarray_kadane
        current = maximum = array[0]
    IndexError: list index out of range
    

    Вы должны проверить, что я прошел через более чем пустой список в начале этой функции. Вы все равно можете создать исключение - a ValueError кажется здесь уместным - но он должен предоставить более информативное сообщение о том, почему что-то пошло не так.

    Возможно, вам захочется взглянуть на то же самое для остальных ваших функций: хотя они не генерируют исключение, они говорят мне, что максимальная сумма подмассива пустого списка равна -inf. Это кажется разумным? Существует ли значительная сумма субарарей пустого списка?


Как работает функция времени выполнения?

  • Сама функция прекрасна. Тот факт, что у вас есть специальный случай, алгоритм разделения и завоевания немного раздражает, но это можно устранить, устраняя необходимость в дополнительных аргументах - см. Выше.

  • Одна слабость механизма заключается в том, что вы проверяете результаты только один раз и для одного массива. Возможно, вы можете получить массив, который играет в сильные стороны одного алгоритма, или вызов несчастлив и занимает необычно долгое время.

    Вы получите более точные результаты, если (а) вы протестировали с помощью множества массивов, и (б) вы повторили и усреднили результаты.

  • Ваш тестовый код находится на верхнем уровне файла, что означает, что он будет запускаться всякий раз, когда этот файл будет выполнен - ​​как напрямую, так и в качестве скрипта, или импортирован как модуль. Лучше построить этот код внутри if __name__ == '__main__' , что означает, что он будет вызываться только при непосредственном запуске скрипта.

    Это позволяет вам импортировать функции из этого файла без вызова этого временного кода.

ответил alexwlchan 24 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 24 Sep 2015 10:39:09 +0300 2015, 10:39:09
2

Я добавлю пару небольших заметок об общем питоническом стиле, так как alexwlchan так хорошо заменил остальных.

У Python есть списки, а не массивы. Ссылаясь на вещи, поскольку массивы являются слегка запутанными и могут быть истолкованы как означающие, что вы реализуете какой-то другой класс, а не обычный встроенный.

Вам не нужно иметь if else, когда вы возвращаете значение в результате if statement, просто удалите else и продолжайте код, если он еще не вернулся.

def max_subarray_div_conquer(array, low, high):
    if low == high:
        return array[low]

    mid = (low + high) / 2
    return max(max_subarray_div_conquer(array, low, mid), 
               max_subarray_div_conquer(array, mid + 1, high),
               max_cross_sum(array, low, mid, high))

Вместо синтаксиса форматирования синтаксиса вместо % используйте новый format. Он имеет много полезного синтаксиса, поэтому полезно привыкнуть.

print("Running Time: {} seconds.\n".format(timeit.default_timer() - start_time))
ответил SuperBiasedMan 24 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 24 Sep 2015 18:32:59 +0300 2015, 18:32:59
2

После исправления ошибок range:

def max_subarray_cubic(array):
    maximum = float('-inf')
    for i in range(len(array)):
        for j in range(i, len(array)):
            current_sum = 0
            for k in range(i, j+1):
                current_sum += array[k]
            maximum = max(maximum, current_sum)
    return maximum

Это можно улучшить с помощью

  • заменив самый внутренний цикл на sum()
  • устранение повторения вызовов функций max путем включения функции в генератор и применения max над этим

-

def subarray_sums(array):
    for i in range(len(array)):
        for j in range(i, len(array)):
            yield sum(array[i:j+1])

def max_subarray_cubic(array):
    return max(subarray_sums(array))
ответил Janne Karila 24 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 24 Sep 2015 22:04:05 +0300 2015, 22:04:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132