僅用於比較已更新列表的高效算法

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