не получите тот же исполнимый файл, а значит не можете быть уверены, что не получили код с закладками.
Исключая конспирологическую теорию закладок (которая, кстати, еще лучше прикладывается к нейросеткам. Они-то - вообще черные ящики), компиляторы производят разный, но практически всегда одинаково работающий код. Особенно, если выключить оптимизации, там вообще будет один в один или очевидно эквивалентный код.
Ну и порядок команд в машинных кодах тоже может значительно измениться от небольших правок исходников.
Опять же, компиляторы генерируют машинный код, который делает ровно то, что написано в исходниках. Там механистический перевод, с понятной логикой и намеринеями, а не неявно через какие-то веса токенов, как в нейросетках. А порядок машинных кодов ни на что практически не влияет. Если не упарываться в абсолютную производительность, правда. Там уже только хардкор, только ассемблер.
А то, что небольшое изменение может сломать что угодно - так на это и тесты.
Абсолютно все тестами вы не покроете, ибо комбинаторный взрыв.
Из прода вы узнаете о каких-то багах в случаях, не покрытых тестами и только о них. И то, не всегда. Так что вот сгенерили вы программу, все тесты зеленые. Потом нашелся баг, добавили тест, перегенерили, снова все зеленое. Но вы попутно могли сломать почти все, что раньше работало, но тестами не покрыто. И каждый релиз обладает какими-то совершенно новыми багами в ранее работающих местах, которые вообще-то менять смысла никакого не было. Это уникальный для вайб-кодинга сценарий проблем.
А то что в 90% случаев она сделает, то что даже не видела.
Часы как раз контр пример. Она часов со временем, отличным от 10:10 практически не видела, потому что это эстетически приятное, по мнению маркетологов, время на всех картинках и выставлено. То же и с бокалами вина. До краев наполненый нигде не показывают - это не красиво.
Вот только проблема: даже с нулевой температорой любая помена промпта приведет к непредсказуемым результатам. Вы нашли косяк, добавили описание этого кейса в ТЗ, а нейросетка c некоторой вероятностью поломает какие-то вообще никак не связанные с этим кейсом ранее работающие места. Она может вообще все совершенно по другому переписать. Потому что любое изменение промпта меняет веса для уже первого сгенеренного токена и далее для всех, потому что они генерятся подряд по одному.
Так что это принципиально работает не так как программисты с исходниками. Они обычно могут дописать программу под этот новый кейс и при этом старые места продолжат работать правильно.
А еще, любое обновление "вайб-компилятора" непредсказуемо опять же изменяет все ранее написанные промпты. Обновление традиционного компилятора же обычно ничего не ломает, если в нем багов, конечно, нет. Так что вам надо копию модели для которой вы писали свой промпт всегда держать под рукой, а они очень жирные.
Ага, вместо видео чата с бизнес-партнером нейросеть вам сгенерирует видео бизнес партнера. Может, лет через 5-10 это видео еще и реагировать и отвечать на ваши реплики будет. Вместо прогноза погоды - покажет вам очень красивые иконки и правдоподобные цифры, не имеющие никакого отношения к реальности. Вместо бухгалтерского отчета - красивая табличка. Сгалюционированная на лету, конечно.
Есть другой способ объяснения, и мне он кажется более интуитивным. Ясно, что равномерно перемешав все карты и взяв первые k мы получим все карты равновероятно. Этот метод работал бы, но требует сохранить все n карт в памяти.
Теперь посмотрим на код, и попробуем его исправить, чтобы не держать в памяти все карты:
for (int i = 0; i < n; ++i) {
int j = rand() % (i+1);
swap(a[i], a[j]);
}
Этот код перетасовывает массив равновероятно за O(N) операций. Делает он это индуктивно: после каждой итерации первые i+1 элементов равномерно перемешаны. После этого мы случайно выбираем любую позицию от 0 до i для i-ого элемента. Ведь в равномерно перетасованом массиве этот элемент может быть на любом из этих мест равновероятно. Теперь можно просто свапнуть i-ый элемент на это место. Все остальные элементы, включая тот, с которым мы свапнули, будут равномерно перемешаны, потому что они уже были равномерно перемешаны до этого.
Теперь, если нам надо взять только k первых элементов в конце, то вместо swap() будем просто записывать новый элемент в одно из k мест. Потому что в первые k мест мы можем только свапнуть какой-то новый элемент. Нам же нужно только началомассива, вот мы и будем игнорировать все, что дальше.
for (int i = 0; i < k; ++i) samples[i] = a[i];
for (int i = k; i < n; ++i) {
int j = rand() % (i+1);
if (j < k) samples[j] = a[i];
}
Кстати, на второй взгляд, переполнение тут есть. Например, если ему дать числа {4294967295, 0}, то оно вообще никак не подсчитает 2147483647. Плюс, тут округление может быть как вверх, так и вниз при вычислении среднего в зависимости от порядка переданных чисел, что тоже не всегда хорошо и совсем не удовлетворяет поставленным автором условиям.
Обычно в таких случаях сортируют один раз сразу сравнивая все критерии. Вы же можете как-то словами описать, какой элемент должен идти раньше из двух данных? Вот это надо записать в виде функции сравнения.
Просто у вас сравнение будет составное, лекикографическое: (a1,a2) < (b1, b2) тогда и только тогда, когда a1 < b1 или a1==b1 и a2 < b2. Т.е. при сравнении двух вариантов сравниваете цену, если она совпала - сравниваете длительность пересадки.
По сравнению с несколькими последовательными сортировками тут будет меньше сравнений, меньше перемещений данных, меньше кода и все будет концептуально проще.
Отсортировать по функции оптимальности и выбрать первый элемент в массиве.
Такое себе. Выбрать минимальный элемент можно быстрее, чем отсортировать все. По любому критерию. Просто сравниваете каждый элемент с текущим оптимумом и, если новый лучше - заменяете текущий оптимум.
Это и быстрее и писать проще. И не надо вообще вводить определение стабильных сортировок (кстати, а зачем вам именно стабильная сортировка?)
Можно получать 2 минимальных элемента так же просто. В общем случае можно получить k минимальных элелементов с использованием кучи или quick_select, но тут уже будет код сложнее наивной сортировки.
Далее, задача проанализирована слабо и решена не оптимльно. Можно было бы воспользоваться свойствами вашего критерия оптимальности и ограничений задачи. Вот у вас ровно одна пересадка разрешена. Тогда надо разбить все рейсы на start->x и x->end. Все остальные просто игнорировать. Потом надо разбить их в группы по х и там внутри группы отсортировать.
Потом можно для каждого города-пересадки методом двух указателей перебирать рейсы туда и оттуда - вам же среди всех рейсов оттуда надо брать ближайший ко времени прибытия туда, вы же сначала минимизируете время пересадки. И вот уже вместо O(N^2 log N) (или O(N^2), если выкинуть сортировку) у вас решение за O(N log N).
Так что с теоретической точки зрения работа проделана неубедительная. Плюс стоило бы рассматривать варианты с произвольным количеством пересадок и использовать алгоритмы на графах со сложной функцией расстояния.
А с практической точки зрения вам уже написали - у вас совершенно нереалистичный критерий оптимизации. Надо давать время на пересадку, опоздания и отмены рейсов, учитывать какие там автовокзалы. Но, судя по оформлению статьи и набору тестовых данных, это чисто теоретическая статья для какого-нибудь отчета в университете.
Справидливости ради, от этого всего никуда не ушли. Просто за счет уменьшения базы по сравнению с машинным словом появилась возможность не выполнять переносы после каждого сложения, а выполнить их все одним махом в самом конце. Так что метод предложенный тут действительно ускоряет, когда вы складываете много чисел, а не только два.
Ну так вы фактически к тому же, что и у автора и придете. Только вы делить будете сначала не на size, а на 2^64, потом еще отдельно делить и сдвигать. Потом можно будет заметить, что можно сразу же делить на size. Вот и тоже самое получается.
А почему тут сериализация раз в несколько тысяч сложений? В этом коде во время перенорсов вычисление каждого следующего разряда завист от предыдущего. Вот цепочка add B,T mov T,B SHR 51 T - тут зависимость по данным.
Вранье. Несуществующую организацию ЛГБТ признали экстремистской. Так что наличие флага - это символика экстремистской организации, а это попадает под статью 280 УК РФ о пропаганде оправдания экстремизма. Это тоже экстремистская статья и по ней возможно вплоть до 5 лет лишения свободы.
Потому что неуловимый джо. На ютубе всякие блогеры и диссиденты пропаганде мешают. Большой пласт людей только за этим туда и идет. Раньше терпели, потому что ссыкатно было, да и родная пропаганда этим каналом доставки информации отлично пользовалась. Когда из-за санкций родную попаганду оттуда выпилили, вред от ютуба однозначно превысил пользу. Стим же особо не мешает пока.
Там разве что всякие порно-игры и пропаганда лгбт нескрепные могут быть, но вся эта борьба является для власти лишь мишурой, да возможностью отрабатывать репрессивные технологии. Плюс стим с властями в основном сотрудничает.
Есть, конечно, вариант, что какие-нибудь бизнесмены продавят свои шкурные интересы и поспособствуют блокировке стима из-за конкуренции, но это вряд ли. Не нужны власти лишние точки напряжения. Только ради прибыли каких-то дядь, хоть и важных, они давление в котле поднимать не будут.
Не к стилистике, а к формулировке. Вы думаете, что "со времен большого взрыва" - это просто оформление сообщения, но большинство читателей восприняли это, как указание на время начала горения.
Скажите какой из сценариев наиболее вероятно описывается фразой "У меня с самого утра до сих пор не прошла мигрень":
1) У человека утром заболела голова, до сих пор болит.
2) У человека голова заболела где-то после обеда, до сих пор болит.
3) У человека сегодня вообще не было мигрени, поэтому и пройти она не могла.
Я думаю, вы со мной согласитесь, что вариант 1 тут самый вероятный. Вот у вас в изначальном комментарии все так же. Раз солнце не погасло, значит оно сейчас горит. Если указывать временной промежуток, воспринимается, что оно в этот промежуток и горит.
Без тавтологии его можно переформулировать: "за несколько миллиардов лет солнце еще ни разу не погасло...", "Солнце пока ни разу не погасло...", "За все время существования солнце не гасло".
Нет, не переполнится (в беззнаковых числах, как в статье). Ответ влезает, потому что это среднее. Разность влезает, потому что худший вариант - это MAX_UINT - 0 = MAX_UINT.
Это называется длинная арифметика. И у автора фактически ровно это и реализовано. Только весьма частный случай: в системе основания с базой size и с оптимизацией, что мы знаем, что нам надо будет выдать обычное целочисленное значение цифр, кроме младшей и оно помещается в uint32_t - так что вместо старших цифр можно сразу хранить их значение в десятичной системе в одной переменной.
Вот что это за мода пошла лениться и просто перепечатывать выхлоп из нейросетей? Во-первых, они галлюционируют. Их вывод надо проверять и осозновать. Если вы его проверили и переварили, то уже можно своими словами одно предложнение скинуть. Во-вторых, если кому-то хочется вывод чатажпт почитать, они у него сами спросят.
Далее, проблема автора - не онлайн или ограничения по памяти, а переполнение целочисленной переменной. Обратите внимание в перепечатоном вами бездумно ответе нейросетки ни слова о переполнении нет.
Вам тут очень повезло, и в этом алгоритме действительно нет переполнения.
Исключая конспирологическую теорию закладок (которая, кстати, еще лучше прикладывается к нейросеткам. Они-то - вообще черные ящики), компиляторы производят разный, но практически всегда одинаково работающий код. Особенно, если выключить оптимизации, там вообще будет один в один или очевидно эквивалентный код.
Опять же, компиляторы генерируют машинный код, который делает ровно то, что написано в исходниках. Там механистический перевод, с понятной логикой и намеринеями, а не неявно через какие-то веса токенов, как в нейросетках. А порядок машинных кодов ни на что практически не влияет. Если не упарываться в абсолютную производительность, правда. Там уже только хардкор, только ассемблер.
Абсолютно все тестами вы не покроете, ибо комбинаторный взрыв.
Из прода вы узнаете о каких-то багах в случаях, не покрытых тестами и только о них. И то, не всегда. Так что вот сгенерили вы программу, все тесты зеленые. Потом нашелся баг, добавили тест, перегенерили, снова все зеленое. Но вы попутно могли сломать почти все, что раньше работало, но тестами не покрыто. И каждый релиз обладает какими-то совершенно новыми багами в ранее работающих местах, которые вообще-то менять смысла никакого не было. Это уникальный для вайб-кодинга сценарий проблем.
Часы как раз контр пример. Она часов со временем, отличным от 10:10 практически не видела, потому что это эстетически приятное, по мнению маркетологов, время на всех картинках и выставлено. То же и с бокалами вина. До краев наполненый нигде не показывают - это не красиво.
Да ладно всякие хитрые комбинации. Аналогвые часы, показывающие ровно 6 часов оно уже может нарисовать? Или полный до краев бокал вина?
Вот только проблема: даже с нулевой температорой любая помена промпта приведет к непредсказуемым результатам. Вы нашли косяк, добавили описание этого кейса в ТЗ, а нейросетка c некоторой вероятностью поломает какие-то вообще никак не связанные с этим кейсом ранее работающие места. Она может вообще все совершенно по другому переписать. Потому что любое изменение промпта меняет веса для уже первого сгенеренного токена и далее для всех, потому что они генерятся подряд по одному.
Так что это принципиально работает не так как программисты с исходниками. Они обычно могут дописать программу под этот новый кейс и при этом старые места продолжат работать правильно.
А еще, любое обновление "вайб-компилятора" непредсказуемо опять же изменяет все ранее написанные промпты. Обновление традиционного компилятора же обычно ничего не ломает, если в нем багов, конечно, нет. Так что вам надо копию модели для которой вы писали свой промпт всегда держать под рукой, а они очень жирные.
Ага, вместо видео чата с бизнес-партнером нейросеть вам сгенерирует видео бизнес партнера. Может, лет через 5-10 это видео еще и реагировать и отвечать на ваши реплики будет. Вместо прогноза погоды - покажет вам очень красивые иконки и правдоподобные цифры, не имеющие никакого отношения к реальности. Вместо бухгалтерского отчета - красивая табличка. Сгалюционированная на лету, конечно.
Есть другой способ объяснения, и мне он кажется более интуитивным. Ясно, что равномерно перемешав все карты и взяв первые k мы получим все карты равновероятно. Этот метод работал бы, но требует сохранить все n карт в памяти.
Теперь посмотрим на код, и попробуем его исправить, чтобы не держать в памяти все карты:
Этот код перетасовывает массив равновероятно за O(N) операций. Делает он это индуктивно: после каждой итерации первые i+1 элементов равномерно перемешаны. После этого мы случайно выбираем любую позицию от 0 до i для i-ого элемента. Ведь в равномерно перетасованом массиве этот элемент может быть на любом из этих мест равновероятно. Теперь можно просто свапнуть i-ый элемент на это место. Все остальные элементы, включая тот, с которым мы свапнули, будут равномерно перемешаны, потому что они уже были равномерно перемешаны до этого.
Теперь, если нам надо взять только k первых элементов в конце, то вместо swap() будем просто записывать новый элемент в одно из k мест. Потому что в первые k мест мы можем только свапнуть какой-то новый элемент. Нам же нужно только началомассива, вот мы и будем игнорировать все, что дальше.
Это можно переписать онлайн:
Фактически, условие
rand() % count < k- это вероятность взять текущий элемент и она равна k/n. Вот откуда она берется.Кстати, на второй взгляд, переполнение тут есть. Например, если ему дать числа {4294967295, 0}, то оно вообще никак не подсчитает 2147483647. Плюс, тут округление может быть как вверх, так и вниз при вычислении среднего в зависимости от порядка переданных чисел, что тоже не всегда хорошо и совсем не удовлетворяет поставленным автором условиям.
Обычно в таких случаях сортируют один раз сразу сравнивая все критерии. Вы же можете как-то словами описать, какой элемент должен идти раньше из двух данных? Вот это надо записать в виде функции сравнения.
Просто у вас сравнение будет составное, лекикографическое: (a1,a2) < (b1, b2) тогда и только тогда, когда a1 < b1 или a1==b1 и a2 < b2. Т.е. при сравнении двух вариантов сравниваете цену, если она совпала - сравниваете длительность пересадки.
По сравнению с несколькими последовательными сортировками тут будет меньше сравнений, меньше перемещений данных, меньше кода и все будет концептуально проще.
Такое себе. Выбрать минимальный элемент можно быстрее, чем отсортировать все. По любому критерию. Просто сравниваете каждый элемент с текущим оптимумом и, если новый лучше - заменяете текущий оптимум.
Это и быстрее и писать проще. И не надо вообще вводить определение стабильных сортировок (кстати, а зачем вам именно стабильная сортировка?)
Можно получать 2 минимальных элемента так же просто. В общем случае можно получить k минимальных элелементов с использованием кучи или quick_select, но тут уже будет код сложнее наивной сортировки.
Далее, задача проанализирована слабо и решена не оптимльно. Можно было бы воспользоваться свойствами вашего критерия оптимальности и ограничений задачи. Вот у вас ровно одна пересадка разрешена. Тогда надо разбить все рейсы на start->x и x->end. Все остальные просто игнорировать. Потом надо разбить их в группы по х и там внутри группы отсортировать.
Потом можно для каждого города-пересадки методом двух указателей перебирать рейсы туда и оттуда - вам же среди всех рейсов оттуда надо брать ближайший ко времени прибытия туда, вы же сначала минимизируете время пересадки. И вот уже вместо O(N^2 log N) (или O(N^2), если выкинуть сортировку) у вас решение за O(N log N).
Так что с теоретической точки зрения работа проделана неубедительная. Плюс стоило бы рассматривать варианты с произвольным количеством пересадок и использовать алгоритмы на графах со сложной функцией расстояния.
А с практической точки зрения вам уже написали - у вас совершенно нереалистичный критерий оптимизации. Надо давать время на пересадку, опоздания и отмены рейсов, учитывать какие там автовокзалы. Но, судя по оформлению статьи и набору тестовых данных, это чисто теоретическая статья для какого-нибудь отчета в университете.
Справидливости ради, от этого всего никуда не ушли. Просто за счет уменьшения базы по сравнению с машинным словом появилась возможность не выполнять переносы после каждого сложения, а выполнить их все одним махом в самом конце. Так что метод предложенный тут действительно ускоряет, когда вы складываете много чисел, а не только два.
Ну так вы фактически к тому же, что и у автора и придете. Только вы делить будете сначала не на size, а на 2^64, потом еще отдельно делить и сдвигать. Потом можно будет заметить, что можно сразу же делить на size. Вот и тоже самое получается.
А почему тут сериализация раз в несколько тысяч сложений? В этом коде во время перенорсов вычисление каждого следующего разряда завист от предыдущего. Вот цепочка add B,T mov T,B SHR 51 T - тут зависимость по данным.
Вранье. Несуществующую организацию ЛГБТ признали экстремистской. Так что наличие флага - это символика экстремистской организации, а это попадает под статью 280 УК РФ о пропаганде оправдания экстремизма. Это тоже экстремистская статья и по ней возможно вплоть до 5 лет лишения свободы.
Хабр - торт. Спасибо за статью!
Да, это хорошая оптимизация.
Потому что неуловимый джо. На ютубе всякие блогеры и диссиденты пропаганде мешают. Большой пласт людей только за этим туда и идет. Раньше терпели, потому что ссыкатно было, да и родная пропаганда этим каналом доставки информации отлично пользовалась. Когда из-за санкций родную попаганду оттуда выпилили, вред от ютуба однозначно превысил пользу. Стим же особо не мешает пока.
Там разве что всякие порно-игры и пропаганда лгбт нескрепные могут быть, но вся эта борьба является для власти лишь мишурой, да возможностью отрабатывать репрессивные технологии. Плюс стим с властями в основном сотрудничает.
Есть, конечно, вариант, что какие-нибудь бизнесмены продавят свои шкурные интересы и поспособствуют блокировке стима из-за конкуренции, но это вряд ли. Не нужны власти лишние точки напряжения. Только ради прибыли каких-то дядь, хоть и важных, они давление в котле поднимать не будут.
Не к стилистике, а к формулировке. Вы думаете, что "со времен большого взрыва" - это просто оформление сообщения, но большинство читателей восприняли это, как указание на время начала горения.
Скажите какой из сценариев наиболее вероятно описывается фразой "У меня с самого утра до сих пор не прошла мигрень":
1) У человека утром заболела голова, до сих пор болит.
2) У человека голова заболела где-то после обеда, до сих пор болит.
3) У человека сегодня вообще не было мигрени, поэтому и пройти она не могла.
Я думаю, вы со мной согласитесь, что вариант 1 тут самый вероятный. Вот у вас в изначальном комментарии все так же. Раз солнце не погасло, значит оно сейчас горит. Если указывать временной промежуток, воспринимается, что оно в этот промежуток и горит.
Без тавтологии его можно переформулировать: "за несколько миллиардов лет солнце еще ни разу не погасло...", "Солнце пока ни разу не погасло...", "За все время существования солнце не гасло".
Нет, не переполнится (в беззнаковых числах, как в статье). Ответ влезает, потому что это среднее. Разность влезает, потому что худший вариант - это MAX_UINT - 0 = MAX_UINT.
Со знаковыми числами, да - может переполниться.
Это называется длинная арифметика. И у автора фактически ровно это и реализовано. Только весьма частный случай: в системе основания с базой size и с оптимизацией, что мы знаем, что нам надо будет выдать обычное целочисленное значение цифр, кроме младшей и оно помещается в uint32_t - так что вместо старших цифр можно сразу хранить их значение в десятичной системе в одной переменной.
Вот что это за мода пошла лениться и просто перепечатывать выхлоп из нейросетей? Во-первых, они галлюционируют. Их вывод надо проверять и осозновать. Если вы его проверили и переварили, то уже можно своими словами одно предложнение скинуть.
Во-вторых, если кому-то хочется вывод чатажпт почитать, они у него сами спросят.
Далее, проблема автора - не онлайн или ограничения по памяти, а переполнение целочисленной переменной. Обратите внимание в перепечатоном вами бездумно ответе нейросетки ни слова о переполнении нет.
Вам тут очень повезло, и в этом алгоритме действительно нет переполнения.