Поиск большого списка в огромном списке

Question

Имеется два больших списка, которые импортируются из внешнего файла. Один на 100000 строк, другой на 1000000. В первом содержится id. Во втором Id и название предмета. Нужно идти по первому списку и искать id во втором списке. Из найденных данных сформировать третий список и сохранить во внешний файл. Таких пар файлов больше сотни. То что сделал я, я импортировать два файла и с помощью цикла бегу по спискам, но это занимает много времени. Есть какой то способ или логика, чтобы быстрее проходить поиском по второму списку. Так как мне кажется именно это замедляет процесс. Заранее спасибо.

Код поиска. Думаю кода импорта файлов, не особо решает. В файле на 100к строк содежится id и количество В файле на 1 миллион строк, id, название предмета. Проще говоря, это справочник с названием предмета. И мне надо сопоставить эти два списка. В списках массивы строк.

for (String[] str:list100k) {
        for (String[] str2:list1mm) {
            if (str[2].equals(str2[1])){
                listEND.add((String[]) ArrayUtils.addAll(str, str2));

            }
        }
    }

Answer 1

Есть два списка:

List<String[]> list1 = ...; // список из N элементов
List<String[]> list2 = ...; // список из M элементов

У следующего кода алгоритмическая сложность O(N*M):

for (String[] s1 : list1) {
    for (String[] s2 : list2) {
        if (s1[0].equals(s2[0])) {
            // что-то делаем с s1 и s2
        }
    }
}

Сложность O(N*M) означает, что если взять списки размерами 10*N и 10*M, то время выполнения кода увеличится примерно в 100 раз.

Как сделать оптимальнее? Сконвертируем List в Map следующим образом:

Map<String, String[]> map1 = new HashMap<>();
for (String[] s1 : list1) {
    map1.put(s1[0], s1);
}

Теперь нам достаточно пройтись только по второму списку, тем самым мы избавимся от вложенного цикла for внутри for:

for (String[] s2 : list2) {
    String[] s1 = map1.get(s2[0]);
    if (s1 != null) {
        // что-то делаем с s1 и s2
    }
}

Вытащить элемент из HashMap занимает O(1), значит, алгоритмическая сложность оптимизированного кода будет O(N+M). Если каждый список увеличить в 10 раз, то время увеличится в 10 раз.

БЛОГ НА HUSL

Поиск большого списка в огромном списке

Ответы (1 шт):