Pull to refresh
55.5
Karma
0
Rating
Денис Кильчичаков @augur

User

  • Followers 22
  • Following 7

Один бит сломал, другой потерял: задачка по передаче данных

Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.

Симметричное и асимметричное шифрование. Разбор алгоритма передачи шифрованных данных между серверами

Так сделать его достаточно длинным, чтобы сделать подбор экономически нецелесообразным?
Да, и, если не ошибаюсь, проще подобрать два ключа по 60 бит, чем один по 120.

Симметричное и асимметричное шифрование. Разбор алгоритма передачи шифрованных данных между серверами

Я правильно понимаю, что SIGNATURE_KEY попадает заранее на обе машины, притом по некоему безопасному каналу? А почему бы тогда не использовать его как постоянный ключ для симметричного шифра?

Почему вам нужно исправлять режим сна


Вот этот ученый много экспериментов ставил.
upd. Не вставляется ссылка, смотрите wiki: Мишель Сифр

UNIX-подобные системы содержат кучу костылей. Крах «философии UNIX»

UNIX – наихудшая операционная система, если не считать всех остальных.

(ц) почти Уинстон Черчилль

Цукерберг с женой пожертвуют $3 млрд, чтобы искоренить болезни к концу века

Это всё пережитки прошлой эпохи, до введения read&comment учеток. В ту пору Хабр выгодно отличался от того же ЛОРа тем, что читая комментарии, не нужно было прогонять каждый из них через ментальный детектор троллинга и трешовости.
Теперь читаешь все эти сотни комментариев к статьям о вакцинах, астрологии, ГМО, религиях, и не знаешь, то ли плакать, то ли смеяться, то ли просто /facepalm делать.

Решаем головоломки шаманов в World of Warcraft генетическим алгоритмом

К сожалению, это не генетический алгоритм. Результатом работы генетического алгоритма будет являться решение, подходящее для любого набора входных данных (в Вашем случае — игрового поля со случайным состоянием ячеек). Вы же ищете решение для конкретного поля перебором с эволюционной эвристикой. Скромно рекомендую для ознакомления эту статью.

Frontend-разработчики должны быть в теме всего

Хорошая статья, единственное замечание:


article.body.replace(/[Ff]rontend[-]?[\s]*/g, "");
//TODO capitalize next word in proper cases

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Оригинальный стиль изложения, интересная идея, но где самое вкусное — реальные замеры производительности в сравнении с классическими структурами?

Нейронная оборона: запись альбома-посвящения Егору Летову при помощи нейросетей

Сначала решил, что тут и голос и музыка синтезированы. А оказывается, только тексты. Тогда прорыв отменяется.

Питерцы чемпионы мира! Не хоккеем, так программированием

Думаю, здесь имел место сарказм (без тега).

Генетическое программирование («Yet Another Велосипед» Edition)

в том числе новомодные вроде нейросетей

Но ведь ИНС уже более 50 лет, и они многократно доказывали свою эффективность. Практически всё современные реализации распознавания образов работают на ИНС, и позволяют решать задачи, которые нам и не снились раньше.
В комментариях выше есть замечательные примеры практического применения концепции ГА.


Никто не говорит о данных методах как о панацее, "серебрянной пуле" и т.п. Но они реально небесполезны, и это факт. Непонятно, почему находятся те, кто с этим по-прежнему спорит.


Что касается примера, использованного в статье — что поделать, на прорыв в кибернетике он не тянет :) С другой стороны, на простом примере, "на пальцах", легче доносить мысли и что-то объяснять.

Генетическое программирование («Yet Another Велосипед» Edition)

Вы, как человек, уже прочитавший серьезную литературу, не могли бы чуть более развернуто аргументировать свою позицию и привести доводы из указанного источника?

Генетическое программирование («Yet Another Велосипед» Edition)

Между ними всё же есть разница, на уровне генотипа, хоть и результат они выдают одинаковый. Я решил определять идентичность основываясь только на генотипе, иначе решения типа:


(x - x)
(0 / x)

признавались бы дубликатами. Хотя разность между их генотипами достаточно существенна, и разбегание результатов с большой долей вероятности наступит уже в следующем поколении.


Операция оптимизации в моём случае называется сокращением, и вынесена как один из вариантов мутации, по тем же соображениям:


((4 - 2) * 3)
6

Первое дерево может прийти ко второму за одну мутацию типа shift, применённую к операции верхнего уровня (умножению). Однако, пока это разные деревья, и у них, соответственно, разные возможные пути мутации.

Генетическое программирование («Yet Another Велосипед» Edition)

Точно! Вот о чем я забыл! Ещё в прошлом году, когда идея с генетическими алгоритмами была только в голове, в одном из экспериментов я планировал заново "изобрести" алгоритм быстого InvSqrt Кармака из Quake. Потом я, уже не помню почему, остановился на варианте с сортировками. А ведь InvSqrt действительно кажется более подходящей задачей для ГА.

Генетическое программирование («Yet Another Велосипед» Edition)

Ваша картинка:
image
Геном в первом эксперименте и представлен в виде дерева, например:


xp2 = Formula::PowerOperator.new(Formula::Variable.new(:x), Formula::IntConstant.new(2)) # (x**2)
xm3 = Formula::MultiplicationOperator.new(Formula::IntConstant.new(3), Formula::Variable.new(:x)) # (3*x)
xp_xm = Formula::SubtractionOperator.new(xp2, xm3) # ((x**2)-(3*x))
xpx = Formula::AdditionOperator.new(xp_xm, Formula::IntConstant.new(2)) # (((x**2)-(3*x))+2)
f = Formula::PowerOperator.new(xpx, Formula::FloatConstant.new(0.5)) # ((((x**2)-(3*x))+2)**0.500)

Да, возможно имело смысл обратиться к готовым решениям по сокращениям.
Спасибо за наводки, ознакомлюсь.

Генетическое программирование («Yet Another Велосипед» Edition)

Кажется стоит допилить сокращения таких штук

Вообще операция возведения в степень неожиданно много проблем вызвала. Я даже задумывался о том, включать ли её вообще. Отчасти поэтому, когда работал над сокращениями, не учел работу с ней


А что если в качестве ещё одного вида мутации константам добавить округление

Это и происходит в случае shift: константа может поменять свой тип с Float на Int, и, таким образом, отбросить дробную часть.


Касательно сортировок. Да, согласен, оценка степени сортированности массива это первый из наиболее напрашивающихся критериев успеха. Но, повторюсь, неверные шаги сортировок искажают их до неузнаваемости. Тут можно провести аналогию с хеш-функцией, где решение это исходная строка, а результат оценивается по её хешу. Один символ в строке поменялся — хеш радикально преобразился.

Two languages, one Cup. Размышления о правилах RCC 2016

По правде говоря, я впервые со школьных времён принял участие в подобном мероприятии. Пришлось заново открывать для себя влияние стресса от столь экстремально сжатых сроков разработки на образ мышления. В обычных условиях, я всё это время потрачу только на вдумчивое чтение условий :)


Кстати, забавная вещь, только что выяснил, #rstrip работает немного быстрее #chomp, хотя для работы с STDIN рекомендуется второй вариант, как более каноничный. И что еще забавнее, вариант t.rstrip!.each_byte.with_index do… работает аж на 5%~ быстрее, чем t.rstrip.each_byte.with_index do ..., хотя казалось бы, второй вариант это более правильный method chaining и вообще Ruby way… Вероятно это объясняется, что при #rstrip! не копируется новая строка в памяти, а уменьшается счетчик длины текущей. Полезно наверное знать и помнить такие частности, но иногда излишнее заглядывание под капот отвлекает. Нужны менее дырявые абстракции :)


Кстати, сейчас поразмыслил, Ваш вариант хоть и проходит все указанные тесты, но имеет некоторую слабину: игнорируется передаваемое общее число комбинаций-попыток, и значит STDIN будет читаться до победного конца. Достаточно добавить одну лишнюю строчку в конце входных данных, не увеличивая передаваемое число комбинаций-попыток, и проверка провалится.

Two languages, one Cup. Размышления о правилах RCC 2016

Вы совершенно правы!


Как я уже писал выше, использование хешей в составленном тогда мною решении хоть и не оптимально, но не существенно — полное исключение работы с ним уменьшило время выполнения всего на 0.3с.
Полагаю, столь большое ускорение (с 1.4с -> до 0.4с) Вашего решения на Ruby, с фактическим приближением по скорости решения на C++, связано главным образом с оптимизацией работы с STDIN. (Ну и работа с байтами вместо символов, хотя привычнее рассуждать, раз строки, значит юникод, значит оперируем символами) В моём решении существовало два этапа — преобразование сырых данных из STDIN с сохранением в промежуточные переменные, и, непосредственно, работа с ними.


Ваше решение вселяет в меня надежду, что Ruby может потягаться в таких ситуациях с Си =)


P.S. чуть подправил compare.sh, а то не собирался

Two languages, one Cup. Размышления о правилах RCC 2016

Спасибо за развернутый ответ!
Согласен, что, скорей всего, можно укладываться в Time Limit и на "медленных" языках. Но тут встает дилемма — тратить дополнительное время на упреждающую сверх-оптимизацию, или сдавать обычное (не наивное, адекватное) решение с риском получить штрафное время за превышение. Лично для себя я сделал вывод, что олимпиады придётся писать на "быстрых" языках.


Что касается, оценки сложности, вот простейшая методика, которая мне видится жизнеспособной:


  • Допустим у нас три теста, входных данных в каждом из них n1=100, n2=1000, n3=10000
  • Решение прошло три теста за времена t1, t2, t3
  • И если t3/ t2 >> t2/t1 значит ресурсоемкость решения неудовлетворительная

P.S. Возможно, найду время и напишу прототип, чтобы проверить методику на практике.

Information

Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Registered
Activity