Более быстрый способ сравнить списки для общего элемента в Java?

Question

У меня есть график (реализованный с помощью Vector) LinkedLists, и я хочу подключить LinkedLists, которые не имеют общих элементов.Я думаю, что способ, которым я делаю это прямо сейчас, занимает O (n ^ 3).У меня есть цикл for, который выполняет итерацию по вектору, затем вложенный цикл внутри, который выполняет итерацию по вектору (чтобы я мог сравнить каждый список с любым другим), а затем внутри цикла for я использую рекурсию для сравнения списков.

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

 public void addEdges(){
  for(int i =0; i < size()-1; i++){
   for(int j = i+1; j < size(); j++){
    if(compatible(get(i),get(j),1,1)){
     get(i).linkTo(get(j));
     get(j).linkTo(get(i));
    }
   }
  }
 }

, а вот мой рекурс:

 public boolean compatible(Row a, Row b, int indexA, int indexB){
  if(a.get(indexA).getEnd() == b.get(indexB).getEnd()){
   return false;
  }
  else if(a.get(indexA).getEnd() == 0){
   return true;
  }
  else if(a.get(indexA).getEnd() > b.get(indexB).getEnd()){
   return compatible(a,b,indexA+1,indexB);
  }
  else{
   return compatible(b,a,indexB+1,indexA);
  }
 }

Answer 1

Если я правильно понял, вы можете заменить метод compatible на вызов статического метода Collections.disjoint.

Редактировать: Пример кода:

public void addEdges(){
  for(int i =0; i < size()-1; i++){
   for(int j = i+1; j < size(); j++){
    if(Collections.disjoint(get(i),get(j))){
     get(i).linkTo(get(j));
     get(j).linkTo(get(i));
    }
   }
  }
 }

Answer 2

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

Answer 3

Я понимаю, что вы ищете более быстрый способ сделать это, и я думаю, @Michael Brewer-Davis предлагает лучший способ сделать это, но есть ли способ решить проблему до создания списки? Таким образом, вместо сравнения списков, когда они уже созданы, чтобы сделать сравнение, когда списки создаются, чтобы вам не пришлось так жестоко повторять? (я имею в виду, вероятно, изменение конструкции: сравнивать элементы для неравенства только один раз, чтобы несвязанные элементы группировались естественным образом и, возможно, избегали рекурсии)

Answer 4

Я мог бы попробовать обратный индекс, element -> [IDs of containing lists].Итерация по индексу покажет вам, какие списки имеют общие элементы, и, следовательно, не может быть подключена.

• Шаг 1: создать обратный индекс
• Шаг 2: создать индекс несовместимости, list ID -> [IDs of incompatible lists]
• Шаг 3: перебрать карту несовместимости для объединения совместимых списков.

Шаг 3 может быть более сложным, если существуют определенные правила для объединения совместимых списков, поскольку совместимость не является 't transient.

---

Некоторая псевдо-Java: Ради себя, я собираюсь предположить, что структуры данных выглядят так (вероятно, мой Bin - это ваш Row, более или менее):

class Bin {
    ID id;
    LinkedList<Element> list;
}

Набор корзин allBins имеет тип Collection<Bin>.

Шаг 1. Обратный индекс имеет тип MultiValueMap<Element, ID>.То есть каждый элемент сопоставляется с набором идентификаторов (ячеек, содержащих этот элемент).

MultiValueMap<Element, ID> reverseIndex;

for (Bin bin : allBins) {
    for (Element e : bin) {
        reverseIndex.put(e, bin.id);
    }
}

Шаг 2. Индекс несовместимости имеет тип MultiValueMap<ID, ID>, где каждый идентификатор ячейки сопоставляется снабор идентификаторов бинов несовместимых бинов.

MultiValueMap<ID, ID> incompatibilityIndex;

for (Element e : reverseIndex.keySet()) {
    List<ID> binsWithE = reverseIndex.get(e);
    for (ID id : binsWithE) {
        incompatibilityIndex.putAll(id, binsWithE); // each bin is incompat with itself
    }
}

Шаг 3: Теперь мы можем объединить любые два бина, которых нет в карте несовместимости друг друга.Поскольку объединение двух корзин изменяет несовместимость, мы должны быть хитрее:

Set<Bin> binsRemainingToProcess; // == original allBins
Set<Bin> binsProcessed; // == new allBins

while (binsRemainingToProcess.size() > 0) {
    Bin bin = // grab any bin to work on from binsRemainingToProcess

    // grab any compatible bins
    // could iterate until we find one, but I'm going to compute all compatible
    List<ID> compatibleBinIDs = // all bin IDs in binsRemaining...
    List<ID> incompatibleBinIDs = incompatibilityIndex.get(bin.id);
    compatibleBinIDs.removeAll(incompatibleBinIDs);

    if (compatibleBinIDs.size() > 0) {
        Bin otherBin = // some bin with ID in compatibleBinIDs

        // joining the two bins -- means joining the inner lists,
        // but also joining the incompatibilities
        joinDataStructures(bin, otherBin);
        incompatibilityIndex.putAll(bin.id, incompatibilityIndex.get(otherBinID));

        // we don't need the other bin anymore, but we may be able to join
        // the first bin to others
        binsRemainingToProcess.remove(otherBin);
    } else {
        // couldn't join with anyone; we're done with this bin and can move on
        binsRemainingToProcess.remove(bin);
        binsProcessed.add(bin);
    }
}

Хорошо, так что последний оказался намного более подробным, чем я планировал ...