J'ai une collection d'environ cent ou tellement de tri Qu'est-ce que j'aimerais faire essentiellement itéralement à travers le plus petit au plus grand entier, qui sont contenus dans tous ces vecteurs triés. Une façon de le faire serait de fusionner tous ces vecteurs triés dans une triée Vector & Simplement itérer. Ainsi, Je suis sûr que l'autre il y a Des moyens plus rapides / intelligents d'accomplir cela sans la fusionner et de la ré-trier le tout - peut-être éclairer le plus petit entier itérité de cette collection de vecteurs triés; Sans les fusionner d'abord .. Donc: Question 2: Quelle est la meilleure façon de faire passer le moins d'élément à partir d'un tas de type Sur la base des réponses ci-dessous et les commentaires à la question que j'ai mis en place une approche où je fais une file d'attente prioritaire d'itérateurs pour les vecteurs triés. Je ne sais pas si cela est efficace de la performance, mais cela semble être très efficace de la mémoire. Je considère que la question toujours ouverte, car je ne suis pas sûr que nous avons encore établi le moyen le plus rapide. vecteur vecteur
3 Réponses :
La première chose à gérer est de créer une structure de tas contenant des itérateurs à chaque vecteur, commandé par la valeur qu'ils pointe actuellement. (Chaque entrée doit contenir également l'itérateur final, bien sûr)
L'élément actuel est à la racine du tas, et d'avancer, vous le faites simplement le faire sauter ou augmenter sa clé. (Ce dernier pourrait être fait en apparaissant, incrémentation, puis poussant)
Je crois que cela devrait avoir une complexité asymptotique Si vous ressemblez vraiment à tous les vecteurs, vous pouvez faire un tas de pointeurs à vos vecteurs, vous voudrez peut-être les traiter comme des tas aussi, pour éviter la pénalité de performance d'effacement de l'avant d'un vecteur. (Ou, vous pouvez tout copier dans Les fusionner tous ensemble en fusionnant des paires à la fois a la même complexité asymptotique si vous faites attention à la commande. Si vous organisez tous les vecteurs dans un arbre binaire complet et équilibré, puis une fusion par paires lorsque vous montez l'arborescence, chaque élément sera copié Pour une efficacité réelle supplémentaire, au lieu de l'arborescence, vous devez fusionner à plusieurs reprises les deux plus petits vecteurs jusqu'à ce que vous n'ayez qu'une seule gauche. (Encore une fois, mettre des pointeurs aux vecteurs dans un tas est la voie à suivre, mais cette fois ordonnée par longueur)
(vraiment, vous voulez commander par "Coût de copier" au lieu de la longueur. Une chose supplémentaire à optimiser pour certains types de valeur)
Si je devais deviner, le moyen le plus rapide serait d'utiliser la deuxième idée, mais avec une fusion de N-Ary au lieu d'une fusion par paire, pour certains n (que je devine, sera soit une petite constante, ou à peu près la racine carrée du nombre de vecteurs) et effectuer la fusion de N-Ary en utilisant le premier algorithme ci-dessus pour énumérer le contenu de N vecteurs à la fois. O (e journal) où e est le nombre total d'éléments et m est le Nombre de vecteurs.
deque s premier)
journal M , menant également à un O ( E journal m) algorithme.
Bien sûr, pour des données spécialisées, vous risquez peut-être mieux de faire un tri linéaire; par exemple. un histogramme ou un type de godet ou une sorte de radix.
Merci de votre réponse, je suis relativement nouveau, pourriez-vous fournir un exemple de code à des fins d'illustration? (1) Comment fonctionne-t-on une fusion de N-Ary? (2) Comment "structure de tas contenant des itérateurs à chaque vecteur, commandé par la valeur qu'elles pointent actuellement. (Chaque entrée devrait également contenir l'itérateur final, bien sûr) L'élément actuel est à la racine du tas, et Pour faire avancer, vous le faites simplement l'avant, ou augmentez sa clé. (Ce dernier pourrait être fait en sautant, incrémentation, puis poussant) "Regardez-la dans le code?
Une option consiste à utiliser un Vous pouvez également envisager d'utiliser des applications répétées de Ceci fonctionne en concaténant d'abord toutes les listes triées ensemble en un longue liste. S'il y avait trois listes de sources, cela signifie qu'il y a quatre «offsets», qui sont quatre points dans la liste complète entre lesquels les éléments sont triés. L'algorithme retirera ensuite trois d'entre eux à la fois, fusionnant les deux listes triées adjacentes correspondantes dans une liste triée, puis se souvenant de deux de ces trois décalages à utiliser dans les nouveaux_offsets. Ceci se répète dans Une boucle, avec des paires de gammes triées adjacentes fusionnées ensemble, jusqu'à une seule plage de tri. En fin de compte, je pense que le meilleur algorithme impliquerait la fusion des paires les plus courtes de gammes adjacentes ensemble. < Pré> xxx std :: file d'attente prioritaire < / a> Pour maintenir un tas d'itérateurs, où les itérateurs bouillonnent le tas en fonction des valeurs qu'elles pointent. std :: inplace_merge . Cela impliquerait d'ajouter toutes les données ensemble dans un grand vecteur et de se souvenir des compensations auxquelles chaque bloc de tri distinct commence et se termine, puis en passant à ceux-ci dans Acace_merge. Cela serait probablement plus rapide que la solution de tas, bien que je pense que je pense fondamentalement la complexité est équivalente.
Merci Aaron, a mis en place la première suggestion et code posté - toute suggestion? Si je me contente de faire la mise à jour à nouveau à la mise à jour.
@Deniz, votre algorithme prioritaire_queue a l'air bien. J'ai maintenant mis à jour ma réponse ici pour inclure une implémentation de mon deuxième algorithme, où les paires de gammes triées adjacentes sont à plusieurs reprises fusionnées, triés de manière répétée jusqu'à ce que une seule gamme reste.
@AaronMcDaid J'ai essayé le programme ci-dessus avec des entrées différentes et les résultats n'ont pas été dans la commande triée. Entrée: int A1 [] = {30, 50, 3, 8}; int A2 [] = {11, 14, 19, 6, 8, 30}; int A3 [] = {8, 6}; Sortie: 11, 14, 19, 6, 8, 30, 30, 50, 3, 8, 6, 8, 8
@Syncmaster, la question suppose que les vecteurs d'entrée sont déjà triés. Mais chaque vecteur que vous avez fourni est pas déjà trié. Je pense donc que mon programme est toujours correct pour la question. Si l'objectif était simplement de fusionner un certain nombre de vecteurs non formés , la solution consiste simplement à concaténer les vecteurs, puis à exécuter une STD standard :: Trier sur elle. Mais le but ici est d'utiliser le fait que les intrants sont déjà triés et utilisent ce fait pour obtenir un tri plus rapide.
J'ai utilisé l'algorithme donné ici et j'ai fait un peu de résumé; convertir en modèles. J'ai codé cette version dans VS2010 et j'ai utilisé une fonction Lambda au lieu du fonctionnement. Je ne sais pas si cela est dans n'importe quel sens «mieux» que la version précédente, mais peut-être que ce sera utile quelqu'un? L'algorithme Priority_Queue_sort :: value_vectors trie les vecteurs contenant uniquement des valeurs; Alors que priority_queue_sort :: paire_vectors trie les vecteurs contenant des paires de données en fonction du premier élément de données. J'espère que quelqu'un peut utiliser ce jour: -)
Cela a un bogue lorsque l'un des vecteurs triés d'entrée est vide. Vous pouvez simplement vérifier cela avant d'ajouter à cluster_feeder
1) Si l'espace n'est pas un problème, effectuez la fusion standard des gammes triées de votre CS101 dans un nouveau vecteur (ou y réfléchissez simplement à une minute et faites la chose évidente). 2) Avant de passer autour de vous, assurez-vous de comprendre les garanties de complexité des conteneurs standard; Modification d'un
std :: vecteur est en général assez cher. 3) Arrêtez l'abuser T'He Apo'strophes!@ Kerrek-SB Merci, a fixé le formatage d'un peu - je suis assez heureux simplement fusionner les vecteurs dans un vecteur et un tri plus grand; Mais je me demande s'il y a des moyens plus rapides de le faire.
Non Non, vous effectuez une fusion triée. Pensez-y, il existe un moyen évident d'exploiter la commande des plages d'entrée pour créer une plage de sortie déjà commandée.
@ Kerrek-SB Je pense que je vois ce que vous voulez dire, je sais utiliser la fonction de fusion régulière pour deux vecteurs triés; Est-ce que cela fonctionne bien de manière récursive / itérative? Comment faire une "fusion multi-fusion" de plus de 2 vecteurs triés?
Utilisez une file d'attente prioritaire (tas) qui stocke les premiers éléments des vecteurs.
@ n.m. Merci, a mis à jour la question avec le code que j'ai piraté cela. Je pense qu'il y a beaucoup de place pour améliorer la mise en œuvre des frais généraux. Seulement si je pouvais savoir facilement lorsque les itérateurs "s'épuisent". Je souhaite qu'ils ont jeté une exception à la fin.