Stockage grande quantité de configurations en java

Question

J'ai un type de données (appelons-il des données) qui contient 2 informations:

int config 
byte weight 

Ce type de données est la conversion d'une série de 32 booléens. Je dois effectuer des changements à ces 32 booléens le convertir en ce type de données et le stocker. Le problème est que je veux seulement stocker des entrées uniques en éliminant les doublons. Le problème est qu'il existe 2^33 configurations possibles pour ce type de données.

J'ai essayé quelque chose comme ceci:

static class searchedconfigs { 
    Data[] searchedconfigs; 
    int position; 
    public searchedconfigs() { 
     searchedconfigs = new Data[150000]; 
    } 
    public void initiateposition() { 
     position = 0; 
    } 
    public boolean searchfield(Data Key, int entries) { 
     boolean exists = false; 
     for (int i = 0; i <= entries; i++) { 
      if (searchedconfigs[i] == Key) { 
       System.out.println("break"); 
       exists = true; 
       break; 
      } 
     } 
     return exists; 
    } 
    public void add(Data config, int position) { 
     searchedconfigs[position] = config; 
    } 
    public int getPosition() { 
     return position; 
    } 
    public void storePosition() { 
     position++; 
    } 
} 

L'initiation de la position se fait et l'augmentation est fait pour chaque fois que je recherche le tableau que dans les positions occupées. Mon problème est que vous pouvez voir que le tableau est seulement de la taille 1500000. Lequel j'ai besoin d'être beaucoup plus grand. Cependant, même l'attribution d'un entier de taille maximale (j'ai besoin d'un long pour faire un tableau de la taille dont j'ai vraiment besoin) provoque une erreur de mémoire insuffisante. En outre, ma fonction de champ de recherche semble ne pas comparer correctement la clé et la configuration stockées à cette position.

Quelqu'un peut-il me dire ce que je peux faire pour corriger ces erreurs ou suggérer une approche différente pour stocker ces données.

Answer 1

Utilisez un HashSet, et mettre en œuvre equals et hashCode dans Data, comme ceci:

import java.util.Objects; 

class Data { 
    int config; 
    byte weight; 

    @Override 
    public int hashCode() { 
     return Objects.hash(config, weight); 
    } 

    @Override 
    public boolean equals(Object other) { 
     if (other == null) return false; 
     if (!(other instanceof Data)) return false; 
     if (other == this) return true; 

     return this.config == other.config && this.weight == other.weight; 
    } 
} 

Set s de toute nature ne contiennent pas d'éléments en double. Puisque votre classe Data semble être un type de valeur (les valeurs membres sont plus importantes que son identité lors de la comparaison pour l'égalité), l'échec de l'implémentation de ces deux méthodes laissera toujours des doublons dans la structure de données de votre choix.

Answer 2

Quelle est la limite d'espace que vous utilisez actuellement? Les tableaux de Java sont limités à Integer.MAX_VALUE (2^31-1?). Êtes-vous dépassement:

• Nombre maximal d'éléments dans un tableau?
• Le tas affecté à la machine virtuelle Java?
• L'espace de RAM + échange disponible sur la machine?

S'il s'agit du nombre d'éléments, examinez une autre structure de données (voir ci-dessous). Si vous avez dépassé le tas, vous devriez allouer plus de mémoire à votre application (-Xmx arg à la JVM lors de l'exécution de votre programme). Si vous manquez de mémoire sur la boîte, les astuces d'économie d'espace ne vous mèneront que très loin; finalement la croissance des données dépassera ces choses. À ce stade, vous devez regarder soit la mise à l'échelle horizontale (calcul distribué) ou la mise à l'échelle verticale (obtenir une plus grande boîte avec plus de RAM). Si vous ne faites que surcharger un tableau parce qu'il ne peut pas être dimensionné au-delà de max et que l'espace est vraiment un souci j'éviterais d'utiliser HashSet car il faudra plus d'espace qu'un List/Array ou un autre Définir l'implémentation comme un TreeSet. Pour que les HashSets fonctionnent efficacement, ils ont besoin d'une table de hachage surdimensionnée afin de réduire le nombre de collisions de hachage dans l'espace. HashSet en Java a un facteur de charge par défaut de 75%, ce qui signifie que quand il dépasse cette capacité, il se redimensionnera lui-même plus grand pour rester sous le facteur de charge.En général, vous échangez une plus grande quantité d'espace pour une insertion/suppression/recherche plus rapide des éléments de l'ensemble qui, je crois, est un temps constant (Big O of 1). Un TreeSet devrait seulement exiger que votre capacité de stockage soit identique au nombre d'éléments (surcharge négligeable) mais au compromis d'une recherche augmentée & temps d'insertion qui est logarithmic (Big O de Log (n)). Une liste partage une caractéristique de stockage similaire (dépend de l'implémentation utilisée) mais a un temps de recherche de N si elle n'est pas ordonnée. (Vous pouvez rechercher les différents temps d'insertion/suppression/recherche des différentes implémentations de la liste & ordonné vs non ordonné ils sont très bien documentés)

Je veux juste noter lorsque vous utilisez un HashSet vous échangez l'efficacité de l'espace pour un look plus rapide -up temps (Big O de 1). Vous devez allouer de l'espace pour la table de hachage qui doit être plus grande que le nombre total d'éléments de votre collection. (Bien sûr, il y a la mise en garde que vous pouvez forcer la taille de votre seau à être 1 en ayant une fonction de hachage horrible qui vous remettrait effectivement aux caractéristiques de performance d'une liste non-ordonnée;)