• Тонкости Компиляторов. Почему в классах с++ не требуется объявление функции до вызова?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Там явно больше одного прохода.

    Правила видимости функций растут еще из Си. Не знаю конкретно о чем думали, но сделали точно также и в Си++. Когда стали вводить классы от этого наследия отказались, ведь в Си никаких классов и методов нет.
    Ответ написан
    Комментировать
  • Как получается формула N*(N-1) / 2?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ну вы подставьте в формулу число. Допустим, N=3: 1+2+3 = 6. N(N-1)/2= 3*2/2 = 3. Не сходится!
    Правильная формула, все-таки N(N+1)/2.

    А разница в том, что в учебнике получается сумма от 1 до N-1. Т.е. в формулу прогрессии от 1 до N надо подставить N-1. Вот и получается (N-1)(N-1+1)/2 = (N-1)N/2
    Ответ написан
    1 комментарий
  • Существуют ли алгоритмы сжатия случайных данных с конечным алфавитом?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Очень мешает ограничение на фиксированный выходной алфавит, если в этом алфавите не степень двойки символов (как для цифр от 0 до 9). Так-то многие алгоритмы сжатия пользуются тем, что можно записать минимально возможную единицу информации - один бит. Иначе неэффективно сжимается. А на случайных данных без какой-то структуры и с большой энтропией и так все хреново работает.

    Советую посмотреть в сторону Burrows-Wheeler transform и потом попробовать RLE или LZ присобачить сверху. Может, ваши данные будут им хорошо сжиматься.

    Еще вам тут сильно помогло бы что-то вроде Base64 encode/decode. Допустим у вас k символов в алфавите. Значит каждый символ несет log_2(k) бит. И если у вас символов N, то ваша входная строка содержит N*log_2(k) бит информации. Округлите это число вверх и сгенерируйте столько битов. Это фактически преобразование из k-ичной системы счисления в двоичную. На больших строках будет тормозить, потому что пока мне не очевидно, как для произвольного k делать преобразование быстро, а не делить большое число на 2 с остатком. Если только у вас k не степень двойки, тогда как в base64 можно быстро преобразовывать по блокам.

    Потом можно эту битовую строку сжать каким угодно алгоритмом (разбить на блоки, скажем, 8 бит и хоть хаффманом, хоть lz). Потом надо сжатую битовую строку преобразовать назад в k-ичную систему счисления.

    Можно комбинировать сжатие на исходном тексте и запись произвольной битовой строки в вашем алфавите. Например после BW-transform вы гоните LZ на тексте из цифр. LZ для эффективности надо уметь писать произвольные битовые строки. Вот вы где-то в памяти отдельно собираете новые символы, которые замыкают новые строки-эталоны (цифры в вашем примере), и отдельно битовую строку. Потом эту строку переведите в k-ичную систему счисления и запишите перед просто символами (как-то закодировав ее длину в скольки-то первых символах заголовка).
    Ответ написан
    Комментировать
  • Как зайти в геймдев с 3d и архитектурой?

    vabka
    @vabka
    Токсичный шарпист
    Дизайн уровней - это больше про геймплей, а не про художественный вкус.

    Но вообще, почему бы не поискать вакансии?
    Какой-нибудь 3d environment artist
    Ответ написан
    2 комментария