003
07.04.2010, 22:45 Uhr
0xdeadbeef
Gott
(Operator)
|
Wenn ich das richtig verstehe, drängt sich std::priority_queue dabei auf. Es handelt sich dabei um einen Container-Adapter, der auf einem angegebenen Container (Vorgabe std::vector) einen Heap aufbaut und die Elemente praktisch on the fly sortiert. Vom Interface her läuft es darauf hinaus, dass man schnell auf das nach der angegebenen Ordnung (Vorgabe std::less<T>) größte Element zugreifen kann, während neue Elemente in logarithmischer Zeit eingefügt werden können. Laufzeitkomplexitätstechnisch kann ich dir nichts besseres bieten, wobei die Auswahl des benutzten Containers eine gewisse Rolle spielt - std::vector ist für deinen Fall wahrscheinlich keine wirklich gute Wahl, ich würde also mit std::deque experimentieren.
Wenn du die kleinsten Elemente zuerst haben willst, ist std::greater als Ordnung dein Freund, siehe unten.
Ich habe mal ein kleines Beispielprogramm / Benchmark zusammengeschrieben, um die Verwendung zu verdeutlichen:
| C++: |
#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <stdexcept>
#include <vector>
template<typename queue_t>
void check_queue(queue_t &q) {
typedef typename queue_t::value_type val_t;
val_t i = std::numeric_limits<val_t>::min();
while(!q.empty()) {
if(i > q.top()) {
throw std::logic_error("Falsche Sortierung");
}
i = q.top();
q.pop();
}
}
int main() {
unsigned long const NUM_ELEMENTS = 1000000;
std::srand(std::time(0));
std::clock_t bench[4];
bench[0] = clock();
{
std::priority_queue<int, std::deque<int>, std::greater<int> > q;
for(std::size_t i = 0; i < NUM_ELEMENTS; ++i) {
q.push(rand());
}
check_queue(q);
}
bench[1] = clock();
{
std::priority_queue<int, std::vector<int>, std::greater<int> > q;
for(std::size_t i = 0; i < NUM_ELEMENTS; ++i) {
q.push(rand());
}
check_queue(q);
}
bench[2] = clock();
{
std::vector<int> v;
v.reserve(NUM_ELEMENTS);
for(std::size_t i = 0; i < NUM_ELEMENTS; ++i) {
v.push_back(rand());
}
std::priority_queue<int, std::vector<int>, std::greater<int> >
q(std::greater<int>(), v);
check_queue(q);
}
bench[3] = clock();
std::cout << bench[1] - bench[0] << std::endl
<< bench[2] - bench[1] << std::endl
<< bench[3] - bench[2] << std::endl;
}
|
Bei mir (g++ 4.4.3) ist die std::deque-Variante deutlich schneller als die std::vector-Variante, was vermutlich damit zusammenhängt, dass der vector in der priority_queue alle Nase lang vergrößert werden muss. Die dritte Variante mit vorher vollständig bekannten Elementen nimmt sich damit nicht all zu viel.
In deinem use case wirst du die Kollisionen in structs verpacken und eine geeignete Ordnung angeben müssen. Denkbar wäre etwa
| C++: |
struct kollision {
double zeit;
partikel p1, p2;
};
struct zeitordnung {
bool operator()(kollision const &lhs, kollision const &rhs) const {
return lhs.zeit > rhs.zeit;
}
};
// ...
std::priority_queue<kollision, std::deque<kollision>, zeitordnung> q;
|
| Bearbeitung von 0xdeadbeef: |
Codebeispiel etwas aufgeräumt, Compilerreferenz eingefügt.
|
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 07.04.2010 um 23:42 Uhr von 0xdeadbeef editiert. |
