• 0
    Кажется, что бывают вплоть до d400
    Настольные игры ЦРУ
  • +2
    Например, в турецком i (маленькое с точкой, U+0069, 1 байт в UTF8) преобразуется в İ (большое с точкой, U+0130, 2 байта в UTF8).
    Немного о строках в Си, или несколько вариантов оптимизировать неоптимизируемое
  • 0
    Проверить формальное доказательство относительно несложно (было бы, если бы они дали на него ссылку). Гораздо сложнее проверять неформализуемую часть — а именно формализацию (что они действительно доказывают «отсутствие утечек», например).
    Немного о строках в Си, или несколько вариантов оптимизировать неоптимизируемое
  • +2
    Очевидно, что ваш код, в отличии от кода стандартной библиотеки, не работает. Понятный неработающий код хуже непонятного работающего.
    Что приняли в C++17, фотография Бьярне Страуструпа и опрос для C++20
  • +1
    ИМХО с С++11 код во многих местах стал понятнее. range-based for и auto вместо страшных итераторов, using вместо typename упрощают жизнь новичкам.

    move-семантика, конечно, усложняет, но читать ее всё равно относительно просто.
    Что приняли в C++17, фотография Бьярне Страуструпа и опрос для C++20
  • +3
    Такие задачи легко решаются через лемму Бернсайда.
    Всего объектов (N — 1)^2 * N^{M — 2}. Группа инвариантных перестановок состоит их 4 элементов, неподвижных точек (для четного M):
    -у id (тождественной перестановки) (N — 1)^2 * N^{M — 2}
    -у T_1 (N — 1) / 2 * N^{M / 2 — 1}
    -у T_2 нету
    -у T_1 T_2 — (N — 1) / 2 * N^{M / 2 — 1}
    Делим сумму числа неподвижных точек на 4, получаем ответ (вроде бы совпадающий с вашим).
    Об одной комбинаторной задаче
  • +1
    N-е число Фибоначчи состоит из (с точностью до константы) N разрядов.
    Сложение двух N-разрядных чисел делается за (опять же с точностью до константы) N операций, так что реализация через сложение потребует O((1 + 2) + (2 + 3) +… + (N — 1 + N)) = O(N^2) операций.

    Если делать умножение длинных чисел наивным способом (за квадрат от числа разрядов), то нам понадобится O(1^2 + 2^2 + 4^2 +… + (N/2)^2) = O(N^2) операций. Правда константа получается куда лучше.
    Ну и если делать более интеллектуальное длинное умножение, то и асимтотика получится лучше.

    Обгоняем компилятор
  • –1
    Очевидно что за o(logN) возвести в N-ю степень нельзя, т.к. O(logN) операций уйдет только на чтение показателя.
    Обгоняем компилятор
  • 0
    В данном случае — да. Поэтому написано «потенциально» (на практике — в случаях, когда тяжелые объекты захватываются по значению).
    Универсальный конструктор Auto
  • 0
    Где вы тут 1 байт увидели?
    Универсальный конструктор Auto
  • +2
    auto f = [](){}; //указатель на функцию
    

    #include <type_traits>
    
    int main() {
        auto f1 = [](){};
        static_assert(std::is_pointer<decltype(f1)>::value, "f1 is not pointer");
    }

    fp.cpp:5:5: error: static_assert failed "f1 is not pointer"
        static_assert(std::is_pointer<decltype(f1)>::value, "f1 is not pointer");
        ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1 error generated.


    Это всё-таки лямбда, а не указатель (в частности, штука с потенциально дорогим копированием).
    Универсальный конструктор Auto
  • 0
    Я вообще не занимаюсь мобильными приложениями. Но вы почему-то делаете вывод, что то, что у многих пишущих на данном языке руки растут не оттуда — существенный недостаток языка.
    Почему JavaScript работает быстрее, чем С++?
  • +2
    Хотите я сделаю еще большие тормоза на любом другом языке?
    Почему JavaScript работает быстрее, чем С++?
  • +12
    Почему JavaScript работает быстрее, чем С++?

    Очевидно потому что авторы конкурирующего кода на С++ умеют писать на плюсах хуже, чем авторы V8 (или какой движок JS там использовался).
    Почему JavaScript работает быстрее, чем С++?
  • +1
    >из скорости дебажной версии вообще не следует ничего о скорости релизной
    правда
    >более того, нет никакого практического смысла бенчмаркить и оптимизировать скорость работы дебажной версии
    неправда
    >шаги в смысле шаги пошаговой отладки
    >ваши дебажные шаги все равно медленнее любого цикла
    Сформулируйте точнее: что именно медленнее чего? (какие отрезки времени больше каких?)
    Главный вопрос программирования, рефакторинга и всего такого
  • 0
    Что такое «дебажные шаги»?
    (ну и хотите я вам напишу код, который в 100 раз ускоряется что в дебаге что в релизе при замене постинкремента преинкрементом?)
    Главный вопрос программирования, рефакторинга и всего такого
  • +3
    А могут и не оптимизировать. Зачем раскладывать лишние грабли там, где их дешево избежать?
    Главный вопрос программирования, рефакторинга и всего такого
  • +2
    Воообще и в релизе может быть разница. Редко, но бывают ситуации, когда итератор тяжелый и копировать его дорого.
    Главный вопрос программирования, рефакторинга и всего такого
  • 0
    Нет, вероятность события «первый раз строка встретилась в позиции N» не выводится однозначно из «вероятность того, что строка встретилась в позиции i».
    Хотя бы элементарно P(строка встретилась первый раз в позиции 2) = P(строка не встретилась в позиции 1) * P(строка не встретилась в позиции 2 | строка не встретилась в позиции 1) — и второй множитель в общем случае не равен P(строка не встретилась в позиции 2).

    Например, если нам гарантируется, что на одной монетке орел и решка при бросках чередуются, а вторая — честно случайная, то вероятность того, что на 1й орел выпадет раньше, чем на второй, равна 1/4 [при первом броске на 1й орел, на 2й решка] + 1/8 [при первом броске на 1й орел, на 2й орел; при втором броске на 2й решка] = 3/8, а вероятность того, что на 2й орел выпадет раньше 1/4 [при первом броске на 1й решка, на 2й орел] — т.е. вероятности отличаются, хотя вероятность получить орла в каждой позиции одинакова.
    Задача про обезьян и бесконечность
  • +1
    Вопрос "почему" в общем случае задавать вообще бессмысленно.
    Можно задавать вопрос "как доказать". Я конечно могу привести доказательство того, что существует ровно одно простое число, запись которого в десятичной системе исчисления заканчивается на 2, но вам точно оно надо?)
    Американские математики обнаружили ранее неизвестное свойство простых чисел
  • 0
    И чем вам поможет знание этого распределения для факторизации? (если можно быстро факторизовать, зная последние цифры — можно просто их перебрать)
    Американские математики обнаружили ранее неизвестное свойство простых чисел
  • 0
    Про 2 и 4 результат доказан, и любой человек в теме на вопрос "сколько раз встречается 2" сходу ответит правильно. А вот на вопрос "как соотносятся 9 и 7 среди последних цифр простых чисел" — возможно, не ответит (хотя может быть специалистам по ТЧ ответ и очевиден; надо поймать такого и допросить).
    Американские математики обнаружили ранее неизвестное свойство простых чисел
  • +3
    А какие игры зависят от распределения последней цифры простых чисел?
    Американские математики обнаружили ранее неизвестное свойство простых чисел
  • +2
    Давайте немного переформулируем. Скажем, что Алиса, выкинув решку, уступает место Еве, которая выигрывает, как только выкинет орла. Пусть А, Б и Е — ожидание числа бросков для Алисы, Боба и Евы.
    Е = 1 + 1/2 Е [выкинута решка, которая Еве бесполезна] + 1/2 0 [выкинут орел — Ева выиграла]
    откуда Е = 2.

    А = 1 + 1/2 А [выкинут орел — Алиса начинает сначала] + 1/2 Е [выкинута решка — осталось выиграть Еве]
    т.е. А = 1 + А/2 + 1, откуда А = 4

    Б = 1 + 1/2 Б [выкинут орел] + 1/2 (1 + 1/2 Б [после орла выпала решка — всё сначала] + 1/2 0)
    откуда Б = 3/2 + 3/4Б, Б = 6.
    Американские математики обнаружили ранее неизвестное свойство простых чисел
  • +3
    И 3-way тоже имеет квадратичную сложность на некоторых наборах.
    Большой опрос по алгоритмам
  • 0
    А вы не пробовали читать комментарий полностью прежде чем отвечать?
    Там написано "нет архиватора, сжимающего любую последовательность".
    Проблема в том, что размер разархиватора зависит от архитектуры, от ОС и т.д.

    Как, собственно, вводится колмогоровская сложность — рассматривается фиксированный разархиватор, и берется сложность относительно него (мин. длина архива, который он распаковывает в данное слово). Затем оказывается, что существует "универсальный" разархиватор — который с точностью до константы не хуже любого другого.
    Проблема в том, что избавиться от этой константы разумными способами нельзя.
    Обстоятельно о подсчёте единичных битов
  • +2
    Вы же понимаете, что это невозможно прочитать?
    Обстоятельно о подсчёте единичных битов
  • 0
    Ну например я бы предполагал, что любой уважающий себя архиватор будет работать хотя бы не хуже, чем код Хаффмана, что уже почти гарантирует равномерность битового распределения.
    Обстоятельно о подсчёте единичных битов
  • +1
    Да, естественно можно подобрать данные, на которых архиватор выдаст строку из одних нулей. Но случайно это сделать (или наткнуться на то, что какой-то формат типично приводит к такому результату) — маловероятно.

    Не в 1 бит — потому что не бывает файлов в 1 бит.

    Вообще есть еще колмогоровский декомпрессор, который "сильно" улучшить нельзя. Правда соответствующий ему архиватор невычислим.
    Обстоятельно о подсчёте единичных битов
  • +3
    Вообще говоря, если вы действительно находите какую-то алгоритмически выразимую закономерность в результатах работы архиватора — то вы можете его улучшить. Т.к. вряд ли хорошие архиваторы можно улучшить нахаляву, то скорее всего закономерность кажущаяся.
    Если нет — предъявите конкретные числа.
    Обстоятельно о подсчёте единичных битов
  • 0
    У большинства последовательностей число 0 и 1 примерно одинаково. Более формально — доля последовательностей длины n, в которых меньше чем 0.4n (или 0.49999n, неважно) единиц, экспоненциальна мала.
    У биномиального распределения при p=0.5 энтропия максимальна — следовательно, если архиватор выдает другое распределение, его вход типично можно сжимать.
    Обстоятельно о подсчёте единичных битов
  • 0
    Конечно, сжать можно любую последовательность (для любого файла можно сделать архиватор, сжимающий этот файл в 1 байт). Нельзя сделать универсальный архиватор, сжимающий любую последовательность.

    Если вам неочевидно, что в случайном файле примерно поровну 0 и 1, то вы понимаете под случайным файлом что-то очень странное. Приведите свое определение, что ли.
    Обстоятельно о подсчёте единичных битов
  • +1
    Потому что хороший архиватор выдает "случайный" файл (иначе его можно было бы еще сжать). А в случайном файле обычно 0 и 1 примерно одинаково.
    Обстоятельно о подсчёте единичных битов
  • 0
    Нет, не следует, выше уже приведен пример (и непрерывность тут неважна — все интересные свойства остаются при прибавлении к распределению равномерного на отрезке [-10^-100; 10^-100] распределения, а сумма уже получится непрерывной).

    В такой формулировке задача корректна (есть неизвестное распределение; можно его обрезать по отрезку; нужно, чтобы сумма с вероятностью 90% попала в фиксированный отрезок). Проблема в том, что для некоторых распределений такого отрезка может и вообще не существовать.
    Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)
  • 0
    Не обратил внимания на масштаб( Да, разность синусов с разными коэффициентами аргумента так и выглядит (где-то одинаковая фаза, где-то разная).

    (я не синус с косинусом перепутал, я мнимую единицу вместе с (a-b) в знаменателе потерял)
    Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)
  • 0
    В этой задаче есть непонятный термин «максимально допустимое отклонение».

    1. Показали — из каких предположений?

    Логика — это про то, как выводить одни формальные утверждения из других. Вы пока что очень не хотите указывать никаких формальных посылок (чтобы из них можно было выводить следствия).
    Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)
  • 0
    Ну возьмите то же самое распределение, и размажьте вероятности с точек на отрезки длины 10^-10. Получится непрерывное распределение, с теми же особенностями.
    Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)
  • 0
    Интеграл для характеристической функции берущийся, он получается вида (e^{ita} — e^{itb}) / t = (cos(ta) — cos(tb)) / t + i * (sin(ta) — sin(tb)) / t. Что совсем непохоже на получающееся у вас.
    Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)
  • 0
    Это при условии, что масса конфеты распределена нормально.
    (и это получается дисперсия, а не «максимально допустимое отклонение», которое вообще непонятно что такое)
    Продолжение задачи о конфетах (или еще раз о Центральной Предельной Теореме)