HashMap avec des plages de dates

Question

Je dois trouver quelques valeurs très rapide basé sur un multi-clé. La clé est composée de: < Int userId, String measureName, Date startDate, Date endDate > et la valeur est un double.

Le problème est que je dois demander la valeur indiquant un jour, et non une plage de dates. Donc, si je demande un userId, un measureName et un jour, la structure de données doit répondre avec la valeur où le jour est entre startDate et endDate (il n'y a pas de chevauchement entre les plages de dates).

Je ne peux pas comprendre quelle est la meilleure structure de données pour implémenter ceci. HashMap? TreeMap? MultiKeyMap? RangeMap? Aidez-moi! :)

Answer 1

Je pense que vous devriez utiliser TreeMap et des méthodes telles que: http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#floorEntry(K) http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#higherEntry(K) mais utiliser en fonction de comparaison une seule date - startDate ou endDate. Comme ces plages ne se chevauchent pas, cela ne devrait pas poser de problème et rendre les méthodes mentionnées de TreeMap utilisables.

Par exemple, si vous décidez d'utiliser en comparaison endDate (et d'autres domaines, à l'exception d'autres dates) que vous devez utiliser la méthode floorEntry

Answer 2

TreeMap avec un objet clé personnalisé serait le mieux. Vous auriez quelque chose comme:

... 
TreeMap<MyMultiKey,Double> map = ... 

class MyMultiKey implements Comparable<MyMultiKey>{ 
... 
} 

En supposant la méthode de compareToMyMultiKey a été mis en œuvre pour commander vos clés multi-correctement, vous pouvez créer une nouvelle MyMultiKey exemple chaque fois que vous vouliez rechercher un jour spécifique en utilisant map.floorKey(MyMultiKey m) et map.higherKey(MyMultiKey m) pour vous assurer que vous avez trouvé une clé avec une heure de début et de fin qui contenait le jour que vous avez spécifié dans votre nouvelle instance de clé.

Answer 3

Je recommande une carte pour la clé partielle utilisateur/mesure. La valeur serait un tableau trié de tuples (plage de dates, floatval). Dans ce tableau, vous effectuez une recherche binaire pour une plage de dates contenant le jour.

Answer 4

Qu'en est-il d'une combinaison de Map et de List? La carte a une clé composée de userId et measureName, la valeur est une gamme liste de date triée et double value:

Map<Key,List<Entry>> data = new HashMap<>(); 
List<Entry> entries = data.get(new Key(userId, measureName)); 
int i = Collections.binarySearch(entries, new Entry(searchDate,searchDate, 0.0)); 
double value = i < 0 ? 0.0 : entries.get(i).value; 

Key doit mettre en œuvre hashCode() et equals() utilisant ses membres userId et measureName. Entry doit Comparable<Entry> où compareTo() doit retourner 0 si une plage fait partie de l'autre (comparaison startDate est < = 0 et la comparaison endDate est> = 0 ou 0 si la comparaison startDate est> = 0 et la comparaison endDate est < = 0) Sinon, comparez startDate + (endDate-startDate)/2 (milieu de la plage) quel que soit le double value.

Si vous lisez et ne modifiez pas cette structure, elle devrait être rapide. La comparaison sera compilée en natif si elle est utilisée beaucoup. Si la fonction fonctionne sur un seul utilisateur et mesure uniquement, vous pouvez uniquement utiliser la liste triée, si seulement sur un seul utilisateur, vous pouvez créer une structure similaire à Map<UserId<Map<MeasureName,List<Entry>>>>.

Essayez d'abord une solution simple, mesurez avant et après, effectuez les optimisations de performance seulement si nécessaire.