23

正しいデータ構造を使用していない可能性があります。セットを使用する必要がありますが、k 番目に小さい要素を効率的に返したいと考えています。TreeSetJavaでこれを行うことはできますか? これを行う組み込みの方法はTreeSetないようです。

4

8 に答える 8

23

TreeSetこれを直接行う方法があるとは思いません。O(log n) ランダム アクセスをサポートする二分探索ツリー (順序統計ツリーと呼ばれることもあります) があり、このデータ構造の Java 実装が利用可能です。これらの構造は通常、ノードの左または右にある要素の数をカウントする各ノードに情報を格納する二分探索ツリーとして実装されるため、ツリーを下方向に検索して適切な要素を見つけることができます。各ステップ。Cormen、Rivest、Leisserson、および Stein による古典的な本「Introduction to Algorithms, Third Edition」では、このデータ構造について、「Augmenting Data Structures」の章で説明しています。

または、(場合によっては)TreeSetのtailSetメソッドと修正された二分探索を使用して、k 番目の要素を見つけようとすることもできます。具体的には、 の最初と最後の要素を見て、TreeSet(内容が与えられている場合) 2 つの要素の中間にある要素を選択し、それを引数として に渡してtailSet、中間点の後のセットの要素のビューを取得します。内の要素の数を使用して、要素tailSetが見つかったかどうか、またはツリーの左半分または右半分を探索するかどうかを決定できます。これは、ツリーに対する補間検索をわずかに変更したものであり、高速になる可能性があります。ただし、内部の複雑さはわかりませんtailSetメソッドなので、これは実際には順序統計ツリーよりも悪い可能性があります。2 つの要素の「中点」を計算できない場合にも失敗する可能性があります。たとえば、 に を格納Stringしている場合などですTreeSet。

于 2012-01-13T20:33:16.200 に答える
18

要素kまで繰り返すだけです。これを行う 1 つの方法は、 GuavaのIterables.getメソッドの1 つを使用することです。

T element = Iterables.get(set, k);

Seta は aではなく、Listそのようなインデックスベースの操作は一般に s 用に予約されているため、これを行うための組み込みメソッドはありませんList。ATreeSetは、>= 何らかの値である最も近い含まれる要素を見つけるようなものに適しています。

k 番目に小さい要素への可能な限り高速なアクセスが本当に重要である場合にできることの1 つArrayListは、a ではなく aを使用TreeSetし、挿入ポイントをバイナリ検索して挿入を処理し、そのインデックスに要素を挿入するか、既存の要素を置き換えることです。検索の結果に応じて、そのインデックス。次に、 を呼び出すだけで、O(1) で k 番目に小さい要素を取得できますget(k)。

本当に必要な場合SortedSetは、すべてを処理してメソッドを追加するの実装を作成することもできます。get(index)

于 2012-01-13T20:32:58.917 に答える
10

TreeSet.iterator()を使用して昇順で反復子を取得し、next()K 回呼び出します。

// Example for Integers
Iterator<Integer> it = treeSet.iterator();
int i = 0;
Integer current = null;
while(it.hasNext() && i < k) {
   current = it.next();
   i++;
}
于 2012-01-13T20:31:40.837 に答える
8

https://github.com/geniot/indexed-tree-map

私も同じ問題を抱えていました。そこで私は java.util.TreeMap のソースコードを取り、IndexedTreeMapを書きました。それは私自身のIndexedNavigableMapを実装しています:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

実装は、赤黒ツリーが変更されたときにノードの重みを更新することに基づいています。重みは、特定のノードの下にある子ノードの数に 1 - 自分自身を加えたものです。たとえば、ツリーが左に回転した場合:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight は、重みをルートまで単純に更新します。

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

インデックスで要素を見つける必要がある場合は、重みを使用する実装を次に示します。

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

キーのインデックスを見つけるのにも非常に便利です。

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    if (e.left != null) {
        index += getWeight(e.left);
    }
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

この作業の結果は、https://github.com/geniot/indexed-tree-mapで確認できます。

于 2013-02-10T22:17:15.367 に答える
1

[以下、「k番目に小さい要素の検索操作」を​​「K番目の操作」と略します。]

あなたはより多くの詳細を与える必要があります。データ構造はどの操作を提供しますか？K番目の操作のKはNに比べて非常に小さいですか、それとも何かできますか？ルックアップと比較して、どのくらいの頻度で挿入と削除がありますか？ルックアップと比較して、 K番目に小さい要素の検索はどのくらいの頻度で行われますか？Javaライブラリ内の数行の簡単な解決策を探していますか、それともカスタムデータ構造を構築するためにいくらかの努力を費やしても構わないと思っていますか？

提供する操作は、次のサブセットにすることができます。

  • LookUp（キーで要素を検索します。キーは同等であり、何でもかまいません）

  • 入れる

  • 消去

  • Kth

ここにいくつかの可能性があります：

  • 挿入と削除がない/非常に少ない場合は、要素を並べ替えて配列を使用できます。ルックアップ時間はO（Log（N）） 、 KthはO（1）です。

  • LookUpの場合はO（Log（N））、Kth opの場合はInsert、Delete、O（k）。十分に良いです、おそらく最も簡単な実装はスキップリストでしょう。（詳細が必要な場合は、ウィキペディアの記事が非常に役立ちます）

  • Kが十分に小さい場合、またはK番目の操作が「挿入および削除フェーズ」の後にのみ行われる場合は、最小のK要素をヒープに保持し、挿入および削除後にO（N + k Log k）時間ソートできます。（ LookUpには別のハッシュも必要になります）

  • Kが任意で、O（N）がKth操作に十分である場合、 O（1）時間ルックアップにハッシュを使用し、Kth操作に「片側クイックソート」アルゴリズムを使用できます（基本的な考え方は、クイックソートですが、すべてのバイナリ除算では、本当に必要な側でのみ再帰します。これにより、（これは大幅な簡略化です）N（1/2 + 1/4 + 1/8 + ...）= O（N）が期待されます時間）

  • 各ノードが子の数を保持する拡張された「単純な」区間木構造を構築できるため、ツリーのバランスが取れている限り、 LookUp、Insert、Delete、KthはすべてO（Log N）時間で計算されます。初心者であれば、実装は難しくありません。

などなど。あなたの質問の可能な解釈として、選択肢のセットは無限です。

于 2012-01-14T01:40:15.413 に答える
0

ConcurrentSkipListSetを使用してtoArray（）メソッドを使用できますか？ConcurrentSkipListSetは、要素の自然な順序で並べ替えられます。私が確信していない唯一のことは、toArray（）がO（n）であるか、それともリスト（ArrayListのような配列に裏打ちされている）によって支えられているのでO（1）であるかということです。

toArray（）がO（1）の場合、k番目に小さい要素を取得するためにskipList.toArray（）[k]になることができるはずです。

于 2012-01-14T16:18:10.040 に答える
-1

この質問はかなり古いものですが、TreeSet は NavigableSet を実装しているため、一定時間で実行される subSet メソッドにアクセスできます。

subSet(k, k + 1).first();

first() 呼び出しには log(n) 時間かかります。ここで、n は元のセットのサイズです。これにより、TreeSet のより堅牢な実装で回避できる不要なオブジェクトがいくつか作成されますが、サードパーティ ライブラリの使用は回避されます。

于 2013-05-30T17:10:15.840 に答える