Comment optimiser la recherche sur array of String array?

Question

J'ai des tableaux de chaînes de tableaux.

List<String[]> mainList = new ArrayList<String[]>(); 

String[] row1 = {"foo", "bar", "moo"} 
String[] row2 = {"cocoa", "zoo", "milk", "coffee"} 

mainList.add(row1); 
mainList.add(row2); 

Disons que je veux trouver un élément « lait ».

Je pourrais faire avec N^2.

for(int i=0, j=mainList.size(); i<j; i++) { 
    for(int x=0, y=mainList.get(i).length(); x<y; x++) { 
     String item = mainList.get(i)[x]; 

     if(item.equals("milk")) { 
      return true; //found milk 
     } 
    } 
} 

J'ai essayé de le rendre plus rapide en mettant tous les éléments comme touche de carte.

//put all elements to map key 
Map m = new HashMap<String, String>(); 
for(int i=0, j=mainList.size(); i<j; i++) { 
    for(int x=0, y=mainList.get(i).length(); x<y; x++) { 
     m.put(mainList.get(i)[x], "whatever"); 
    } 
} 

//now iterate and see if key "milk" is found 
if(m.contains("milk")) { return true; } 

Mais je compris cela est encore N^2 (c.-à boucle à l'intérieur de la boucle, lorsque le nombre de rangées ajouté à mainlist comme row3 [ « item1 », « item2 », « item3 »], le incréments d'itération dans N^2)

comment puis-je optimiser ceci sans N^2?

Answer 1

Aucun des deux algorithmes n'est N^2 puisque vous ne visitez qu'une seule fois les éléments. Cependant, le premier algorithme est O (N) pour chaque recherche, mais le deuxième algorithme est O (N) pour remplir la carte et O (1) pour chaque consultation ultérieure.

Answer 2

Si vous connaissez la clé que vous êtes à la recherche d'une opération get pour une hashmap est en fait O (1)

source: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Answer 3

Pourquoi ne peut pas être le code ci-dessous?

 String[] row1 = {"foo", "bar", "moo"}; 
     String[] row2 = {"cocoa", "zoo", "milk", "coffee"}; 

     HashMap<String, String> mainMap = new HashMap<String, String>(); 
     for(String s: row1) { 
      mainMap.put(s, s); 
     } 

     for(String s: row2) { 
      mainMap.put(s, s); 
     } 

     System.out.println(mainMap.get("milk") != null); 

Answer 4

Bkail m'a battu à cette réponse, mais la mienne pourrait fournir un peu plus de perspicacité (même si elle est la même.)

Je crois que vous pourriez être un peu clair sur votre temps de recherche et votre construction temps.

Pour le premier exemple que vous avez fourni, je pense que vous avez un temps de construction constant (alloue une constante de tableau statique en Java?). Ensuite, votre temps de recherche (pour chaque recherche) est n (pour n éléments, pas n * n). Je peux voir comment cela peut être un peu déroutant avec votre notation, car vos éléments n viennent en deux rangées. Cependant, pour votre deuxième exemple, vous dépensez n en construction. Votre recherche actuelle est O (1), comme les autres réponses ont dit. Donc, la chose importante à considérer est ce que vous mesurez. Asymptotic notation pour la recherche est ce qui vous intéresse.

Bonne chance!