Мой аргумент. Может быть немного перефразирую в том, что в
"Но, если бы не было побитовых операций, то на все разряды надо было бы O(32*n)=O(n)."
32 это не просто константа. По условию задачи почти все числа во входном наборе данных могут повторяться только p раз. Поэтому чем больше n, тем больше должна быть минимальная разрядность каждого числа. То есть у Вас не 32n, а plog(n)*n бит. И если считать в битах, то я согласен с оценкой в O(n), а, если в количестве значений входящего массива, то нет.
Пусть проблема решается для пятикратных повторов. Если взять число пусть даже в двоичной системе счисления, то для каждого шага сложения одной позиции по модулю 5 нужно сначала преборазовать число из входящего формата (предположим двоичного) в пятиричный. Правильно?
То есть Вам совершенно нормально, что математические концепции, которые пердназначены для описания эффективности алгоритмов в пределе (n -> inf в данном случае), используются для описания задачи с предпосылками, которые в общем-то устанавливают для n максимальное значение?
Если да, то, пожалуй, тут больше не о чем дискутировать. „Вы можете получить «Форд-Т» любого цвета, при условии, что этот цвет будет черным.“ — Генри Форд
Вот не поверите. Ровно то же обощение предложил в https://habr.com/ru/articles/764718/#comment_26019878, но пишут "что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти."
"Так что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти." Не имеют. Просто общее решение для представленного класса задач. Да еще и не для всех вариантов по повторениям (а только от 2 до 9), потому что я ленивый, а для демонстрации принципа этого должно быть достаточною. Про потребление памяти в задаче нет требований по минимизации. Только, что оно должно быть константным. Опять же. Как автор написал.
"Ну и ограничения с литкода автор не стал писать - там все числа умещаются в 32 бита и входной массив не менее минимальной необходимой длины." Ну не стал и не стал - я комментирую по написанному в статье. "Вы же в курсе, что для компьютера операция XOR, как и любые другие операции, уже происходят на бинарном представлении вне зависимости от того что вы пишите в своей программе. " Это все здорово только до тех пор, пока у Вас бинарный формат на входе И все умещается в разрядность процессора. О чем я собственно и пишу. В общем (с точки зрения математики или реализации на условном 8-битном МК) случае эту задачу не получится решить за O(n), потому что 1) используется XOR для которого принята условная константная производительность и потому что 2) входной формат не определен условиями задачи. Примечательно, что автор статьи сам напоминает, что "К сожалению, вы можете не знать какая вычислительная и пространственная сложность скрывается за библиотечными функциями. " Точно тот же аргумент работает и для операций типа XOR.
Я не уверен, что представленные решения первой и второй задачи имеют сложность O(n) кроме тех случаев, когда числа уже заданы в двоичной системе счисления (чего нет в условиях), поскольку XOR не получится сделать без преобразования систем счисления, а оно в свою очередь будет сложнее, чем O(n), потому что чем больше n, тем больше будет разрядность используемых в массиве уникальных значений. Да и сам XOR добавит log(n). Так что скорее всего эти решения имеют такую же сложность, что и преобразование систем счисления для чисел, которые не помещаются в аппаратный DEC2BIN целевой платформы.
Вот обобщенное решение для произвольного количества повторяющихся элементов и поиска неповторяющегося при помощи BASEN "XOR" преобразования.
Последние тренды от Норникеля это видимо как допускать халатность приводящую к экологическим катастрофам и как руководстуву компании не нести за это никакой отвественности.
«Давайте просто отключим эту дурацкую штуку fTPM hwrnd. Зачем кому-то использовать эту дрянь, если она есть на любой машине? Я не вижу ничего плохого в том, чтобы просто сказать: "Эта штука с fTPM не работает". Даже если в будущем это сработает — альтернативы ничем не хуже. Исправления AMD, которые мы видели и о которых сообщали разработчики, "очевидно, не оправдались"», — пояснил Торвальдс.
А было бы неплохо не использовать прямую цитату, если Вы обрезаете переведенный текст. Из КМК важного в опущенном тексте Линус предлагает максимум использовать fTPM во время загрузки в качестве источника дополнительной энтропии, но не в рантайме. Он так же не говорит ничего про наличие fTPM "на любой машине". Его предпложение переводится как: "Почему кто-либо будет пользоваться этой дрянью [fTPM], когда любая машина на которой ее [fTPM] предположительно починили (а это очевидино и оказалось неправдой по факту) так же имеет инструкцию ЦПУ rdrand, с которой нет проблем?"
Если загранпаспорт не истечет до получения нового гражданства, то вероятно обойтись только вопросами по поводу пункта анкеты на ВНЖ/гражданство "У меня есть судимость и/или меня подозревают в совершении преступлений да/нет". А если истечет, то проблем станет существенно больше, потому что без действующего загранника негражданин становится нелегалом независимо от того есть у него ВНЖ или нет.
Если человека преследуют за неуплату налогов, то скорее всего ему никто на новом месте жительства ничего из перечисленного не даст. Уклоняющихся от упалты налогов не любят нигде.
Ага. И был бы обязательный к исполнению кодекс программирования на MISRA C для всех. Не нравится - живите (на улице) без компуктера. А в Германии еще бы требовали обои на выбор из 3 стандартных цветов в зависимости от того в какой части города живет человек.
Ну вот примерно такое же произошло с ИТ - в общем-то ни один человек не "знает", что на самом деле происходит при запуске программы - и мнение, что можно это "знание" каким-то образом получить сродни позитивистской веры в "познаваемость мира" - думать конечно очень приятно, но смысла нет.
Вы правы. В силу того, что полупроводниковые устройства работают на эффекте квантового туннелирования действительно не возможно знать "что _на самом деле происходит ". Но это к делу и не относится. Автор, на сколько я понял статью, не предлагает знать что происходит, а предлагает знать вещи, которые влияют на то, как программа исполняется. Это благодаря стараниям инженеров, разрабатывающих процессоры и микроконтроллеры, в общем-то не большой список вещей и знать их программисту очень желательно, если программист рассчитывает использовать ресурсы доступной вычислительной техники ЭФФЕКТИВНО. Ну а если не рассчитвает, то можно и в майнкрафте Тюринг-полный компьютер замоделировать и там что-нибудь считать. Почему бы и нет?
Ну до некоторой степени вторые рейнджеры сами же активно пародировали первые. По-сути весь сюжет с доминаторами целиком основан на том, что после первой войны все расслабились и еще и сами начали устраивать эксперименты над захваченными Клисанами. Лично я прошел и первых и вторых с удовольствием, но новые механики во вторых реально расширили пространство кастомизации корабля, так что переигрывал только их после релиза.
Там в общем-то указано, но очень кратко. Это сделано через эмулятор box64 https://github.com/ptitSeb/box64 Ну и Wine/Proton, конечно, потому что Линукс.
Не знаю как в Канаде, а в Финляндии сделка может быть целиком устной и иметь силу с точки зреня суда. Так что эмодзи это уже письменный контракт со всеми обязательствами. А вот например, недвижимость (участки) требует много дополнительных действий и подтверждения каждой сделки судом.
Мой аргумент. Может быть немного перефразирую в том, что в
"Но, если бы не было побитовых операций, то на все разряды надо было бы O(32*n)=O(n)."
32 это не просто константа. По условию задачи почти все числа во входном наборе данных могут повторяться только p раз. Поэтому чем больше n, тем больше должна быть минимальная разрядность каждого числа. То есть у Вас не 32n, а plog(n)*n бит. И если считать в битах, то я согласен с оценкой в O(n), а, если в количестве значений входящего массива, то нет.
del.
Думаю я понял Ваш подход. Да, так получится O(n), если n это количество бит. Спасибо.
Пусть проблема решается для пятикратных повторов. Если взять число пусть даже в двоичной системе счисления, то для каждого шага сложения одной позиции по модулю 5 нужно сначала преборазовать число из входящего формата (предположим двоичного) в пятиричный. Правильно?
То есть Вам совершенно нормально, что математические концепции, которые пердназначены для описания эффективности алгоритмов в пределе (n -> inf в данном случае), используются для описания задачи с предпосылками, которые в общем-то устанавливают для n максимальное значение?
Если да, то, пожалуй, тут больше не о чем дискутировать. „Вы можете получить «Форд-Т» любого цвета, при условии, что этот цвет будет черным.“ — Генри Форд
Вот не поверите. Ровно то же обощение предложил в https://habr.com/ru/articles/764718/#comment_26019878, но пишут "что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти."
"Так что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти."
Не имеют. Просто общее решение для представленного класса задач. Да еще и не для всех вариантов по повторениям (а только от 2 до 9), потому что я ленивый, а для демонстрации принципа этого должно быть достаточною.
Про потребление памяти в задаче нет требований по минимизации. Только, что оно должно быть константным. Опять же. Как автор написал.
"Ну и ограничения с литкода автор не стал писать - там все числа умещаются в 32 бита и входной массив не менее минимальной необходимой длины."
Ну не стал и не стал - я комментирую по написанному в статье.
"Вы же в курсе, что для компьютера операция XOR, как и любые другие операции, уже происходят на бинарном представлении вне зависимости от того что вы пишите в своей программе. "
Это все здорово только до тех пор, пока у Вас бинарный формат на входе И все умещается в разрядность процессора. О чем я собственно и пишу. В общем (с точки зрения математики или реализации на условном 8-битном МК) случае эту задачу не получится решить за O(n), потому что 1) используется XOR для которого принята условная константная производительность и потому что 2) входной формат не определен условиями задачи.
Примечательно, что автор статьи сам напоминает, что "К сожалению, вы можете не знать какая вычислительная и пространственная сложность скрывается за библиотечными функциями. " Точно тот же аргумент работает и для операций типа XOR.
Я не уверен, что представленные решения первой и второй задачи имеют сложность O(n) кроме тех случаев, когда числа уже заданы в двоичной системе счисления (чего нет в условиях), поскольку XOR не получится сделать без преобразования систем счисления, а оно в свою очередь будет сложнее, чем O(n), потому что чем больше n, тем больше будет разрядность используемых в массиве уникальных значений. Да и сам XOR добавит log(n). Так что скорее всего эти решения имеют такую же сложность, что и преобразование систем счисления для чисел, которые не помещаются в аппаратный DEC2BIN целевой платформы.
Вот обобщенное решение для произвольного количества повторяющихся элементов и поиска неповторяющегося при помощи BASEN "XOR" преобразования.
https://gist.github.com/Kreastr/025a1fd08189d736fbe8fe3132a0cb1c
Последние тренды от Норникеля это видимо как допускать халатность приводящую к экологическим катастрофам и как руководстуву компании не нести за это никакой отвественности.
Доступ к информации это не доступ к развлекательным услугам и сервисам.
«Давайте просто отключим эту дурацкую штуку fTPM hwrnd. Зачем кому-то использовать эту дрянь, если она есть на любой машине? Я не вижу ничего плохого в том, чтобы просто сказать: "Эта штука с fTPM не работает". Даже если в будущем это сработает — альтернативы ничем не хуже. Исправления AMD, которые мы видели и о которых сообщали разработчики, "очевидно, не оправдались"», — пояснил Торвальдс.
А было бы неплохо не использовать прямую цитату, если Вы обрезаете переведенный текст. Из КМК важного в опущенном тексте Линус предлагает максимум использовать fTPM во время загрузки в качестве источника дополнительной энтропии, но не в рантайме. Он так же не говорит ничего про наличие fTPM "на любой машине". Его предпложение переводится как: "Почему кто-либо будет пользоваться этой дрянью [fTPM], когда любая машина на которой ее [fTPM] предположительно починили (а это очевидино и оказалось неправдой по факту) так же имеет инструкцию ЦПУ rdrand, с которой нет проблем?"
Штрафы копеечные, но их еще как-то оплатить надо кстати. В подсанкционных реалиях не везде будет удобно.
Если загранпаспорт не истечет до получения нового гражданства, то вероятно обойтись только вопросами по поводу пункта анкеты на ВНЖ/гражданство "У меня есть судимость и/или меня подозревают в совершении преступлений да/нет". А если истечет, то проблем станет существенно больше, потому что без действующего загранника негражданин становится нелегалом независимо от того есть у него ВНЖ или нет.
Если человека преследуют за неуплату налогов, то скорее всего ему никто на новом месте жительства ничего из перечисленного не даст. Уклоняющихся от упалты налогов не любят нигде.
Ага. И был бы обязательный к исполнению кодекс программирования на MISRA C для всех. Не нравится - живите (на улице) без компуктера. А в Германии еще бы требовали обои на выбор из 3 стандартных цветов в зависимости от того в какой части города живет человек.
Вы правы. В силу того, что полупроводниковые устройства работают на эффекте квантового туннелирования действительно не возможно знать "что _на самом деле происходит ".
Но это к делу и не относится. Автор, на сколько я понял статью, не предлагает знать что происходит, а предлагает знать вещи, которые влияют на то, как программа исполняется. Это благодаря стараниям инженеров, разрабатывающих процессоры и микроконтроллеры, в общем-то не большой список вещей и знать их программисту очень желательно, если программист рассчитывает использовать ресурсы доступной вычислительной техники ЭФФЕКТИВНО. Ну а если не рассчитвает, то можно и в майнкрафте Тюринг-полный компьютер замоделировать и там что-нибудь считать. Почему бы и нет?
Ну до некоторой степени вторые рейнджеры сами же активно пародировали первые. По-сути весь сюжет с доминаторами целиком основан на том, что после первой войны все расслабились и еще и сами начали устраивать эксперименты над захваченными Клисанами. Лично я прошел и первых и вторых с удовольствием, но новые механики во вторых реально расширили пространство кастомизации корабля, так что переигрывал только их после релиза.
Там в общем-то указано, но очень кратко. Это сделано через эмулятор box64 https://github.com/ptitSeb/box64
Ну и Wine/Proton, конечно, потому что Линукс.
Не знаю как в Канаде, а в Финляндии сделка может быть целиком устной и иметь силу с точки зреня суда. Так что эмодзи это уже письменный контракт со всеми обязательствами. А вот например, недвижимость (участки) требует много дополнительных действий и подтверждения каждой сделки судом.
Это уже есть в Ф2.