Java-алгоритм: записи списка пар по нескольким критериям для случая

Question

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

данных:

Что мы работаем с здесь является CSV-файл, содержащий несколько столбцов, соответствующие них для этой задачи являются:

• ID пользователя (Integer, от 3 до 8 цифр, несколько записей с одинаковыми UserID существуют) СПИСОК СРАВНЕТСЯ НА ЭТОЙ
• Query (String)
• Epoc (Long, значение времени EPOC)
• ClickURL (String)

Каждая запись в данных мы работаем с здесь! Нулевые значения для этих атрибутов.

Пример данные:

SID,UID,query,rawdate,timestamp,timegap,epoc,lengthwords,lengthchars,rank,clickurl 
5,142,westchester.gov,2006-03-20 03:55:57,Mon Mar 20 03:55:57 CET 2006,0,1142823357504,1,15,1,http://www.westchestergov.com 
10,142,207 ad2d 530,2006-04-08 01:31:14,Sat Apr 08 01:31:14 CEST 2006,10000,1144452674507,3,12,1,http://www.courts.state.ny.us 
11,142,vera.org,2006-04-08 08:38:42,Sat Apr 08 08:38:42 CEST 2006,11000,1144478322507,1,8,1,http://www.vera.org 

Примечание: есть несколько записей, которые имеют одинаковое значение «Epoc», это происходит из-за инструменты, используемых для сбора данных

Примечание2: этот список имеет размер ~ 700000, только fyi

Цель: Матч пары записей, которые имеют тот же запрос

Область применения: элементы, которые разделяют один и тот же UserID

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

Если две записи имеют одинаковое значение для «Query» и для «Epoc», следующие элементы в списке должны быть проверены для этих критериев, пока следующая запись не будет иметь другое значение для одного из этих атрибутов. Группа записей, которые имеют одни и те же значения Query и Epoc, должна рассматриваться как «одно-запись», поэтому для сопоставления пары должна быть найдена другая запись, соответствующая значению «Query». Из-за отсутствия лучшего названия, давайте называть группу, которая разделяет тот же запрос и EPOC значением а «цепь»

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

1. записи & записи
2. записи & цепи
3. цепи & цепи

Тип 1 здесь означает только две записи в списке, которые имеют одинаковое значение для «Запроса», но не для «Epoc».

Так что это подводит итог Равное запросов Пары

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

После того как мы соответствовали равные пары запросов, есть возможность наличия записей, которые не были сопряжены с другими записями, потому что их запрос не совпал - каждая запись, которая не была сопоставлена ​​с другой записью, из-за этого является частью набора , называемого «разные запросы».

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

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

Пример:

Следующие записи должны быть спарены

UID,Query,Epoc,Clickurl 
772,Donuts,1141394053510,https://www.dunkindonuts.com/dunkindonuts/en.html 
772,Donuts,1141394053510,https://www.dunkindonuts.com/dunkindonuts/en.html 
772,Donuts,1141394053510,https://www.dunkindonuts.com/dunkindonuts/en.html 
772,raspberry pi,1141394164710,http://www.raspberrypi.org/ 
772,stackoverflow,1141394274810,http://en.wikipedia.org/wiki/Buffer_overflow 
772,stackoverflow,1141394274850,http://www.stackoverflow.com 
772,tall women,1141394275921,http://www.tallwomen.org/ 
772,raspberry pi,1141394277991,http://www.raspberrypi.org/ 
772,Donuts,114139427999,http://de.wikipedia.org/wiki/Donut 
772,stackoverflow,1141394279999,http://www.stackoverflow.com 
772,something,1141399299991,http:/something.else/something/ 

В этом примере, пончики представляет собой цепь, поэтому пары (номера строк без заголовка):

• Равные пары запросов: (1-3,9) (4,8) (5,6) (5,10) (6,10)
• Различные пары Запрос: (7,11)

Мой -failed- подход к проблеме:

алгоритм я разработал для решения этой проблемы работает следующим образом:

итерацию списка записей пока значение для UserID не изменится.

Затем наносят на отдельный список, который содержит только лишь итерированные элементы, которые разделяют один и тот же UserID:

for (int i = 0; i < list.size(); i++) { 
      Entry tempI = list.get(i); 
      Boolean iMatched = false; 
      //boolean to save whether or not c1 is set 
      Boolean c1done = false; 
      Boolean c2done = false; 

     //Hashsets holding the clickurl values of the entries that form a pair 
     HashSet<String> c1 = null; 
     HashSet<String> c2 = null; 

     for (int j = i + 1; j < list.size(); j++) { 
      Entry tempJ = list.get(j); 
      // Queries match 
      if (tempI.getQuery().equals(tempJ.getQuery())) { 
       // wheter or not Entry at position i has been matched or not 
       if (!iMatched) { 
        iMatched = true; 
       } 
       HashSet<String> e1 = new HashSet<String>(); 
       HashSet<String> e2 = new HashSet<String>(); 
       int k = 0; 
       // Times match 
       HashSet<String> chainset = new HashSet<String>(); 
       if (tempI.getEpoc() == tempJ.getEpoc()) { 
        chainset.add(tempI.getClickurl()); 
        chainset.add(tempJ.getClickurl()); 
       } else { 
        e1.add(tempI.getClickurl()); 
        if (c1 == null) { 
         c1 = e1; 
         c1done = true; 
        } else { 
         if (c2 == null) { 
          c2 = e1; 
          c2done = true; 
         } 
        } 
       } 
       //check how far the chain goes and get their entries 
       if ((j + 1) < list.size()) { 
        Entry tempjj = list.get(j + 1); 
        if (tempjj.getEpoc() == tempJ.getEpoc()) { 
         k = j + 1; 
         //search for the end of the chain 
         while ((k < list.size()) 
           && (tempJ.getQuery().equals(list.get(k) 
             .getQuery())) 
           && (tempJ.getEpoc() == list.get(k).getEpoc())) { 

          chainset.add(tempJ.getClickurl()); 
          chainset.add(list.get(k).getClickurl()); 
          k++; 

         } 
         j = k + 1; //continue the iteration at the end of the chain 
         if (c1 == null) { 
          c1 = chainset; 
          c1done = true; 
         } else { 
          if (c2 == null) { 
           c2 = chainset; 
           c2done = true; 
          } 
         } 

         // Times don't match 
        } 
       } else { 
        e2.add(tempJ.getClickurl()); 
        if (c1 == null) { 
         c1 = e2; 
         c1done = true; 
        } else { 
         if (c2 == null) { 
          c2 = e2; 
          c2done = true; 
         } 
        } 
       } 

       /** Block that compares the clicks in the Hashsets and computes the resulting data 
       * left out for now to not make this any more complicated than it already is 
       **/ 

       // Queries don't match 
      } else { 
       if (!dq.contains(tempJ)) { //note: dq is an ArrayList holding the entries of the differen query set 
        dq.add(tempJ); 
       } 
      } 

      if (j == al.size() - 1) { 
       if (!iMatched) { 
        dq.add(tempI); 
       } 
      } 
     } 
     if (dq.size() >= 2) { 

      for (int z = 0; z < dq.size() - 1; z++) { 
       if (dq.get(z + 1) != null) { 
        /** Filler, iterate dq just like the normal list with two loops 
        * 
        **/ 
       } 
      } 
     } 

    } 

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

Хорошо, надеюсь, что я не забыл ничего важного, я добавлю дополнительную информацию позже Если вы сделали это так далеко, спасибо за чтение - надеюсь у вас есть идея, которая может мне помочь

Answer 1

Во-первых, удалите все, кроме одной записи, из каждой цепочки. Для этого выполните сортировку по (userid, query, epoch), удалите дубликаты.

Затем сканируйте отсортированный список. возьмите все записи для пары (userid, query). Если есть только один, сохраните его в списке для последующей обработки, иначе испустите все пары.

Для всех записей для данного пользователя, сохраненных для последующей обработки (это типы 2 & 3), испускайте пары.

Answer 2

Используйте SQL для импорта данных в db, а затем выполните запросы. Ваш txt-файл слишком велик; неудивительно, что для этого требуется много времени. :)