Qui structure de données utilisez-vous: TreeMap ou table de hachage? (Java)

Question

Description | Un programme Java pour lire un fichier texte et d'imprimer chacun des mots uniques dans l'ordre alphabétique avec le nombre de fois que le mot apparaît dans le texte.

Le programme devrait déclarer une variable de type Map<String, Integer> pour stocker les mots et les correspondants de la fréquence. Qui type de béton, si? TreeMap<String, Number> ou HashMap<String, Number> ?

L'entrée doit être convertie en minuscules.

Un mot ne contient pas l'un de ces caractères: \t\t\n]f.,!?:;\"()'

Exemple de sortie |

 Word            Frequency
  a                 1
  and               5
  appearances       1
  as                1
         .
         .
         .

Remarque | je sais, j'ai vu des solutions élégantes pour cette en Perl, avec à peu près les deux lignes de code. Cependant, je veux le voir en Java.

Edit: Ah oui, il sera utile de montrer une mise en œuvre à l'aide de l'un de ces structures (en Java).

Answer 1

TreeMap semble une évidence pour moi - tout simplement parce que le "par ordre alphabétique" exigence. HashMap a pas de commande lorsque vous itérer dessus; TreeMap itère dans la nature de la touche de commande.

EDIT: je pense que Konrad commentaire peut avoir été suggérant "utiliser la table de hachage, puis trier." C'est bien parce que bien que nous aurons N itérations d'abord, nous aurons K <= N touches par la fin en raison des doublons. On pourrait ainsi économiser le peu cher (tri) jusqu'à la fin lorsque nous avons moins de touches que de prendre le petit-mais-non-constante coup de le garder triés comme nous allons le voir.

Cela dit, je m'en tiens à ma réponse pour le moment: parce que c'est le plus simple moyen d'atteindre l'objectif. Nous ne savons pas vraiment que l'OP est particulièrement inquiet au sujet de la performance, mais la question implique qu'il est préoccupé par l'élégance et la concision. À l'aide d'un TreeMap fait de cette très courte, ce qui me convient. Je pense que si la performance est vraiment un problème, il peut y avoir une meilleure façon de l'attaquer que soit TreeMap ou HashMap :)

Answer 2

TreeMap beats HashMap parce que TreeMap est déjà trié pour vous.

Cependant, vous pouvez envisager d'utiliser un plus appropriée structure de données, un sac. Voir Communes des Collections et de la TreeBag classe:

C'est une belle optimisé la structure interne et de l'API:

bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")

EDIT: la question de La HashMap vs TreeMap performance a été répondu par Jon - HashMap et de tri qui peut être plus rapide (essayez!), mais TreeBag est plus facile. La même chose est vraie pour les sacs. Il y a un HashBag ainsi que d'un TreeBag. Basé sur la mise en œuvre (utilise une mutable entier) un sac devrait dépasser l'équivalent de la plaine de la carte de l'Entier. La seule façon de le savoir est de tester, comme avec toutes les performances de la question.

Answer 3

Je vois très peu de gens en disant: "TreeMap look-up prend O(n log n)"!! Comment venir?

Je ne sais pas comment il a été mis en œuvre, mais dans ma tête il prend O(log n).

C'est parce que de recherche dans un arbre qui peut être fait en O(log n). Vous n'avez pas trier l'ensemble de l'arbre chaque fois que vous insérez un élément en elle. C'est l'idée de l'aide d'un arbre!

Donc, revenir à la question initiale, les chiffres à des fins de comparaison à son tour d'être:

HashMap approche: O(n + k log k) moyenne de cas, dans le pire des cas pourrait être beaucoup plus

TreeMap approche: O(k + n log k) pire des cas

où n = nombre de mots dans le texte , k = nombre de mots distincts dans le texte.

Answer 4

Vous ne pouvez pas affecter un TreeMap<String,Number> à une variable de type Map<String,Integer>. Double, Long, etc. peut être "mis" en TreeMap<String,Number>. Quand je "obtenir" une valeur à partir d'un Map<String,Integer>, il doit être un Integer.

Complètement ignorant tout de l'i18n les enjeux, les contraintes de mémoire, et les erreurs de manipulation, va ici:

class Counter {

  public static void main(String... argv)
    throws Exception
  {
    FileChannel fc = new FileInputStream(argv[0]).getChannel();
    ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
    CharBuffer cb = Charset.defaultCharset().decode(bb);
    Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
    Map<String, Integer> counts = new TreeMap<String, Integer>();
    Matcher m = p.matcher(cb);
    while (m.find()) {
      String word = m.group();
      Integer count = counts.get(word);
      count = (count == null) ? 1 : count + 1;
      counts.put(word, count);
    }
    fc.close();
    for (Map.Entry<String, Integer> e : counts.entrySet()) {
      System.out.printf("%s: %d%n", e.getKey(), e.getValue());
    }
  }

}