顯示廣告
隱藏 ✕
※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2019-11-10 09:49:23
看板 Gossiping
作者 arrenwu (二乃騎士)
標題 [問卦] 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
morichi: import 二乃1F 49.214.212.241 台灣 11/10 03:03
a58524andy: 說起來這類簡單儲存資料結構有沒有什2F 140.112.244.224 台灣 11/10 03:05
dklash: 難道你要用java?3F 114.24.193.51 台灣 11/10 03:05
Java很好啊 Java臭了嗎?臭了嗎?臭了嗎?臭了嗎?
a58524andy: 麼公認的標準測資阿4F 140.112.244.224 台灣 11/10 03:05
測資這個你隨便寫都很可以吧
a58524andy: 當年刻紅黑只知道自己丟隨機以及助教5F 140.112.244.224 台灣 11/10 03:06
a58524andy: 給的測資沒問題
lucifiel1618: 那不就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)
MagicSword: 改用 Jython 呀8F 36.235.194.118 台灣 11/10 03:12
lucifiel1618: 可是如果是這個排序的話,內建的dic9F 89.15.237.232 德國 11/10 03:16
lucifiel1618: t本來就是照這樣排序啊
wuyiulin: 不知道,我資結做的時候是byC11F 223.141.120.186 台灣 11/10 03:24
yamakazi: C++有 改用C++12F 89.200.5.230 荷蘭 11/10 03:30
MagicSword: [(k,dic[k]) for k in sorted(dic.key13F 36.235.194.118 台灣 11/10 03:35
MagicSword: ())]  這樣?
horseface: 我以為pandas能支援?15F 172.58.19.52 美國 11/10 03:42
giaour 
giaour: 不會去stackoverflow問喔16F 112.104.15.9 台灣 11/10 03:42
Ericz7000: sorted map應該插入就會排序了吧 你那17F 59.127.81.29 台灣 11/10 03:45
Ericz7000: 個ordereddict還要先sort不太一樣
horseface: 所以你是要插入資料時就排好,還是全19F 172.58.19.52 美國 11/10 03:46
horseface: 部資料放進來再排?
Ericz7000: 我看java那個是每次插入都要比21F 59.127.81.29 台灣 11/10 03:48
horseface: 如果每次插入都要比,那你在py可以每22F 172.58.19.52 美國 11/10 03:50
horseface: 次插入都sort啊?
oxlittle: 八卦版臥虎藏龍24F 140.113.229.138 台灣 11/10 03:59
Ericz7000: 要看你時間複雜度啊==25F 59.127.81.29 台灣 11/10 04:02
lucifiel1618: 那這樣講的話python預設的dict不就26F 89.15.237.232 德國 11/10 04:06
lucifiel1618: 是sorted map了嗎
lucifiel1618: 不管你照什麼順序塞,裡面都是由小
lucifiel1618: 到大這樣排啊
不是 = = 你可以跑跑看下面這個:
x = dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
for i in x.keys():
    print(i)

他印出來的東西絕對不是按照順序
s06i06: 每次插入都排是三小 不要寫糞扣好嗎30F 36.225.218.23 台灣 11/10 04:33
stupidgod08: 每個工具想解決的問題不同31F 182.233.196.234 台灣 11/10 04:46
stupidgod08: 沒放在 lib 又不願意 pip 又不想自幹
stupidgod08: 那可能你的情境不適合用 python
stupidgod08: *stdlib
lucifiel1618: 我好像知道你問題在哪了,我猜你現35F 88.130.56.143 德國 11/10 05:50
lucifiel1618: 在是用python3吧你試試用python2就
lucifiel1618: 知道這不是個問題了
https://repl.it/languages/python
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
wang2346581: 自己寫很難嗎?38F 223.136.149.141 台灣 11/10 06:08
CYCUTalker: C++歡迎你39F 107.77.211.196 美國 11/10 06:12
wuyiulin: 說老實話這種功能應該要內建可以call40F 1.165.197.76 台灣 11/10 06:14
wuyiulin: 又不是多客製化的fun.
bobogei81123: 不過像 C++ 除了極少情形大部分都是42F 171.66.12.120 美國 11/10 06:16
bobogei81123: 用 unordered_map , 多了 map 反而
bobogei81123: 讓很多初學者誤用
lucifiel1618: 但就是啊?有什麼問題嗎?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
stupidgod08: 回wuy大, 不夠日常的功能都不會內建46F 182.233.196.234 台灣 11/10 06:40
stupidgod08: 日常 -> 內建, 常用 -> stdlib
stupidgod08: 偶爾 -> pip
Killercat: .keys()抓出來sort key, 用[]取value49F 220.157.179.73 日本 11/10 06:54
Killercat: 由於[]的O(n)是常數 所以效能是sort的
Killercat: O(nLogn)
t3265199847: 可以用sortedcontainers的SortedDict52F 118.166.79.188 台灣 11/10 06:57
t3265199847: 如果不是用Anaconda要pip就是了
這個sortedcontainers算是一統天下了嗎? 我是裝大蟒蛇沒錯
a72737363: Key值排序在java是treemap吧?54F 223.137.255.131 台灣 11/10 07:05
是的
※ 編輯: arrenwu (71.198.27.180 美國), 11/10/2019 07:12:17
asas1asas200: kotlin>>>>>Java55F 39.8.225.2 台灣 11/10 07:20
shala: #1SZX_t2_ (Python)56F 205.185.222.199 美國 11/10 07:58
Re: [問題] set中key的順序是如何決定的? - 看板 Python - 批踢踢實業坊
連同推文有幾點值得留意 沒錯dict和set 內部都是hash table, 所以內部 的儲存次序和hash 有關,也即是沒特別的順 序。 但在 python 3.6 開始(在3.7 成為標準),
 
askaleroux: 效能57F 42.76.162.172 台灣 11/10 09:18

--
※ 看板: Gossiping 文章推薦值: 0 目前人氣: 0 累積人氣: 243 
作者 arrenwu 的最新發文:
點此顯示更多發文記錄
分享網址: 複製 已複製
1樓 時間: 2019-11-10 10:47:28 (台灣)
  11-10 10:47 TW
小孩子才用 Python
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,因尋獲項目的速度較快,並且通常只有在初始化階段才會被增加項目。
r)回覆 e)編輯 d)刪除 M)收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇