2

これは、素集合の私の Objective-C 実装です。- 親への正数ポイント。- 負の数は、ルートと子の数を示します。(したがって、それらはそれぞれ -1 でバラバラに開始します。) - インデックスは、グループ化するデータとして機能します。問題ないようです... いくつか質問がありました。

  1. find:パスを圧縮するにはどうすればよいですか? 私は再帰的に行っていないので、ルートを見つけた後に設定するために、パスを保存して再度ループする必要がありますか?

  2. join: 深さではなく、子の数に基づいて結合しています!? それは正しくないと思います。深さが等しい場合、結合中に何か特別なことをする必要がありますか?

ありがとう。

DisjointSet.h

@interface DisjointSet : NSObject
{
    NSMutableArray *_array;
}

- (id)initWithSize:(NSInteger)size;
- (NSInteger)find:(NSInteger)item;
- (void)join:(NSInteger)root1 root2:(NSInteger)root2;

@end

DisjointSet.m

#import "DisjointSet.h"

@implementation DisjointSet

- (id)initWithSize:(NSInteger)size
{
    self = [super init];
    if (self)
    {
        _array = [NSMutableArray arrayWithCapacity:size];
        for (NSInteger i = 0; i < size; i++)
        {
            [_array addObject:[NSNumber numberWithInteger:-1]];
        }
    }
    return self;
}

- (NSInteger)find:(NSInteger)item
{
    while ([[_array objectAtIndex:item] integerValue] >= 0)
    {
        item = [[_array objectAtIndex:item] integerValue];
    }
    return item;
}

- (void)join:(NSInteger)root1 root2:(NSInteger)root2
{
    if (root1 == root2) return;

    NSInteger data1 = [[_array objectAtIndex:root1] integerValue];
    NSInteger data2 = [[_array objectAtIndex:root2] integerValue];
    if (data2 < data1)
    {
        [_array setObject:[NSNumber numberWithInteger:data2 + data1] atIndexedSubscript:root2];
        [_array setObject:[NSNumber numberWithInteger:root2] atIndexedSubscript:root1];
    }
    else
    {
        [_array setObject:[NSNumber numberWithInteger:data1 + data2] atIndexedSubscript:root1];
        [_array setObject:[NSNumber numberWithInteger:root1] atIndexedSubscript:root2];
    }
}

@end
4

3 に答える 3

4

検索操作では、パスを ( とは別に_array) 保存したり、再帰を使用したりする必要はありません。これらのアプローチのいずれも、O(P) ストレージ (P = パスの長さ) を必要とします。代わりに、パスを 2 回トラバースできます。初めて、ルートを見つけます。2 回目は、すべての子がルートを指すように設定します。これには O(P) 時間と O(1) ストレージが必要です。

- (NSInteger)findItem:(NSInteger)item {
    NSInteger root;
    NSNumber *rootObject = nil;
    for (NSInteger i = item; !rootObject; ) {
        NSInteger parent = [_array[i] integerValue];
        if (parent < 0) {
            root = i;
            rootObject = @(i);
        }
        i = parent;
    }

    for (NSInteger i = item; i != root; ) {
        NSInteger parent = [_array[i] integerValue];
        _array[i] = rootObject;
        i = parent;
    }

    return root;
}

マージ操作では、各ルートの子孫数ではなく、各ルートのランク (深さの上限) を格納する必要があります。各ルートのランクを保存すると、短いツリーを高いツリーにマージできます。これにより、検索操作に O(log N) の時間が保証されます。ランクは、マージされるツリーのランクが等しい場合にのみ増加します。

- (void)joinItem:(NSInteger)a item:(NSInteger)b {
    NSInteger aRank = -[_array[a] integerValue];
    NSInteger bRank = -[_array[b] integerValue];
    if (aRank < bRank) {
        NSInteger t = a;
        a = b;
        b = t;
    } else if (aRank == bRank) {
        _array[a] = @(-aRank - 1);
    }

    _array[b] = @(a);
}
于 2013-01-06T18:16:38.097 に答える
1

再帰を使用してパス圧縮を実装する必要があります。私はそれを非再帰的にしようとさえ考えませんでした。

disjoin-set データ構造の実装は非常に簡単で、数行で実行できます。疑似コードから任意のプログラミング言語に変換するのは非常に簡単です。Wikipediaで疑似コードを見つけることができます。(残念ながら、私は Objective-C を読むことができないため、コードが正しいかどうかを実際に判断することはできません)。

于 2013-01-06T18:02:42.480 に答える
1

はい。再帰なしで最上位の祖先圧縮を実装するには、独自のリストを維持する必要があります。親ポインターを変更する必要があるセットへのポインターを取得し、ルートを学習するために、チェーンを 1 つパスさせます。次に、2 番目のパスを作成して、必要な親ポインターを更新します。

再帰的な方法は同じことをしています。最初のパスは再帰の「巻き上げ」であり、親ポインターの更新が必要なセットをプログラム スタックに格納します。2 番目のパスは、再帰が巻き戻されるときに逆になります。

私は、再帰的な方法が常に最善であると言う人々とは異なります。妥当な数のシステム (特に組み込みシステム) では、プログラム スタックのサイズは限られています。検索の前に、多くのユニオンが連続して実行される場合があります。このような場合、親チェーンは n 要素のサイズで O(n) になる可能性があります。ここで、再帰によって折りたたむと、スタックが吹き飛ばされる可能性があります。Objective C で作業しているため、これは iOS である可能性があります。そこのデフォルトのスタック サイズはわかりませんが、再帰を使用する場合は一見の価値があります。思ったより小さいかもしれません。 この記事は、セカンダリ スレッドに 512K、メイン スレッドに 1Mb を意味します。

反復的で一定のスペース代替

実際、私が書いている主な理由は、n 個の償却された操作に対してまだ O(log^* n) を取得していることを指摘することです。折りたたむよりも効率的ではありませんが、効果的には O(1) です。 2 倍の圧縮: 検索操作で、ルートではなく祖父母を指すように親ポインターを変更します。これは、定数ストレージでの反復で実行できます。 このプリンストンでのレクチャーでは、このアルゴリズムについて説明し、5 行の C でループに実装しています。スライド 29 を参照してください。

于 2013-01-06T18:18:15.883 に答える