2

この問題を説明することさえ難しいです、しかし私はそれをやってみます。私はこれに数日間苦労していて、ここで尋ねることに決めました。

さて、私は「概念」または「もの」を私が呼んでいるようにモデル化しようとしています。一般的な概念だけです。それは処理ロジックと関係があります。

したがって、各「もの」は、他のものとの関係によって定義されます。これを関係ごとに5ビットのセットとして保存します。「もの」は次のようになります。

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
}

だから、私はそのような「モノ」をモデル化しています。関係ごとに5ビット。各ビットは、1つの可能な関係を表します。このように：1は等しい、2は内側、3は外側、4は含む、5はオーバーラップします。5ビットすべてがオンになっているということは、関係が何であるかを完全に知らないことを意味します。2ビットがあるということは、関係が2つの可能性のうちの1つである可能性があることを意味します。関係は「不明」（5ビットすべてが真）として始まり、時間が経つにつれてより具体的になります。

これが、時間の経過とともに増加する知識をモデル化する方法です。物事は完全に未知の状態で始まり、部分的に既知の状態を通過し、完全に既知の状態に到達する可能性があります。

もう少し背景：

追加のクラスを使用して、「概念」（モノ）のモデリングに追加の定義を追加しようとしています。このような：

class ArrayDefinition {
    Array<Thing> Items;
}

そして、私のThingクラスは次のようになります。

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
    ArrayDefinition* ArrayDef;
}

この「ArrayDef」は使用する必要はありません。必要に応じて、使用するだけです。配列を持たない「もの」もあれば、配列を持っているものもあります。しかし、すべての「もの」には関係があります。

この「ArrayDefinition」を処理して、2つのものの関係を理解することができます。たとえば、との場合X = [ A B C D E ]、Y = [ C D E ]私のコードはこれら2つの配列を処理し、「Y inside X」を理解できます。

OK、それで十分な背景です。あらゆる種類の気が散る詳細を含む実際のコードを避けて、コアの問題について説明しました。

ここに問題があります：

問題は、これが途方もなく遅くならないようにすることです。

想像してみてください。2000の「もの」があります。これらのうち1000個に配列定義があるとしましょう。さて、それは私たちが互いに比較する必要がある500,000（ish）の可能な「配列ペア」を作ります。

私は今やっと意味をなすようになり始めていることを願っています。それらすべてを互いに処理しないようにするにはどうすればよいですか？2つの「もの」が完全に既知の関係にある場合、それらの「配列定義」を比較しても意味がないことはすでに理解しています。これは、関係の詳細を把握するために使用されるだけですが、正確な関係があるためです。意味がありません。

つまり...これらの「配列を持つもの」のうち、未知または部分的に既知の関係を持っているのは500個だけだとしましょう。それでも、250000（ish）の「配列ペア」を比較することができます。

さて...私にとって、最も明白な出発点は、2つの配列を定義するために使用される関係が変更されない限り（より具体的になる）、この「配列ペア」を処理する意味がないことを理解することです。

たとえば、次の2つの配列があるとします。

    X = [ A B C D E ]
    Y = [ Q W R T ]

今、私がそれを言うならばT=R、それはとてもいいです。しかし、これはXとYの関係には影響しません。したがって、TとRの関係が「等しい」と呼ばれるようになったからといって、完全に不明になる前に、XとYを再度比較する必要があるわけではありません。

一方、「T outside E」と言えば、これは2つの配列を定義するために使用されるものの間の関係です。つまり、「T outside E」とは、Yの配列に対してXの配列を処理する必要があることを意味します。

1000個の配列間でほとんど何も変更されていないときに、1000個の配列のロジックを処理するためだけに、500,000個の「配列ペア」を比較する必要はありません。

だから...これを単純化する最初の試みは、物事が定義するために使用されるすべての配列のリストを保持することでした。

私が3つの配列を持っているとしましょう：

    A = [ X Y Z ]
    B = [ X X X X ]
    C = [ X Z X F ]

さて、Xは3つの配列で使用されます。したがって、Xは、内部で使用されているすべての配列のリストを保持できます。

したがって、私が言った場合"X inside Y"、これにより、Yが定義に使用され、すべての配列Xが定義に使用されるすべての配列のリストが表示される可能性があります。Xが3つの配列で使用され、Yが1つの配列で使用されているとします。このことから、比較する必要のある「アレイペア」が2つあることがわかります（AとB、およびAとC）。

配列ペアのいずれかがすでに完全に既知の関係を持っているかどうかを確認することで、このリストをさらに整理できます。

私がこれに関して持っている問題は、それがまだ過度に見えるということです。

Xが本当に一般的な「もの」であるとしましょう。10,000アレイで使用されています。そして、Yは本当に一般的なもので、10,000個のアレイで使用されます。

私はまだ比較するために100,000,000の配列ペアで終わります。OK、それで、それらすべてを比較する必要はないとしましょう。実際、それらのうちの50だけが部分的に知られているか、完全に知られていません。

しかし...私はまだ1億の配列ペアのリストを調べて、これらのどれが部分的に知られているのかを理解する必要がありました。したがって、それでも非効率的です。

これを行う効率的な方法がないかどうか本当に疑問に思っています。そして、本当に私にできることは、いくつかの効果的な「ヒューリスティック」戦略を立てることだけです。私はまだ良い戦略を思い付くのにあまり運がありませんでした。

この問題は非常に特殊化されていることを認識しています。そして、私はこの長い投稿を読むのに時間がかかりすぎるかもしれないことを理解しています。ポストの長さを短くする方法や、より一般的な問題の観点からこれを説明する方法がわかりません。

それが役に立ったら...これを一般的な言葉で表現するための私の最善の試みは、「更新されたリストのみを比較する方法」です。

誰かアイデアがありますか？それは素晴らしいことです。そうでない場合は...おそらく私がこれを書き出すだけで私の思考プロセスが役立つかもしれません。

問題は、この問題を高速かつ効率的に実行できるアルゴリズムまたはアプローチがあると感じずにはいられないということです。そのアルゴリズムが何であるかはわかりません。

皆さんありがとう

4

5 に答える 5

0

あなた自身の答えから、未知の関係は既知の関係よりもはるかに多いと推測します。その後、個別のハッシュ テーブル/セットでそれぞれの不明な関係を追跡できます。さらなる最適化として、モノが使用されているすべての定義を追跡する代わりに、これらの定義のどれが不明な関係を持っているか、つまりどの関係が影響を受ける可能性があるかを追跡します。次に、X と Y の間の新たに定義された関係が与えられた場合、そのうちの 1 つの影響を受ける定義を取得し、未知の関係のそれぞれと他の関係の影響を受ける定義との交点を見つけます。加速データ構造を最新の状態に保つには、関係が既知になったら、それを未知の関係から削除し、不明な関係が残っていない場合は、配列定義を調べて、can-affect セットから物を削除します。

データ構造は次のようになります。

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
    Set<Thing*> UnknownRelationships;
    ArrayDefinition* ArrayDef;
    Set<Thing*> CanAffect; // Thing where this in ArrayDefinition and UnknownRelationships not empty
}

class ArrayDefinition {
    Array<Thing> Items;
}
于 2010-02-04T22:53:40.153 に答える
0

ぐっすり眠って目が覚めたとき、新しい考えが浮かびました。それはうまくいくかもしれません...

各「もの」がすべての「配列定義」のリストを保持している場合、それは定義に使用されます。

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
    ArrayDefinition* ArrayDef;
    Set<ArrayDefinition*> UsedInTheseDefs;
}

class ArrayDefinition {
    Array<Thing> Items;
    Set<int> RelationModifiedTag;
}

そして、すべての「比較可能な配列ペア」のグローバル リストを保持しています。

また、すべての「比較可能な配列」のグローバル リストも作成します (ペアではなく、1 つずつ)。

次に、関係が変更されるたびに、私が中にいる「配列定義」のリストを調べて、それに小さな「タグ」を追加できます:)

だから私はこのようなことができます：

static CurrRel = 0;
CurrRel++; // the actual number doesn't matter, it's just used for matching

foreach(Arr in this->UsedInTheseDefs) {
    Arr->RelationModifiedTag.Add( CurrRel );
}
foreach(Arr in other->UsedInTheseDefs) {
    Arr->RelationModifiedTag.Add( CurrRel );
}

私は関係の両側を変えました。したがって、これを行った場合: "A outside B"、「変更されたタグ」を、定義に使用されるすべての配列 A と、定義に使用されるすべての配列 B に追加しました。

そのため、「比較可能な配列ペア」のリストをループします。もちろん、各ペアは 2 つの配列であり、それぞれに「RelationModifiedTag」が設定されます。

そこで、両方の RelationModifiedTag セットを相互にチェックして、一致する番号があるかどうかを確認します。一致する場合、これは、この配列ペアが変更されたばかりの関係を持っていることを意味します! だから...私は配列の比較を行うことができます。

それはうまくいくはずです:)

少しオーバーヘッドが必要ですが、主なことは、より大きなデータセットにうまくスケーリングできることです。10 個の配列しかない小規模なデータセットの場合は、より単純でより強引なアプローチを使用できます。完全に既知の関係を持たないすべての配列ペアを比較するだけで、変更された関係を追跡する必要はありません。

さらなる最適化が可能です。しかし、メインのアルゴリズムから注意をそらしてしまうだけなので、ここでは説明しません。たとえば、比較する 2 つのセットがある場合、小さい方のセットをループして、大きい方のセットをチェックする必要があります。

この長いテキストをすべて読まなければならないことをお詫びします。そして、助けようとするすべての試みに感謝します。

于 2010-02-04T15:27:29.913 に答える
0

あなたが何をしているのかを完全に理解しているかどうかはわかりませんが (ArrayDefinition の目的は特にあいまいです)、オブジェクトのモデリングをそれらの関係から分離することを検討する必要があると思います。つまり、関係ごとにオブジェクトからオブジェクトへの個別のマッピングを作成します。オブジェクトが整数インデックスで表される場合、整数から整数へのマッピングを表す効率的な方法を見つけるだけで済みます。

于 2010-02-04T03:34:21.990 に答える
0

さて、まずは用語集です。

デザインパターン：Observer

これは、オブジェクトが自分自身を他のオブジェクトに登録し、イベントに関する通知を要求できるようにするデザイン パターンです。

たとえば、それぞれが管理する にThingWithArray自身を登録して、が更新された場合に に通知を受け取ることができます。ThingThingThingWithArray

現在、通常はunsubscribeメソッドがあります。つまり、それらを使用するすべてのリレーションが使用されたためThingWithArrayに が一部に依存しなくなるとすぐに、変更が通知されないようにすることができます。Thingunsubscribe

このようにして、更新を実際に気にかけている人だけに通知します。

ただし、考慮すべき点が 1 つあります。再帰的な関係がある場合、複雑になる可能性があるため、これを回避する方法を考え出す必要があります。

また、ergosys のアドバイスに従い、オブジェクトの外部で関係をモデル化します。通常、大きなクラスが 1 つあると問題が発生します... 論理的な部分に切り分けるのが難しい場合は、問題が明確ではないため、モデル化の方法について助けを求める必要があります...明確なモデルが得られたので、物事は通常、もう少し簡単に収まります。

于 2010-02-04T19:06:07.680 に答える
0

一般に、すべての操作で可能な限り高速な構造を考え出すことはできません。トレードオフが必要です。

この問題は、リレーショナル データベースでクエリを実行する場合の問題と非常によく似ていますSELECT * WHERE ...。インスピレーションを得るためにそこを探すことを検討するかもしれません。

于 2010-02-04T02:32:26.900 に答える