J'utilise malheureusement, lorsque la collection upd: je sais comment travailler autour de cela. J'aimerais savoir pourquoi PriorityQueue pour le tri partiel de certaines données. En particulier, c'est le code: est vide, le code échoue, car priorityQueue ne peut pas être transmis zéro comme initialeCapacité. Quelles sont les raisons de cette décision de conception? Pourquoi ne peut-il pas y avoir un priorityQueue ? prioritorakeeue inclure ce code max (1, n) à l'intérieur - y a-t-il des raisons ou s'agit-il d'une mauvaise conception de l'API?
5 Réponses :
Si vous pensez que les moyens de capacité, cela signifie la préparation de la file d'attente pour pouvoir stocker au moins X articles sans nécessiter d'allocations de mémoire internes supplémentaires. Donc, si vous attendez une file d'attente pour contenir un maximum de 100 éléments, vous pourriez définir la capacité de 100 dans le constructeur pour préparer cela.
Quel est le point de dire à une file d'attente d'attendre aucun article? Il n'a pas de sens d'autoriser 0 en premier lieu de sorte que la valeur minimale est 1 et que le constructeur jette une exception si vous passez 0 (ou moins).
Votre exemple semble beau mais comment le développeur devrait-il savoir que ce sera 100 articles lorsqu'il écrit le code? Il pense normalement à "N", et n étant = 0 est une situation normale.
@chiccodoro: souvent, vous pouvez obtenir une approximation de n d'autres données. Et si vous ne pouvez pas, cela n'a pas d'importance. Ceci est juste un indice. S'il est trop petit, la file d'attente se redimenstrera.
@chiccodoro, 100 articles est Mereley la capacité et non le nombre d'articles qui seront stockés. N'appliquez pas votre expérience à tout le monde. De nombreux problèmes ont un domaine fini des intrants, donc dans de nombreux cas, un développeur a une très bonne idée de quel type de capacité dont ils pourraient avoir besoin. De plus, n = 0 pourrait être une situation normale, mais c'est une situation où vous n'utiliseriez pas le conteneur, alors pourquoi faire une grosse objectivité?
@Mikerobi: Vous avez raison de dire que vous n'utiliseriez pas le conteneur du tout. La chose est que si votre N peut être quelque chose de 0 ... XYZ, il est plus confortable d'écrire "N" au lieu de choses comme "Math.min (n, 1)".
@chiccodoro, la capacité est juste un indice - "Je m'attends à ce que de nombreux articles Tops". Si cette valeur est dépassée, la file d'attente allouera toujours un espace supplémentaire. Si vous ne pouvez pas estimer la limite supérieure avec précision, faites une hypothèse approximative. Si vous ne pouvez pas faire cela, ne vous préoccupez pas de définir un indice et d'utiliser la valeur par défaut. Il est probable que cela ne fait pas une différence énorme de performance, mais elle enregistre l'allocation et la copie des données d'un tableau à un autre de temps en temps.
@Locka, en fait, je sais exactement combien d'articles la file d'attente stockera - autant que la collection que je vais trier. Mais cela arrive juste que parfois cette collection est vide.
Pourquoi voudriez-vous créer une collection, puis spécifier qu'il devrait être vide?
Vous pouvez simplement instancier la priorityQueue avec math.max (1, données.Size ())
Je fais plusieurs transformations sur la collection initiale et je ne veux pas écrire de code séparé pour le cas quand il est vide. Le moins de code, mieux c'est.
Il y a PriorityQueue<Data> queue = new PriorityQueue<Data>(Math.max(data.size(), 1), dataComparator);
Je suppose qu'il utilise l'autre constructeur parce que c'est la seule façon de passer un comparateur spécial.
@ Péter Török: Ah, c'est vrai. C'est un comparateur, pas une collection. J'ai mal lu. J'ai édité ma réponse pour refléter cela.
du code source de pritorakeeue: Lire la suite:
Il décrit la façon dont la file d'attente fonctionne en interne et je demande à son API.
L'API est une mise en œuvre de la structure de données prioritaires. Essentiellement, @Stark est correct.
Cela ne répond toujours pas à la question.
Le gentleman Elite: peu importe la mise en œuvre, le constructeur pourrait permettre des valeurs 0..n juste pour des raisons d'homogénéité. En fait, la solution idéale pour cela serait de permettre la création d'une prioritéQueue (collecte, constructeur).
Je suis d'accord que cela ne répond pas à la question et c'est une décharge de commentaire. Dans ma défense, il fait en réalité des détails sur la structure de données sous-jacente (une matrice de modélisation d'un tas binaire équilibré) et des indices que la raison de cette restriction est de simplifier la mise en œuvre.
Si cela ne répond pas à la question, pourquoi est-ce la réponse la plus votée? whyyyy?
Pourquoi voulez-vous utiliser une file d'attente? Une file d'attente est une structure de données conçue pour le cas où vous avez un "producteur" qui en fait des éléments et un "consommateur" qui les résonne. Une file d'attente prioritaire commande les éléments enrocence à l'aide d'une structure d'arborescence. Un tampon est nécessaire pour qu'un producteur puisse en faire encaissant, donc initialcapacity = 0 code> n'a aucun sens. for (Data item : Collections.sort(data, dataComparator)) {
// ...
}
Je l'utilise pour / partiel / trier. Je peux avoir beaucoup d'éléments de données, mais je dois sélectionner seulement les 10 premiers ou plus, pas besoin de trier le reste.
Vous devez les trier tous afin d'obtenir le top 10. (+1 pour comprendre le problème)
Obtenir les top k Éléments d'un ensemble peut facilement être effectué dans O (n) Temps, tout en triant, en général, nécessite (sur le journal N). CLRS CommNets sur elle et Wikipedia donne une référence extrêmement bonne sur le sujet: en.wikipedia.org/wiki/selection_algorithm . Pour le traitement paralell / distribué, il existe des techniques de carte / de réduction: PL.Postech. AC.KR/~MYSON/PastWork/dr.html
@Daniel: C'est un très bon indice! Toutefois, si Shooshpanchick n'a pas besoin exactement de 10 éléments, mais plutôt après que chaque article décidait s'il en a besoin d'une autre, je crains que cela ne fonctionne plus dans O (n), malheureusement. Ai-je raison?
Le priorityQueue Javadoc dit explicitement que Supprimer () est o (journal (n)) . Cela signifie que je sais que je sache combien d'éléments dont j'ai besoin, la récupération de premier k sera O (k journal (n)) qui est meilleur que O (n journal (n)) pour le tri.
Combien de temps l'insert prend-il? Parce que vous avez toujours besoin de les trier tous sur INSERT. Donc, l'insertion de tous les éléments sera O (n journal (n)), puis en supprimant les dix premières seront O (k log (n)). O ((n + k) * journal (n)) est plus lent que O (n * journal (n)).
@chiccodoro: Oui. Si vous utilisez des algorithmes de sélection de temps constants pour un tel scénario, vous pouvez finir par avoir un algorithme O (N ^ 2). C'est en fait l'idée même derrière la sélection. La question est pragmatique: comment votre k compare-t-il avec votre n. Si k = o (lg n), le tri tout sera aussi bon. En pratique, la plupart des systèmes qui utilisent des algorithmes Top K ont réellement k jusqu'à 2000 ou 10000, et ces chiffres sont bien inférieurs à N, ce qui est généralement dans l'échelle des millions ou des milliards. La seule meilleure pratique consiste à utiliser votre intelligence.
@Daniel: Merci! J'ai incorporé votre allusion dans ma réponse.
Qu'entendez-vous par «le code échoue»? Qu'est-ce qui se passe exactement?
Le constructeur de prioritésQueue lancera une idée illegalargumentException, voir télécharger.oracle .Com / Javase / 6 / Docs / API / Java / Util / ...
Vous pouvez toujours demander à Joshua bloch ( en.wikipedia.org/wiki/joshua_bloch ). Il a écrit priorakeeeue.
The Elite Gentleman: Pensez-vous qu'il répondrait?