Comment implémenter un cache avec une matrice binaire en tant que matrice de clés et binaire en tant que valeurs en Java

Question

J'ai besoin de créer un cache Java qui contient toutes les villes et tous les aéroports. Donc, si je demande le cache pour un emplacement, disons une ville, il devrait retourner tous les aéroports de cette ville et si je demande un emplacement qui est un aéroport, je devrais revenir cet aéroport. En outre, chaque emplacement doit être stockée en tant que tableau d'octets dans la mémoire cache (comme l'interface exposée pour l'interrogation de la mémoire cache a byte [] en tant que paramètre pour la localisation) D'autres considérations sont les suivantes:.

1. La récupération doit être très rapide, aussi vite que possible
2. Le cache est chargé une seule fois au démarrage du système. Il ne change pas après avoir reçu chargé.
3. Comme il est chargé une seule fois, nous pouvons le garder trié si cela accélère la récupération.

Ce que j'ai jusqu'à présent:

Approche 1

Créer une enveloppe mince sur octet tableau [], permet de dire ByteWrapper. Placez chaque emplacement (les deux aéroports et les villes) comme une clé dans la carte (TreeMap?). Utilisez les listes de ByteWrapper (contenant les aéroports où cela s'applique) comme valeurs.

Approche 2

Créer octet tableau multidimensionnel [] qui est triée sur place. C'est essentiellement une carte. Ensuite, utilisez la recherche binaire pour localiser la clé et renvoyer les résultats.

Quelle approche suggérez-vous? S'il vous plaît laissez-moi savoir dans le cas où vous avez de meilleures idées Merci

Answer 1

Vous n'avez pas besoin de tableaux d'octets, les chaînes seraient bien.

À quelle fréquence ajouteriez-vous des éléments dans ce cache? Je suppose que c'est complètement statique, car ils ne font pas de nouvelles villes ou d'aéroports tous les jours. Donc, ce que vous pouvez faire est d'utiliser deux MultiHashMaps, une clé sur la ville et une autre sur les aéroports. Commander Google Multimap http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

Si vous utilisez mySQL par hasard, vous pouvez utiliser une table basée sur Memory Storage Engine.

De nombreuses bases de données peuvent épingler une table en mémoire, certainement Oracle, ce qui est une autre façon de procéder.

Answer 2

Le fait que l'API exposée soit basée sur byte [] ne doit pas nécessairement dicter les détails internes de votre cache.

La deuxième observation est qu'il ne s'agit pas d'un problème de structure de données généralisé. L'espace de tous les aéroports et l'espace de toutes les villes sont finis et bien connus. (Vous connaissez même la taille).

Les hachages de cartes, d'arbres, etc. sont tous des algorithmes qui garantissent certaines caractéristiques de performance dans les limites établies pour un usage général.

Depuis l'intégrité des données est un non-problème (« les données ne change pas ») et si des considérations d'espace ne sont pas critiques (« aussi vite que possible »), alors pourquoi pas:

[Edit: ce bit en quelque sorte coupées perdu dans la coupe et coller: vous index (nombre) vos villes et aéroports, étant donné que vous connaissez ces ensembles et ils sont effectivement statique]

// these need to get initialized on startup 
// this initialization can be optimized. 

Map<byte[], Long> airportIndexes = new HashMap<byte[], Long>(NUMBER_OF_AIRPORTS); 
Map<byte[], Long> citiesIndexes = new HashMap<byte[], Long>(NUMBER_OF_CITIES); 

Map<Long, byte[]> airports = new HashMap<Long, byte[]>(NUMBER_OF_AIRPORTS); 
Map<Long, byte[]> cities = new HashMap<Long, byte[]>(NUMBER_OF_CITIES); 

long[][] airportToCitiesMappings = new byte[NUMBER_OF_AIRPORTS][]; 
long[][] citiesToAirportMappings = new byte[NUMBER_OF_CITIES][]; 


public List<byte[]> getCitiesNearAirport(byte[] airportName) { 
    Long[] cityIndexes = getCitiesByIdxNearAirport(airportName); 
    List<byte[]> cities = new ArrayList<byte[]>(cityIndexes.length); 
    for(Long cityIdx : cityIndexes) { 
     cities.add(cities.get(cityIdx)); 
    } 
    return cities; 
} 
public long[] getCitiesByIdxNearAirport(Long airportIdx) { 
    return airportToCitiesMappings[airportIdx]; 
} 
public long[] getCitiesNearAirport(byte[] airportName) { 
    return getCitiesNearAirport(airportIndexes.get(airportName)); 
} 
public long[] getCitiesNearAirport(Long airportIdx) { 
    return airportToCitiesMappings[airportIdx]; 
} 
// .. repeat above pattern for airports. 

cela devrait vous donner O (1) caractéristiques de performance du temps. . Il y a une redondance considérable en termes d'espace.

Answer 3

Donnez essayer d'approcher 1, comme octet [] est un type d'objet, vous pouvez utiliser quelque chose comme:

Map<byte[], List<byte[]>> cache = ... 

Il est probablement l'approche la plus simple, il vous suffit devrez choisir la mise en œuvre de votre carte. Probablement vous devriez aller avec un HashMap parce qu'il est le plus simple ...

Comme gustavc dit en utilisant un HashMap ne fonctionne pas, vous pouvez utiliser à la place un TreeMap avec un comparateur donné:

Map<byte[], List<byte[]>> m = new TreeMap<byte[], List<byte[]>>(new Comparator<byte[]>() { 
    public int compare(byte[] o1, byte[] o2) { 
     int result = (o1.length < o2.length ? -1 : (o1.length == o2.length ? 0 : 1)); 
     int index = 0; 
     while (result == 0 && index < o1.length) { 
      result = (o1[index] < o2[index] ? -1 : (o1[index] == o2[index] ? 0 : 1)); 
      index++; 
     } 
     return result; 
    } 
}); 

Answer 4

SO cette est ce que je l'ai fait jusqu'à présent:

private static byte[][][] cache = null; // this is the actual cache 
// this map has ByteArrayWrapper(a wrapper over byte[]) as key which 
// can be an airport or city and index of corresponding 
// airport/airports in byte[][][]cache as value 
Map<ByteArrayWrapper, Integer> byteLocationIndexes = null; 
/** 
* This is how cache is queried. You can pass an airport or city as a location parameter 
* It will fetch the corresponding airport/airports 
*/ 
private byte[][] getAllAirportsForLocation(ByteArrayWrapper location) { 
    byte[][] airports = null; 
    airports = byteLocationIndexes.get(location)== null ? null : cache[byteLocationIndexes.get(location).intValue()]; 
    return airports; 
} 

banc I marqué performance à l'aide à la fois chaîne comme clé dans indexmap (et en utilisant le cache String [] []) et ByteArrayWrapper comme la clé (et byte [] en cache). Il y a une amélioration de 15 à 20% si j'utilise ByteArrayWrapper et byte [] [] [] cache.

Que peut-on faire d'autre pour améliorer les performances? Serait-il utile si j'utilise une autre implémentation de Map? Comme le cache n'est chargé qu'une seule fois et ne change jamais, il peut être trié. La plupart du temps est pris dans la recherche de clé dans byteLocationIndexes et c'est le goulot de la bouteille. Je calcule déjà hashCode au moment de la création de l'objet et le stocke comme une variable locale dans ByteArrayWrapper.

Des suggestions?