Задача на 150 баллов

!!!! Внимание !!!! Аккаунты пользователей, публикующих "спам" или "ответы не в тему" в моих заданиях – подвергаются жёсткой проверке, чистке, и, в конечном счёте, я стараюсь добиваться удаления таких аккаунтов.

!!!! Аккаунты двух пользователей уже были удалены только на этом задании !!!!

Все творческие люди – Welcome!


: : : ЗАДАЧА : : :

Для работы некоторого облачного сервиса, на высокоскоростном SSD-RAID диске выделяется пространство размером 4 ГБ. Блок данных размером в 4 КБ считается минимальным, так что если в какой-то из байтов такого блока будет записана какая-то информация – блок считается полностью занятым. Блоки данных пронумерованы пятёрками шестнадцатеричных чисел от нуля до xFFFFF. В эти блоки данных некоторым образом записывают разнородную информацию: это может быть текстовый, графический, мультимедийный и пр. типы данных. Количество различных типов данных может достигать нескольких тысяч. Каждому типу данных однозначно сопоставлено целое число, которое записано в первые два байта каждого блока данных.

Известно, что когда несколько подряд идущих блоков данных содержат однотипную информацию – сервис работает быстрее. Подпоследовательности нескольких подряд идущих блоков однотипной информации удобно называть кусками данных. Чем чаще встречаются такие скомпонованные подпоследовательности (куски данных) – тем выше скорость работы всего сервиса. И наоборот, когда все блоки данных содержат тип данных, отличный от типа данных в соседних блоках – сервис работает с наименьшей скоростью, при этом, очевидно, количество кусков данных равно числу 4-килобайтных блоков.

Для текущей оценки потенциальной производительности сервиса, специальный внутренний модуль сервиса (СВМС) после каждой перезаписи данных определяет состояние их размещения, подсчитывая число W кусков данных в пространстве дисковой памяти, выделенной под сервис. Когда число W достигает некоторого порогового значения (которое настраивает системный администратор) – сервис дожидается времени, когда им пользуется минимальное число пользователей и производит высокоуровневую дефрагментацию, минимизируя число W кусков данных, так чтобы сервис снова работал максимально быстро.

Необходимо составить текстовое описание алгоритма СВМС, который мог бы производить не дольше чем за 10 секунд – миллион оценок числа W кусков данных. Предполагается, что под работу СВМС выделяется ресурс производительности – не более 100 млн. операций в секунду и 200 МБ оперативной памяти.

Для тестирования программы, написанной по алгоритму, который необходимо представить в ответе к заданию, заказчик СВМС будет подавать на его вход некоторую стартовая конфигурацию размещённых данных в виде последовательного перечисления типов данных, заполняющих все 4-килобайтные блоки в 4-Гигабайтном пространстве дисковой памяти, а кроме того – тестовый поток из одного миллиона описаний перезаписи блоков, в виде строк, в каждой из которых будут содержаться два числа: первое – шестнадцатеричный адрес блока данных в формате xZZZZZ, и второе – номер типа данных (двухбайтное целое число), которые записываются в 4-килобайтный блок с указанным в первом числе адресом.

Процесс записи данных в 4-килобайтные блоки можно считать почти мгновенным, к тому же это неизбежные и неустранимые затраты, так что время записи вообще не нужно учитывать при составлении алгоритма. Главная задача СВМС – постоянная переоценка числа W кусков данных.

Формат описания алгоритма должен носить максимально абстрактный характер, т.е. не подразумевается подробное изложение преобразования шестнадцатеричных чисел и т.п. Тем не менее, алгоритм должен решать поставленную задачу в условиях жёстко оговоренных параметров времени/скорости/производительности. Для описания алгоритма было бы удобно использовать следующие обозначения:
{X} – множество адресов блоков данных;
Y[X] – тип данных в адресуемом блоке;
W[i] – оценка числа кусков после i-ой перезаписи.

*** переоценка числа W кусков данных путём полного перебора заголовков блоков данных после каждой перезаписи, очевидно, потребовала бы триллион операций, т.е. около 3 часов – что неприемлемо по требованию заказчика.

*** не забудьте разместить полную копию своего решения в дубль-задаче znanija.com/task/17546460 для получения обещанных 150 баллов.

!!!! Внимание !!!! Аккаунты пользователей, публикующих "спам" или "ответы не в тему" в моих заданиях – подвергаются жёсткой проверке, чистке, и, в конечном счёте, я стараюсь добиваться удаления таких аккаунтов.

Все творческие люди – Welcome!

Что касается времени, 10 секунд по 100млн операций -> млрд операций, по 100 операций на каждую оценку, так что должно хватить

Всё отлично! 100 операций на оценку точно хватит.

Добавье копию своего решения в копию задачи znanija.com/task/17546460 . Я же всё таки 150 баллов обещала.