Генерация всех уникальных пар из списка чисел, n выберите 2 - PullRequest
Новая
       35

Генерация всех уникальных пар из списка чисел, n выберите 2

3 голосов
/ 26 февраля 2012

У меня есть список элементов (скажем, целые числа), и мне нужно сделать все возможные 2-парные сравнения.мой подход O (n ^ 2), и мне интересно, если есть более быстрый путь.Вот моя реализация в Java. 

public class Pair {
 public int x, y;
 public Pair(int x, int y) {
  this.x = x;
  this.y = y;
 }
}

public List<Pair> getAllPairs(List<Integer> numbers) {
 List<Pair> pairs = new ArrayList<Pair>();
 int total = numbers.size();
 for(int i=0; i < total; i++) {
  int num1 = numbers.get(i).intValue();
  for(int j=i+1; j < total; j++) {
   int num2 = numbers.get(j).intValue();
   pairs.add(new Pair(num1,num2));
  }
 }
 return pairs;
}

пожалуйста, обратите внимание, что я не разрешаю самосопряжение, поэтому должно быть ((n (n + 1)) / 2) - n возможных пар.то, что у меня сейчас работает, но с ростом n у меня уходит нестерпимо много времени на получение пар.Есть ли способ превратить алгоритм O (n ^ 2) выше в суб-квадратичный?кстати, любая помощь приветствуется.

, я также попробовал алгоритм, приведенный ниже, но когда я тестирую, эмпирически, он работает хуже, чем у меня выше.я думал, что, избегая внутреннего цикла, это ускорит процесс.этот алгоритм не должен быть быстрее?я бы подумал, что это O (n)?если нет, пожалуйста, объясните и дайте мне знать.спасибо. 

public List<Pair> getAllPairs(List<Integer> numbers) {
 int n = list.size();
 int i = 0;
 int j = i + 1;
 while(true) {
  int num1 = list.get(i);
  int num2 = list.get(j);
  pairs.add(new Pair(num1,num2));

  j++;

  if(j >= n) {
   i++;
   j = i + 1;
  }

  if(i >= n - 1) {
   break;
  }
 }
}

Ответы [ 2 ]

6 голосов
/ 26 февраля 2012

Ну, вы не можете, верно?

В результате получается список с n*(n-1)/2 элементами, независимо от того, что это за элементы, просто для заполнения этого списка (скажем, с нулями) требуется O(n^2)время, так как n*(n-1)/2 = O(n^2) ...

4 голосов
/ 26 февраля 2012

Вы не можете сделать его субквадрическим, потому что, как вы сказали - выход сам по себе является квадричным - и для его создания вам нужно как минимум #elements_in_output ops.

Тем не менее, вы можете сделать "обман" создать свой список на лету :
Вы можете создать класс CombinationsGetter, который реализует Iterable<Pair>, и реализовать его Iterator<Pair>. Таким образом, вы сможете выполнять итерацию элементов на лету, не создавая сначала список, что может снизить задержку для вашего приложения.

Примечание : все равно будет квадрикой! Время создания списка на лету будет просто распределено между другими операциями.

EDIT: Другое решение, которое быстрее, чем наивный подход, - это многопоточность .
Создайте несколько потоков, каждый получит свой «кусочек» данных - и сгенерирует соответствующие пары, а также создаст собственный неполный список.
Позже - вы можете использовать ArrayList.addAll() для преобразования этих разных списков в один.
Примечание: , хотя сложность невелика O(n^2), скорее всего, это будет намного быстрее - поскольку создание пар выполняется параллельно, а ArrayList.addAll() реализован гораздо эффективнее, чем тривиальная вставка один за другим.

EDIT2: Ваш второй код по-прежнему O(n^2), хотя это «одиночный цикл» - сам цикл будет повторяться O(n^2) раз. Посмотрите на вашу переменную i. Увеличивается только при j==n и уменьшается j до i+1 при этом. Таким образом, это приведет к n + (n-1) + ... + 1 итерациям, а это сумма арифметической прогрессии , и вернет нас к O(n^2), как и ожидалось.

Мы не можем стать лучше, чем O (n ^ 2), потому что мы пытаемся создать O (n ^ 2) различных Pair объектов.

...