Bon intersection d'une collection de jeux en C++

De nuit est un bon conseiller et je pense que j'ai peut-être une idée 😉

• De la mémoire est beaucoup plus lent que le CPU de ces jours, si toutes les données s'inscrit dans le cache L1 pas une grosse affaire, mais il facilement les déversements de plus de L2 ou L3: 5 séries de 1000 éléments est déjà 5000 éléments, à savoir 5000 nœuds, et un ensemble de nœud contient au moins 3 pointeurs + l'objet (c'est à dire, au moins de 16 octets sur une machine 32 bits et de 32 octets sur une machine 64 bits) => c'est au moins de 80k de la mémoire et de la récente Processeurs seulement 32k pour le L1D nous sommes donc déjà à se déverser dans L2
• La précédente fait est aggravé par le problème que les ensembles de nœuds sont probablement dispersés autour de la mémoire, et pas étroitement emballés ensemble, ce qui signifie que la partie de la ligne de cache est rempli complètement indépendants des trucs. Ce pourrait être atténué par fourni un allocateur qui garde les nœuds proches les uns des autres.
• Et cela est encore aggravé par le fait que les Processeurs sont beaucoup mieux à des lectures séquentielles (où ils peuvent prélecture de la mémoire avant d'en avoir besoin, de sorte que vous ne pas attendre que ça) plutôt que de lectures aléatoires (et une structure en arbre conduit malheureusement à tout à fait les lectures aléatoires)

C'est pourquoi, où les vitesses de question, un vector (ou peut-être un deque sont si grandes structures: ils jouent très bien avec de la mémoire. En tant que tel, je recommanderais certainement à l'aide de vector que nos structures intermédiaires; bien que les soins doivent être prises pour ne jamais insérer/supprimer à partir d'une extrémité pour éviter les délocalisations.

Alors j'ai pensé à une approche assez simple:

#include <cassert>
#include <algorithm>
#include <set>
#include <vector>
//Do not call this method if you have a single set...
//And the pointers better not be null either!
std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
for (auto s: sets) { assert(s && "I said no null pointer"); }
std::vector<int> result; //only return this one, for NRVO to kick in
//0. Check obvious cases
if (sets.empty()) { return result; }
if (sets.size() == 1) {
result.assign(sets.front()->begin(), sets.front()->end());
return result;
}
//1. Merge first two sets in the result
std::set_intersection(sets[0]->begin(), sets[0]->end(),
sets[1]->begin(), sets[1]->end(),
std::back_inserter(result));
if (sets.size() == 2) { return result; }
//2. Merge consecutive sets with result into buffer, then swap them around
//   so that the "result" is always in result at the end of the loop.
std::vector<int> buffer; //outside the loop so that we reuse its memory
for (size_t i = 2; i < sets.size(); ++i) {
buffer.clear();
std::set_intersection(result.begin(), result.end(),
sets[i]->begin(), sets[i]->end(),
std::back_inserter(buffer));
swap(result, buffer);
}
return result;
}

Il semble correct, je ne peux pas garantir sa vitesse bien que, évidemment.

OriginalL'auteur Matthieu M.