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

move-семантика, конечно, усложняет, но читать ее всё равно относительно просто.
mihaild
+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, получаем ответ (вроде бы совпадающий с вашим).
mihaild
+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) операций. Правда константа получается куда лучше.
Ну и если делать более интеллектуальное длинное умножение, то и асимтотика получится лучше.

mihaild
–1
Очевидно что за o(logN) возвести в N-ю степень нельзя, т.к. O(logN) операций уйдет только на чтение показателя.
mihaild
0
В данном случае — да. Поэтому написано «потенциально» (на практике — в случаях, когда тяжелые объекты захватываются по значению).
mihaild
0
Где вы тут 1 байт увидели?
mihaild
+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.


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

Очевидно потому что авторы конкурирующего кода на С++ умеют писать на плюсах хуже, чем авторы V8 (или какой движок JS там использовался).
mihaild
+1
>из скорости дебажной версии вообще не следует ничего о скорости релизной
правда
>более того, нет никакого практического смысла бенчмаркить и оптимизировать скорость работы дебажной версии
неправда
>шаги в смысле шаги пошаговой отладки
>ваши дебажные шаги все равно медленнее любого цикла
Сформулируйте точнее: что именно медленнее чего? (какие отрезки времени больше каких?)
mihaild
0
Что такое «дебажные шаги»?
(ну и хотите я вам напишу код, который в 100 раз ускоряется что в дебаге что в релизе при замене постинкремента преинкрементом?)
mihaild
+3
А могут и не оптимизировать. Зачем раскладывать лишние грабли там, где их дешево избежать?
mihaild
+2
Воообще и в релизе может быть разница. Редко, но бывают ситуации, когда итератор тяжелый и копировать его дорого.
mihaild
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й орел] — т.е. вероятности отличаются, хотя вероятность получить орла в каждой позиции одинакова.
mihaild
+1
Вопрос "почему" в общем случае задавать вообще бессмысленно.
Можно задавать вопрос "как доказать". Я конечно могу привести доказательство того, что существует ровно одно простое число, запись которого в десятичной системе исчисления заканчивается на 2, но вам точно оно надо?)
mihaild
0
И чем вам поможет знание этого распределения для факторизации? (если можно быстро факторизовать, зная последние цифры — можно просто их перебрать)
mihaild
0
В долгоиграющей стратегии в какой игре?
mihaild
0
Про 2 и 4 результат доказан, и любой человек в теме на вопрос "сколько раз встречается 2" сходу ответит правильно. А вот на вопрос "как соотносятся 9 и 7 среди последних цифр простых чисел" — возможно, не ответит (хотя может быть специалистам по ТЧ ответ и очевиден; надо поймать такого и допросить).
mihaild
+3
А какие игры зависят от распределения последней цифры простых чисел?
mihaild
+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.
mihaild
+3
И 3-way тоже имеет квадратичную сложность на некоторых наборах.
mihaild
0
А вы не пробовали читать комментарий полностью прежде чем отвечать?
Там написано "нет архиватора, сжимающего любую последовательность".
Проблема в том, что размер разархиватора зависит от архитектуры, от ОС и т.д.

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

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

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

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

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

(я не синус с косинусом перепутал, я мнимую единицу вместе с (a-b) в знаменателе потерял)
mihaild
0
В этой задаче есть непонятный термин «максимально допустимое отклонение».

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

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