通過識別序列中的間隙來測試流的可靠性

我正在研究一個我認爲簡化到以下問題並希望找到能夠以高效內存方式解決問題的數據結構或算法的問題。通過識別序列中的間隙來測試流的可靠性

假設您正在讀取序列號的（無限）蒸汽。有些製作人連續不斷地將數字發送到這個流中，而沒有重複，並從另一端讀取它們。但是有一些問題。

1.）這個系統有一些固有的不可靠性。流或生產者或其中之一可以丟棄一段數據，因此數字可能不會出現在消費者處，並且總體上存在任何給定數量可能丟失的（未知的）概率。

2.）流不能完全保證順序。爲了爭論起見，假設有一些（衆所周知的）常量N，這樣如果您從流中讀取x數字，您可以確定在該點之後，您將永遠不會看到數字流中的數字y < x - N。

也就是說，數字序列在任何時候都只能是「無序」的N值。

在這種情況下，我真的很想確定p。或者p的合理估計值是重要的。

我會很感激任何有關數據結構或算法的參考，這將有助於以有效的內存方式解決此問題。一些簡短的僞代碼也會有幫助。謝謝！

編輯：通過記憶效率我的意思是我希望能夠解決這個問題，而不必使用O（N）內存，其中N是從流中讀取的條目數。

來源

2015-12-23 Moodragonx

我的確發現了類似的問題（http://stackoverflow.com/questions/15323362/what-is-the-most-efficient-datastructure-for-an-ordered-sequence-with-gaps-searc）但我不確定如何使用亂序問題。 – Moodragonx

你想根據這個描述來想出一個合理的'p'估計值嗎？或者你想根據收到的一些數據樣本來確定'p'的值？ –

@JimMischel通過對數據進行採樣;我不相信你可以僅僅通過我所說的來估計'p'。雖然這會令人印象深刻。 – Moodragonx

一個簡單的方法可以如下。

假設您聽足夠長的時間流，並且您讀取的最後一個數字是x。然後你知道所有數字減去x-N要麼已經收到，要麼丟失。如果你存儲了所有收到的號碼，你可以很容易地找出有多少個號碼小於x-N你已經收到實際上;假設您實際收到了A號碼。並且你肯定知道^*有多少個號碼比x-N少想要接收，假設你期望收到B號碼。這兩個值的比率，A/B，會給你一個很好的估計p。

^*這取決於您是否知道您應該收到的第一個號碼。例如，如果您知道序列從0開始，那麼您應該預計有B=x-N數字。如果您不知道起始號碼，您可以將其限制爲與上面描述的相同，方法是先收到第一個號碼z，並僅考慮z+N和x-N之間的數字。

爲了能夠找到A您可以使用許多數據結構。二叉搜索樹是一個明顯的選擇。或者您只能存儲收到的總數和有史以來收到的最大數量，因此BST也是一個不錯的選擇。

來源

2015-12-23 09:30:34 Petr

通過識別序列中的間隙來測試流的可靠性

回答

相關問題