Alternative aux vecteurs pour les grands ensembles de données? C++

Question

Je cherche une structure de données qui contient des données afin qu'elles soient insérées (comme un vecteur) qui doit contenir des millions de longs non signés. La clé est qu'elle doit avoir une recherche meilleure que O (logn), car elle sera recherchée par rapport à un vecteur similaire de la même taille. Y a-t-il quelque chose qui existe comme ça? Si j'insère 10, 20, 30 et ensuite itérer sur l'ensemble, je dois garantir l'ordre de 10, 20, 30. Mes données sont une chaîne que j'ai convertie en un long non signé pour réduire l'utilisation de la mémoire, c'est-à-dire décodable inverse. Comme les gens me le demandent, je compare deux vecteurs les uns par rapport aux autres (tous les deux de très grande taille) pour obtenir la différence.

Petit exemple:

vector 1: 10 20 30 40 50 60 

vector 2: 11 24 30 40 55 70 90 

result: 30 40 

Answer 1

Une carte de hachage est une façon vous aurez plus rapide recherche qu'un vecteur trié. Vous devez avoir le support de C++ 11 pour l'utiliser.
http://www.cplusplus.com/reference/unordered_map/unordered_map/
Pour préserver l'ordre des données, la seule façon serait de maintenir un vecteur à côté qui a stocké et
de l'int Avant de sauter à l'utiliser, vous devriez considérer comment vous allez utiliser cette structure de données (modèle d'accès). Considérez également ce que les données que vous obtiendrez est susceptible d'être.
Voici la version de boost de la même chose http://www.boost.org/doc/libs/1_53_0/doc/html/unordered.html

Answer 2

Je pense que vous devriez utiliser est unordered_map combinée avec peut-être une liste doublement liée à l'ordre. Donc, chaque fois que vous ajoutez un nouvel élément à votre base de données, vous l'ajoutez d'abord au début (ou à la fin) de la liste chaînée, puis vous l'ajoutez au hashmap dont la clé est la valeur (l'entier non signé) et la "valeur" (de la paire clé/valeur) est le pointeur vers l'objet dans la liste chaînée. Donc maintenant, si vous voulez une recherche rapide, vous regardez dans la hashmap, et si vous voulez itérer par ordre, vous utilisez la liste chaînée. Bien sûr, lorsque vous voulez supprimer un objet, vous devez le supprimer des deux, mais la complexité est la même (O (1) amorti pour tout).

Cela va bien sûr augmenter votre mémoire de 2 ou 3 par rapport à l'utilisation d'un hashmap.

Answer 3

Je ne l'ai jamais utilisé moi-même et il pourrait être obsolète comparé aux fonctionnalités récentes de la version C++ (la dernière mise à jour date de 2011), mais STXXL est censé être un ensemble de conteneurs et d'algorithmes construits pour une très grande quantité de Les données. Cela pourrait correspondre à votre besoin.

Le noyau de STXXL est une implémentation de la bibliothèque de modèles de calculs C standard de STL pour la mémoire externe (out-of-core), i. e., STXXL implémente des conteneurs et des algorithmes capables de traiter d'énormes volumes de données qui ne tiennent que sur les disques . Alors que la proximité de la norme STL prend en charge la facilité d'utilisation et la compatibilité avec les applications existantes, une autre priorité de conception est la haute performance.

Les principales caractéristiques de STXXL sont:

• Support transparent des disques parallèles. La bibliothèque fournit des implémentations d'algorithmes de disques parallèles de base.STXXL est la seule bibliothèque d'algorithmes de mémoire externe prenant en charge les disques parallèles.
• La bibliothèque est capable de gérer des problèmes de très grande taille (testés jusqu'à des dizaines de téraoctets).
• Amélioration de l'utilisation des ressources informatiques. Les implémentations STXXL d'algorithmes de mémoire externe et de structures de données bénéficient de chevauchement d'E/S et de calcul.
• Petits facteurs constants dans le volume d'E/S. Une fonctionnalité de bibliothèque unique appelée "pipelining" permet d'économiser plus de la moitié du nombre d'E/S, par de transmettre des données entre les composants algorithmiques, au lieu de les stocker temporairement sur le disque. Une branche de développement prend en charge l'exécution asynchrone des composants algorithmiques , permettant le parallélisme de tâche de haut niveau.
• Temps de développement plus courts grâce aux interfaces compatibles avec la norme STL pour les algorithmes de mémoire externe et les structures de données.
• Les algorithmes STL peuvent être directement appliqués aux conteneurs STXXL; de plus, la complexité d'E/S des algorithmes reste optimale dans la plupart des cas .

Pour le calcul interne, des algorithmes parallèles à partir de la MCSTL ou le libstdC++ mode parallèle sont éventuellement utilisés, ce qui rend les algorithmes bénéficient intrinsèquement de parallélisme multi-core.