21

O(1) の 2 つのリンクされたリストを、jdk1.6、Google、または apache commons collection などを介して Java と連結するにはどうすればよいですか? たとえば、jdk には、O(n) である addAll メソッドしかありません。

私が見逃しているもう 1 つの機能は、それぞれが逆順になる可能性がある 2 つのリストを連結することです。これを説明するために、2 つのリスト a->b->c と e->f->g をマージして

  1. a->b->c->e->f->g
  2. a->b->c->g->f->e
  3. c->b->a->e->f->g
  4. c->b->a->g->f->e

そのようなリストの実装を知っていますか、それとも独自のリンク リストを実装する必要がありますか? また、既存のソリューションを微調整する方法を知っておくと役立ちます (たとえば、jdk LinkedList には多くのプライベート メソッドしかありません)。これらの機能は私には非常に明白に思えます。

MicSim が指摘したように、 Java で一定時間内に 2 つのリストをマージすることは関連していますが、実際の重複ではありません! 質問は次のとおりです。

  1. 他のコレクションライブラリで可能ですか?
  2. 逆を連結する方法は?
4

6 に答える 6

6

Iterable の結果で解決したい場合は、google-collections の Iterables.concat と Iterables.reverse を使用できます。

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables.html

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c,
                                 Iterable<? extends T> d)

public static <T> Iterable<T> concat(Iterable<? extends T>... inputs)

public static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs)
于 2010-03-22T17:52:46.557 に答える
2

現時点で私が目にする唯一の解決策は、List を実装し、次のようなコンストラクターを作成することです。

public EnhancedList (List l1, List l2)

すべてのメソッドをオーバーライドします。このようなソリューションでは、LinkedLists を連結するか、他のリストを連結するかは実際には重要ではありません。

于 2010-03-22T16:49:46.543 に答える
0

jdk で O(1) concat を取得するように LinkedList を調整すると、次の場合に機能します。

  1. メソッド entry() と変数 header と size と内部クラス Entry は保護されます
  2. addAll は LinkedList を検出してから sth を実行します。お気に入り:

    JdkLinkedList secondList = (JdkLinkedList) secondColl;
    int numNew = secondList.size();
    if (numNew == 0)  return false;
    modCount++;
    Entry<E> successor = (index == size ? header : entry(index));
    Entry<E> predecessor = successor.previous;
    // TODO LATER if reverse
    
    // connect the last element of this list with the first element of the second list
    // linked list is implemented as a 'cycle' => header.next == first element of second list
    Entry<E> first = secondList.header.next;
    predecessor.next = first;
    first.previous = predecessor;
    
    // append the last element of the second list with the rest of this list
    Entry<E> last = secondList.header;
    successor.previous = last;
    last.next = successor;
    
于 2010-03-22T18:49:02.833 に答える
0

連結については、次のことをお勧めします。

  • すべてのパラメータ/変数が LinkedList<...> ではなく List<...> として宣言されていることを確認してください
  • 新しい LinkedList<...>(); を変更します。new ArrayList<...>(); に
  • アプリケーションのプロファイリング
  • new ArrayList<...> を new LinkedList<...>(); に変更します。
  • アプリケーションのプロファイリング

使い方によっては、ArrayList は LinkedList よりも大幅に高速になる場合があります。また、プロファイル データを見ると、addAll を使用してどの程度のパフォーマンス ヒットが発生したかを確認できます。それほど大きくない場合は、「修正」する必要はありません。

他の言語での経験が当てはまらないものもあります。addAll が Java の要件を満たしていることがわかる場合があります。

独自の連結可能なリストを作成する場合は、それが List インターフェイスに準拠していることを確認してから、コードを変更して再プロファイリングし、より高速であることを確認してください。そうでない場合は、それを捨てて、標準の List 型に固執してください。

于 2010-03-22T18:58:52.583 に答える
0

リンクされたリストのリストの途中または最後への挿入は O(1) であるため、これはどのような種類の基本リスト構造でも書くのはそれほど難しくないと思います。

于 2010-03-22T16:58:44.037 に答える
0

javolution の FastListはすぐに使えるソリューションではありませんが、tail() と head() は私のお気に入りにかなり近いものです。

O(1) には invert や addAll の便利なメソッドはありませんが、troveが解決策だと思います。

于 2010-03-22T20:45:25.187 に答える