Рассчитать время перекрытия внутри карты Переполнение стека
У меня есть карта с ключом = startTime и значением = endTime, например:
map<uint32_t,uint32_t>time_map;
(будучи uint32_t является unsigned __int32, но это здесь не актуально).
Я хочу подсчитать, сколько перекрывающихся значений существует среди этих значений (которые представляют startTime для соединения и endTime этого, так что на самом деле сколько существует перекрывающихся соединений).
Какой самый быстрый способ рассчитать это? есть ли какая-либо функция / метод внутри std::map думал решить эту проблему?
Изменить: Поскольку исходный вопрос неясен, идея состоит в том, чтобы рассчитать максимальное количество перекрывающихся соединений в любой данный момент времени. Это значит, учитывая эти времена:
start 100 - end 1000 / start 120 - end 200 / start 250 - end 400 / start 600 - end 800
ответ 2 (1 с 2, 1 с 3, 1 с 4, но ни один из других друг с другом)
Решение
Сначала я бы использовал наивный подход, используя приставной столик; это будет близко к алгоритму быстрой линии.
Идея:
- перебирать соединения по порядку (здесь упорядочено по времени начала)
- сохранение набора текущих подключений
Хитрость заключается в том, чтобы эффективно отслеживать соединения, особенно когда их нужно удалить; приоритетная очередь отлично подходит для этого.
Некоторая помощь:
struct Connection {
uint32_t start;
uint32_t end;
}; // struct Connection
// WATCH OUT:
// std::priority_queue only let you access the MAXIMUM element, so the predicate
// is the OPPOSITE of what we usually write...
struct OrderByEnd {
bool operator()(Connection const& left, Connection const& right) const {
if (left.end > right.end) { return true; }
if (left.end < right.end) { return false; }
return left.start > right.start;
}
}; // struct OrderByEnd
using CurrentlyOverlappingType = std::priority_queue<Connection, std::deque<Connection>, OrderByEnd>;
И тогда мы подметаем:
size_t countMaxNumberOfOverlaps(std::map<uint32_t, uint32_t> const& connections) {
if (connections.empty()) { return 0; }
size_t max = 0;
CurrentlyOverlappingType currentlyOverlapping;
for (auto const& con: connections) {
// Purge no longer overlapping connections
while (not currentlyOverlapping.empty() and currentlyOverlapping.top().end < con.first) {
currentlyOverlapping.pop();
}
// Debug:
if (not currentlyOverlapping.empty()) {
std::cout << "[" << con.first << ", " << con.second <<
"] is overlapping with: " << currentlyOverlapping.size() << " connections\n";
}
// The current connection is necessarily overlapping with itself
currentlyOverlapping.push(Connection{con.first, con.second});
max = std::max(max, currentlyOverlapping.size());
}
return max;
} // countMaxNumberOfOverlaps
А также работает как положено:
[120, 200] is overlapping with: 1 connections
[250, 400] is overlapping with: 1 connections
[600, 800] is overlapping with: 1 connections
Max number of overlaps: 2
Сложность понять сложнее. Вы должны пролистать весь набор соединений, но на каждом шаге объем работы пропорционален текущему количеству перекрывающихся соединений …
- В худшем случае сложность: O (N * log (N)) я бы сказал (потому что вставка в очередь с приоритетами логарифмическая)
- Средняя сложность случая: O (N * log (O)), где O — количество перекрывающихся соединений
Примечание: в алгоритмическом анализе я считал, что сложность продувочной части является амортизированной постоянной; мы знаем, что элементы будут очищаться, поэтому мы можем учесть их чистку в стоимости их вставки. N элементов вставлено, N элементов будет очищено. Число сравнений, выполненных как часть процесса очистки, является (я думаю) также амортизированной константой (сумма для всех элементов, ограниченная максимумом 2N), хотя это интуиция, а не вычисление. И, следовательно, стоимость очистки уменьшается из-за затрат на вставку элементов в приоритетную очередь, которые регистрируют (O) на элемент.
Другие решения
Я думаю, что ваша проблема связана с пересечением отрезка (http://en.wikipedia.org/wiki/Bentley-Ottmann_algorithm), если вы рассматриваете временные интервалы как одномерные line segments (а не обычные двумерные отрезки в евклидовой плоскости).
Алгоритмически, вы можете использовать один из алгоритмов стреловидной линии в вычислительной геометрии, чтобы достичь сложности, которая меньше O (n ^ 2), связанной с наивным подходом. Приведенный выше алгоритм Бентли – Оттмана является одним из них. Концептуально вы ведете сканирование строчной развертки слева направо, ведете учет интервалов входа или выхода из вашей строчной развертки. Подробности можно найти в любых хороших учебниках по вычислительной геометрии.
Я не думаю std::map поддерживать алгоритмы строчной развертки, и вам нужно будет реализовать необходимую структуру данных, связанную с ней.
Вы можете использовать библиотеку Boost’s Date / Time. У него есть класс time_period, который поддерживает метод пересечений, как показано в этих Примеры. Это избавляет вас от необходимости писать код для «перекрытия этих двух интервалов?» хотя вам все равно придется решить, как пройти вашу коллекцию (избежать обхода O (n ^ 2) кажется трудным).
РЕДАКТИРОВАТЬ: вам нужно максимальное количество одновременных интервалов в любое время.
В этом случае предложение Ting L о алгоритме стреловидности кажется лучшим. Сортируйте интервалы по времени начала и перебирайте их по порядку. Поддерживайте стек во время итерации. Для каждого нового интервала вставляйте все интервалы в стеке, которые истекли до начала нового интервала. Отслеживание максимального размера стека даст вам максимальное количество одновременных интервалов (если вам нужно знать, какие это интервалы, вам нужно будет поддерживать отдельный контейнер «текущий самый длинный набор», обновленный во время итерации)
Карта (стандартная карта) — это дерево, отсортированное по ключу. Проверьте этот ссылка на сайт. Поэтому, если вы выполните итерацию, вы получите ее по порядку времени запуска. Однако, помимо этого, для проверки определенного времени перекрытия, не будет никакой дополнительной поддержки от API std :: map.
Теперь, чтобы проверить время перекрытия, вы должны использовать классический итераторный подход как метод наихудшего случая. Проверьте время окончания элемента iвсегда меньше времени начала i в N ,
НТН!
Я думаю, что природа проблемы связана с множествами и множествами пересечений. Вы можете попробовать STL задавать контейнер и set_intersection функция, которая эффективно находит пересечения двух отсортированных последовательностей. (Действительно, set — это просто карта с только ключами (без значений), поэтому вы можете работать с картами, они также сортируются.)
Скажем, вы можете представить интервал времени как пару (начало, конец) и построить пересечение всех интервалов, пересекающих множества. Вы можете определить свою собственную функцию сравнения.
Точная логика будет следовать из деталей вашей задачи, которые не совсем понятны.
(Это также set_difference, set_union, а также set_symmetric_difference функции.)