Здравствуй!
Предлагаю в качестве тренировки для следующую задачку:
Общаются между собой две машины. Шлют друг другу цифровые данные, натурально нули и единицы. Только канал между ними не очень: биты регулярно то искажаются, то пропадают вовсе. Допустим, наш канал из 20 бит в среднем один бит ломает, другой теряет. А теперь пишем алгоритм, наиболее оптимально эти данные передающий.
Нужно найти компромисс между оверхедом над полезной нагрузкой сети, и временем работы передающей и принимающей машин.
Вы скажете, серьезные ребята из IEEE и смежных организаций уже всё давно придумали, и будете правы. Но когда это мешало переизобретать, just for lulz? И вылезти ненадолго из зоны комфорта надежных и простых сокетов (Не подсматривая какие-нибудь RFC)? Тем более, делать это будем на JavaScript, в браузере, без сторонних библиотек, еще желательно чтобы на один экран влезло:
Понимаю предвзятое отношение многих к JavaScript, однако его единственного можно за 5 минут встроить в браузер и дать возможно редактировать и исполнять. Несложный базовый синтаксис, пишешь будто на псевдкоде.
Весь код исполняется локально. Подключен CodeMirror для редактора кода.
Пишем содержимое двух функций, периодически вызываемых на передающей (Sender Source) и (Receiver Destination) машинах.
В нашем распоряжении контекст this, имеющий аж 5 методов:
var runs = this.counter();Счетчик того, сколько раз была вызвана основая функция. Помогает ориентироваться во времени, для отсчета таймуатов например.
var frame = this.getPayload(n);
Доступен на передающей машине. Считывает и возвращает следующие n бит полезной нагрузки.
this.write(frame);
Передает frame, являющийся массивом бит, другой машине. Проходя по каналу передачи, сообщение, возможно, будет искажено.
var frame = this.read(n);
Считывает из входящего сетевого буфера до n бит. Если ничего нет, вернет пустой массив.
this.acceptPayload(frame);
Доступен на принимающей машине. Помещает frame в результирующий массив.
Если основная функция вернет true, значит она хочет быть вызвана еще раз в будущем. Иначе, машина завершает свое исполнение. На принимающей машине вызовется проверка целостности принятых данных, а также подсчитается оверхед.
Я добавил несколько примеров исходного кода:
- Tutorial — чуть более подробное описание возможностей передающих и принимающих машин.
- No Corrections — простейший алгоритм, не следящей за целостностью передаваемых данных. Оверхед отсутствует, но целостность оставляет желать лучшего.
- Naive 900% Overhead — думаю, понятно из названия. Шлем не торопясь по одному биту, продублированному десять раз. Работает более-менее стабильно (хотя изредка целостность нарушалась), но оверхед по нагрузке сети 900%.
Между первой идеей и последней точкой этой статьи пока что еще прошло меньше 12 часов, так что не обессудьте, если что пропустил. Пишите, поправлю как можно оперативней.
Автор: Денис Кильчичаков
