Определенная структура данных

Question

Ну, этот вопрос немного конкретен, но я думаю, что в нем есть какая-то общая идея, что я не могу его получить.

Допустим, я получил K серверов (это константа, по которой я знаю его размер). У меня есть программа, которая получает запросы, и каждый запрос имеет идентификатор и идентификатор сервера, который будет обрабатывать его. У меня n запросов - неизвестного размера и может быть любым числом.

Мне нужна структура данных для поддержки следующих операций в рамках данной сложности:

GetServer - функция получает идентификатор запроса и возвращает идентификатор сервера, который должен обрабатывать этот запрос в текущей ситуации, а не обязательно на исходном сервере (см. Ниже).

Сложность : O (log K) в среднем.

KillServer - функция получает в качестве входных данных идентификатор сервера, который должен быть удален, и идентификатор другого сервера, на который следует передавать все запросы удаленного сервера.

Сложность : O (1) в худшем случае.

-

Место сложность для всей структуры O (K + n)

-

Функция KillServer заставила меня задуматься об использовании Union-Find, поскольку я могу выполнить объединение в O (1) по запросу, но моя проблема - первая операция. Почему это LogK? На самом деле, независимо от того, как я «сохраняю» запросы, если я хочу получить доступ к любому запросу (скажем, это дерево AVL), поэтому сложность будет O (log n) в худшем случае и сказал, что я не могу предположить K > n (и, вероятно, K

Пытался обдумать это пару часов, но я не могу найти никакого решения. Известные структуры, которые можно использовать: дерево B +, дерево AVL, список пропусков, хэш-таблица, Union-Find, дерево рангов и, конечно, все основы, такие как массивы и тому подобное.

Answer 1

Рассмотрим структуру данных, состоящую из двух частей:

• конечной карты (дерево AVL и т. Д.) Из идентификаторов клиентов в job идентификаторов
• aструктура данных union-find для группировки идентификаторов заданий и маркировки каждой группы идентификатором сервера

Первоначально идентификаторы задания равны идентификаторам сервера.При удалении серверов серверы будут обрабатывать несколько заданий.

Другими словами, вы просто добавляете небольшую косвенную ссылку client -> job -> server, чтобы ваши операции касались только первой или только второй стрелки.

Answer 2

Можно попробовать использовать хеш-таблицу (где каждая запись хеш-таблицы является ссылкой на список):

Пусть размер хеш-таблицы будет наименьшим простым числом (p), котороебольше, чем K.

Тогда хеш-функция для requestID будет requestID % p.Это сделало бы сложность для GetServer O (1).Однако недостатком этого является отсутствие балансировки идентификаторов requestID.

Answer 3

Union-find, начиная с запросов, разделенных сервером, должен работать.Вы начинаете с каждого запроса, указывающего на его сервер, затем объединяете серверы (а не запросы).Таким образом, амортизированная стоимость GetServer будет O (альфа (K)), а не O (альфа (n)), где O (альфа (K)) << O (log K).