※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2019-11-10 09:49:23
看板 Gossiping
作者 標題 [問卦] Python 怎麼到現在還沒內建 sorted map ??
時間 Sun Nov 10 03:00:38 2019
這裡所謂的 sorted map 指的是以key值進行排序的 map,
不管讀取增加還是刪除的時間複雜度都是 o(log n)
這種map Java在1.2版就已經有了,
而我剛剛才發現Python的標準函式庫到現在還沒有 zzzzzzzzzzzzzzzzzzzzzzzzz
他媽的總不會要使用者自己實現紅黑樹吧? 幹你娘勒
有沒有Python到現在還沒有sorted map 的八卦啊?
--
「他不能睡車上嗎?」 ~中野二乃
https://i.imgur.com/s9ENvjt.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.198.27.180 (美國)
※ 文章代碼(AID): #1TnmpOjW (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1573326040.A.B60.html
推 : import 二乃1F 49.214.212.241 台灣 11/10 03:03
推 : 說起來這類簡單儲存資料結構有沒有什2F 140.112.244.224 台灣 11/10 03:05
→ : 難道你要用java?3F 114.24.193.51 台灣 11/10 03:05
Java很好啊 Java臭了嗎?臭了嗎?臭了嗎?臭了嗎?→ : 麼公認的標準測資阿4F 140.112.244.224 台灣 11/10 03:05
測資這個你隨便寫都很可以吧→ : 當年刻紅黑只知道自己丟隨機以及助教5F 140.112.244.224 台灣 11/10 03:06
→ : 給的測資沒問題
→ : 給的測資沒問題
→ : 那不就OrderedDict = =7F 89.15.237.232 德國 11/10 03:11
不是,ordered dictionary 是會保留「插進來的順序」,這個在Java 的對應是 LinkedHashMap
我現在是要一個能對key排序的map,也就是我插入 (3,2) (1,3) (2,5),
依序丟出來的entry pairs 會是 (1,3) (2,5) (3,2)
→ : 改用 Jython 呀8F 36.235.194.118 台灣 11/10 03:12
→ : 可是如果是這個排序的話,內建的dic9F 89.15.237.232 德國 11/10 03:16
→ : t本來就是照這樣排序啊
→ : t本來就是照這樣排序啊
推 : 不知道,我資結做的時候是byC11F 223.141.120.186 台灣 11/10 03:24
推 : C++有 改用C++12F 89.200.5.230 荷蘭 11/10 03:30
→ : [(k,dic[k]) for k in sorted(dic.key13F 36.235.194.118 台灣 11/10 03:35
→ : ())] 這樣?
→ : ())] 這樣?
推 : 我以為pandas能支援?15F 172.58.19.52 美國 11/10 03:42
噓 : 不會去stackoverflow問喔16F 112.104.15.9 台灣 11/10 03:42
推 : sorted map應該插入就會排序了吧 你那17F 59.127.81.29 台灣 11/10 03:45
→ : 個ordereddict還要先sort不太一樣
→ : 個ordereddict還要先sort不太一樣
推 : 所以你是要插入資料時就排好,還是全19F 172.58.19.52 美國 11/10 03:46
→ : 部資料放進來再排?
→ : 部資料放進來再排?
推 : 我看java那個是每次插入都要比21F 59.127.81.29 台灣 11/10 03:48
推 : 如果每次插入都要比,那你在py可以每22F 172.58.19.52 美國 11/10 03:50
→ : 次插入都sort啊?
→ : 次插入都sort啊?
推 : 八卦版臥虎藏龍24F 140.113.229.138 台灣 11/10 03:59
推 : 要看你時間複雜度啊==25F 59.127.81.29 台灣 11/10 04:02
→ : 那這樣講的話python預設的dict不就26F 89.15.237.232 德國 11/10 04:06
→ : 是sorted map了嗎
→ : 不管你照什麼順序塞,裡面都是由小
→ : 到大這樣排啊
不是 = = 你可以跑跑看下面這個:→ : 是sorted map了嗎
→ : 不管你照什麼順序塞,裡面都是由小
→ : 到大這樣排啊
x = dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
for i in x.keys():
print(i)
他印出來的東西絕對不是按照順序
噓 : 每次插入都排是三小 不要寫糞扣好嗎30F 36.225.218.23 台灣 11/10 04:33
推 : 每個工具想解決的問題不同31F 182.233.196.234 台灣 11/10 04:46
→ : 沒放在 lib 又不願意 pip 又不想自幹
→ : 那可能你的情境不適合用 python
→ : *stdlib
→ : 沒放在 lib 又不願意 pip 又不想自幹
→ : 那可能你的情境不適合用 python
→ : *stdlib
→ : 我好像知道你問題在哪了,我猜你現35F 88.130.56.143 德國 11/10 05:50
→ : 在是用python3吧你試試用python2就
→ : 知道這不是個問題了
https://repl.it/languages/python→ : 在是用python3吧你試試用python2就
→ : 知道這不是個問題了
Python 2.7.16
x = dict([('sape', 4139), ('guid', 4127), ('aack', 4098)])
for i in x.keys():
print(i)
Output:
aack
sape
guid
他如果built-in map 是sorted map 那問題更大
※ 編輯: arrenwu (71.198.27.180 美國), 11/10/2019 05:58:18
→ : 自己寫很難嗎?38F 223.136.149.141 台灣 11/10 06:08
推 : C++歡迎你39F 107.77.211.196 美國 11/10 06:12
推 : 說老實話這種功能應該要內建可以call40F 1.165.197.76 台灣 11/10 06:14
→ : 又不是多客製化的fun.
→ : 又不是多客製化的fun.
推 : 不過像 C++ 除了極少情形大部分都是42F 171.66.12.120 美國 11/10 06:16
→ : 用 unordered_map , 多了 map 反而
→ : 讓很多初學者誤用
→ : 用 unordered_map , 多了 map 反而
→ : 讓很多初學者誤用
→ : 但就是啊?有什麼問題嗎?45F 88.130.56.143 德國 11/10 06:20
不是啊 output 結果是 aack sape guid 這怎麼會是sorted 的結果?Python 2.7.17 Documentation 裡面寫得很明白:
"The keys() method of a dictionary object returns a list of all the keys used
in the dictionary, in arbitrary order (if you want it sorted, just apply the
sorted() function to it)."
Link: https://docs.python.org/2/tutorial/datastructures.html
推 : 回wuy大, 不夠日常的功能都不會內建46F 182.233.196.234 台灣 11/10 06:40
→ : 日常 -> 內建, 常用 -> stdlib
→ : 偶爾 -> pip
→ : 日常 -> 內建, 常用 -> stdlib
→ : 偶爾 -> pip
推 : .keys()抓出來sort key, 用[]取value49F 220.157.179.73 日本 11/10 06:54
→ : 由於[]的O(n)是常數 所以效能是sort的
→ : O(nLogn)
→ : 由於[]的O(n)是常數 所以效能是sort的
→ : O(nLogn)
推 : 可以用sortedcontainers的SortedDict52F 118.166.79.188 台灣 11/10 06:57
→ : 如果不是用Anaconda要pip就是了
這個sortedcontainers算是一統天下了嗎? 我是裝大蟒蛇沒錯→ : 如果不是用Anaconda要pip就是了
推 : Key值排序在java是treemap吧?54F 223.137.255.131 台灣 11/10 07:05
是的※ 編輯: arrenwu (71.198.27.180 美國), 11/10/2019 07:12:17
推 : kotlin>>>>>Java55F 39.8.225.2 台灣 11/10 07:20
Re: [問題] set中key的順序是如何決定的? - 看板 Python - 批踢踢實業坊
連同推文有幾點值得留意 沒錯dict和set 內部都是hash table, 所以內部 的儲存次序和hash 有關,也即是沒特別的順 序。 但在 python 3.6 開始(在3.7 成為標準),
連同推文有幾點值得留意 沒錯dict和set 內部都是hash table, 所以內部 的儲存次序和hash 有關,也即是沒特別的順 序。 但在 python 3.6 開始(在3.7 成為標準),
噓 : 效能57F 42.76.162.172 台灣 11/10 09:18
--
※ 看板: Gossiping 文章推薦值: 0 目前人氣: 0 累積人氣: 244
作者 arrenwu 的最新發文:
- ENDER MAGNOLIA: Bloom in the Mist Final Trailer Link: 相較於終結者莉莉,這代看起來有不少活著的NPC夥伴 操作機制也有比較多的樣子 1/23 號 …52F 34推
- 20F 15推
- 17F 13推
- 11F 8推
點此顯示更多發文記錄
2樓 時間: 2019-11-10 11:00:17 (台灣)
→
11-10 11:00 TW
推文是不是有人搞錯了什麼?unordered_map 是到 C++11 才出現,map 可是它的老前輩。因此,是「多了 unordered_map」而不是「多了 map」,而且它們的用途也不太一樣。需要「頻繁」增減項目時使用 map 會比較快,因為不用像 unordered_map 需要計算 hash。unordered_map 適合當 event table,因尋獲項目的速度較快,並且通常只有在初始化階段才會被增加項目。
回列表(←)
分享