Comments 33
Заметим важную вещь: Максимальное произведение двух чисел в массиве — это
либо произведение двух самых больших чисел
либо произведение двух самых маленьких (т.е. самых отрицательных) чисел
А вот это бы хорошо доказать. На первый взгляд это не очевидно. При чем, раз уж вы тут людей учите, надо привести рассуждения, как до этого додуматься вообще.
А вот это бы хорошо доказать.
Это несложно. Просто надо по отдельности рассматривать варианты, что среди набора этих 4 элементов имеется то или иное количество положительных, отрицательных и нулевых элементов.
Извините, это любому 5-7 класснику очевидно с базовыми склонностями к информатике. Если к такому на Хабре нужно прилагать доказательство, ресурс можно закрывать.
Во-первых, вы переоцениваете 5-7 классников. И вообще людей. Если бы это было так очевидно, это не было бы задачей для собеседований.
Во-вторых, я не просил строгое формальное доказательство, достаточно было бы какого-то наброска рассуждений.
В-третьих, для кого, по вашему, эта статья? Она как раз "для самых маленьких", людей только учащихся решать задачи. Для всех остальных вся статья тривиальна и не нужна. А вот для этих начинающих это тем более не очевидно.
Я даже не подумал, что можно перебирать все возможные пары или сортировать массивы. Давайте что-нибудь более элегантное.
С обработкой строк 1000+ таких примеров.
Если x > max1 → max2 = max1, max1 = x
Иначе если x > max2 → max2 = x
Чтобы алгоритм работал, в паре max1, max2 необходимо поддерживать условие max2 >= max1 после каждого переприсвоения, тогда как у вас этот момент отмечен только в самом начале описания алгоритма, а не в описании блока перебора. А в нижеприведённом коде такая сортировка выполняется именно в процессе перебора, к тому же ну совершенно неявно. Впрочем, тому, кто захочет разобраться, это даже полезно..
Если писать на питоне, то я бы использовал всю его мощь для таких задач. Ваше решение можно сократить более, чем в два раза и, мне кажется, в таком коде сложнее ошибиться (что особенно важно, если эта задача с собеседования):
def max_product_linear(arr):
n = len(arr)
if n < 2: return None
max1 = max(range(n), key=lambda i: arr[i])
max2 = max(range(n), key=lambda i: arr[i] if i != max1 else -math.inf)
min1 = min(range(n), key=lambda i: arr[i])
min2 = min(range(n), key=lambda i: arr[i] if i != min1 else math.inf)
return max(arr[max1]*arr[max2], arr[min1]*arr[min2])
То есть O(n) вы превратили в O(4n), создавая по новому итератору на каждый поиск ради синтаксического сахара.
O(4n) - это тот же O(n). Нафига бороться за константу в коде на питоне? Тогда уж надо на c++ писать.
Я не спорю, что асимптотика остаётся O(n). Но если мы обсуждаем оптимальные алгоритмы, то сознательно добавлять лишние полные проходы по данным — странно. Это не n², но это всё равно ухудшение константы, которое в реальном коде иногда выливается в заметную разницу.
Плюс это не выглядит как выигрыш в читаемости. Конструкция с key=lambda и костылём через math.inf добавляет скрытую логику и хуже читается, чем один явный проход с понятными инвариантами. Хотя может это моя деформация.
И да, «мощь языка» имеет обратную сторону — на нём очень легко писать неоптимальные вещи, которые выглядят лаконично, что вы выше и продемонстрировали. Настоящая мощь — это когда код одновременно читаемый и не делает лишней работы.
Если бы это давало и читаемость, и скорость — ок. Но повышения скорости тут нет, а повышение читаемости сомнительно.
что вы понимаете под оптимальными алгоритмами?
обычно это означает "асимптотически оптимальные", но вы имеете в виду, видимо, абсолютное время? тогда перепишите код на c++ и скомпилируйте с -Ofast -march=native и это будет оптимально, так как упрется в пропускную способность памяти (и то не на всех архитектурах, так как иногда в один поток невозможно нагрузить память, надо будет параллелить).
Даже если вы имеете в виду абсолютное время на питоне, то наверняка какой-нибудь numpy.partition будет быстрее, так как выполняется нативно на numpy-массивах. Ну и даже для вашего алгоритма наверняка распараллеливание на несколько потоков его ускорит.
повышение читаемости сомнительно
это стандартный шаблон argmax (одна из полезных функций, отсутствующих в питоне, но присутствующих, например, в numpy) - он обычно легко распознается при чтении, если вам знаком
вот я тоже удивился самому факту существования этой темы, потому что обычно питонистам насрать на оптимизацию, DRY и прочее)
Если массив из 4 элементов получим сложность O(n²) :)
Ну нет, тут замедление не в 4 раза алгоритмически. Максимум в 2. Ибо у вас тоже 4 сравнения в теле цикла. Но зато вы экономите на единой проверке счетчика итераций, а тут 4 цикла каждый отдельно проверяют i. И некоторые проверки у вас иногда пропускаются.
Оригинальный подход был бы быстрее на языке более низкого уровня, там бы один проход читал бы из памяти лишь один раз, что на больших массивах сильно быстрее чтения 4 раза. Но в питоне все эти оптимизации весьма условные, все переменные - огромные объекты, а ручная итерация по массиву работает вообще страшно медленно по сравнению со встроенными функциями. Так что это еще большой вопрос, чей код на самом деле быстрее. Надо бенчмарки гонять.
И вообще O(4n) - то же самое O(n).
В контексте статьи для обучения и интервью вот эти вот 4 отдельных цикла на порядки читабельнее и поэтому лучше.
Я не поленился и побенчил. Вариант с лямбдами медленнее в 3 раза.
------------------------------------------------------------------------------------------------------------- benchmark: 12 tests --------------------------------------------------------------------------------------------------------------
Name (time in ns) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_linear[10] 708.0380 (1.0) 57,209.0503 (1.02) 835.6700 (1.0) 295.8940 (1.0) 833.0680 (1.0) 1.1642 (1.0) 354;43287 1,196,644.5862 (1.0) 142861 1
test_linear2[10] 2,583.0232 (3.65) 55,833.9525 (1.0) 2,728.8291 (3.27) 399.6901 (1.35) 2,708.0532 (3.25) 1.1642 (1.0) 294;50327 366,457.5425 (0.31) 116509 1
test_linear[100] 6,582.8208 (9.30) 97,834.0395 (1.75) 6,750.1172 (8.08) 746.9517 (2.52) 6,708.0837 (8.05) 41.9095 (36.00) 712;11586 148,145.5749 (0.12) 129734 1
test_linear2[100] 18,165.9125 (25.66) 61,791.8558 (1.11) 18,398.7960 (22.02) 924.1897 (3.12) 18,291.8739 (21.96) 83.1205 (71.40) 1113;4551 54,351.3825 (0.05) 50850 1
test_linear[1000] 67,624.9620 (95.51) 179,792.0559 (3.22) 68,376.8114 (81.82) 2,290.5980 (7.74) 67,957.9098 (81.58) 166.0082 (142.60) 724;1534 14,624.8411 (0.01) 14261 1
test_linear2[1000] 200,291.8627 (282.88) 309,707.8297 (5.55) 202,454.4575 (242.27) 5,584.4435 (18.87) 200,666.0216 (240.88) 1,750.0133 (>1000.0) 325;564 4,939.3825 (0.00) 4497 1
test_linear[10000] 682,916.9579 (964.52) 791,667.0293 (14.18) 691,476.7826 (827.45) 8,098.1468 (27.37) 689,707.9293 (827.91) 3,542.0526 (>1000.0) 117;182 1,446.1802 (0.00) 1442 1
test_linear2[10000] 2,076,457.9531 (>1000.0) 2,245,165.8733 (40.21) 2,090,560.7943 (>1000.0) 19,249.7314 (65.06) 2,084,770.4727 (>1000.0) 11,041.0620 (>1000.0) 29;29 478.3405 (0.00) 434 1
test_linear[100000] 6,895,666.0107 (>1000.0) 7,726,832.9915 (138.39) 6,937,461.8904 (>1000.0) 80,379.9075 (271.65) 6,919,166.4224 (>1000.0) 24,874.9275 (>1000.0) 11;16 144.1449 (0.00) 142 1
test_linear2[100000] 20,933,165.9134 (>1000.0) 21,397,583.1866 (383.24) 21,026,074.6729 (>1000.0) 100,371.3917 (339.21) 20,985,625.4514 (>1000.0) 73,229.5448 (>1000.0) 7;6 47.5600 (0.00) 48 1
test_linear[1000000] 69,027,584.0461 (>1000.0) 69,449,540.9261 (>1000.0) 69,141,688.9119 (>1000.0) 132,736.1878 (448.59) 69,087,291.8349 (>1000.0) 164,583.9075 (>1000.0) 2;0 14.4631 (0.00) 15 1
test_linear2[1000000] 209,953,666.1990 (>1000.0) 210,920,625.1334 (>1000.0) 210,415,533.2316 (>1000.0) 376,636.6391 (>1000.0) 210,339,416.9826 (>1000.0) 564,583.2280 (>1000.0) 2;0 4.7525 (0.00) 5 1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Код бенчмарка
import math
import random
import pytest
def max_product_linear(arr):
if len(arr) < 2:
return -1
# Инициализируем экстремумы первыми двумя элементами
if arr[0] > arr[1]:
max1, max2 = arr[0], arr[1]
min1, min2 = arr[1], arr[0]
else:
max1, max2 = arr[1], arr[0]
min1, min2 = arr[0], arr[1]
# Проходим по оставшимся элементам
for i in range(2, len(arr)):
x = arr[i]
# Обновляем максимумы
if x > max1:
max2 = max1
max1 = x
elif x > max2:
max2 = x
# Обновляем минимумы
if x < min1:
min2 = min1
min1 = x
elif x < min2:
min2 = x
return max(max1 * max2, min1 * min2)
def max_product_linear_2(arr):
n = len(arr)
if n < 2: return None
max1 = max(range(n), key=lambda i: arr[i])
max2 = max(range(n), key=lambda i: arr[i] if i != max1 else -math.inf)
min1 = min(range(n), key=lambda i: arr[i])
min2 = min(range(n), key=lambda i: arr[i] if i != min1 else math.inf)
return max(arr[max1]*arr[max2], arr[min1]*arr[min2])
@pytest.fixture(scope="session")
def rng():
return random.Random(123456)
@pytest.mark.parametrize("n", [10, 100, 1_000, 10_000, 100_000, 1_000_000])
def test_linear(benchmark, rng, n):
arr = [rng.randint(-10**6, 10**6) for _ in range(n)]
benchmark(max_product_linear, arr)
@pytest.mark.parametrize("n", [10, 100, 1_000, 10_000, 100_000, 1_000_000])
def test_linear2(benchmark, rng, n):
arr = [rng.randint(-10**6, 10**6) for _ in range(n)]
benchmark(max_product_linear_2, arr)
Спасибо. Значит лямбды добавляют накладных расходов. Но все-равно, вы утверждали про 4 раза, а тут 3.
Все равно, мне переписанный код кажется более полезным. Он проще и понятнее. На интервью его проще написать без ошибок, ни один адекватный интервьювер прикапываться к константе не будет. Людям, обучающимся решать задачи, он тоже более понятен и к нему проще прийти. На практике же, если вам важно ускорение этого кода в 3 раза, вы перепишите его с numpy (что с раздельными 4-мя циклами проще, чем с одним) и получите ускорение в несколько десятков раз.
Да хоть 3, а не 3. По сути просто из желания показать какой синтаксический сахар есть в Питере, человек взял простое и быстрое решение реализовал так, что начали рождаться вопросы, а действительно ли это оптимально. Иногда лучше сделать просто, без заигрываний.
Нет, там желание сделать более понятный код. Можно хоть 4 цикла написать, хоть 4 min/index, хоть с лямбдами. Оно понятнее, не надо в голове держать инварианты max1 > max2 и думать, все ли варианты покрыты, или нет. Это более естественный перевод с человеческого "найти минимальный и второй минимальный элемент". Сразу явно видно, что вот минимальный, а вот минимальный из оставшихся.
Вопросы там - к микрооптимизациям только. Их новички не задают и не понимают. И практической ценности они для интервью или соревнований не несут никакой. Любой линейный алгоритм обычно работает достаточно быстро.
И все-таки, самый быстрый вариант — без циклов ))
def max_product_linear_3(arr):
if len(arr) < 2:
return -1
max1 = max(arr)
i = arr.index(max1)
arr[i] = -math.inf
max2 = max(arr)
arr[i] = max1
min1 = min(arr)
i = arr.index(min1)
arr[i] = math.inf
min2 = min(arr)
arr[i] = min1
return max(max1 * max2, min1 * min2)
Для max1 и min1 не нужны никакие lambd-ы, можно просто функцию от списка взять и сыкономить еще и на обращении по индексу.
На python функции max, min имеют реализацию на C, и по идее быстрее циклов написанных на python, так что возможно, что 4 вызова функциц отработат даже быстрее одного цикла на python.
Может импортнуть heapq проще ?
Вы сейчас привели типичный пример использования мощи языка превращающий его в говнокод сложно читаемый
да я уже понял, что зря залез со своим комментарием. Я просто хотел поделиться подходом к решению таких задач, который минимизирует скорость написания и количество ошибок.
Такие задачи - это не ентерпрайз, это либо собеседования, либо соревнования по программированию.
И на хабре, и на реддите многие жалуются, что на собесе не решили задачу, стресс, не хватило времени, запутались в граничных условиях, не нашли ошибку (На контестах тоже частая проблема - не хватает времени на сложные задачи, так как слишком много времени ушло на написание и отлаживание простых). Это нормально - в условиях стресса люди всегда делают больше ошибок, поэтому всегда имеет смысл писаль код максимально близкий к объяснению решения задачи на словах.
Ну и если вы думаете, что это - говнокод, значит вы не видели, как пишут код люди уровня чемпионов ICPC - не потому, что иначе не умеют, а потому, что это более эффективно.
Задача сложнее - это найти в реальном мире где это вообще можно использовать.
Это, наверно, был риторический вопрос, но я попробую ответить.
Конкретно эта задача, может, и не имеет практического значения, но она является упражнением на поиск второго маскимума(минимума).
Это частный случай поиска k-го максимума (или первых k максимумов). Практическое значение - Вас с помощью этой задачи подводят к алгоритму quick-select (используется много где, например, в статистике для вычисления медианы/перцентилей)
Второе применение - поиск второго максимума/минимума в более сложных объектах. Классическая задача - поиск второго оптимального пути в ациклических направленных графах. Практическое применение - быстрое вычисление оптимальной траектории в вашей сети, если одно из ее ребер удалить (то есть, нарушилась связность между двумя узлами в сети).
Все классно, но хоть бы ответ ии не копировали точь-в-точь. Начали про вопрос с собеседования, закончили сгенерированной выкладкой.
Ну если есть положительные и отрицательные числа то при проходе по массиву надо сравнивать значения по модулю. Произведение минимальных отрицательных не факт что больше произведения максимальных положительных и наоборот. А еще они могут быть и равны. Так что алгоритм сложнее должен быть. Если данная задача нужна лишь для демонстрации оптимального однопроходного решения, то это интересно только для начинающих, типа как в шахматах, найди мат в два хода. Для более менее продвинутого программера этот алгоритм типа на знания "таблицы умножения". Но есть нюансы, которые я описал выше.
@its_fire_fire_fun_fun_fun, Я же говорил, что алгоритм не так очевиден, как вам кажется.
В поисках O(n): как научиться видеть эффективные решения задач