multimap primitif en java avec de bonnes caractéristiques de performance (insertion, itération)

Je suis en train de faire un gros traitement (construction d'indices inverses) en utilisant ints/longs en Java.multimap primitif en java avec de bonnes caractéristiques de performance (insertion, itération)

J'ai déterminé que (un) boxe des cartes java.collections standard prend une grande partie du temps de traitement total. (par rapport à une implémentation similaire utilisant des tableaux, que je ne peux pas utiliser en raison de contraintes de mémoire).

Je suis à la recherche d'une rapide mise en œuvre 3ème partie (ou toute mise en œuvre du tout d'ailleurs) qui pourrait soutenir la structure suivante:

Carte avec des caractéristiques:

dans la carte -Les clés sont clairsemés (+/- 10.000.000 clés dans la plage [0,2^64] -les valeurs sont toujours ajoutées à la fin de la liste -insertion rapide (amortissement O (1) si possible) -fixe itération dans la clé

J'ai regardé trove, fastuti l, etc. mais n'a pas pu trouver une implémentation multimap en utilisant des primitives (seulement des cartes normales)

toute aide est appréciée.

Merci, Geert-Jan

Source

2009-11-12 Geert-Jan

est perdu: Carte –

Quel type d'API vous attendriez d'avoir des valeurs de toute clé donnée? Ou seriez-vous simplement en train de faire des requêtes contenant (clé, valeur)? –

Je pense que l'insertion O (1) amortie et l'itération rapide dans l'ordre des clés se contredisent, ou vous avez besoin d'un hachage qui maintient l'ordre des clés, ce qui serait mauvais si votre table de hachage est plus petite que la clé. –

Avez-vous envisagé la mise en œuvre la partie à plusieurs vous à l'aide d'une primitive longue -> Object-carte et primitive int-définie comme la valeur?

Source

2009-11-12 13:35:14

ouais je pensais à ce sujet .. Jamais fait quelque chose comme ça. Quel serait l'inconvénient d'avoir une carte longue -> longue primitive? Je demande parce que je pense à l'alternative de décodage {int} comme 1 long (en utilisant un peu de manipulation de bits, éliminant ainsi le 'multi' partie.Cette alternative me demanderait cependant de faire une recherche de la valeur chaque fois que j'insère/ajoute une nouvelle valeur afin que la nouvelle valeur décodée peut être calculée .. (espérons que cela a du sens) Du haut de ce que diriez-vous serait plus performant? –

Honnêtement, je ne sais pas. devrait faire un test rapide? –

Oui, je suis allé avec ma 2ème approche, qui s'avère être éclairant rapidement. (Je n'ai pas comparé si) Je signale votre réponse depuis (en combinaison avec les commentaires) il était le plus utile. Merci. –

Qu'en est-il de la bibliothèque de collections de Google? http://code.google.com/p/google-collections/

la structure

Source

2009-11-12 14:04:59 Dmitry

Nous ne prenons pas en charge les collections basées sur des primitives, donc chaque int devra être encadré. On dirait que ce serait un problème .. –

multimap primitif en java avec de bonnes caractéristiques de performance (insertion, itération)

Répondre

Questions connexes