J'ai un haschmap et j'aimerais parcourir les paires de la valeur clé dans un ordre aléatoire différent à chaque fois que je reçois l'itérateur. Conceptuellement, je voudrais "shuffer" la carte avant d'appeler l'itérateur (ou si vous le souhaitez, "mélanger" l'itérateur).
J'ai deux options que je vois:
1) Utilisez l'approche de LinkedHashMap et gardez une liste des entrées en interne, mélangez-la en place et renvoyez cette vue lorsque l'itérateur est appelé.
2) Prenez la carte.Entryset (), construisez une arraylist et utilisez Shuffle () dessus.
Alors que les deux approches semblent protégées similaires à moi, je m'attends à de très grandes halfmaps, donc je suis vraiment préoccupé par les détails et les internaux, car je ne suis vraiment pas en mesure de perdre de mémoire ni de calcul.
3 Réponses :
Essayez d'utiliser une carte de hachage de concurrente et d'obtenir la clé par aléatoire avant le cycle d'itération
Map<String, String> map = Maps.newConcurrentMap();
map.put("1", "1");
map.put("2", "2");
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
map.remove("2");// add random key values
map.put("2", "2");
String next = iterator.next();
System.out.println("next" + next);
}
Mettre peut mélanger vos entrées, mais sa très improbable. Supprimer / mettre ne fera rien.
Reshuffler une grande collection va toujours être cher. Vous aurez besoin d'au moins une référence par entrée. par exemple. Pour 1 million d'entrées, vous aurez besoin d'environ 4 Mo.
note; L'opération de vente de lecture est J'utiliserais O (n)
Comment va-t-il mélanger o (n lg n)? Un shuffle-Yates de pêcheur ne prend que du temps linéaire et donc collections.shuffle .
Correct, un tri du tri boiteux est o (n * journal n) et le shuffle java utilise est en effet o (n)
C'est fondamentalement mon (2) approche proposée. Vous comptez sur le fait que les frais généraux supplémentaires sont 4bytes par entrée? Pourquoi ça?
Les versions les plus récentes de JVMS prennent en charge les références 32 bits. Pour une grande collection, la plupart des espaces de la liste seront les références au map.Entry s. Il y a une légère optimisation si vous réélivez à plusieurs reprises la même liste.
Dans Java 1.7, vous pouvez éliminer l'argument de type explicite map.Entry = nouvelle arrayliste <> (map.entryset ());
En fait, vous n'avez pas besoin de shuffer du tout:
Dessinez simplement un index aléatoire dans un tableau de touches et retirez la clé en remplaçant avec le dernier:
public class RandomMapIterator<K,V> implements Iterator<V> {
private final Map<K,V> map;
private final K[] keys;
private int keysCount;
@SuppressWarnings("unchecked")
public RandomMapIterator(Map<K,V> map) {
this.map = map;
this.keys = (K[]) map.keySet().toArray();
this.keysCount = keys.length;
}
@Override
public boolean hasNext() {
return keysCount!=0;
}
@Override
public V next() {
int index = nextIndex();
K key = keys[index];
keys[index] = keys[--keysCount];
return map.get(key);
}
protected int nextIndex() {
return (int)(Math.random() * keysCount);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
Supprimer () sur une arracheListe n'est pas exactement une opération de chep, car elle nécessite un changement de données. En outre, cela nécessite un accès aléatoire à la structure de données via GET (), qui est O (1) mais toujours plus cher que d'itération à l'intérieur de la structure de données.
@MARCOROSSI Merci d'accord sur le Supprimer () mais mon point principal reste: le tirage au sort aléatoire atteint le même objectif que le mélange à une fraction du coût. ArrayList N'était PAS le meilleur choix de structure car nous n'avons pas besoin de l'ordre des clés à maintenir de toute façon. J'ai révisé ma solution avec un tableau simple. La décision vient de savoir si vous préférez prendre le coût O (n) Coût initial ou O (1) Coût de chaque suivant ().
Vous n'êtes pas au courant des détails de la mise en œuvre, mais vous pouvez toujours vérifier les sources Java ... Si vous connaissez le calcul de la complexité de temps, vous devriez être capable d'extrapoler quelque chose vous-même, du moins pour la partie de calcul :)