仅用于比较已更新列表的高效算法

Question

即使描述此问题也很难，但我会放弃它。我一直在努力挣扎几天，并决定在这里问问。

好的，所以我试图对我所谓的“概念”或“事物”进行建模。一般概念。这与处理逻辑有关。

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

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

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

所以这就是我随着时间的推移逐渐增加知识的模型。事情始于一个完全未知的状态，并可以通过部分已知的状态，并可以达到完全已知的状态。

多一点背景：

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

class ArrayDefinition { 
    Array<Thing> Items; 
} 

而且我的事类变成这样：

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的数组。

我真的不希望比较500,000个“数组对”，只是为了处理1000个数组上的逻辑，而几乎在它们之间没有任何变化！

所以......我第一次尝试简化这个，就是保留一个事物用来定义的所有数组的列表。

比方说，我有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个数组对来比较。好吧，让我们说我不需要全部比较它们，实际上，其中只有50个是部分已知的或完全未知的。

但是......我仍然需要运行100,000,000个数组对的列表，以找出其中哪些部分已知。所以它仍然是低效的。

我真的想知道是否没有这样做的有效方法。如果我真的只能做一些有效的“heuristicish”策略。我还没有太多的运气来提出好的策略。

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

如果有帮助...我最好的尝试是用通常的术语来表达这个意思，就是“如何只比较已经更新的列表”。

任何人有任何想法？那太好了。如果没有......也许只是我写出来可能会帮助我的思考过程。

事情是，我只是不禁觉得有一些算法或方法可以使这个问题快速和有效地运行。我只是不知道那个算法是什么。

感谢所有

Answer 1

一般情况下，你将无法拿出那是因为，快速的，可能每个操作的结构。有权衡取舍。

此问题与在关系数据库上执行查询非常相似 - SELECT * WHERE ...。你可能会考虑寻找灵感。

Answer 2

我不确定我完全理解你在做什么（ArrayDefinition的目的特别模糊），但我认为你应该考虑将对象的建模与关系分开。换句话说，为每个关系创建一个从对象到对象的单独映射。如果对象由其整数索引表示，则只需找到一种有效的方法将整数表示为整数映射。

Answer 3

我有一个睡眠，当我醒来时，我有一个新的想法。它可能工作...

如果每个“东西”保留所有“数组定义”的列表，它用于定义。

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

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

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

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

然后，每次的关系改变了，我可以走了的“阵列定义”列表中，我的里面，加点“标签”来了:)

所以我可以这样做这个：

​​

我改变了双方的关系。因此，如果我这样做了："A outside B"，那么我已经为所有数组A添加了“modifiedtag”，并使用所有数组B来定义。

因此，然后我遍历我的“可比数组对”列表。每一对当然是两个数组，每一个将有一个“RelationModifiedTag”集。

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

它应该工作:)

它确实需要一些开销，但更主要的是，我认为它很好地扩展到更大的数据集。对于较小的数据集来说，只有10个数组，可以使用更简单更蛮力的方法，只比较所有没有完全已知关系的数组对，并且不打算跟踪哪些关系已被改变。

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

道歉不必去阅读所有这些长文本。并感谢所有的帮助尝试。

Answer 4

嗯，首先，一些词汇。

设计模式：Observer

这是一个设计模式，它允许对象将自己注册为他人，并要求对事件的通知。

例如，每个ThingWithArray可以在他们所管理的Thing自身进行注册，因此，如果Thing更新的ThingWithArray会得到通知回来。

现在，有通常是一个unsubscribe方法，这意味着只要ThingWithArray不再依赖于一些Thing，因为已使用的所有使用它们的关系，那么他们可能会unsubscribe自己，以免被通知更改。

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

有一点考虑是：如果你有递归关系，它可能会很麻烦，你就需要拿出一个办法来避免这种情况。

此外，遵循ergosys建议，以及对象的外模型关系。有1个BIG课程通常是麻烦的开始......如果你很难将其划分为逻辑部分，那么问题就不清楚了，你应该询问如何对它进行建模......一旦你完成了得到了一个清晰的模型，事情通常更容易一点。

Answer 5

从你自己的答案，我推断出未知的关系是大大已知的关系过度编号。然后，您可以在单独的散列表/集中跟踪每个事物的未知关系。作为进一步的优化，不是跟踪所有定义的使用情况，而是跟踪哪些定义具有未知关系 - 哪些关系可能会受到影响。然后给定一个新定义的X与Y之间的关系，取其中一个的受影响定义，并找出每个未知关系与另一个的受影响定义的交集。为了使加速度数据结构保持最新状态，当关系变为已知时，将其从未知关系中删除，并且如果没有未知关系，则继续检查数组def并从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; 
}