У вас есть 2 разных вопроса здесь:
- Как представить вашу структуру данных
- Как сделать его безопасным, в эффективном поместье
Ваша структура данных будет выполнять (20-80) x (2-8) операций чтения для каждой записи.
(1). Во-первых, давайте предположим, что ваш диапазон является структурой данных следующим образом
<code>
struct Interval
{
Interval(int start, int length)
: m_start(start),
m_length(length)
{}
int m_start;
int m_length;
int value; // Or whatever
};
Поскольку число операций чтения превышает количество записей, поиск должен быть быстрым, а изменения - нет.
Использование списка для вашей структуры данных означает O (N) поиск и O (1) модификацию - в точности наоборот.
Самым простым представлением вашей структуры является вектор. Если интервалы хранятся в отсортированном порядке, поиск - O (logN), а модификации - O (N).
Чтобы реализовать это, просто добавьте компаратор в интервал:
bool operator<(const Interval& rhs) const
{
return m_start < rhs.m_start;
}
Затем вы можете использовать std::lower_bound, чтобы найти первый интервал, равный или меньший вашему интервалу поиска в O (logN).
Следующим и предыдущим интервалом являются O (1) - уменьшать или увеличивать возвращаемый итератор.
Разделение интервала означает вставку нового элемента после текущего и настройку длины текущего - O (N).
Соединение двух интервалов означает добавление длины следующего к текущему и стирание следующего - O (N).
Вы должны reserve() иметь достаточно места в векторе для максимального количества элементов, чтобы минимизировать накладные расходы на изменение размера.
* 1 034 * (2). Следуя Кнуту, «
преждевременная оптимизация - корень всего зла ».
Одной блокировки чтения / записи на структуре, содержащей ваш вектор , скорее всего будет достаточно. Единственными возможными проблемами являются (2a) голодание писателя, поскольку читатели монополизируют блокировку, или (2b) голодание читателя, потому что обновления писателей занимают слишком много времени.
(2a) Если (и только если) вы столкнетесь с голодом писателя, вы можете сделать блокировку более детальной. Это крайне вероятно, что это не так. Для этого:
Заставьте ваш вектор удерживать свои интервалы указателем, а не значением. Это так, что изменения размеров не перемещают ваши объекты в памяти. Каждый интервал должен содержать блокировку чтения / записи.
Для чтения:
Возьмите блокировку чтения коллекции, затем требуемого интервала. Если вам не нужно читать какие-либо другие интервалы, отмените блокировку сбора, как только вы получите блокировку интервала, чтобы другие потоки могли продолжить.
Если вам нужно прочитать другие сегменты, вы можете заблокировать их чтение в любом порядке, пока не снимите блокировку чтения коллекции, после чего писатель может добавить или удалить любые интервалы, которые вы не заблокировали. Порядок не имеет значения при получении этих блокировок, так как записывающее устройство не может изменять вектор, пока вы удерживаете блокировку чтения в коллекции, и блокировки чтения не конкурируют.
Для записи:
Возьмите блокировку записи коллекции, а затем требуемого интервала. Обратите внимание, что вы должны удерживать блокировку записи в коллекции для всех обновлений, которые будут добавлять или удалять интервалы. Вы можете снять блокировку коллекции, если обновляете только один интервал. В противном случае вам нужно удерживать блокировку записи и получать блокировку записи через любые интервалы, которые вы будете изменять. Вы можете получить интервальные блокировки в любом порядке, так как никакие читатели не могут получить новые блокировки чтения без блокировки коллекции.
Вышесказанное работает, будучи более эгоистичным по отношению к писателю, что должно устранить голод.
(2b) Если вы сталкиваетесь с голодом читателя, что еще более маловероятно, лучшим решением будет разделение набора записей и чтения на части. Удерживайте коллекцию с помощью общего указателя и установите для нее одну блокировку записи.
Для чтения:
Возьмите блокировку записи и копию shared_ptr. Откажитесь от блокировки записи. Теперь читатель может читать коллекцию без каких-либо блокировок (она неизменна).
Для записи:Отнесите shared_ptr в коллекцию согласно читателю, отказавшись от блокировки. Сделайте личную копию коллекции и измените ее (блокировка не требуется, поскольку она является частной копией). Снова заблокируйте запись и замените существующий shared_ptr новой коллекцией. Последний поток, заканчивающийся старой коллекцией, уничтожит ее. Все будущие темы будут использовать недавно обновленную коллекцию.
Обратите внимание, что этот алгоритм работает только с одним писателем, согласно описанию вашей проблемы.