2

リストのリストが 2 つあり、サブリストはパスを表します。すべてのパスを検索したい。

List<List<E>> pathList1
List<List<E>> pathList2

もちろん素朴な解決策：

List<List<E>> result = new ArrayList<List<E>>();

for(List<E> p1 : pathList1) {
   for(List<E> p2: pathList2) {
      List<E> newList = new ArrayList<E>(p1.size()+p2.size());
      newList.addAll(p1);
      newList.addAll(p2);
      result.add(newList);
   }
}

無関係な理論上の問題

最近、時間の複雑さについて学びました。これは自己チェックです。私が正しければ、誰かがコメントしてくれることを願っています。

N = pathList1 の num リストとする

M = pathList2 の num リストとする

X = pathList1 のパスの平均の長さ

Y = pathList2 のパスの平均の長さ

「この関数の複雑さは何ですか?」と聞かれたら、私は与えるだろう

~O(NM(X + Y))

これを行うためのより速い方法があるかどうか疑問に思っていましたか？

多分より良いデータ構造？

同時進行？

ある種の「未来」を作り、代わりにそれを返しますか？（完全な開示、私は先物について97％無知です）。

私は巧妙なトリックやユニークなソリューション、または純粋に実用的なものに対してオープンです。

ありがとう。

4

2 に答える 2

3

特にSets#cartesianProductにグアバを見ることができます

つまり、次のようなことができます。

Sets.cartesianProduct(ImmutableList.of(
       ImmutableSet.of(Sets.newHashSet(pathList1)),
       ImmutableSet.of(Sets.newHashSet(pathList2)))
于 2014-01-08T19:03:09.030 に答える
0

私はあなたの目標が正確に何であるかについて混乱しています。

次のパスのリストがある場合「(A,B,C)(D,E)」および「(C,D)(A,B)」

その後、現在のコードが返されます

"(A,B,C,C,D),(D,E,C,D),(A,B,C,A,B),(D,E,A,B)"

それはあなたが望むものですか？それはすべてのパスではなく、パスのすべての組み合わせです。

すべてのパスのリストは次のようになります

"(A,B,C)(D,E)(C,D)(A,B)"

これは、単純な O(N) 時間で実行できます。

また、Big-O 記法では、通常、個々の変数については気にせず、問題の複雑さの全体的なスケールのみを気にします。これは一般に、要素の数である単一の変数 n の関数として純粋に記述されます。

しかし、2 つのリストを「乗算」したい場合、一方の各要素を他方に対して「乗算」すると、O(n^2) になり、これ以上高速な方法はありません。

于 2014-01-08T18:50:06.637 に答える