Получить общее количество счетов

Question

У меня есть два ArrayList<Long> с огромными размерами около 5,00,000 в каждом. Я попытался использовать для цикла, использование которого list.contains(object), но это занимает слишком много времени. Я попытался разбить один список и сравнить в нескольких потоках, но эффективный результат не найден.

Мне нужен нет. элементов, которые одинаковы в обоих списках.

Любой оптимизированный способ?

Answer 1

Вы считаете, что вместо этого вы разместили элементы в HashSet? Это значительно ускорит поиск. Это, конечно, будет работать только в том случае, если у вас нет дубликатов.

Если у вас есть дубликаты, вы можете построить HashMap, который имеет значение в качестве ключа и счетчика как значение.

Answer 2

l1 be first list и l2 второй список. В нотации Big O, которая работает в O(l1*l2)

Другим подходом может быть вставка одного списка в HashSet, а затем для всех остальных элементов в другом списке, если он существует в HashSet. Это даст примерно 2*l1+l2 -> O(l1+l2)

Answer 3

Общий механизм должен сортировать оба списка, а затем повторять отсортированные списки, которые ищут совпадения.

Answer 4

Список не является эффективной структурой данных, когда у вас много элементов, вам нужно использовать структуру данных, более эффективную при поиске элемента. Например дерево или хэшмап!

Answer 5

Предположим, что в списке один есть m элементов, а список два имеет n элементов, m> n. Если элементы не численно упорядочены, кажется, что они не являются, общее количество шагов сравнения - это стоимость метода-фактора mxn-n^2/2. В этом случае коэффициент затрат составляет около 50000x49999.

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

int i=0,j=0; 
int count=0; 
while(i<List1.size() && j<List2.size()) 
{ 
    if(List1[i]==List2[j]) 
    { 
     count++; 
     i++; 
    } 
    else if(List1[i]<List2[j]) 
     i++; 
    else 
     j++; 
} 

Если это возможно для вас, чтобы держать списки заказали все время, этот метод будет сделать разницу. Также я считаю, что невозможно разделить и сравнить, если списки не упорядочены.