2

即使描述这个问题也很难，但我会试一试。我已经为此苦苦挣扎了几天，并决定在这里问。

好的，所以我正在尝试为我所说的“概念”或“事物”建模。只是一般的概念。这与处理逻辑有关。

因此，每个“事物”都是由它与其他事物的关系来定义的。我将其存储为每个关系一组 5 位。一个“东西”可能是这样的：

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

所以，我对“事物”进行建模。每个关系 5 位。每个位代表一种可能的关系。像这样：1 等于，2 内部，3 外部，4 包含，5 重叠。开启所有 5 位意味着我们完全不知道这种关系是什么。拥有 2 位意味着我们认为这种关系可能是两种可能性之一。关系从“未知”开始（所有 5 位都是真的），随着时间的推移变得更加具体。

所以这就是我如何模拟随着时间的推移不断增加的知识。事物以完全未知的状态开始，可以通过部分已知的状态，并可以达到完全已知的状态。

多一点背景：

我尝试通过使用额外的类来为我的“概念”（事物）建模添加额外的定义。像这样：

class ArrayDefinition {
    Array<Thing> Items;
}

我的 Thing 类变成了这样：

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

不必使用此“ArrayDef”。如果需要，它只是在那里使用。有些“事物”没有数组，有些则有。但所有“事物”都有关系。

我可以处理这个“ArrayDefinition”来弄清楚两件事之间的关系！例如，如果X = [ A B C D E ]和Y = [ C D E ]，我的代码可以处理这两个数组，并找出“ Y inside X”。

好的，这就是足够的背景。我已经解释了核心问题，避免了包含各种令人分心的细节的真实代码。

这是问题所在：

问题是让它运行起来不会慢得离谱。

想象一下，有 2000 个“东西”。假设其中 1000 个具有数组定义。现在，这使得我们需要相互比较的 500,000（ish）个可能的“数组对”。

我希望我现在终于开始明白了。如何避免将它们全部相互处理？我已经意识到，如果两个“事物”具有完全已知的关系，那么比较它们的“数组定义”是没有意义的，因为这只是用来找出关系的额外细节，但我们有确切的关系，所以毫无意义。

所以......假设这些“带有数组的事物”中只有 500 个具有未知或部分已知的关系。这仍然使 250000(ish) 可能的“数组对”进行比较！

现在......对我来说，最明显的起点是意识到除非用于定义两个数组的关系发生变化（变得更具体），否则处理这个“数组对”是没有意义的。

例如，假设我有这两个数组：

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

现在，如果我这么说T=R，那就太好了。但这并不影响 X 和 Y 之间的关系。所以仅仅因为 T 与 R 的关系已经被称为“相等”，而在它可能完全未知之前，这并不意味着我需要再次比较 X 和 Y。

另一方面，如果我说“ T outside E”，这是用于定义两个数组的事物之间的关系。所以说“ T outside E”意味着我需要针对 Y 的数组处理 X 的数组。

我真的不想为了处理 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 vs B，以及 A vs C）。

我们可以通过检查任何数组对是否已经具有完全已知的关系来进一步修剪这个列表。

我遇到的问题是它仍然看起来过分。

假设 X 是一个非常常见的“事物”。它用于 10,000 个阵列。而 Y 是一个很常见的东西，用在 10,000 个数组中。

我最终还是要比较 100,000,000 个数组对。好的，假设我不需要全部比较它们，实际上，其中只有 50 个部分已知或完全未知。

但是...我仍然需要遍历 100,000,000 个数组对的列表，才能确定其中哪些是部分已知的。所以它仍然是低效的。

我真的想知道是否没有有效的方法来做到这一点。如果真的我能做的就是制定一些有效的“启发式”策略。我还没有太多运气想出好的策略。

我意识到这个问题是高度专业化的。而且我意识到阅读这篇长篇文章可能需要很长时间。我只是不确定如何缩小帖子长度或用更常见的问题来描述这一点。

如果它有帮助......我最好的尝试用通用术语表达这一点，是“如何仅比较已更新的列表”。

有人有什么想法吗？那很好啊。如果不是……也许只有我写出来可能有助于我的思考过程。

问题是，我只是忍不住觉得有一些算法或方法可以让这个问题运行得快速高效。我只是不知道那个算法是什么。

谢谢大家

4

5 回答 5

0

I'm not sure I understand what you are doing completely (the purpose of ArrayDefinition is particularly hazy), but I think you should consider separating the modeling of the objects from their relationships. In other words, create a separate mapping from object to object for each relationship. If objects are represented by their integer index, you need only find an efficient way to represent integer to integer mappings.

于 2010-02-04T03:34:21.990 回答
0

通常，您将无法为每个操作提供尽可能快的结构。需要权衡取舍。

这个问题看起来非常类似于在关系数据库上执行查询 - SELECT * WHERE .... 你可以考虑在那里寻找灵感。

于 2010-02-04T02:32:26.900 回答
0

从您自己的回答中，我推断未知关系大大超过已知关系。然后，您可以在单独的哈希表/集中跟踪每个事物的未知关系。作为进一步的优化，不是跟踪使用事物的所有定义，而是跟踪这些定义中的哪些具有未知关系——哪些关系会受到影响。然后给定一个新定义的 X 和 Y 之间的关系，取其中一个的受影响定义，并找到每个未知关系与另一个受影响的定义的交集。为了使加速数据结构保持最新，当关系变得已知时，将其从未知关系中删除，如果没有未知关系仍然存在，则遍历数组 def 并从可以影响集中删除该事物。

然后数据结构将如下所示：

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;
}

我保留了所有“可比较数组对”的全局列表。

而且我还构建了一个全局列表，包含所有“可以比较的数组”（不是成对的，只是一个一个）。

然后，每次更改关系时，我都可以查看我所在的“数组定义”列表，并在其中添加一个小“标签”:)

所以我可以做这样的事情：

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 添加了一个“modifiedtag”，并且所有的数组 B 都用于定义。

所以，然后我遍历我的“可比较数组对”列表。每对当然是两个数组，每个数组都有一个“RelationModifiedTag”集。

所以我检查了两个 RelationModifiedTag 集，看看它们是否有任何匹配的数字。如果他们这样做了，那么这意味着这个数组对的关系刚刚被改变！所以...我可以做我的数组比较。

它应该工作:)

它确实需要一些开销，但主要是我认为它可以很好地扩展到更大的数据集。对于较小的数据集，比如只有 10 个数组，可以使用更简单、更暴力的方法，只需比较所有不具有完全已知关系的数组对，并且不必费心跟踪已更改的关系。

还有进一步的优化可能。但我不会在这里讨论这些，因为它只是分散了主要算法的注意力，而且它们很明显。例如，如果我有两个要比较的集合，我应该遍历较小的集合并检查较大的集合。

很抱歉不得不阅读所有这些长文本。并感谢所有尝试提供帮助。

于 2010-02-04T15:27:29.913 回答
0

嗯，首先，一些词汇。

设计模式：Observer

这是一种允许对象将自己注册到其他对象并请求事件通知的设计模式。

例如，每个人都ThingWithArray可以在他们管理的地方注册自己Thing，这样如果Thing更新了，ThingWithArray就会得到通知。

现在，通常有一种unsubscribe方法，意思是一旦ThingWithArray不再依赖某些Thing，因为所有使用它们的关系都已被使用，那么它们就可以unsubscribe自己，从而不再被通知更改。

这样，您只会通知那些真正关心更新的人。

但是有一点需要考虑：如果你有递归关系，它可能会变得很复杂，你需要想出一种方法来避免这种情况。

此外，请遵循 ergosys 的建议，并对对象之外的关系进行建模。拥有 1 个 BIG 类通常是麻烦的开始……如果您难以将其切割成逻辑部分，那是问题对您来说不清楚，您应该就如何建模它寻求帮助……一旦您有了清晰的模型，事情通常会更容易到位。

于 2010-02-04T19:06:07.680 回答