J'ai donc une liste d'objets, disons une liste d'étudiants avec des variables telles que Je cherche une structure de données pouvant stocker des objets de l'étudiant et permet également la recherche sur l'une des variables ci-dessus. La complexité de temps est la partie clé ici car il y aura des milliers de recherches effectuées sur les données.
EX: Si j'utilise l'arbre binaire, je peux prendre un hashcode de toute variable dire, Y a-t-il une structure de données qui peut permettre de stocker l'étudiant une fois et permet également à la recherche de l'étudiant sur les différentes variables. Ou toute structure de données hybride pouvant être créée pour répondre à l'exigence.
J'aimerais obtenir une complexité de temps de nom d'utilisateur , numéro de rouleau , standard , , Division , etc.
nom d'utilisateur puis en sortit et stocke l'objet étudiant dans l'arborescence binaire. Cependant, cela a une limitation, comme si je souhaite rechercher l'étudiant sur la norme , il n'est pas possible comme l'index auquel l'étudiant est stocké dans l'arborescence binaire a été généré à partir de Nom d'utilisateur .
O (1) au mieux O (journal n) . .
3 Réponses :
Si vous souhaitez trouver tous les élèves ayant un numéro de rôle particulier code> ou particulier standard code>, vous pourriez maintenir plusieurs hachements de hashmaps aux étudiants: HashMap<Standard, List[Student]>
HashMap<RollNumber, List[Student]>
HashMap<Username, Student> (assuming usernames are unique)
L'idée de HASHMAP n'est pas le bon choix car la structure de données interne de la HASHMAP, EX: S'il y a des milliers d'enregistrements stockés dans le hashmap, il y aura certainement des collisions d'index, qui créeront une liste lieded à l'intérieur du hashmap et La complexité de temps sera pire, c'est-à-dire O (n). En outre, créer différents hashmap pour chaque variable augmente la complexité de l'espace. Dans KDTREE, je peux stocker des données sur plusieurs variables. Toutefois, les recherches sont également effectuées à l'aide de plusieurs variables uniquement et non une ou moins que les dimensions.
Notez que bien que la complexité du pire des cas de la recherche de hashMAP soit O (n), l'affaire moyenne est O (1).
Si je devais faire cela, je créerais un tableau de Ensuite, je créerais un étudiant s, où l'index de chaque étudiant serait son identifiant.
hashmap hashmap numéro de rouleau à un identifiant, etc.
Considérant le nom d'utilisateur, les numéros de rouleaux sont uniques pour chaque élève et standard, les divisions peuvent être partagées par plusieurs étudiants.
Vous pouvez élaborer une solution à la fin de la mode pour atteindre le O (1) / O (journal (n) ) / O (n) en fonction des cas. P>
permet de définir la structure de classe en premier: p> permet de créer des cartes pour stocker ces étudiants p> Map<String, Set<String>> standardMap; // standard to set of student's username/rollnumber.
Le seul nom d'utilisateur est unique, tous les autres paramètres peuvent être répétés, disent que deux étudiants différents de différentes normes ou divisions peuvent être les mêmes. Il y aura également des scénarios, où je voudrais rechercher si deux étudiants différents ont le même numéro de rôle dans le même STD et la même division.
Il est déjà implémenté avec la base de données de base de données et NOSQL pourquoi vous voulez le faire dans votre programme sans les utiliser?
@tashkhisi afin qu'il soit nécessaire d'être fait en mémoire, car dire que nous exécutons ce dos à dos dans un travail de lot avec des milliers d'enregistrements.
Quelle est la requête la plus complexe et la question la plus fréquente que vous devrez soutenir?
En outre, quelle est la taille de votre ensemble de données (c'est-à-dire combien d'étudiants et la taille de chaque enregistrement d'étudiant)?
En moyenne, il y aura 10k enregistrements sur lesquels la recherche sera effectuée.