12.5 секунд. На 25% медленнее, чем изначальное решение. Выделение этого k все портит. Ну и я не очень понимаю, где вы тут один проход убрали. Раньше у вас было temp[temp > 0] = len(numbers) - i , вместо него стало temp.astype(bool)*k
Видимо, вы избавляетесь от пересылки индексов через питон в первом случае, но проигрываете от больших выделений памяти.
Да, не, там не в памяти дело. Вообще, 1000 раз пройтись по массиву размером 80м, это 80 миллиардов операций. В секунду влезает 2-5 миллиардов. Ну вот и получается. что где-то 16-40 секунд оно и должно работать. Операции очень непросытые, ибо там условие, несколько проверок и присваение. Так что ближе к 40с. С векторизацией в 8 раз быстрее из-за векторизации, но в пару раз медленнее из-за дополнительных проходов (надо там отдельно roll сделать, отдельно занулить что-то и отдельно максимумы взять). Так что все более менее сходится.
Я был не прав. Мое изначальное решение на C++, которое шло по массиву задом-наперед, было гораздо медленнее. 50с вместо 10с у numpy. Развернув цикл, оно стало работать чуть быстрее - за 35с.
Действительно, векторизация внутри numpy перевешивает накладные расходы из-за питона.
Ну это такой аргумент, numpy если я не ошибаюсь написан на том же си и так же использует SIMD векторизацию.
Ну если бы в numpy была операция для всех вычислений, то да. Но все, что вы из встроенного используете - это np.roll. А дальше там пересылка индексов через питон. Всякие максимумы, которые не факт что векторизованы.
Не совсем так, я храню индекс числа в оригинальном массиве, в перевёрнутом виде.
Ну так это же и есть количество единиц. Индекс в перевернутом виде - номер строки с конца. Вот это взятое число - это та строка, с которой начинаются единицы. Вот и получается, что номер числа с конца это и есть количество единиц. Ну, может там +1 откуда-то получается везде, но это не принципиально.
Хотелось бы сравнить алгоритм с вашей реализацией по скорости.
Попозже сравню у себя питоновскую реализацию с си++.
Ну вот вы и пришли почти к тому же, что и в статье. Автор остановился на arccos, но в комментах выше уже несколько раз предлагали использовать арктангенс, векторное и скалярные произведения - последнюю формулу.
Да. Это, похоже, лучшее по памяти решение. И если вы будете его сравнивать с линейным решателем, то надо делить время на 10. Ведь решатель-то написан на каком-нибудь с++, а из питона вы лишь вызваете библиотеку. А циклы в питоне, да и вот это перекладывание из одного numpy массива в другой - это медленно. Там еще массив temp будет выделятся на каждй итерации, да и всякие конструкции вроде temp[temp>0] похоже выделяют память под список индексов. А решение на С++ будет вообще без лишних выделений памяти и сильно быстрее.
Я придумал, кажется, весьма интуитивное его объяснение этому решению. Очевидно, что можно хранить прямоугольный битовый dp[][] - не одну строчку, а всю матрицу. По ней восстановление ответа легко сделать - можно взять число j, если dp[i-j][j-1]. Потом можно заметить, что каждый столбец там начинается с нулей, но где-то станет равен 1 и дальше будут только 1. поэтому можно вместо прямоугольной матрицы хранить строку чисел, где помечать, где именно начинаются 1 в каждом столбце. У вас в решении примерно это и хранится, только перевернутое - вы храните, сколько там единиц в столбце. Мой код на С++ где-то в комментах тут хранит само число с номером равным этой строке.
Восстановление ответа работает так: если в каком-то столбце где-то начались 1, то можно взять число в этой строке - ведь раз тут единицы начались, то они начались из-за перехода по этому числу, а столбец, куда вы попадете при вычитании этого числа, имел единицы на предыдущей строке, значит дальше вы будете брать только более ранние числа. Поэтому не надо даже перебирать какое число суда прикладывается, а просто взять одно известное.
И сортировка тут вообще никак не поможет. В [2,3,3,4]->8 вы можете случайно взять 4, что делать нельзя. В [2,1,1] -> 3 вы можете взять 1 и потом опять 1. Тут все еще хуже, ибо тут надо использовать не ту 1, которую вы берете сейчас, а что-то, что вы рассмотрели еще раньше. При этом сами числа могут быть как больше, так и меньше текущего.
Ну вот новый контрпример: [2, 3, 3, 4, 52, 52, 100, 1000, 1000]
Вы опять придумали заплатку, которая никак логически не может влиять на основную проблему. Еще раз, проблема в том, что можно получить ситуацию, что вам надо набрать 8, а у вас остались числа [2, 3, 3, 4]. И тут вы никак не можете понять, что 4 брать нельзя. Или что-то подобное. Вы сделали так, что нельзя брать 100 в этом конкретном примере, чтобы попасть в 108-100=8? Ну вот я добавил пару 1000 в массив и ваша эвристика сломалась.
Пока вы логически не покажете, почему вы исключаете ситуацию, что dp[i-j] требует использовать j в сумме - вы не правы. В общем случае, а не затыкая конкретные контр-примеры.
И я не вижу никакого способа по лишь одной строке dp в конце этого избежать.
Если вам только понять, в какую сторону вращать, то вам достаточно знака угла. И тут даже тригонометрических функций не надо - просто смотрите на знак векторного произведения на плоскости (забейте на нулевые x компоненты векторов). Ведь на плоскости векторное произведение будет равно синусу угла, помноженному на длины векторов.
В прошлом возражении вы начинали брать числа с меньших (для теста {2,3,3,4}, а тут берете с больших. Как так-то?
Ну хорошо, если вы рассуждения не принимаете и с завидным упорством цепляетесь за частности, то запустите ваш код на ([2, 3, 3, 4, 52, 52, 100], 108), ([110,70,60,50,30,1,1], 161) и ([2,2,1,1], 3). И в конце убедитесь, что сумма ответа равна искомой target_sum. Ни в одном из этих трех тестов ответ не сойдется ([3,4,100], [1,1], [60,50,30,1,1]). Конкретнее некуда.
например так
def test(numbers: list):
total_sum = sum(numbers)
if total_sum % 2 == 1:
print ("!!! Odd sum " + str(total_sum))
ans = find_subset_sum(numbers, total_sum // 2)
if sum(ans) != total_sum // 2:
print( "Wrong answer for " + str(numbers) + " : " + str(ans))
Оно заранее завершает процесс заполнения dp, и исключает во многом те ситуации, что вы описывали в предыдущем ответе.
Но не исключает их в принципе, все еще оставляя алгоритм неправильным. Всегда можно все числа умножить на 10 и добавить в конец две единицы. И тогда, пока вы одну из этих единиц не обработаете, вы нечетную нужную сумму никак не наберете, а значит все интересные числа обработаются. Если же числа по возрастанию сортируются, то можно в конец добавить несколько больших чисел, так что все интересные для ошибки числа все-равно обработаются, как в первом примере.
Я привел тесты, где числа и по возрастанию и по убыванию упорядочены. Похожие тесты можно сделать, даже если вы в восстановлении ответа будете числа не с конца брать, а с начала списка (без [::-1] в последнем цикле). Например, на тесте ([2, 3, 3, 4, 52, 52, 100], 108) исправленный так код вернет [52,52,2], что не дает нужную сумму.
Какую бы вы эвристику не придумали, пока вы ее не докажете - она по умолчанию не работает. Вы должны четко и с математичесской строгостью показать, почему эта эвристика делает так, что dp[i-j] можно будет собрать не используя j и уже ранее взятые числа.
Так, т.е. берем от младших чисел к старшим? Ну вот пример:
Надо набрать 6. Есть {3,6}. Вы первым делом возьмете 3, потому что 3 набрать можно. И вот уже не правильно. Более сложный пример, когда надо половину набрать, как в исходной задаче из статьи: {3, 5, 6, 7, 11}. Надо набрать 16. Проверяем 3. 16-3=13=6+7 взять можно, вы беретe 3. Осталось набрать 13. 13-5=8 набрать можно? Можно: 3+5. Вы берете 5. Осталость набрать 8. А никак вы 8 оставшимеся {6,7,8} не наберете. Его можно набрать 3+5, но вы из оба уже использовали. А так-то ответ должен быть, например, 3+6+7 или 5+11.
Хоть минимальные сначала берите, хоть максимальные, хоть в случайном порядке числа проверяйте, все равно будет тест, который вам все сломает.
Нет, не достаточно. Смотрите, что у вас в dp[] хранится по итогу? У вас там пометка, можно ли набрать вот такую вут сумму всеми числами или нет. Только по этой информации никак не восстановить множество, ведь вы не знаете, какими числами каждую сумму можно набрать, и поэтому не знаете, можно ли брать заданное число.
И не важно, с какого конца их брать. Вот контр-пример к сортировке:
Вам надо набрать 8, есть числа {2,3,3,4}. Первым шагом вы возьмете 4, ведь можно же набрать 4 всеми этими числами. И дальше все. Оставшиеся 4 вы никак из {2,3,3} не наберете.
Вот только тут большая ошибка. Он правильно найдет, есть ли решение, или нет. Но ваше восстановление ответа не работатет. Потому что нельзя брать число i, только если dp[j-i]. Как пример, у вас есть набор чисел {4,2}, надо набрать 4. Если вы сначала посмотрите i=2, то вы его возьмете. И как бы вам пришлось бы брать 2 два раза, но это делать нельзя же. Понятно, что реальный пример должен быть сильно сложнее, ведь набирать надо половину всех чисел. Но подобные ситуации могут и там возникнуть.
Чтобы восстановить ответ, посмотрите мой комментарий с кодом на c++. Там пара опечаток, почитайте всю ветку, но для восстановления ответа вам нужен массив чисел, а не битов.
Если вам только проверить надо на существование ответа, а не сам список получить, то массив битов работает отлично.
Все еще непонятно. Из-за первых байт файла телеграм считет его картинкой и скачивает. Потом пытается отобразить? В какой момент выполняется питоновый скрипт? Нужно ли для этого отдельно устанавливать питон и чтобы он был ассоциированс pyzw файлами?
Да блин, очевидна причина этого явления. LLM генерируют по одному токену, предсказывая его по контексту так, что бы распределение токенов было похоже на то, что было видно в обучающей выборке. Никаких знаний или логики у нее нет. Когда выданный ответ совпадает с фактами, это называют удивительными способностями к дедукции. Когда не совпадает - галлюцинациями.
12.5 секунд. На 25% медленнее, чем изначальное решение. Выделение этого k все портит. Ну и я не очень понимаю, где вы тут один проход убрали. Раньше у вас было
temp[temp > 0] = len(numbers) - i, вместо него сталоtemp.astype(bool)*kВидимо, вы избавляетесь от пересылки индексов через питон в первом случае, но проигрываете от больших выделений памяти.
Вообще-то, это лишь уведомление, о том, что есть такая возможность. Мерзкая реклама, но пока никакого принуждения.
Да, не, там не в памяти дело. Вообще, 1000 раз пройтись по массиву размером 80м, это 80 миллиардов операций. В секунду влезает 2-5 миллиардов. Ну вот и получается. что где-то 16-40 секунд оно и должно работать. Операции очень непросытые, ибо там условие, несколько проверок и присваение. Так что ближе к 40с. С векторизацией в 8 раз быстрее из-за векторизации, но в пару раз медленнее из-за дополнительных проходов (надо там отдельно roll сделать, отдельно занулить что-то и отдельно максимумы взять). Так что все более менее сходится.
Я был не прав. Мое изначальное решение на C++, которое шло по массиву задом-наперед, было гораздо медленнее. 50с вместо 10с у numpy. Развернув цикл, оно стало работать чуть быстрее - за 35с.
Действительно, векторизация внутри numpy перевешивает накладные расходы из-за питона.
Ну если бы в numpy была операция для всех вычислений, то да. Но все, что вы из встроенного используете - это np.roll. А дальше там пересылка индексов через питон. Всякие максимумы, которые не факт что векторизованы.
Ну так это же и есть количество единиц. Индекс в перевернутом виде - номер строки с конца. Вот это взятое число - это та строка, с которой начинаются единицы. Вот и получается, что номер числа с конца это и есть количество единиц. Ну, может там +1 откуда-то получается везде, но это не принципиально.
Попозже сравню у себя питоновскую реализацию с си++.
Ну вот вы и пришли почти к тому же, что и в статье. Автор остановился на arccos, но в комментах выше уже несколько раз предлагали использовать арктангенс, векторное и скалярные произведения - последнюю формулу.
Да. Это, похоже, лучшее по памяти решение. И если вы будете его сравнивать с линейным решателем, то надо делить время на 10. Ведь решатель-то написан на каком-нибудь с++, а из питона вы лишь вызваете библиотеку. А циклы в питоне, да и вот это перекладывание из одного numpy массива в другой - это медленно. Там еще массив temp будет выделятся на каждй итерации, да и всякие конструкции вроде temp[temp>0] похоже выделяют память под список индексов. А решение на С++ будет вообще без лишних выделений памяти и сильно быстрее.
Я придумал, кажется, весьма интуитивное его объяснение этому решению. Очевидно, что можно хранить прямоугольный битовый dp[][] - не одну строчку, а всю матрицу. По ней восстановление ответа легко сделать - можно взять число j, если dp[i-j][j-1]. Потом можно заметить, что каждый столбец там начинается с нулей, но где-то станет равен 1 и дальше будут только 1. поэтому можно вместо прямоугольной матрицы хранить строку чисел, где помечать, где именно начинаются 1 в каждом столбце. У вас в решении примерно это и хранится, только перевернутое - вы храните, сколько там единиц в столбце. Мой код на С++ где-то в комментах тут хранит само число с номером равным этой строке.
Восстановление ответа работает так: если в каком-то столбце где-то начались 1, то можно взять число в этой строке - ведь раз тут единицы начались, то они начались из-за перехода по этому числу, а столбец, куда вы попадете при вычитании этого числа, имел единицы на предыдущей строке, значит дальше вы будете брать только более ранние числа. Поэтому не надо даже перебирать какое число суда прикладывается, а просто взять одно известное.
И как же этот аргумент, собственно, вычислить?
Вы сумму до 1108 исправили? В этом случае ваш код набирает 1106.
И сортировка тут вообще никак не поможет. В [2,3,3,4]->8 вы можете случайно взять 4, что делать нельзя. В [2,1,1] -> 3 вы можете взять 1 и потом опять 1. Тут все еще хуже, ибо тут надо использовать не ту 1, которую вы берете сейчас, а что-то, что вы рассмотрели еще раньше. При этом сами числа могут быть как больше, так и меньше текущего.
Ну вот новый контрпример: [2, 3, 3, 4, 52, 52, 100, 1000, 1000]
Вы опять придумали заплатку, которая никак логически не может влиять на основную проблему. Еще раз, проблема в том, что можно получить ситуацию, что вам надо набрать 8, а у вас остались числа [2, 3, 3, 4]. И тут вы никак не можете понять, что 4 брать нельзя. Или что-то подобное. Вы сделали так, что нельзя брать 100 в этом конкретном примере, чтобы попасть в 108-100=8? Ну вот я добавил пару 1000 в массив и ваша эвристика сломалась.
Пока вы логически не покажете, почему вы исключаете ситуацию, что dp[i-j] требует использовать j в сумме - вы не правы. В общем случае, а не затыкая конкретные контр-примеры.
И я не вижу никакого способа по лишь одной строке dp в конце этого избежать.
Если вам только понять, в какую сторону вращать, то вам достаточно знака угла. И тут даже тригонометрических функций не надо - просто смотрите на знак векторного произведения на плоскости (забейте на нулевые x компоненты векторов). Ведь на плоскости векторное произведение будет равно синусу угла, помноженному на длины векторов.
В прошлом возражении вы начинали брать числа с меньших (для теста {2,3,3,4}, а тут берете с больших. Как так-то?
Ну хорошо, если вы рассуждения не принимаете и с завидным упорством цепляетесь за частности, то запустите ваш код на ([2, 3, 3, 4, 52, 52, 100], 108), ([110,70,60,50,30,1,1], 161) и ([2,2,1,1], 3). И в конце убедитесь, что сумма ответа равна искомой target_sum. Ни в одном из этих трех тестов ответ не сойдется ([3,4,100], [1,1], [60,50,30,1,1]). Конкретнее некуда.
например так
Но не исключает их в принципе, все еще оставляя алгоритм неправильным. Всегда можно все числа умножить на 10 и добавить в конец две единицы. И тогда, пока вы одну из этих единиц не обработаете, вы нечетную нужную сумму никак не наберете, а значит все интересные числа обработаются. Если же числа по возрастанию сортируются, то можно в конец добавить несколько больших чисел, так что все интересные для ошибки числа все-равно обработаются, как в первом примере.
Я привел тесты, где числа и по возрастанию и по убыванию упорядочены. Похожие тесты можно сделать, даже если вы в восстановлении ответа будете числа не с конца брать, а с начала списка (без [::-1] в последнем цикле). Например, на тесте ([2, 3, 3, 4, 52, 52, 100], 108) исправленный так код вернет [52,52,2], что не дает нужную сумму.
Какую бы вы эвристику не придумали, пока вы ее не докажете - она по умолчанию не работает. Вы должны четко и с математичесской строгостью показать, почему эта эвристика делает так, что dp[i-j] можно будет собрать не используя j и уже ранее взятые числа.
Так, т.е. берем от младших чисел к старшим? Ну вот пример:
Надо набрать 6. Есть {3,6}. Вы первым делом возьмете 3, потому что 3 набрать можно. И вот уже не правильно. Более сложный пример, когда надо половину набрать, как в исходной задаче из статьи: {3, 5, 6, 7, 11}. Надо набрать 16. Проверяем 3. 16-3=13=6+7 взять можно, вы беретe 3. Осталось набрать 13. 13-5=8 набрать можно? Можно: 3+5. Вы берете 5. Осталость набрать 8. А никак вы 8 оставшимеся {6,7,8} не наберете. Его можно набрать 3+5, но вы из оба уже использовали. А так-то ответ должен быть, например, 3+6+7 или 5+11.
Хоть минимальные сначала берите, хоть максимальные, хоть в случайном порядке числа проверяйте, все равно будет тест, который вам все сломает.
Нет, не достаточно. Смотрите, что у вас в dp[] хранится по итогу? У вас там пометка, можно ли набрать вот такую вут сумму всеми числами или нет. Только по этой информации никак не восстановить множество, ведь вы не знаете, какими числами каждую сумму можно набрать, и поэтому не знаете, можно ли брать заданное число.
И не важно, с какого конца их брать. Вот контр-пример к сортировке:
Вам надо набрать 8, есть числа {2,3,3,4}. Первым шагом вы возьмете 4, ведь можно же набрать 4 всеми этими числами. И дальше все. Оставшиеся 4 вы никак из {2,3,3} не наберете.
Вот только тут большая ошибка. Он правильно найдет, есть ли решение, или нет. Но ваше восстановление ответа не работатет. Потому что нельзя брать число i, только если dp[j-i]. Как пример, у вас есть набор чисел {4,2}, надо набрать 4. Если вы сначала посмотрите i=2, то вы его возьмете. И как бы вам пришлось бы брать 2 два раза, но это делать нельзя же. Понятно, что реальный пример должен быть сильно сложнее, ведь набирать надо половину всех чисел. Но подобные ситуации могут и там возникнуть.
Чтобы восстановить ответ, посмотрите мой комментарий с кодом на c++. Там пара опечаток, почитайте всю ветку, но для восстановления ответа вам нужен массив чисел, а не битов.
Если вам только проверить надо на существование ответа, а не сам список получить, то массив битов работает отлично.
Все еще непонятно. Из-за первых байт файла телеграм считет его картинкой и скачивает. Потом пытается отобразить? В какой момент выполняется питоновый скрипт? Нужно ли для этого отдельно устанавливать питон и чтобы он был ассоциированс pyzw файлами?
Ну и будет сетка тогда рандомно отвечать "не знаю", на то, что в обучающей выборке вполне себе было.
Да блин, очевидна причина этого явления. LLM генерируют по одному токену, предсказывая его по контексту так, что бы распределение токенов было похоже на то, что было видно в обучающей выборке. Никаких знаний или логики у нее нет. Когда выданный ответ совпадает с фактами, это называют удивительными способностями к дедукции. Когда не совпадает - галлюцинациями.
Да, действительно. Можно не перебирать слишком большие j, ведь больше суммы текущих чисел все-равно собрать мы никак не сможем.