這樣的數據結構是否存在？

我正在尋找一個數據結構，它可以像普通列表一樣快地排序，並且應該允許以下列方式刪除元素。比方說，我們有一個列表如下：這樣的數據結構是否存在？

[{2,[1]}, 
{6,[2,1]}, 
{-4,[3,2,1]}, 
{-2,[4,3,2,1]}, 
{-4,[5,4,3,2,1]}, 
{4,[2]}, 
{-6,[3,2]}, 
{-4,[4,3,2]}, 
{-6,[5,4,3,2]}, 
{-10,[3]}, 
{18,[4,3]}, 
{-10,[5,4,3]}, 
{2,[4]}, 
{0,[5,4]}, 
{-2,[5]}]

即含元組一個列表（這是Erlang的語法）。每個元組包含和列表，其中包括用於計算以前編號的列表的成員。我想對列表做如下處理。首先，排序它，然後取頭的名單，最後乾淨的名單。 clean我的意思是從尾部刪除包含頭部中的元素的所有元素，或換句話說，尾部與頭部相交的所有元素不爲空。例如，排序後的頭是{18,[4,3]}。下一步是去除含有4或3，列表中的所有元素，即所產生的名單應該是這樣：

[{6,[2,1]}, {4,[2]}, {2,[1]}, {-2,[5]}]

過程遵循通過採取新的頭，直到整個列表被消耗再次清洗。請注意，如果清理過程保留了訂單，則不需要每次迭代均列出清單。

瓶頸在這裏是清潔過程。我需要一些結構，使我能夠以比現在更快的速度進行清潔。

有誰知道一些允許以有效的方式做到這一點，而不會丟失順序或至少允許快速排序的結構嗎？

來源

2016-07-27 Salvador Tamarit

您需要某種支持索引結構來爲您創建非線性查找效率。即跟蹤哪些節點具有哪個整數值。然後，您需要考慮在成本制定中維護支持指數結構的開銷。 – mba12

究竟是「高效」？什麼是「快速排序」？標準列表是不夠的嗎？您需要什麼操作以及平均複雜程度如何？ – Bergi

這是不是很清楚您是否在談論外部列表，內部列表或結構作爲一個整體。 – Bergi

是的，你可以得到比這更快。你的問題是你代表第二個元組成員列表。搜索它們很繁瑣而且不必要。它們都是5..1的連續子串。你可以簡單地將它們表示爲索引的元組！

事實上，你甚至不需要這些索引元組的列表。把它們放在一個二維數組就在通過各自的元組給定的位置，你會得到一個triangular array：

h\l| 1 2 3 4 5 
---+---------------------- 
1 | 2 
2 | 6 2 
3 | -4 -6 -10 
4 | -2 -4 18 2 
5 | -4 -10 -10 0 -2

而不是一個二維數組存儲數據，你可能希望存儲他們在一個簡單的數組中有一些索引魔術來解釋三角形的形狀（如果你的編程語言只允許矩形的二維數組），但這不影響複雜性。

這就是您需要快速篩選「列表」所需的所有結構，只需查看事情即可。

而是先排序並獲得頭，我們只需通過整個結構重複一次找到最大價值和指數：

max_val = 18 
max = (4, 3) // the two indices

過濾器是相當簡單的。如果我們不使用列表（not (any (substring `contains`) selection)）或集合（isEmpty (intersect substring selection)）而是元組，那麼它只是sel.high < substring.low || sel.low > substring.high。而我們甚至都不需要遍歷整個三角形陣列，我們可以簡單的迭代的海格客車和下部三角形：

result = [] 
for (i from 1 until max[1]) 
    for (j from i until max[1]) 
     result.push({array[j][i], (j,i)}) 
for (i from max[0] until 5) 
    for (j from i until 5) 
     result.push({array[j+1][i+1], (j+1,i+1)})

而且你已經得到了你所需要的元素：

[{ 2, (1,1)}, 
{ 6, (2,1)}, 
{ 4, (2,2)}, 
{-2, (5,5)}]

現在你只需要對其進行排序並獲得結果。

事實上，三角形陣列的整體複雜性並沒有得到改善。你仍然得到O(n)從建立名單和發現最大值。無論您是通過針對每個子字符串索引元組進行測試來篩選O(n)還是通過智能選擇篩選O(|result|)都無所謂，但是您特別提出了有關快速清理步驟的問題。如果數據很大，或者需要進行多次清理，這仍然可能對實際情況有益。
影響整體複雜度的唯一因素是僅對結果進行排序，而不是整個輸入。

來源

2016-07-28 16:26:51 Bergi

是的，這樣做我已經消除了瓶頸。以這種方式進行過濾要快得多。非常感謝：） –

我不知道你的原始數據結構是否可以看作是一個有向圖的鄰接表？例如;

{2,[1]}, 
{6,[2,1]}

表示您有這些節點和邊;

node 2 => node 1 
node 6 => node 2 
node 6 => node 1

所以你的問題可以改寫爲;

如果我找到一個鏈接到節點4和3的節點，如果我刪除了節點4和3，圖表會發生什麼變化？

一種方法是建立一個鄰接矩陣;一個NxN位矩陣，其中每個邊緣都是1位。你的問題現在變成了;

將4行中的每一位和4列中的每一位都設置爲零。

也就是說，沒有任何鏈接進出這個被刪除的節點。

作爲一種優化，保留一個長度爲N的位數組。該位在節點未被刪除時設置。因此，如果節點1，2，4，和5「活」和3,6「刪除」，數組看起來像

[1,1,0,1,1,0]

我們刪除「4」，只需清除該位;

[1,1,0,0,1,0]

當您完成後刪除，經過鄰接矩陣，而忽略在一個行或列編碼與0設置任何優勢。

完整的例子。比方說你有

[ {2, [1,3]}, 
    {3, [1]}, 
    {4, [2,3]} ]

這是鄰接矩陣

1 2 3 4 
1 0 0 0 0 # no entry for 1 
2 1 0 1 0 # 2, [1,3] 
3 1 0 0 0 # 3, [1] 
4 0 1 1 0 # 4, [2,3]

和麪罩

[1 1 1 1]

要刪除節點2，您只需改變面具;

[1 0 1 1]

現在，找出結構，僞代碼，如：

rows = [] 
for r in 1..4: 
    if mask[r] == false: 
    # this row was deleted 
    continue; 

    targets = [] 
    for c in 1..4: 
    if mask[c] == true && matrix[r,c]: 
     # this node wasn't deleted and was there before 
     targets.add(c) 

    if (!targets.empty): 
    rows.add({ r, targets})

鄰接矩陣可以得到大 - 這是N×N個位，畢竟 - 所以這將只對小而密的矩陣，而不是更好大，稀疏的。

如果這不是很大，你可能會發現，它更容易谷歌的圖形算法自己不是創造他們:)

來源

2016-07-28 08:58:26

元組的第一個數字不是圖的節點，因此您錯誤地理解了該問題。我已經添加了更多的文字來解釋問題，因爲我已經看到了這個問題被解釋清楚了。我希望現在可以更好地理解:)謝謝你的答案。無論如何，我一直在用圖表和樹木來思考這個問題，但是我找不到滿足我所有要求的解決方案。 –

這樣的數據結構是否存在？

回答

相關問題