DjangoBB LoFi version

Полная версия: Решение задачи по массивам (МФТИ)

Начало » Python для новичков » Решение задачи по массивам (МФТИ)

1 2 3 4

KEKIs

Июнь 20, 2022 09:00:22

py.user.next
Да, извиняюсь, ерунду написал) ближе к вечеру мозг уже не работает)
Дело было как раз в обратном. Сортировка инплейс осуществлялась не корректно, видимо потому, что в какой-то момент сортировка идет по частично отсортированному массиву

Если мое предположение неверно, прошу поправить. Факт в том, что при замене sort на sorted код работает правильно.

py.user.next

Июнь 20, 2022 12:44:53

KEKIs
Сортировка инплейс осуществлялась не корректно, видимо потому, что в какой-то момент сортировка идет по частично отсортированному массиву

Звучит бредово.

Скинь конечный код.

KEKIs

Июнь 20, 2022 14:36:02

py.user.next
Ну в целом вот тут появляется разница:

 #Способ 1, нерабочий
results = [(0, 3), (0, 10), (2, 3), (2, 2), (2, 4)]
results.sort(key=lambda x: x[1], reverse=True)
results.sort(key=lambda x: sum([k[1] for k in results if k[0] == x[0]]), reverse=True)
print(results) #[(0, 10), (2, 4), (0, 3), (2, 3), (2, 2)]
#Способ 2, рабочий
results = [(0, 3), (0, 10), (2, 3), (2, 2), (2, 4)]
results = sorted(results, key=lambda x: x[1], reverse=True)
results = sorted(results, key=lambda x: sum([k[1] for k in results if k[0] == x[0]]), reverse=True)
print(results) #[(0, 10), (0, 3), (2, 4), (2, 3), (2, 2)]

FishHook

Июнь 20, 2022 15:17:48

 results.sort(key=lambda x: sum([k[1] for k in results if k[0] == x[0]]), reverse=True)

то есть на каждой итерации сортировки вы вызываете функцию, которая каждый вызов создает список и его суммирует? Вы же понимаете, что сортировка имеет временную сложность больше чем O(n)? Один раз пройдите по списку и создайте структуру данных, которую будет удобно сортировать

    
results = [(0, 3), (0, 10), (2, 3), (2, 2), (2, 4)]
d = {}
for i in range(len(results)):
    k, n = results[i]
    if k not in d:
        d[k] = sum(p[1] for p in results if p[0] == k)
    results[i] = (d[k], k, n)
results.sort(key=lambda i: i[0], reverse=True)
results = [(i[1], i[2]) for i in results]
print(results)

KEKIs

Июнь 20, 2022 16:04:15

FishHook
Согласен, до оптимальности тут далеко. Мне самому больно смотреть на код, который я запостил полторы недели назад)
Справедливости ради, мое решение прошло проверку, в т.ч. по времени выполнения, а само задание не предполагает использование словарей.

FishHook

Июнь 20, 2022 16:22:25

KEKIs
Справедливости ради, мое решение прошло проверку

А “проверка” она божественная что-ли? Вы так говорите, будто непогрешимость проверки сомнений не вызывает. Если ваше решение прошло проверку, то очевидно, что это хреновая проверка. Это вообще первое правило алгоритмирования - не допускать повторяющихся операций. СмОтрите в свой код, если видите, что в цикле происходит повторяющийся расчет - переписываете, потому что это плохой код. Проходит он проверку или нет, это не важно, это плохой алгоритм

FishHook

Июнь 20, 2022 16:35:47

хммм, я вот тут бороду почесал и кажется что питон кеширует ключ для каждого элемента
так что может это и не так сильно ускорит как хотелось бы, но все равно ускорит, потому что словарь сократит количество проходов по списку

FishHook

Июнь 20, 2022 16:42:57

KEKIs
сортировка идет по частично отсортированному массиву

тут скорее ошибка в том, что вы обращаетесь к списку во время его изменения
выполните вот этот код, и крайне удивитесь

    
import random
l =list(range(10))
random.shuffle(l)
print(l)
j = 0
def foo(i):
    global j, l
    j += 1
    print(f"{j=}, {l=}")
    return i
l.sort(key=foo)
print(l)

py.user.next

Июнь 20, 2022 18:04:31

KEKIs
Сортировка инплейс осуществлялась не корректно, видимо потому, что в какой-то момент сортировка идет по частично отсортированному массиву

KEKIs
Ну в целом вот тут появляется разница:
  
...
results.sort(key=lambda x: sum([k[1] for k in results if k[0] == x[0]]), reverse=True)
...

В этой строке идёт два одновременных обращения к списку results. Так как метод list.sort() проводит сортировку в самом массиве, переставляя в нём элементы местами для временного хранения элементов, то при обращении к этому же массиву параллельно может происходить повторное обращение к одному и тому же элементу несколько раз. Так что код неправильный в любом случае.
Если же ты заменяешь list.sort() на sorted(), то сначала в sorted() создаётся новый список и элементы из первоначального списка попадают туда на свои места, а параллельный код обращается к неизменному первоначальному списку.

На практике оно так, конечно, не работает

  
>>> lst = [3, 2, 1]
>>> tmp = []
>>> 
>>> lst.sort(key=lambda i: (i, tmp.append([j for j in lst])))
>>> lst
[1, 2, 3]
>>> tmp
[[], [], []]
>>>

  
>>> lst = [3, 2, 1]
>>> tmp = []
>>> 
>>> lst.sort(key=lambda i: (i, tmp.append(str(lst))))
>>> lst
[1, 2, 3]
>>> tmp
['[]', '[]', '[]']
>>>

потому что там что-то происходит секретное.
Здесь видно, что lst вообще не имеет элементов, хотя имена эти видны внутри функции lambda и lambda не говорит, что не знает такого имени lst.

Так что я заменил в твоём нерабочем коде results на пустой список

  
>>> results = [(0, 3), (0, 10), (2, 3), (2, 2), (2, 4)]
>>> results.sort(key=lambda x: x[1], reverse=True)
>>> results.sort(key=lambda x: sum([k[1] for k in [] if k[0] == x[0]]), reverse=True)
>>> results
[(0, 10), (2, 4), (0, 3), (2, 3), (2, 2)]
>>>

получилось то же самое, что и у тебя.

py.user.next

Июнь 20, 2022 18:06:17

KEKIs
а само задание не предполагает использование словарей

Почему не предполагает?