Помогите написать класс

[CRobin]

Здравствуйте. Есть таблица с тремя полями key1, key2, value. Оба поля key1 и key2 являются не зависимыми друг от друга уникальными ключами. По ключу key1 происходит добавление/считывание/обновление записи, это служебное поле репликации (техноческий ключ), а по ключу key2 происходит только считывание данных, это идентификатор данных в системе (логический ключ). Количество записей в таблице не определено, но может колебаться в диапазоне от нескольких десятков, до нескольких сотен записей, не более того. Задача в том, чтобы обеспечить максимально возможную скорость считывания и записи данных в многопоточном окружении. Одновременно к таблице обращаются десятки потоков, скорость выполнения каждой операции не должна превышать несколько микросекунд. Скорость критически важна. Буду благодарен тому, кто возьмется подсказать как решить эту задачу.

[resident]

Обращений по 1 и по 2 одинаковое количество?
Удаление не требуется?
Примеры ключей может приведете?

з.ы. А база данных не подходит?

[CRobin]

База данных не обеспечивает требуемой скорости. Удалось отчасти решить задачу через использование указателей, для key2 просто создается дополнительный массив типа key2=>Key1, а сими данные кладутся в массив key1=>Val. Проблема остается в том, что ключи Key1 и Key2 имеют тип Int64 (примеры 1742123456..1742123789), соответственно массивы с такими ключами не помещаются в память. На данный момент вручную объявляю статические массивы с учетом диапазона, в котором могут быть ключи

Код: Выделить всё

elems : array[1742111111..1743111111] of record

. Если ли способ динамически объявить этот массив так чтоб low(elems) был 1742111111 а не 0?

[Mirage]

Элементарно же.
Храним в массиве запись (key1, key2, value).
Заводим две хеш-таблицы, отображающие key1 и key2 в индекс в массиве с value.
Т.е. Int64 => Integer.
При считывании, просто получаем по ключу индекс и отдаем из массива по индексу.
При добавлении записи, сперва добавляем в массив с value, затем добавляем индекс в хеш-таблицы.
При обновлении записи, если обновляется только value, но не ключи, просто обновляем value в массиве.
Если обновляется также ключ, то удаляем из хеш-таблицы старый и добавляем новый.
С удалением сложнее: например, удаляем ключи из хеш-таблиц и помечаем как-нибудь в массиве, что запись удалена удаленную.
Время от времени проходимся по всей структуре и перестраиваем ее так, чтобы не было дырок. Небольшой размер позволяет.
Все операции атомарны, например, внутри критической секции.

Есть и другие варианты, в зависимости от недостающих деталей:
как распределены ключи, каков характер доступа, т.е. что чаще - считывание, добавлени, удаление

Если ли способ динамически объявить этот массив так чтоб low(elems) был 1742111111 а не 0?

Да пусть будет 0, можно же прибавлять смещение к индексу, раз оно известно.

[resident]

На данный момент вручную объявляю статические массивы с учетом диапазона, в котором могут быть ключи

Этот диапазон будет изменятся?

Если ли способ динамически объявить этот массив так чтоб low(elems) был 1742111111 а не 0?

Зачем динамически?

Добавлено спустя 1 минуту 15 секунд:

соответственно массивы с такими ключами не помещаются в память

Какое ограничение памяти на это?

Добавлено спустя 12 минут 10 секунд:

С удалением сложнее

Вроде удалять не нужно.

[Pavia]

Наймите студента. Он вам всё сделаете.
Задача простая. В ваше ТЗ вписывается массив и линейный поиск.
Если всё же размеры изменяются. То тогда двусвязный список.
А если нужен максимум скорости, то деревья.
Всё это уже описано в книгах про структуры данных и алгоритмы.

[resident]

Pavia
Если уж начал теоретизировать, так рассказывай с самого начала "Человек произошел от обезьяны ... и т.д.".

[CRobin]

При добавлении записи, сперва добавляем в массив с value, затем добавляем индекс в хеш-таблицы.

массив с value в считанные минуты сохрет всю память, поскольку самих обновлений по key1 приходит слишком много (ограничение ширина интернет канала и возможности tcp стека)

Да пусть будет 0, можно же прибавлять смещение к индексу, раз оно известно.

как раз на этом решении я и остановился, но сейчас нахожу проблему, поскольку для использования смещения, нужно точно знать минимальное значение key1

Этот диапазон будет изменятся?

диапазон значений key1 и диапазон значений key2 может изменятся

Зачем динамически?

Потому что лиапазон значений ключей может изменятся

Какое ограничение памяти на это?

для хранения даже одного массива array[int64] of string просто посчитайте сколько нужно для этого памяти

Наймите студента. Он вам всё сделаете.

Студент конечно сделает, но строчки задания, где написано, что скорость не должна превышать микросекунды для него скорее всего это будет пустой звук.

Задача простая. В ваше ТЗ вписывается массив и линейный поиск.

Не подходит ни линейный поиск ни деревья, увы.

[Mirage]

массив с value в считанные минуты сохрет всю память, поскольку самих обновлений по key1 приходит слишком много (ограничение ширина интернет канала и возможности tcp стека)

Массив с value растет только при добавлении элемента. При обновлении в нем просто изменяется значение на новое.

Количество записей в таблице не определено, но может колебаться в диапазоне от нескольких десятков, до нескольких сотен записей, не более того.

Это говорит о том, что добавлений не много.

[resident]

массив с value в считанные минуты сохрет всю память, поскольку самих обновлений по key1 приходит слишком много (ограничение ширина интернет канала и возможности tcp стека)

Кхе, а к чему здесь вообще сторонний массив?
Также две хеш таблицы.
В первой по 1-му ключу искать связный список и в нем уже копаться ища нужную запись. Список-массив можно и сортировать при вставке для пущей скорости.
Во второй будет таким же образом хранится зависимость 1-го ключа от 2-го.

для хранения даже одного массива array[int64] of string просто посчитайте сколько нужно для этого памяти

Это понятно, вы сколько можете выделить на решение?

Добавлено спустя 11 минут 32 секунды:

Время от времени проходимся по всей структуре и перестраиваем ее так, чтобы не было дырок.

Дырки от удаленных в массиве?

[Mirage]

Дырки от удаленных в массиве?

Да. Если удалений нет, то это не нужно и такой вариант самый быстрый.
Если удаления нужны, то лучше действительно только хэшмапы оставить, одна отображает key1 на запись с данными, другая key2 на key1.

[resident]

Ok

[CRobin]

Массив с value растет только при добавлении элемента. При обновлении в нем просто изменяется значение на новое.

Прошу прощения, недопонял сразу. Действительно, решение со всех сторон оптимально, остается только каким то образом выяснить минимальные значение key1 b key2 для того чтоб делать offset.

[Mirage]

для того чтоб делать offset.

key1 и key2 используются как ключи в хеш-мапах. Поэтому им никакой offset не требуется. Требуется приличная хеш функция для int64.
Массив value растет постепенно, индекс очередного элемента кладется в хеш-мапы. Offset также не требуется.

[CRobin]

На данный момент воспользовался вашим советом

пусть будет 0, можно же прибавлять смещение к индексу, раз оно известно

и храню данные в двух массивах с ключами key = key - min(key). Запись/чтение до 1мкс на относительно слабой машине меня устраивает, благодарю за решение.