Как я могу оптимизировать поиск по массиву массив строк?

Question

У меня есть строковые массивы массивов.

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

Я попытался сделать это быстрее, поместив все элементы в качестве ключа карты.

//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', 'item3'], увеличивается итерация в N ^ 2)

как я могу оптимизировать это без N ^ 2?

Answer 1

Ни один из этих алгоритмов не является N ^ 2, поскольку вы посещаете элементы только один раз. Тем не менее, первый алгоритм - это O (N) для каждого поиска, а второй алгоритм - это O (N) для заполнения карты и O (1) для каждого последующего поиска.

Answer 2

Почему не может быть код, указанный ниже?

        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 3

Если вы знаете, что ключ, который вы ищете для операции get для хэш-карты, на самом деле O (1)

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

Answer 4

Бкаил побил меня этим ответом, но мой мог бы дать немного больше понимания (даже если это то же самое).

Я полагаю, вы можете быть немного неясными относительно времени поиска и времени строительства.

Для первого примера, который вы предоставили, я думаю, что у вас есть постоянное время конструирования (выделяется ли константа статического массива в Java?). Тогда ваше время поиска (для каждого поиска) равно n (для n элементов, а не n * n). Я могу видеть, как это может немного смущать ваши нотации, так как ваши n элементов располагаются в две строки.

Однако, для вашего второго примера, вы тратите n на строительство. Ваш фактический поиск O (1), как и в других ответах.

Итак, важно учитывать то, что вы измеряете. Асимптотическая запись для поиска - это то, что вас интересует.

Удачи!