Voici une description:
Il fonctionne comme une carte régulière avec Pour mon cas d'utilisation spécifique, j'ajoute, en supprimant et en ajustant de nombreuses valeurs dans la structure, mais à une fois, il y a environ 500-1000 éléments; Je souhaite retourner efficacement les entrées des 10 clés top 10.
J'espère que o (1) Quelle est une structure de données pour renvoyer efficacement les éléments haut-k d'une carte?
Mon autre question est similaire, mais est pour Le cas du retour Si cela aide, les clés et les valeurs sont des entiers de 4 octets. Obtenir , mettre et supprimer des méthodes , mais a un gettopkentries (int k) Méthode pour obtenir les éléments Top-K, triés par la clé:
mettre et supprimer méthodes beaucoup fois.
gettopkentries méthode.
Mettez et Supprimer Méthodes d'autres fois.
gettopkentries méthode.
obtenez , mettre et supprimer opérations et pour gettopkentries Ne dépend que sur K, pas sur la taille de la carte.
8 Réponses :
Un arbre de recherche binaire (i.e. En outre, puisque vous prévoyez beaucoup d'opérations "Supprimer", une table de hachage ne sera pas bien adaptée de toute façon: supprimer les opérations Détruisez les caractéristiques du facteur de charge des tables de hachage qui entraînent une détérioration rapide du temps d'exécution. std :: map en C ++) sonne comme la structure parfaite: elle est déjà ordonnée de manière lexicographique, c'est-à-dire une simple traversée dans l'ordre produira les éléments de l'ordre croissant. Par conséquent, itérant sur les premiers éléments k donneront directement les éléments k directement.
Un arbre binaire a une heure (log n) dans le cas moyen, mais a besoin d'une heure (n) dans le pire des cas. Pas vraiment O (1) .. Je pense que dans ce cas O (1) est impossible sans utiliser de Treemap (arbre binaire + carte de hachage).
Cependant, le problème de la maintenance d'un arbre de recherche binaire est que les opérations deviennent O (log n) ... et je suis heureux que vous ayez pris la prise sur le supprimer opérations; J'ai une mise en œuvre de carte de hash spécialisée avec un bon comportement en temps réel pour une augmentation et un compactage en douceur de la capacité.
@chris Kannon: J'espère certainement qu'il est possible d'obtenir les entrées Top-K sans trier le tout. En regardant les réponses à mon autre question, je pourrais maintenir les indices, puis obtenir uniquement les éléments du top-k au lieu de trier le tout. Mais je sens qu'il y a une meilleure façon ...
Bien que je suis d'accord avec Chris dans le choix de Treemap, ne peut-il pas ajouter à un arbre binaire encore O (log n)? Je ne suis pas sûr que vous puissiez obtenir O (1) pour ajouter ou supprimer de tout ce type.
Il ne sera pas possible d'obtenir les entrées Top-K sans trier le tout. Pourquoi pas, vous demandez? Parce que si vous souhaitez supprimer l'une des entrées Top-K, vous devez déjà savoir quelle entrée est la K + 1ème, et ainsi de suite à la fin. L'alternative est quelque chose comme une sélection - Tri sur les entrées restantes pour déterminer ce qui est maintenant dans le top-k, qui tube absolument vos performances de suppression.
@bill k: correct; Toute structure basée sur la comparaison qui maintient la chose totale dans l'ordre triée va avoir un autre BIG OH . @Anon.: mais je pense que cela peut être résolu pour O (1) Ajout et suppression, et une récupération rapide du top-k, ou du moins plus rapide que le tri du tout chose...
Alors, que se passe-t-il si vous supprimez un objet dans le top K, puis essayez d'obtenir les meilleures entrées K?
@Chris: Eh bien, o (1) est trop important pour espérer. Et O (log n) est en fait très, très bien - beaucoup mieux que la plupart des gens assument intuitivement. Et avec seulement 500 à 1000 éléments, cela ne vaut même pas la peine de parler.
@konrad rudolph: Je ne pense pas o (1) est trop pour espérer (un homme peut rêver, putain de ça!) ... mais tu es à droite; J'ai probablement besoin de profiler les solutions plus simples avant de sortir des tables d'adresse directe ...
@Rudger, pré-optimiser peut parfois être la pire chose à faire. Faites-le travailler, que de le rendre rapide :)
@stephan Eggermont: Qu'est-ce qu'un quad-arbre? Cela devrait peut-être aller dans une nouvelle réponse?
Je recommanderais un Fibonacci Heap .
Intéressant, mais j'ai juste autant de supprimer des opérations comme mettre les opérations (asymptotiquement); Un tas de fibonacci n'est probablement pas si grand dans ce cas ... et je devrai peut-être réévaluer l'utilisation de structures de données amorties, car quelques opérations qui prennent beaucoup de temps à compléter puissent tuer les performances en temps réel ...
Je ne suis pas sûr que j'accepte l'opinion de Konrad que de nombreuses opérations détruiraient la structure d'une table de hachage.
sans supprimer les opérations, vous pouvez conserver tous les objets dans une table de hachage et garder le top K dans un tas de priorité qui serait incrémentiellement mis à jour. Cela rendrait l'insertion O (1 + log K), c'est-à-dire une fois constante dans N en supposant que k est constant et non dépendant de n (n = nombre d'objets dans la table). Cependant, cela ne fonctionne pas lorsque vous avez l'opération Supprimer disponible. Le projet de tas de fibonacci proposé a O (log n) d'opération de suppression amortie de sorte qu'il ne donne pas une bonne solution non plus, car tous les objets auraient besoin de maintenir dans le tas, et si vous supprimez éventuellement chaque objet que vous insérez, vous obtenez O (log n) comportement en général par une paire d'insert + Suppr.
Je voudrais peut-être essayer l'approche suivante:
Stockez les objets dans une table de hachage, en supposant que vous ayez besoin de la table entière à d'autres fins que de renvoyer les objets supérieurs. Maintenir un tas de priorités (le tas standard va) contenant des objets K * C pour C dont la valeur dont vous avez besoin pour rechercher expérimentalement. Chaque fois que vous ajoutez un nouvel objet, essayez de l'insérer dans le tas; Si elle s'adapte à l'espace K C (le tas n'est pas encore en capacité ou qu'il appuie un autre objet), insérez-le et définissez un peu dans la table de hachage pour indiquer que l'objet est dans le tas; Lorsque vous appuyez sur un objet hors du tas, effacez le bit. Lorsque vous Le réglage C est empirique car cela dépend de la façon dont vos objets viennent et vont; Mais le réglage doit être facile comme vous pouvez l'accorder juste basé sur le profilage d'exécution.
Complexité: Insérer est O (1 + journal (kc)). Retirer est O (1 + p journal (kc) + q n) où p est la probabilité qu'un objet retiré était dans le tas et q est la probabilité que le tas doit être reconstruit. P dépend des caractéristiques de la façon dont les objets arrivent et vont. Pour une analyse simple, nous pouvons définir p = (kc / n), c'est-à-dire assumer une probabilité uniforme. q est encore plus sensible au "flux" des objets. Par exemple, si de nouveaux objets en général augmentent de leur valeur au fil du temps et que vous supprimez toujours des objets plus anciens, q tend vers zéro.
Notez que assez de p est
Que supprimer les opérations détruire les caractéristiques de la performance de la table de hachage n'est pas ma "vue" - c'est un fait inhérent à l'adressage ouvert pour la résolution de la collision, ce qui est ce que l'utilisation de nombreuses implémentations avancées de table de hachage à usage général. Même des systèmes d'adressage ouverts sophistiqués souffrent de cette limitation. (Accordé, une chaînage distinct fait pas a ce problème.)
@Konrad Oui, avec l'adressage ouvert que vous avez ce problème. Mais ce n'est pas une propriété générale de la construction de la table de hachage, plutôt un sous-produit du système d'adressage ouvert. L'aspect "View" était que votre demande était ainsi généralisée ... mais hé, merci d'avoir fourni des commentaires précieux !!
Sauf si je suis sévèrement créatif aujourd'hui, vous ne pouvez tout simplement pas tout faire à O (1).
Si vous maintenez une ordonnance de tri, les ajouts et les suppressions seront probablement sur O (log n). Si vous n'êtes pas, alors votre recherche devra être O (n).
Les tables de hachage ne font que le tri. Je vous suggère de vivre avec le O (journal de journalisation) pour insertion et supprime et utilisez l'une des structures de données suggérées (le tas est probablement le meilleur). Si vous avez besoin de O (1) recherches, vous pouvez combiner un hachage, mais vous maintenez deux structures de données en parallèle et pourraient aussi bien utiliser un TREEMAP.
Une alternative serait juste de trier les éléments.
Dans votre scénario d'utilisation, il n'y a que 1 000 articles - les trier est juste d'incroyablement rapide (gardez à l'esprit que le journal 2 1000 ≈ 10 = presque 1), et il semble ne pas se produire Trop souvent.
Vous pouvez même adapter le algorithme de sélection pour renvoyer les k articles les plus petits. Malheureusement, cela va toujours dépend de n , non seulement sur k comme vous l'avais espéré: o ( n + k log k ).
(J'ai ajouté cela comme une nouvelle réponse car elle est en fait complètement non liée à ma première entrée.)
Mais cela déplace beaucoup de mémoire avec insert et supprime. Un petit btree peut-être?
@Stephan: J'aurais dû être plus clair, je suppose. Je faisais référence à une solution de table de hachage (avec un gros facteur de charge afin que la traversée soit efficace), puis copier les éléments dans un tableau - ou même ne pas les copier et effectuer la sélection en place. Ceci est juste une supposition sauvage, mais je serais certainement intéressé par une comparaison de performance de certaines des méthodes proposées.
Si la clé de tri est un nombre entier ou décimal simple, une trie sera assez rapide. Il utilisera la mémoire et trouvera techniquement un élément dans une trie est O (log n). Mais dans la pratique, ce sera quelque chose comme le journal 256 n, donc le facteur constant est très petit (log 256 de 2 milliards = 4) .
Je me sens, le tas est la meilleure structure de données de ce problème. Parce que, retirez, retirez et retournez K Les éléments supérieurs peuvent être retournés dans O (Klog (N)). Utilisez un tas Max-Heap si vous voulez des éléments max.
Ici, je suppose que k Eléments K signifie que les éléments K ont besoin de la valeur maximale.
Quelle est la clé? (direct ou un pointeur?)
@Stephan Eggermont: Les touches et les valeurs sont des entiers de 4 octets.