Оптимизация сравнения двух списков

Question

У меня есть два списка (A и B) контактов, поступающих из SQL DB. В моем приложении мне нужно отобразить таблицу сравнения этих списков на основе имени контакта. Если в списке A существует контакт A, но не B, детали контакта A отмечены зеленым, а рядом с ним у меня пустое красное пространство (для отсутствия записи из списка B. Если имя контакта существует в B, а не в A , B отмечен зеленый цвет. Если имя контакта существует в обеих списках, но с разницей в адресе, оба контакт помечен желтым цвет.

Я генерация как сравнения CSV и постраничный интерфейс.

в настоящее время , мое не очень оптимальное решение сначала создаст третий список со всеми именами контактов из A и B, удалив дубликаты. Затем (если разбиение на страницы) я буду применять размер смещения +. Наконец, с остальными записями я буду искать A и B по имени контакта (из нового списка), и вызовите метод сравнения, который скажет мне, что делать с цветовой маркировкой.

Это работало нормально для данных, которые у меня есть, до 4 -5k, с задержками в 2 секунды в разбивке на страницы. Хотя я знаю, что это не идеальное решение, но не может придумать лучшего. Также я получил некоторые новые функции (изменения фильтра/добавления/удаления), которые не будут работать оптимально с этим методом.

Какой еще подход можно использовать для этой проблемы сравнения?

Update

контроллер код:

//createCompareList() based on parameters generate HQL query and pull contacts from Contact table 
     def listA = createCompareList(params) 
     def listB = createCompareList(params) 

     def unionList = listA.collect{it.details.name}.plus(listB.collect {it.details.name}) 
     unionList = unionList.unique() 
     result.unionListSize = unionList.size() 
     unionList.sort() 

И сравнение остальное происходит в GSP (это будет перемещен в контроллер, и передать то, что требует меньше обработки в GSP)

 <table class="table table-bordered"> 
      <thead> 
       <tr> 
        <th> C 

ontact name</th> 
       <th> List A </th> 
       <th> List B </th> 
      </tr> 
     </thead> 
     <tbody> 
      <g:each in="${unionList}" var="unionName"> 
       <g:set var="listAContact" value="${listA.find {it.details.name.equals(unionName)}}"/> 
       <g:set var="listBContact" value="${listB.find {it.details.name.equals(unionName)}}"/> 
       <tr> 

        <td> 
        <b>${unionName}</b> 
        </td> 

        <g:if test="${listAContact}"> 
         <g:if test="${listBContact}"> 
          <g:if test="${listAContact?.compareTo(listBContact) == 1}"> 
           <td class="warning"> 
          </g:if> 
          <g:else> 
           <td> 
          </g:else> 
          <g:render template="compare_cell" model="[obj:listAContact]"/> 
          </td> 
         </g:if> 
         <g:else> 
          <td class="danger"> 
           <g:render template="compare_cell" model="[obj:listAContact]"/> 

          </td> 
         </g:else> 
        </g:if> 
        <g:else><td></td></g:else> 


        <g:if test="${listBContact}"> 
         <g:if test="${listAContact}"> 
          <g:if test="${listBContact?.compareTo(listAContact) == 1}"> 
           <td class="warning"> 
          </g:if> 
          <g:else> 
           <td> 
          </g:else> 
          <g:render template="compare_cell" model="[obj:listBContact]"/> 

          </td> 
         </g:if> 
         <g:else> 
          <td class="success"> 
          <g:render template="compare_cell" model="[obj:listBContact]"/> 
          </td> 
         </g:else> 
        </g:if> 

        <g:else><td></td></g:else> 

       </tr> 

      </g:each> 
     </tbody> 
    </table> 

Answer 1

Если вы получаете данные из базы данных SQL, а ваши контакты указаны в разных таблицах, вы можете перенести orm a LEFT JOIN между их таблицами. Например:

SELECT A.*, B.id 
FROM ContactsA A 
LEFT JOIN ContactsB B ON A.id = B.id; 

И получить его результаты с помощью jdbc. Эти результаты содержат все контакты, принадлежащие ContactsA, плюс дополнительную колонку с id, если контакт присутствует в списке ContactsB или NULL, если нет. Вы можете использовать этот столбец, чтобы различать, какие записи представлены в обоих списках.

EDIT

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

Например, предположим, вы распределяете свои записи по возрасту, то запрос должен быть:

SELECT A.*, B.id 
FROM ContactsA A 
LEFT JOIN ContactsA B ON A.id = B.id AND B.age >= 18 
WHERE A.age < 18; 

END EDIT

Если вы не можете изменить свои запросы и у вас есть уже два Java List S: A и B, лучший способ проверить, является ли контакт присутствует или нет в обеих есть построить набор из короткого списка и использования которые устанавливают для проверки того, какие элементы более длинных списков отсутствуют в более короткие.

Answer 2

Мой совет: используйте SortedSet как аккумулятор. Таким образом, вы можете сохранить вызовы unique() и sort(), оба из которых будет перебирать весь список:

SortedSet unionList = new TreeList() 
for(def a in listA) unionList << a.details.name 
for(def b in listB) unionList << b.details.name 
unionList // now it's unique and sorted in one sit 

Answer 3

Чтобы ускорить Comparation из 2 Списков использовать наборы. Если вы используете значение хеша, введите имя контакта, которое вы можете проверить в O (1), если запись указана в списке. Если да, проверьте другие сведения.

Set<Contact> set_a = a.toSet 
Set<Contact> set_b = b.toSet 
foreach(e in (a union b)) 
    if(set_a contains e && !set_b contains e) 
    //in a but not in b 
    else if(!set_a contains e && set_b contains e) 
    //in b but not in a 
    else 
    //in b and in a, check additional information for these elements 

Если ускорить все это потому, что comparations намного дешевле

Это приводит к общей сложности O (2n) от Comparation + строит наборы. (Одна проверка для e в одной и одной проверке на e в b)

Answer 4

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

Согласно мне, пусть db обрабатывает сравнение, которое будет довольно быстро, чем код jdbc.

А и В список контактов и в БД оба присутствуют в виде таблиц

REQ1: список контактов в А, которые не присутствуют в B

select id <or required attrib> from A where id not in (select id from B) 

Это будет список ids, которые находятся только в A, добавьте их в java-список A с цветным зеленым цветом, как вы знаете, нет соответствующих записей в B, чтобы сохранить соответствующие записи в B как пусто

Req2: аналогичные материалы для уникального конта каратов в B

select id <or required attrib> from B where id not in (select id from A) 

точно напротив вещи в обоих списках, теперь добавьте этот список в B с зеленым цветом и соответствующих пустых записей в

Req3: тот же идентификатор в обоих списках, но адр дифф

select A.id from A,B where A.id=B.id and A.addr<>B.addr 

это дает список идентификаторов, которые совпадающих, но имеет дифференциалов адреса, теперь добавьте идентификаторы в обоих списках с желтым цветом

Это экономит сравнение, задание раскраски, которое немного тяжело в языках java/pgming.

Answer 5

Очевидное решение, о котором я не думал с самого начала, заключалось в создании карты из списка базы данных, используя Contact.name как ключ. Это значительно ускорило поиск, и с некоторыми изменениями в коде сравнения я получил 58 секунд обработки до 4 секунд.