生成所有独特的双起号码清单，正选2 [英] generating all unique pairs from a list of numbers, n choose 2

问题描述

我有元素的列表（假设整数），我需要尽一切可能的2对比较。我的做法是O（n ^ 2），我想知道是否有一个更快的方法。这是我的Java实现。

 公共类对{
 公众诠释的x，y;
 公众对（INT X，int y）对{
  this.x = X;
  this.y = Y;
 }
}

公开名单＆LT;对＆GT; getAllPairs（名单＆LT;整数GT;数字）{
 名单＆LT;对＆GT;对=新的ArrayList＆LT;对＆GT;（）;
 INT总= numbers.size（）;
 的for（int i = 0; I＆LT;全;我++）{
  INT NUM1 = numbers.get（我）.intValue（）;
  对于（INT J = I + 1; J＆LT;全; J ++）{
   INT NUM2 = numbers.get（J）.intValue（）;
   pairs.add（双新（NUM1，NUM2））;
  }
 }
 返回对;
}
 

请注意，我不允许自行配对，所以应该有（（N（N + 1））/ 2） - n个可能的对。我有什么现在的工作，但随着n的增加，它正在我无法忍受漫长的时间来获得对。有没有什么办法打开为O（n ^ 2）算法上面的东西分二次？任何帮助是AP preciated。

顺便说一句，我也尝试了下面的算法，但是当我的基准，根据经验，它执行最差的比我有以上。我原以为，避免内部循环，这将加快速度。不应该这样的算法如下更快？我会认为这是为O（n）？如果没有，请解释一下，让我知道。谢谢。

 公开名单＆LT;对＆GT; getAllPairs（名单＆LT;整数GT;数字）{
 INT N =则为list.size（）;
 INT I = 0;
 INT J = I + 1;
 而（真）{
  INT NUM1 = list.get（ⅰ）;
  INT NUM2 = list.get（J）;
  pairs.add（双新（NUM1，NUM2））;

  J ++;

  如果（J＆GT; = N）{
   我++;
   J = 1 + 1;
  }

  如果（I＆GT; = N  -  1）{
   打破;
  }
 }
}
 

解决方案

您不能让它分二次，因为如你所说 - 输出本身就是二次 - 而且创建它，你需要至少 #elements_in_output 欢声笑语。

不过，你可以做一些作弊的创建列表的飞行：
您可以创建一个类 CombinationsGetter 实现的 可迭代＆LT;对＆GT; ，并实现其的 迭代器＆LT;对＆GT; 。这样，您就能够重复上飞的元素，在不先创建的列表中，这可能会减少等待时间为您的应用程序。

注意：这仍然是二次！以动态生成列表的时间将只是更多的操作之间的分配。

---

编辑： 另一种解决方案，这是更快那么天真的方法 - 是的多线程。
创建几个线程，每个将获得的数据他的片 - 并产生相关的对，并建立了自己的部分名单。
之后 - 您可以使用<一个href="http://docs.oracle.com/javase/1.4.2/docs/api/java/util/ArrayList.html#addAll%28java.util.Collection%29"相对=nofollow> ArrayList.addAll（） 这些不同的列表转换成一个。
注意：虽然复杂stiil 为O（n ^ 2），很可能要快得多 - 自创建以来对是并行进行，而 ArrayList.addAll（）由一个元件实现更effieciently那么琐碎的插件之一。

EDIT2： 你的第二个code仍为O（n ^ 2），即使它是一个单循环 - 环本身会重复 0 （N ^ 2）次。有一个在你的变量我。它增加仅在Ĵ==ñ，并降低Ĵ返回 I + 1 当它吧。因此，它会导致 N +（N-1）+ ... + 1 迭代，这是的总和的算术级数，并得到我们回到为O（n ^ 2）预期。

我们不能得到更好，然后为O（n ^ 2），因为我们正努力创造为O（n ^ 2）不同的对的对象。

i have a list of elements (let's say integers), and i need to make all possible 2-pair comparisons. my approach is O(n^2), and i am wondering if there is a faster way. here is my implementation in 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;
}

please note that i don't allow self-pairing, so there should be ((n(n+1))/2) - n possible pairs. what i have currently works, but as n increases, it is taking me an unbearable long amount of time to get the pairs. is there any way to turn the O(n^2) algorithm above to something sub-quadratic? any help is appreciated.

by the way, i also tried the algorithm below, but when i benchmark, empirically, it performs worst than what i had above. i had thought that by avoiding an inner loop this would speed things up. shouldn't this algorithm below be faster? i would think that it's O(n)? if not, please explain and let me know. thanks.

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;
  }
 }
}

解决方案

You cannot make it sub-quadric, because as you said - the output is itself quadric - and to create it, you need at least #elements_in_output ops.

However, you could do some "cheating" create your list on the fly:
You can create a class CombinationsGetter that implements Iterable<Pair>, and implement its Iterator<Pair>. This way, you will be able to iterate on the elements on the fly, without creating the list first, which might decrease latency for your application.

Note: It will still be quadric! The time to generate the list on the fly will just be distributed between more operations.

---

EDIT: Another solution, which is faster then the naive approach - is multithreading.
Create a few threads, each will get his "slice" of the data - and generate relevant pairs, and create its own partial list.
Later - you can use ArrayList.addAll() to convert those different lists into one.
Note: though complexity is stiil O(n^2), it is likely to be much faster - since the creation of pairs is done in parallel, and ArrayList.addAll() is implemented much more effieciently then the trivial insert one by one elements.

EDIT2: Your second code is still O(n^2), even though it is a "single loop" - the loop itself will repeat O(n^2) times. Have a look at your variable i. It increases only when j==n, and it decreases j back to i+1 when it does it. So, it will result in n + (n-1) + ... + 1 iterations, and this is sum of arithmetic progression, and gets us back to O(n^2) as expected.

We cannot get better then O(n^2), because we are trying to create O(n^2) distinct Pair objects.

这篇关于生成所有独特的双起号码清单，正选2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！