如何優化對字符串數組數組的搜索？

我有數組的字符串數組。如何優化對字符串數組數組的搜索？

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

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

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

比方說我想找到一個元素「牛奶」。

我可以用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 
     } 
    } 
}

我試圖通過將所有元素設置爲Map鍵來使其更快。

//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; }

但是我想這仍然是N^2（即，對於環的for循環內，作爲添加的行的數量以mainList像ROW3 [ 'ITEM1'， 'ITEM2'， '項目3']，則迭代在N^2中遞增）

如何在沒有N^2的情況下優化這個？

來源

2011-05-11 masato-san

'Map m = new HashMap （）;'這不會編譯爲Map有兩個類型參數。另外，是什麼讓你認爲這將是O（n^2）？ – 2011-05-11 05:20:36

哎呀，我現在就修復它，謝謝指出 – 2011-05-11 05:21:05

由於您只訪問了一次元素，因此兩種算法都不是N^2。然而，第一種算法對每次查找都是O（N），但第二種算法是O（N）來填充地圖，O（1）用於每次後續查找。

來源

2011-05-11 05:22:27

哦，我認爲它是N^2，因爲for循環內循環。我可能會誤解 – 2011-05-11 05:25:54

循環邊界是不同的，所以它不能是N^2。你可以用M = mainList.size（）和N = max（mainList中的任何數組的長度）將它稱爲M * N，但是算法複雜性的重要部分是確定你的重要操作是什麼。在這種情況下，它是比較的數量，它具有所有列表中所有數組中所有元素的上限（即一些數字N）。如果你的算法試圖用（mainList）for（array）for（mainList）for（array）來計算重複次數，那麼這將是N^2。 – 2011-05-11 05:29:48

如果你知道你正在尋找一個GET操作的HashMap中的關鍵實際上是O（1）

來源：http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

來源

2011-05-11 05:24:27 Dimitar

爲什麼不能像下面的代碼？

 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);

來源

2011-05-11 05:28:37

Bkail打我這個答案，但我可以提供一些更深入的瞭解（即使它是一樣的。）

我相信你可能會在您的查找時間和你的建築有點不清楚時間。對於你提供的第一個例子，我認爲你有一個固定的構造時間（在Java中分配一個靜態數組常量？）。然後，你的查找時間（對於每個查找）是n（對於n個元素，而不是n * n）。我可以看到這可能會對你的符號有點混亂，因爲你的n個元素有兩行。

然而，對於你的第二個例子，你正在建設n。你的實際查找是O（1），就像其他答案一樣。

所以，重要的是要考慮的是你正在測量的東西。 Asymptotic notation爲查找是你感興趣的。

祝你好運！

來源

2011-05-11 05:29:30

如何優化對字符串數組數組的搜索？

回答

相關問題