Dev Faq
8
votes

Structure de données avec index rapide?

J'ai besoin d'une structure de données commandée avec O (1) index de fonctionnement. Je stocke les pointeurs d'objet dans la structure de données. Des idées? Une sorte de linkedhashmap?

Voir ce que "indexof" signifie: list.indexof (objet)

0 commentaires

5 Réponses :

0
votes

Essayez d'utiliser la file d'attente prioritaire plutôt que de le faire commander ...

1 commentaires

? Hachmaps ne sont même pas ordonnés.

7
votes

Cette question est ambiguë pour commencer.

  1. Ce serait bien si vous pouviez qualifier ce que vous entendez par simple indexof (..) code> opération. LI>
  2. Quel genre d'objets allez-vous stocker dans la collection? LI>
  3. trouve l'index (..) code> la seule responsabilité de la collection. li> ol>

    Mettez simplement, une façon de le faire serait de maintenir un fichier qui indiquerait chaque objet ou des touches avec la liste des indices. P> 

    HashMap<Object, List<Integer>>

3 commentaires

Alors pourquoi ne pas avoir une autre structure de données qui stocke des références à chaque objet de la liste d'origine?

Je dois gérer HashMap > chaque fois que j'insère ou supprimer des objets de la structure de données principale? N'y a-t-il pas une telle structure de données pour le faire.

Par une source de données, vous voulez dire dans des collections Java - alors. Si vous voulez dire s'il existe une structure de données définie par l'utilisateur ou un moyen de le faire, alors bien sûr.

1
votes

Si vous utilisez une liste de sauts ou un arbre équilibré, vous pouvez obtenir O (journal n) pour Insérer et indexof .

Si vous maintenez une liste de liste triée pour enregistrer les éléments que vous souhaitez suivre, avec un hashmap pour stocker la position de départ de Chaque élément, vous pouvez obtenir O (1) indexof dans Exchange pour O (n) Insérer .

Je n'y ai pas pensé profondément, mais je ne pense pas qu'il soit possible d'obtenir O (1) Insert et O (log n) index de.

0 commentaires
2
votes

sonne comme si vous voulez un triedmap < / Code> , TREEMAP < / Code> Être la mise en œuvre de la référence. La performance est journal (n) , et c'est probablement le meilleur que vous allez obtenir de la recherche dans une structure ordonnée (au moins dans les bibliothèques standard).

0 commentaires
0
votes

Stockez l'objet comme clé et valeur dans HASHMAP. Je suppose que vous cherchez à récupérer l'objet éventuellement.

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