перебор и сравнение больших наборов данных

Question

В основном я получаю 2 большие списки данных из 2 различных баз данных, список выглядит следующим образом:

List 1: 
============= 
A000001 
A000002 
A000003 
. 
. 
A999999 

List 2: 
============= 
121111 
000111 
000003 
000001 
. 
. 

Мне нужно сравнить два список и выяснить, каждый из данных, которые в List 1 доступен в List 2(после добавления к нему стандартного ключа), так что, если он доступен, поместите его в 3-й список для дальнейших манипуляций. Например, A000001 доступен в List 1, а также в List 2(после добавления к нему стандартного ключа), поэтому мне нужно поместить его в 3-й список.

В принципе, у меня этот код, он подходит для каждой строки в List 1, я повторяю все данные в List 2 и делаю сравнение. (Оба являются списками массивов)

List<String> list1 = //Data of list 1 from db 
List<String> list2 = //Data of list 2 from db 

for(String list1Item:list1) { 
    for(String list2Item:list2) { 
    String list2ItemAfterAppend = "A" + list2Item; 
    if(list1Item.equalsIgnoreCase(list2ItemAfterAppend)) { 
     //Add it to 3rd list 
    } 
    } 
} 

Да, эта логика работает нормально, но я считаю, что это не эффективный способ перебора списка. После размещения таймеров он занимает 13444 миллисекунды в среднем для 2000x5000 списка данных. Мой вопрос в том, есть ли какая-нибудь другая логика, о которой люди могут подумать, или предложить мне улучшить производительность этого кода?

Надеюсь, я поняла, если не сообщите, если я могу улучшить вопрос.

Answer 1

---

Я думаю, проблема в том, насколько большой список и сколько у вас памяти. Для меня для менее 1 миллиона записей, я буду использовать HashSet, чтобы сделать это быстрее. код может понравиться:

Set<String> set1 = //Data of list 1 from db, when you get the data you make it a Set instead of a List. HashSet is enough for you to use. 
List<String> list2 = //Data of list 2 from db 

Тогда вам просто необходимо:

for(String list2Item:list2) { 
    if(set1.contains("A" + list2Item) { 
    } 
} 

Надеется, что это может помочь вам.

Answer 2

Вы можете заказать оба списка, а затем использовать только один цикл итерации по обоим значениям, переключение которых индексируется в зависимости от того, какое значение является наибольшим. Что-то вроде:

boolean isWorking = true; 
Collections.sort(list1); 
Collections.sort(list2); 
int index1 = 0; 
int index2 = 0; 

while(isWorking){ 
    String val1 = list1.get(index1); 
    String val2 = "A" + list2.get(index2); 
    int compare = val1.compareTo(val2) 

    if(compare == 0){ 
     list3.add(val1); 
     index1++; 
     index2++; 
    }else if (compare > 0){ 
     val2++; 
    }else{ // if(compare < 0) 
     val1++; 
    } 

    isWorking = !(index1 == list1.size() || index2 == list2.size()); 
} 

Остерегайтесь того, какой список вы используете. get(int i) на LinkedList стоит дорого, тогда как он не находится на ArrayList. Кроме того, вы можете захотеть сохранить list1.size() и list2.size(), я не думаю, что он вычисляет его каждый раз, но щекочу его. Я не уверен, действительно ли он полезен/эффективен, но вы можете инициализировать list3 с размером самого маленького из обоих списков (принимая во внимание loadFactor, ищите его), поэтому list3 не должен изменять размер каждый раз.

Код выше не проверен (возможно, коммутатор val1++ и val2++), но вы получите эту идею. Я считаю, что это быстрее, чем ваш (потому что это O (n + m), а не O (n * m), но я дам вам увидеть (оба sort() и compareTo() добавят некоторое время по сравнению с вашим методом, но обычно это не должно слишком много). Если вы можете, используйте свою RDBMS для сортировки обоих списков, когда вы их получите (так что вам не нужно это делать в коде Java).

Answer 3

Вы можете использовать метод пересечения из сообщества apache.Пример:

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collection; 
import java.util.List; 
import org.apache.commons.collections4.CollectionUtils; 

public class NewClass { 

    public static void main(String[] args) { 
     List<String> list1 = Arrays.asList("A000001","A000002","A000003"); 
     List<String> list2 = Arrays.asList("121111","000111","000001"); 
     List<String> list3 = new ArrayList<>(); 
     list2.stream().forEach((s) -> {list3.add("A"+s);}); 
     Collection<String> common = CollectionUtils.intersection(list1, list3);  
    } 
} 

Answer 4

Вы можете попробовать использовать Stream API для этого код, чтобы создать новый список с Streams очень кратким и понятным, и, вероятно, очень похожи по производительности:

List<String> list3 = list2.stream() 
           .map(s->"A"+s) 
           .filter(list1::contains) 
           .collect(Collectors.toList()); 

Если список большой, вы можете попытаться обработать список параллельно и использовать несколько потоков для обработки списка. Этот может или не может улучшить производительность. Выполнение некоторых мер важно, чтобы проверить, действительно ли обработка списка параллельна, фактически повышает производительность.

Для обработки потока параллельно, вам нужно всего лишь вызвать метод parallel на потоке:

List<String> list3 = list2.stream() 
           .parallel() 
           .map(s->"A"+s) 
           .filter(list1::contains) 
           .collect(Collectors.toList()); 

Answer 5

Ваш код делает много манипуляций со строками, «equalsIgnoreCase» преобразовать символы в верхний/нижний дело. Это выполняется в вашем внутреннем цикле, а размер вашего списка - 5000x2000, поэтому манипуляция с String выполняется миллионы раз.

В идеале, получите свои строки в верхнем или нижнем регистре из базы данных и избегайте преобразования внутри внутреннего цикла. Если это невозможно, возможно, преобразование случая строки в начале улучшает производительность.

Затем, вы можете создать новый список с элементами одного из списков и сохранить все элементы, присутствующие в другом списке, код с прописной преобразования может быть:

list1.replaceAll(String::toUpperCase); 
List<String> list3 = new ArrayList<>(list2); 
list3.replaceAll(s->"A"+s.toUpperCase()); 
list3.retainAll(list1);