Улучшение кода за счет минимизации количества итераций

У меня есть упражнение, которое я выполнил хорошо, но я ищу улучшения.

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

def main(l1):
    newlist = []
    numbers= max(l1) + 1
    for i in range(0,numbers):
        counter = 0
        for number in l1:
            if number >= i:
                counter += 1
        newlist.append(counter)
    print(newlist)

l1=[1,5,4,3,7,8,9]
main(l1)

он возвращает индекс [7, 7, 6, 6, 5, 4, 3, 3, 2, 1] 10 (максимальное значение l1 +1)

цель упражнения - найти максимальное значение в l1, а затем проверить каждое число в диапазоне (0, максимальное число + 1),

сравнивая каждое число в l1 с числом в диапазоне (if (число> = число в диапазоне)) и подсчитайте, во сколько раз число в l1 больше, чем число диапазона.

Надеюсь, это насколько понятно, по коду понятнее

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

awesoon 31.10.2018 12:16

снова сортировка будет иметь внутренний цикл для сортировки

Abdul Waheed 31.10.2018 12:23

Сортировка - O (NlogN), что лучше, чем текущее O (N ^ 2)

awesoon 31.10.2018 12:25

@ Скоро в этом случае вы даже можете перейти к O (N) с сортировкой по голубиной дыре.

Dominique Fortin 04.11.2018 19:15
2
4
103
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Вы можете улучшить время, используя сортировку (как сказал @soon в комментарии).

Отсортируйте список ввода, а затем только цикл по всем числам и проверьте текущую позицию.

Рассмотрим следующий код:

def improvedTime(l):
    l.sort() # this take O(nlogn) when n in the length of l
    cnt = 0
    ans = []
    for i in range(0, l[-1]+1): # last index in the ordered list is the max element
        while (i > l[cnt] and cnt < len(l)): #until you reach bigger element
            cnt = cnt + 1
        ans.append(len(l) - cnt)
    print(ans)

l1 = [1,5,4,3,7,8,9]
l2 = [2,9,7,5,3,8,7]
improvedTime(l1)
improvedTime(l2)

Выход:

[7, 7, 6, 6, 5, 4, 3, 3, 2, 1]
[7, 7, 7, 6, 5, 5, 4, 4, 2, 1]

Сложность равна O (max (n + m, nlogn), когда n - это размер списка, а m - максимальный элемент.

Обратите внимание, что в любом случае вам также нужно выполнить цикл до элемента max - что может быть хуже при вводе [3,7,150000] -> вы также можете немного улучшить это, но мой ответ должен исправить ваш случай.

Это способ, предложенный @LieRyan: (я объясню шаг за шагом)

def a(l):
    ansSize = max(l) +1 # calculate the size of the output array 
    ans = [0] * (ansSize) # init the output array with zeros
    for i in l:
        ans[i] += 1 # count and mark every element from the input array and add to ans array
                    # according our example here ans = [0, 0, 1, 1, 0, 1, 0, 2, 1, 1]
    total = 0 # reset var to calculate accumulate sum
    for i in range(-1, -ansSize -1, -1): #loop the output array from the end to start
        total += ans[i] # save new total by adding all previous with current element (accumulate sum)
        ans[i] = total # set current i-index-position with total

    print(ans) # out put is: [7, 7, 7, 6, 5, 5, 4, 4, 2, 1]

l2 = [2,9,7,5,3,8,7]
a(l2)

Большое спасибо, Дэвид, я даже не мог так думать, не могли бы вы дать какое-нибудь предложение или хороший способ учиться, я только начал Python.

LordNord 31.10.2018 20:32

Я не эксперт по питону - думаю, вы можете найти множество руководств на YouTube. Этот вопрос больше касается алгоритма. Если это вам поможет, отметьте это как принятие

dWinder 31.10.2018 20:40

У меня небольшая проблема, если я помещу список [2,9,7,5,3,8,7], он даст [7, 7, 7, 6, 5, 5, 4, 4, 3, 2], но должно быть [7, 7, 7, 6, 5, 5, 4, 4, 2, 1] Еще раз спасибо :)

LordNord 31.10.2018 20:57

@LordNord Это происходит потому, что у вас дважды 7. Я обновляю ответ, чтобы также поддержать этот случай

dWinder 31.10.2018 21:33

Спасибо за вашу помощь и поддержку, у меня есть тестовый файл проблемы, он все еще дает мне ошибку :( Я даже не знаю, где ошибка. Решение @Lie Ryan отлично работает, НО я не понимаю алгоритм

LordNord 31.10.2018 22:20

@LordNord Я попытался объяснить решение @ Lie Ryan (которое лучше моего) в моем обновленном ответе. Надеюсь, теперь это более понятно

dWinder 31.10.2018 23:22

Вот довольно простое улучшение:

from itertools import accumulate
def one(l1):
    counts = [0] * (max(l1) + 1)
    for n in l1:
        counts[-n - 1] += 1
    return list(accumulate(counts))[::-1]

Эта версия намного сложнее, но все делает всего за два прохода, что, по моему мнению, является минимумом для этой проблемы:

def two(l1):
    counts = []
    for n in l1:
        try:
            counts[n] += 1
        except IndexError:
            counts.extend([0] * (n - len(counts)) + [1])

    total = counts[-1]
    for i in range(-2, -len(counts) - 1, -1):
        total += counts[i]
        counts[i] = total

    return counts

Оба решения - O (n) и амортизированные O (n) соответственно.

Вы можете изменить второе решение, чтобы оно стало O (n), предварительно выделив список, но это придет к компромиссу, так как потребуется три прохода по списку.


Основная идея двух приведенных выше решений заключается в том, что вы сначала выполняете счетная сортировка, а затем выполняете текущая сумма с конца списка.

Большое спасибо! Мне нельзя пользоваться библиотеками, я забыл это заметить. но в любом случае, я должен сначала изучить эти функции, например, попробовать и за исключением того, что вы открываете мне глаза на что-то новое, что я должен изучить

LordNord 31.10.2018 20:29

Другие вопросы по теме