Je cherche un moyen efficace de couper ou de copier un sous-ensemble d'un STD existant :: Vecteur. Les critères d'éléments à éligibles pour le sous-ensemble / restent sont que leur index est contenu dans un STD distinct STD :: Vector. Je ferai cela sur un très grand vecteur et probablement de manière régulière, je cherche donc la méthode aussi efficace que possible. Une alternative que je considère également, mais sans savoir une méthode efficace est ... comme le Le test d'objet est rempli (dans mon cas, il s'agit d'un objet défini de tiers), il résulte d'une seule passe à l'aide d'un itérateur (aucun accès direct d'élément n'est possible). Je me demandais si, si possible, il est possible d'ajouter uniquement aux éléments de vecteur de test qui apparaissent dans le compte défini dans Selectionv mais je suppose Cela entraînera une passe à travers le Selectionv sur chaque itération, qui serait beaucoup moins efficace que d'ajouter simplement tous les éléments et de sélectionner ultérieurement un sous-ensemble. Toute aide beaucoup appréciée.
4 Réponses :
Vous pouvez trier votre vecteur de Selectionv en augmentant la commande, puis vous pouvez réécrire votre boucle quelque chose comme:
selectionv est (en pourcentage de test ), et si des éléments dans Selectionv Répétition. Vous pouvez potentiellement optimiser en calculant pas Selectionv à la place.
- Notez que dans votre exemple, puisque
Selectionv est un index, et non une valeur, la recherche est déjà O (1) rapide (c'est déjà un énorme plus).
- Si
test et Selectionv ne change pas, et si elles sont grandes, vous pouvez également diviser selectionv par n threads et avoir chaque fil de lecture de manière indépendante des valeurs de recherche dans test , puis combinez les sorties individuelles ultérieurement (non différente de la carte). L'inconvénient peut être une perte dans les coups de cache de la CPU.
- sur des appels répétés, vous voudrez peut-être faire la différence entre votre ancien
Selectionv et nouveau Selectionv et utiliser cette valeur. Ce type d'optimisation du cache fonctionnera bien pour un petit nombre de changements entre itérations.
surtout, assurez-vous de vraiment bien optimiser cela avant de passer du temps à le faire (et pire, compliquer votre code).
Il y a une très grande probabilité que d'autres parties de votre application (par exemple, I / O) puissent être des grandes fois plus lentes.
1) La taille relative du sous-ensemble requis variera et sera décidée au moment de l'exécution.
2) Au départ, ce qui va se passer est que la Selectionv restera la même, essayant de sélectionner le même sous-ensemble d'un certain nombre de "tests" différents.
@ Oracle3001 Avez-vous fait profilé vos échantillons? Configuration de SelectionV et de test (surtout si vous lisez à partir du disque ou une base de données) pourrait réellement prendre beaucoup plus de temps que l'algorithme de sélection.
L'objet que j'écoule de l'échantillonnage est une série d'objets maillés (tels que définis par cette bibliothèque openmesh.org). Une fois chargé en mémoire, je tente d'échantillonner à plusieurs reprises un sous-ensemble de sommets de ces objets.
Peut-être que ce qui suit pourrait être utile pour quelqu'un à l'avenir:
template<typename T>
T vector_select(const std::vector<T>& vector, const std::size_t index)
{
assert(index < vector.size());
return vector[index];
}
template<typename T>
class VectorSelector
{
public:
VectorSelector(const std::vector<T>& v) : _v(&v) { }
T operator()(const std::size_t index){ return vector_select(*_v, index); }
private:
const std::vector<T>* _v;
};
template<typename T>
std::vector<T> vector_select(const std::vector<T>& vector,
const std::vector<std::size_t>& index)
{
assert(*std::max_element(index.begin(), index.end()) < vector.size());
std::vector<T> out(index.size());
std::transform(index.begin(), index.end(), out.begin(),
VectorSelector<T>(vector));
return out;
}
Vous pouvez également utiliser la bibliothèque standard:
std :: vecteur std :: transformation (sélectionv.begin (), selectionv.end (), résultat.begin (), [Test] (Taille_t POS) {Retour Test [POS];});
C'est une si belle solution!
Selectionv doit-il être un vecteur? Est-ce que c'est statique pendant que le test / le résultat est en cours de remplissage?
Et quelle est la taille de Selectionv par rapport au test? (Juste quelques éléments? Presque tous?)
Aucun Selectionv n'a pas besoin d'être un vecteur. Oui Test / Résultat sont statiques lorsqu'ils sont remplis. Selectionv est susceptible d'être un pourcentage important de test, mais cela est défini au moment de l'exécution et pourrait être un pourcentage, bien qu'il soit certainement d'un minimum de plusieurs 1 000 indices.