您在这里有两个不同的问题:
- 如何表示你的数据结构
- 如何以高效的方式使其线程安全
您的数据结构将为每次写入执行 (20-80) x (2-8) 次读取。
(1)。首先,假设您的范围是如下数据结构
struct Interval
{
Interval(int start, int length)
: m_start(start),
m_length(length)
{}
int m_start;
int m_length;
int value; // Or whatever
};
Since reads massively outnumber writes, lookup needs to be fast, while modifications don't.
Using a list for your data structure means O(N) lookups and O(1) modification - exactly the wrong way around.
The simplest possible representation of your structure is a vector. If the intervals are held in sorted order, lookups are O(logN) and modifications are O(N).
To implement this, just add a comparator to Interval:
bool operator<(const Interval& rhs) const
{
return m_start < rhs.m_start;
}
You can then use std::lower_bound
to find the first interval equal or lower to your search interval in O(logN).
Next and previous interval are O(1) - decrement or increment the returned iterator.
Splitting an interval means inserting a new element after the current one and adjusting the length of the current - O(N).
Joining two intervals means adding the length of the next one to the current one and erasing the next one - O(N).
You should reserve()
enough space in the vector for the maximum number of elements to minimise resizing overhead.
(2). Following Knuth, 'premature optimisation is the root of all evil'.
A single read/write lock on the structure holding your vector<Interval>
很可能就足够了。唯一可能的问题是(2a)由于读者独占锁而导致写入者饥饿,或(2b)由于写入者更新花费太长时间而导致读取者饥饿。
(2a) 如果(且仅当)您面临作家饥饿,您可以使锁定更加精细。不过,这种情况极有可能不会发生。去做这个:
使您的向量通过指针而不是值保持其间隔。这样调整大小就不会在内存中移动对象。让每个间隔都包含一个读/写锁。
对于读取:获取集合的读取锁,然后获取所需的时间间隔。如果您不需要读取任何其他区间,请在获得区间锁后立即放弃集合锁,以允许其他线程继续执行。
如果您需要读取其他存储桶,您可以按任何顺序对它们进行读锁定,直到您放弃集合读锁定,此时写入器可以添加或删除您尚未锁定的任何间隔。获取这些锁时顺序无关紧要,因为当您持有集合上的读锁时,作者无法更改向量,并且读锁不会竞争。
对于写入:
获取集合的写锁,然后获取所需的时间间隔。请注意,对于将添加或删除间隔的所有更新,您必须持有集合写锁。如果您只更新一个间隔,您可以放弃收集锁。否则,您需要持有写锁并在您将要修改的任何时间间隔上获取写锁。您可以按任何顺序获取间隔锁,因为没有集合锁,没有读者可以获取新的读锁。
上述工作对作者线程更加自私,这应该消除饥饿。
(2b) 如果您面临读者饥饿(这种情况更不可能),最好的解决方案是将集合写入和读取分开。通过共享指针持有集合,并对其有一个写锁。
对于读取:获取写入锁和 shared_ptr 的副本。放弃写锁。读者现在可以在没有任何锁的情况下读取集合(它是不可变的)。
对于写入:根据读者将 shared_ptr 带到集合中,放弃锁定。制作集合的私有副本并对其进行修改(因为它是私有副本,所以不需要锁定)。再次获取写锁并将现有的 shared_ptr 替换为您的新集合。完成旧集合的最后一个线程将销毁它。所有未来的线程都将使用新更新的集合。
请注意,根据您的问题描述,此算法仅适用于一位作家。