Dev Faq
8
votes

Trouver les valeurs les plus élevées sur une carte

J'ai une grande carte de String-> Entier et je souhaite trouver les 5 valeurs les plus élevées sur la carte. Mon approche actuelle consiste à traduire la carte dans une liste de matrices d'objet paire (clé, de valeur), puis à trier à l'aide de collections.sort () avant de prendre le premier 5. Il est possible pour une clé de la mise à jour de sa valeur au cours de l'opération. .

Je pense que cette approche est acceptable unique filetée, mais si j'avais plusieurs threads qui déclenchent toutes les transpositions et trichent fréquemment, il ne semble pas très efficace. L'alternative semble être de conserver une liste distincte des 5 entrées les plus élevées et de la conserver à mises à jour lorsque des opérations pertinentes sur la carte ont lieu.

Pourrais-je avoir des suggestions / alternatives à l'optimisation de cela s'il vous plaît? Je suis heureux d'envisager différentes structures de données s'il y a un avantage.

merci!

3 commentaires

Deux questions: 1) Pourquoi avoir une carte? Avez-vous besoin de rechercher des valeurs pour des clés données? 2) Avez-vous également besoin de connaître les clés des 5 valeurs les plus élevées?

@pgras - Oui, une autre fonction de l'API est de recevoir une clé et de renvoyer la valeur actuelle afin que une carte soit un bon point de départ. Nous avons besoin de connaître les clés pour les valeurs les plus élevées, c'est pourquoi j'ai été forcé d'utiliser un objet paire et non seulement créer une liste d'entiers.

Pouvez-vous spécifier les exigences de l'heure d'exécution exactement avez-vous à l'esprit? Votre actuel gethighestfive est O (n log n) , tout en modifiant la carte avec lookup , insérer et Supprimer est O (journal n) chacun. Voulez-vous obtenir gethaghestfive vers le bas de o (1) tout en préservant les autres heures d'exécution? Qu'est-ce que cela a à voir avec plusieurs threads, voulez-vous parallementer gethighestfive ?

7 Réponses :

5
votes

Eh bien, pour trouver les 5 valeurs les plus élevées sur une carte, vous pouvez le faire dans O (n) temps où toute sorte est plus lente que celle-là.

Le moyen le plus simple est de simplement faire A Pour boucle via l'ensemble de saisie de la carte. xxx

0 commentaires
2
votes

Je pense que cette approche est acceptable unique filetée, mais si j'avais plusieurs threads qui déclenchent toutes les transpositions et trichent fréquemment, il ne semble pas très efficace. L'alternative semble être de conserver une liste distincte des 5 entrées les plus élevées et de la conserver à mises à jour lorsque des opérations pertinentes sur la carte ont lieu.

Il y a une approche entre ceux que vous pouvez prendre aussi bien. Lorsqu'un thread demande une "vue triée" de la carte, créez une copie de la carte, puis gérez le tri à ce sujet. xxx

idéalement si vous avez un état (tel que cette carte) accessible par plusieurs threads, vous encapsulez l'état derrière une autre classe de sorte que chaque thread ne met pas à jour la carte. directement.

0 commentaires
0
votes

Veuillez essayer une autre structure de données. Supposons qu'il y ait une classe nommée MyClass que ses attributs sont la clé (chaîne) et la valeur (int). MyClass, bien sûr, doit mettre en œuvre une interface comparable. Une autre approche consiste à créer une classe nommée MyClassComparator qui étend le comparateur.

La méthode de comparète (peu importe où elle est) doit être définie comme ceci: comparèteo (paramètres) { Valeur de retour2 - Value1; // décroissant }

Le reste est facile. Utilisation de la liste et d'invoquer la méthode des collections.sort (Paramètres) fera la partie de tri.

Je ne sais pas ce qui trie les collections d'algorithme.sort (paramètres) utilise. Mais si vous sentez que certaines données peuvent venir au fil du temps, vous aurez besoin d'une sorte d'insertion. Comme il est bon pour une donnée qui a presque trié et c'est en ligne .

1 commentaires

Une autre fonction de l'API a la nécessité de récupérer une clé rapidement afin d'échanger une collection au lieu d'une carte blesser cette performance inacceptable comme la liste est grande. Cependant, votre idée est sonore - il n'y a aucune raison pour que je ne puisse pas mapper (clé -> composite (clé, valeur)) où le composite implémente comparable. Je pourrais alors juste dire des collections.sort (Carte.Values ​​()). Malheureusement, cela a toujours l'impact de la performance lorsque vous introduisez plusieurs threads à mesure que chaque thread pourrait une sorte de fusion (N (N log n)).

3
votes

Vous pouvez utiliser deux cartes: xxx

et assurez-vous de toujours les garder en synchronisation (éventuellement envelopper les deux dans une autre classe responsable de mettre, d'obtenir, etc.). Pour les valeurs les plus élevées, utilisez byvalue.navigablekeyset (). Descendickatorator () .

2 commentaires

J'aime vraiment ça, mais de la mémoire ne ferait pas que cela nécessite que toutes les valeurs sont uniques. Il est peu probable que cela soit le cas dans mon domaine, la carte de Byvalue serait probablement corrompue.

Bon point, j'ai modifié byvalue pour contenir tous les noms d'une valeur donnée.

0
votes

Si des modifications sont rares, j'étais implémenter quelque chose triétébyvalhashmap étend hashmap , similaire à linkedhashmap ) qui maintient les entrées commandées par valeur.

0 commentaires
1
votes

Je créerais une méthode comme: xxx

tirer parti de collections.max () et collections.singleton () < / p>

1 commentaires

Ceci est O (n), mais dans la pratique fonctionne assez lentement par rapport à d'autres méthodes.

1
votes

Il y a deux façons de le faire facilement:

  1. mettre la carte dans un Structure de tas et revenir le n éléments que vous voulez d'it.
  2. Itérate via la carte et mettre à jour une liste de n les valeurs les plus élevées en utilisant chaque entrée.

    Si vous souhaitez rétrécir un inconnu ou un grand nombre de valeurs les plus élevées, la première méthode est la voie à suivre. Si vous avez une petite quantité de valeurs fixe pour récupérer, la seconde pourrait être plus facile à comprendre pour certains programmeurs. Personnellement, je préfère la première méthode.

0 commentaires

Articles qui pourrait vous intéresser :

Comment envoyer une liste vide à la clause IN
Code de réponse 403 inattendu lors de la récupération des données des API
Impossible de trouver la classe UnityPlayerActivity dans com.unity3d.player
Comment définir un tableau dans jsonobject