Задача на 150 баллов !!!! Внимание !!!! Аккаунты пользователей, публикующих "спам" или

Задача на 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!