607156

26.12.2020 12:19

Информатика

Есть ответ 👍

На 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 часов – что неприемлемо по требованию заказчика. *** не забудьте разместить полную копию своего решения в дубль- для получения обещанных 150 . внимание аккаунты пользователей, публикующих "спам" или "ответы не в тему" в моих – подвергаются жёсткой проверке, чистке, и, в конечном счёте, я стараюсь добиваться удаления таких аккаунтов. все творческие люди – welcome!