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

#java #arrays #algorithm #optimization

#java #массивы #алгоритм #оптимизация

Вопрос:

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

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

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

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

Допустим, я хочу найти элемент «milk».

Я мог бы использовать 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 внутри цикла for, поскольку количество строк, добавленных в mainList, например row3[‘item1’, ‘item2’, ‘item3’], увеличивается на итерации в N ^ 2)

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

1. Map m = new HashMap<String>(); Это не будет компилироваться, поскольку Map имеет два параметра типа. Кроме того, что заставляет вас думать, что это будет O (n ^ 2)?

2. упс, я сейчас это исправлю, спасибо, что указали

Ответ №1:

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

1. О, я предположил, что это было N ^ 2, потому что цикл for внутри цикла for. Возможно, я неправильно понимаю

2. Границы цикла разные, поэтому их не может быть N ^ 2. Вы могли бы назвать это M * N с M =mainList.size() и N = max (длина любого массива в mainList), но важной частью алгоритмической сложности является определение того, в чем заключается ваша существенная операция. В данном случае это количество сравнений, которое имеет верхнюю границу всех элементов во всех массивах во всех списках (т. Е. некоторое число N). Если бы ваш алгоритм вместо этого пытался подсчитать количество дубликатов, используя for(mainList) for (array) for(mainList) for (array), это было бы N ^ 2.

Ответ №2:

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

источник: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Ответ №3:

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

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

Ответ №4:

Bkail опередил меня в этом ответе, но мой может дать немного больше информации (хотя это то же самое).

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

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

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

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

Удачи!