Предложение структуры данных для бизнес-требований

Question

Моя структура записи выглядит следующим образом: - (Имя, Опция, StartNum, EndNum, Vacancy)

Имя, Опция, StartNum, EndNum образуют составные ключи структуры / таблицы.Таким образом, для данной комбинации из них будет только одна запись вакансии.

Образцы записей

ABC, X, 2,14,1
ADE, X, 3,8,0
AEF, Y, 1,12,2
ERF, X, 12,13,17

Может быть:

1. 250-300 имен

2. для каждого имени 20-30 параметров

3. для каждого варианта 1-45 StartNum

4. Для каждого StartNum 1-14 EndNum

5. Для каждой комбинации указанных выше записей будет только одна запись для вакансии.

Таким образом, может быть максимум 5 670 000 (300 * 30 * 45 * 14) записей

Быстрые операции для поддержки

1. Поиск по составному ключу, т. Е. (Имя + Опция + StartNum +EndNum) и извлеките его значение записи Vacancy
2. Для заданного имени, опции и номера найдите и удалите записи, имеющие заданные имя, опцию и начальный номер <= Number <= EndNum </li>

Может ли кто-нибудь предложить подходящую структуру данных для моих вышеупомянутых требований?т.Операция построения структуры данных может быть медленной, так как она выполняется в автономном режиме, но вышеупомянутые две операции должны быть очень очень быстрыми.

Спасибо,
Harish

Answer 1

Я бы создал хеш-карту на основе кортежа (Имя, Опция).Для каждой из этих комбинаций может быть простой список, упорядоченный по (StartNum, EndNum).Вставка в этот список будет иметь размер O (N), но вы знаете, что размер довольно мал.Другим вариантом может быть сбалансированное двоичное дерево поиска или список пропусков.

Если у вас хороший хеш (который не должен быть сложным, должны работать стандартные), временная сложность для извлечения будет O (1 + log (| StartNum | * | EndNum |)).

При поиске согласно пункту 2. вы проверяете все значения с StartNum <= Number, имеют ли они соответствующий EndNum. </p>

Answer 2

Хеш-карта должна хорошо служить вашим целям. Вам просто нужно выяснить, как создать хороший хеш для составного ключа. Если у вас уже есть хэши для отдельных элементов, вы можете объединить их, используя простой XOR .