複雜的排序字典到排序列表

我有下面的類：也有與一幫這些SalesRecords與SalesRecord.name爲重點的結構性的字典複雜的排序字典到排序列表

class SalesRecord: 
    name = '' 
    dollarsSpent = 0 
    itemsPurchased = 0 
    itemsSold = 0 
    position = 0

我。我怎麼能值進行排序與以下標準排序列表（假設一切都爲整數）：

排序dollarsSpent遞減
然後通過itemsPurchased - itemsSold遞減
然後通過itemsPurchased遞減
然後按位置asc

此外，只是好奇，但這樣的整體運行時間是什麼？在最壞的情況下是否需要迭代4次？

來源

2014-02-25 Gyrien

你能展示你的字典結構嗎？ –

這只是一個簡單的字典結構。例如： 'sales ['Johnson1'] = SalesRecord對象其中SalesRecord.name ='Johnson1'' – Gyrien

使用複合鍵。

sorted((k, v) for (k, v) in somedict, key=lambda (k, v): 
    (-v.dollarsSpent, -(v.itemsPurchased - v.itemsSold), 
    -v.itemsPurchased, v.position))

來源

2014-02-25 05:24:00

這樣做與使用user2357112提供的選項1相比有什麼好處？ – Gyrien

它不會爲範圍添加其他名稱。這兩種方式都沒什麼大不了的。 –

您有兩種選擇。兩個選項均在線性時間運行，O(nlog(n))，但您可以考慮更具可讀性。您可以使用複合排序關鍵字：

def sortkey(salesrecord): 
    r = salesrecord 
    return (
     -r.dollarsSpent, 
     -r.itemsPurchased + r.itemsSold, 
     -r.itemsPurchased, 
     r.position 
    ) 
sorted(salesdict.values(), key=sortkey)

或排序多次，依靠排序算法的穩定性：

l = salesdict.values() 
l.sort(key=lambda r: r.position) 
l.sort(key=lambda r: r.itemsPurchased, reverse=True) 
l.sort(key=lambda r: r.itemsPurchased - r.itemsSold, reverse=True) 
l.sort(key=lambda r: r.dollarsSpent, reverse=True)

隨着stable sort，您可以通過許多不同的鍵排序通過從最低優先級到最高優先級排序每個密鑰。在按優先級較高的密鑰進行排序後，通過該密鑰進行比較的項目保證按優先級較低的排序後的順序保持不變。

來源

2014-02-25 05:26:07 user2357112

這兩個選項仍然排序timsorts最壞情況下的時間O（nlog（n））？ – Gyrien

@Gyrien：是的。人們可能會有一個更糟糕的常數因素，但這可能無關緊要。 – user2357112

謝謝！另外，爲什麼在第二種情況下首先排序？ – Gyrien

最簡單的方法是利用sort stability分多個階段進行排序（先按位置，然後按購買下降的物品等）。

這比看起來便宜，因爲TimSort algorithm利用已經部分排序的元素。

這種方法比試圖構建過於複雜的key-function更容易。

來源

2014-02-25 06:00:10

複雜的排序字典到排序列表

回答

相關問題