Блог

Мне нужно обработать динамический отсортированный список событий на C . Каждое событие состоит из 3 переменных: время (используется для сортировки списка) и 2 других. Я обрабатываю события данных по событиям, беру первое в отсортированном списке (с меньшей переменной времени), обрабатываю его, а затем удаляю из списка. Во время обработки событий я также должен добавить другие в этот список, которые могут быть добавлены в любую позицию.

Я пытался использовать prioriy_queue composed by tuple ( std::priority_queue<tuple<double, int, int>, std::vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> ) , значение double — это переменная времени, используемая для сортировки списка, а целые числа — другие переменные, полезные для обработки. Это работает, он сохраняет список отсортированным по времени, я могу легко добавлять новые события и удалять первое, и мне просто нужно получить доступ к первому (с меньшим значением времени).

Но это занимает много времени. Большая часть времени, затрачиваемого моей программой, используется для добавления и удаления элементов в мой список. Существуют ли другие альтернативы, кроме приоритетной очереди? Использование tuple<double, int, int> , вероятно, не самый лучший способ и должно сильно повлиять, есть ли другие альтернативы?

std::priority_queue Это, по сути, куча, lg2 N push и pop. Обратите внимание, что для миллиона элементов, которые будут равны 20 тыс. M, K малой константе, M обращений к памяти. Использование памяти 8 МБ для одного ядра, поэтому время для обновления до процессора, который предоставляет L3 доступ по крайней мере к такому объему памяти.

Это может быть улучшено до lg lg N (эквивалент Thorup) с некоторыми усилиями, но могут быть более простые варианты.

Если существует много временных коллизий, то кортеж не является правильной структурой.

Что-то вроде

 struct item {
  double time;
  int first, second;

  operator>(const item amp; other) const {
    return time > other.time;
  }
};

using pQueue = std::priority_queue<item, std::vector<item>, std::greater<item>>;
  

Это должно использовать operator> else использовать lampda в качестве компаратора.

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

Другая возможность заключается в использовании std::partial_sort первых 128 элементов, оставляя остальные несортированными, сверяйте с наивысшим значением в отсортированном массиве при вставке нового, чтобы увидеть, нужно ли его включать в лучшие оценки или просто помещать обратно в другие. Когда верхние оценки пусты, создайте новый std::partial_sort . Использование std::deque вместо std::vector может быть лучше в этом случае, из-за лучшего pop_front из O(1) . Необходимо выполнить некоторую дополнительную бухгалтерию.