|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.11.2019, 00:07 | #1 |
Новичок
Джуниор
Регистрация: 19.11.2019
Сообщений: 0
|
Кеширующий сервер
Код на C# или Java
Дормидонт работает в компании, которая занимается обработкой больших данных. Обрабатываемые данные находятся где-то в распределенной системе. Количество различных данных в системе ограничено и каждое данное имеет свой номер. Эти данные регулярно требуются различным клиентам и, поскольку время обращения к ним достаточно велико, для ускорения обработки информации Дормидонту поручено написать часть middlware — сервер-посредник, к которому и обращаются теперь клиенты за данными. Так как система — распределенная, а сервер — нет, все требуемые данные на сервер не помещаются, но он имеет возможность запоминать результаты своих запросов к распределенной системе. Для этого на сервере выделена ограниченная память на N запросов. Важно, что клиент не имеет возможности обращаться к распределенной системе и результат запроса к распределенной системе всегда должны оказаться на сервере. К большой радости Дормидонта оказалось, что самые крупные и значимые клиенты всегда обращаются за одними и теми же данными в одном и том же порядке, так что у него есть последовательность запросов. Дормидонт придумал такой алгоритм, что как можно большее количество запросов исполняется из кеша сервера, без обращения к распределенной системе. Придумаете ли вы что-то подобное? Формат входных данных: На вход программы подается размер памяти под кеширование запросов 1 ≤ N ≤ 100000, количество запросов 1 ≤ M ≤ 100000 и ровно M запросов с номерами 0 ≤ Ri ≤ 1018 . Количество различных номеров запросов ограничено и не превосходит 100000. Формат выходных данных: Требуется вывести одно число: сколько раз пришлось обратиться к распределенной системе за данными, отсутствующими в кеше. В начале работы кеш пуст Замечание В приведенном примере первые три запроса произойдут к данным под номерами 3, 1 и 4, так как их нет в кеше. Следующий запрос, 1, есть в кеше и обращения к распределенной системе не произойдет. Запросы 5 и 9 занесут их в кеш. Следующий запрос — 2 — в кеше отсутствует, но мы выкинем из кеша запрос 1 и запрос 2 займет его место. Далее, запрос 6 вытеснит из кеша значение 2(у нас есть информация о дальнейших запросах и из нее мы видим, что запрос под номером 2 больше не повториться и нет причин хранить его далее), после чего следующие три запроса удовлетворятся из кеша. Затем произойдет еще два вытеснения — 8 и 7. Итого 9 обращений к распределенной системе. Нетрудно установить, что меньше сделать нельзя. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Ищу человека который может создать работающий файл обработки платежей по системе (сервер-сервер). Фаил должен быть .php, код должен быть написан в JSON или C++ | Stop3 | Фриланс | 2 | 29.11.2018 20:19 |
Помогите, пожалуйста, переписать код приложения по TCP клиент-сервер в UDP клиент - сервер... | KhNJu | C/C++ Сетевое программирование | 3 | 12.03.2017 23:43 |
Qt , COM и OPC сервер | utang | Qt и кроссплатформенное программирование С/С++ | 0 | 23.10.2013 13:54 |
Кеширующий прокси на основе IndyHttpProxyServer | cardon | Работа с сетью в Delphi | 0 | 21.09.2012 20:16 |
Сервер что это??? | VintProg | Работа с сетью в Delphi | 34 | 20.07.2010 08:42 |