拖拽排序的演算法思考
一、背景
今天有同事問我:有沒有做過用db一個欄位來做排序索引,然後支援使用者隨意更改排序的需求?
起初看到這個問題,我以為是按照一個欄位排序,然後支援人工干預。
不過一想,不對,人工干預了就沒辦法按照指定欄位排序了。 一旦人工干預,所以欄位的位置都固定了。
那個同事說,就是所有位置都固定,但是需要支援拖拽排序。
需要維護一個排序索引欄位,不知道有沒有成熟的類似的演算法?
需求簡化一下就是,有一批資料儲存在DB中,會刪除一條資料或插入一個數據,希望有個演算法能夠儲存這個順序。
二、字串排序
最簡單的是每次插入的時候,修改所有資料的編號。
不過這個資料儲存在DB中,一條記錄一行,修改所有資料的編號的複雜度是O(n)
了,資料少還可以,多了不能接受。
接著我想,如果使用整數的話,可能會衝突。衝突了還需要調整區域性區間的標號,怪複雜的。 但是使用字串的話,衝突了就加字尾即可,簡單粗暴。 於是我提供了第一個方法:字串中值+字尾解決。
比如對於下面的資料
p0001 p0004 p0005 p0009
p0001
拖到p0005
之後, 通過計算 (p0005
,p0009
)的值,得到p0007
p0001
拖到p0004
之後,通過計算(p0004
,p0005
)的值,得到p00045
同事看之後,說:使用字串排序比較慢。
三、整數
我想,這個建個索引的話,複雜度還是log(n)
的,只是常數比較大。
非要使用整數的話,還是使用上面的中值方法,只不過衝突的時候,需要進行小範圍重調整了。
當然,我們可以使用32位整數或者64整數來當做編號,需要人工拖拽的資料量一般是人一個個加進去的,一般也就十幾條,頂多幾百條。
衝突的概率是非常小的,使用32位整數就夠了。
於是,使用這個方法差不多就解決問題了。
四、儲存率
然後,我又思考:如果到了衝突那一步才進行調整,可能情況已經很壞了。 如果能夠提前就進行調整,平均複雜度應該會更低。
怎麼判斷是否需要調整呢?
我引入了一個儲存率的概念。
設第 i 個數字的值是 P(i),第 j 個數字的值是 P(j),則(i,j)的儲存率就是 (j - i + 1)/(P(j) - P(i) + 1)。
儲存率越高,衝突的概率越大。
然後,每次調整位置後,檢查新插入位置在區域性小區間的儲存率是否超過指定值,超過了就在區域性大區間進行調整。
當然,這個只是我的猜測,沒有數學公式證明這個平均複雜度更低。
五、浮點數
後來,想了想,使用浮點數也可以降低衝突的概率。
但是衝突的久了,還是需要進行區間調整的。
六、分塊
有序資料或者陣列,其本質還是遞迴形式的連結串列。
但是使用裸的連結串列效能顯然是不能接受的。
於是我想可以使用ACM中常使用的分塊思想。
分塊+連結串列,自然想到了分塊連結串列。
但是考慮具體實現細節的時候,發現在DB中維護連結串列的關係成本蠻高的。
每個連結串列節點需要有一個唯一標示,這個唯一標示需要快速定位到連結串列節點的首地址。
首地址的元素可能會刪除,那還需要使用雙向連結串列。
雖然方案是可行,但是實現成本太高,實現了程式碼也太複雜,不可行。
接著,我想,陣列既然是連結串列,那連結串列也是陣列了。
於是我就想到了分塊陣列。
每個分塊有一個唯一的標號,標號的大小順序代表分塊的順序。
這個就轉化為了兩個欄位來決定資料順序了。
第一級的標號是分塊,每個分塊內獨立進行分配標號。這樣衝突的概率就大大的降低了。
有多低呢? 原先的數量級是O(N)
,現在降為了srqt(N)
。
而且維護兩級的成本比一級的成本高不了多少。
七、最後
有一週沒寫東西了,其實那一週也沒看書。
最近雜事變得很多很多,把很多計劃都打亂了,以至於我都懷疑人生了:我在幹什麼?
還好,現在敲了一些程式碼後慢慢恢復正常了。
後面會多寫一些演算法上的東西,有利於提高思維能力。
本文首發於公眾號:天空的程式碼世界,微信號:tiankonguse-code。