J'ai une grande grille 2D, X-by-y. L'utilisateur de l'application ajoutera des données sur des points spécifiques sur cette grille. Malheureusement, la grille est beaucoup trop grosse pour être implémentée comme un grand tableau X-by-y, car le système sur lequel il est en cours d'exécution n'a pas assez de mémoire.
Qu'est-ce qu'un bon moyen de mettre en œuvre cela afin que seuls les points qui les aient ajoutés sont stockés en mémoire?
Ma première idée était de créer une BST des points de données. Une fonction de hachage telle que "(long) x << 32 + y" serait utilisé pour comparer les nœuds.
J'ai ensuite conclu que cela pourrait perdre de l'efficacité s'il n'est pas bien équilibré, alors je suis venu avec l'idée d'avoir une BST de BST de points comparables. La BST extérieure comparerait les BST internes en fonction de leurs valeurs x. Les BST internes compareraient les points par leurs valeurs Y (et ils auraient tous les mêmes x). Ainsi, lorsque le programmeur veut voir s'il y a un point à (5,6), ils interrogeraient la BST extérieure pour 5. Si une BST intérieure existe à ce point, le programmateur interrogeait la BST intérieure pour 6. Le résultat serait être retourné.
Pouvez-vous penser à un meilleur moyen de mettre en œuvre cela?
Edit: En ce qui concerne HashMaps: la plupart des hachages nécessitent une matrice pour la recherche. On dirait "données [hachage (point)] = point ();" Pour définir un point, trouvez le point en hachage pour trouver l'index. Le problème, cependant, est que la matrice devrait être la taille de la plage de la fonction de hachage. Si cette plage est inférieure au nombre total de points de données ajoutés, ils n'auraient plus de place ni être ajoutés à un débordement. Parce que je ne connais pas le nombre de points qui seront ajoutés, je devrais supposer que ce nombre serait inférieur à une certaine quantité, puis définir la matrice à cette taille. Encore une fois, cela instancie un très grand tableau (bien que moins que à l'origine si l'hypothèse est qu'il y aura moins de points de données que x * y). J'aimerais que la structure s'élève linéairement avec la quantité de données et ne prenez pas une quantité importante lorsqu'elle est vide.
On dirait que ce que je veux, c'est un Sparsarray, comme certains l'ont mentionné. Sont-ils mis en œuvre de la même manière à avoir une BST à l'intérieur d'une BST?
Edit2: map <> est une interface. Si je devais utiliser une carte, il ressemble à Treemap <> serait le meilleur pari. Donc, je me retrouverais avec Treemap Edit3: Pour ceux qu'il peut s'agir, la réponse sélectionnée est la meilleure méthode. Premièrement, il faut créer une classe de points contenant (x, y) et implémente comparable. Le point pourrait potentiellement être comparé par quelque chose comme (((long) x) << 32) + y). Ensuite, on tracerait chaque point sur les données. La recherche est efficace car elle est dans un arbre équilibré de sorte que le coût du journal (n). L'utilisateur peut également interroger toutes ces données, ou itérer à l'aide de la fonction Treeemap.EntrySet (), qui renvoie un ensemble de points avec les données.
En conclusion, cela permet de mettre en œuvre une matrice rare-efficacité et efficace de recherche d'un réseau de race, ou dans mon cas, un tableau 2D, qui peut également être itéré à travers efficacement.
8 Réponses :
Vous pouvez avoir une liste de listes d'un objet et cet objet peut encoder sa position horizontale et verticale.
class MyClass
{
int x;
int y;
...
}
Mais à chaque fois qu'un nouvel objet est ajouté, car je souhaite avoir un ensemble de points unique, je devrais effectuer une recherche dans la liste de toutes les données à voir si elle existe déjà avant de mettre à jour le point de données ou d'ajouter un nouveau. J'essayais d'éviter ce processus inefficace.
@Reedb, ce n'est pas qu'innefficace, surtout si vous avez une liste Liste des listes avec la liste extérieure correspondant à x et la liste intérieure correspondant à y . La recherche serait O (x + y) la complexité du temps
Vous pouvez utiliser une carte comparable et utilisation navigagblap
+1 bonne solution; Battez-moi-moi :) J'aime aussi la mention de NavigaBablap .
Pourquoi ne pas simplement utiliser la classe point ?
@splungebob que vous voulez dire java.awt.point ? Je pense que c'est toujours une mauvaise idée d'utiliser des classes destinées à un objectif totalement différent, juste parce qu'ils ont les bonnes propriétés. Le point AWT est mutable, peut être défini avec des doubles et peut avoir des transformations appliquées - totalement pas ce dont nous avons besoin ici.
@Kirilraychev: Bonne explication.
@Kirilraychev j'ai eu un point réimmenté à utiliser dans des systèmes embarqués où Java.Awt n'était pas disponible, c'est plus de travail qu'il n'y paraît d'abord.
Donc, si je voulais itération à chaque point de la carte sans vérifier chaque mappage potentiel, je pourrais utiliser la fonction Treeemap.KeSet () pour obtenir un ensemble de toutes les valeurs de clé, puis itérairez-les?
@Reedb oui vous pouvez. La manière recommandée est d'itérer entrée et non KEYSET car il est plus efficace, mais le fera soit.
Peut-être que je suis trop simpliste ici, mais je pense que vous pouvez simplement utiliser un puis vous remplacez la méthode des égaux (et donc la méthode de code HASHCODE) à être basée sur hashmap . Il contiendrait des objets sur mesure d'objets sous forme de touches: x et y . De cette façon, vous ne stockez que des points qui ont des données.
Je pense que vous êtes sur la bonne voie pour le faire de manière efficace de mémoire - il peut être mis en œuvre assez facilement en utilisant une carte des cartes, enveloppé dans une classe pour donner une interface propre pour les recherches.
Une approche alternative (et plus efficace de la mémoire) serait d'utiliser une seule carte, où la clé était un tuple (x, y). Cependant, cela serait moins pratique si vous devez faire des requêtes comme 'Donnez-moi toutes les valeurs où x == Quelques valeur '.
La carte des cartes a l'air prometteuse. Comme je l'ai dit dans quelques autres commentaires, si j'utilisais une carte unique qui était un Treemap, il devrait comparer les nœuds basés sur une sorte de valeur hachée générée à partir des deux points, comme mon idée originale d'une seule BST . Si cette carte était une carte linéaire, comme une liste, cela serait très inefficace car chaque fois que je souhaitais ajouter des données, je devrais rechercher de manière linéaire dans la liste pour voir s'il existe déjà avant de la mettre à jour ou d'ajouter un Nouveau point de données.
Une approche pourrait être Une autre approche consiste à représenter la ligne et la colonne sous forme de coordonnée de classe de classe ou d'un point mappe data dans ce cas) correspond aux données à (rangée, colonne) . Bien sûr, cela ne vous aidera pas si vous envisagez d'essayer de faire des opérations de matrice ou de telles. Pour cela, vous aurez besoin de matrices clairsemées.
point . Vous devrez implémenter égale et hashcode (devrait être très trivial). Ensuite, vous pouvez représenter vos données comme mapper mappe
soit un Quadtree , un k -d-p arbre ou un r-arbre .
Magasin d'index sur le grand tableau de points dans l'une des structures spatiales. Ces structures spatiales sont avantageuses si les données ne sont pas également distribuées de manière égale, comme des données géographiques qui se concentrent dans les villes et n'ont pas de point dans la mer.
pense que si vous pouvez oublier la grille régulière et rester avec l'arbre quad.
(Pense, pourquoi avez-vous besoin d'une grille régulière? Une grille régulière n'est généralement qu'une simplification)
En aucun cas, utilisez des objets pour stocker un point. Un tel objet nécessite 20 octets que pour le fait que c'est un objet! Une mauvaise idée d'un énorme ensemble de données.
Un envisager de lire
Hanan Samet 's "Fondations de structures de données multidimensionnelles"
(au moins l'introduction). int x [] , et int [] y ou un int [] xy est idéal pour l'utilisation de la mémoire.
@Andrealigios, oui avec ceux-ci, vous pouvez augmenter la performance d'un facteur de 100 à 1000, par rapport à votre ancienne mise en œuvre
Ce sont de bonnes structures, mais un quadtree ne serait pas préférable car mes données sont organisées dans des lignes et des colonnes discrètes au lieu de points répartis dans un domaine continu 2D, ce que le Quadtree a été conçu. Merci d'avoir répondu!
Le Quadtree a été conçu pour des coordonnées continues. C'est pour les coordonnées entière, généralement une puissance de deux. Si discret. L'arbre quadrière est un index et non le stockage lui-même. Il avait l'habitude de trouver les points à proximité avec un minimum d'effort. Vous pouvez stocker vos données comme pintes (rangées, col) ou (x, y). Vos données sont-elles également distribuées ou regroupées sur certaines taches?
Je recommande également une sorte de structure d'arbres comme ceux mentionnés ici pour préserver la corrélation spatiale, alors que l'approche de la table de hachage vous perdez cette information.
Vous voudrez peut-être examiner FlexCompcolmatrix, CompcolMatrix et d'autres implémentations de matrices rares à partir du Projet Toolkit Matrix < / a>.
La performance dépendra vraiment du rapport d'écriture / lecture et de la densité de la matrice, mais si vous utilisez un emballage matriciel, il sera plus facile à expérimenter en commutant la mise en œuvre
Ma suggestion à vous est d'utiliser Math Math: la bibliothèque mathématique Apache Commons . Parce que cela sauvera votre journée, en tirant parti de la force de calcul de votre application.
Stackoverflow.com/Questions/390181/...
Ne réinventez pas la roue, regardez les structures de données spatiales
Vous semblez être intéressé davantage dans la mise en œuvre sous-jacente de la structure de données, au lieu de la manière dont vous allez l'utiliser. Si vous avez besoin de requêtes spatiales (points avec X entre 10 et 40) ou des requêtes de voisin les plus proches, vous pouvez utiliser certaines des structures Alexwien mentionnées, ou une carte navigable. Si vous avez besoin de rechercher un point spécifique uniquement, un vieil hashmap clair ferait un bon travail - docs.oracle.com/javase/6/docs/aplap.html/hashmap.html
@Kiril Raychev: Une fois que les points sont ajoutés, je prévois d'utiliser toutes les données de la structure pour effectuer des calculs, mais je n'ai pas besoin de requêtes à distance.
Ok, semble que la carte est la meilleure pour votre utilisation. Mais lorsque vous entrez dans la vitesse d'un problème spatial S, envisagez d'utiliser un hashmap qui n'est pas basé sur un objet, qui économise 60% de l'espace mémoire. (Objet Point VS Types primitifs)
@ALEXWIEN: Si j'utilise un hashmap primaire, je devrais appuyer sur une grande matrice sur la pile, comme expliqué mon premier édition. Cela est presque aussi inefficace de mémoire que l'utilisation d'une matrice mappée directe car les deux nécessitent une grande quantité d'espace au démarrage. Si le mappage est alloué de manière dynamique, je suis capable d'utiliser très peu de mémoire quand il y a peu de points (mais oui, il y aura une surcharge de pointeur).
Tant que vous n'expliquez pas vos opérations, il n'est pas possible de trouver la meilleure structure. Un arbre B avec des points dans une matrice indexée du morton est également possible. ou une grille de hashmaps