作者ddchris (克里斯)
看板Python
標題[問題] 超長字串的讀取?
時間Sat Sep 16 07:04:15 2017
最近做 onlinejudge 時遇到一個狀況,
題目會給出一個超長字串(皆為數字中間以空白分隔)
ex.10 200 3 6000 40545 87242 ... (長度約10^7個數字)
之前的處理方法都是先做切割(以空白分隔)再轉成數字
list1 = input().split(' ')
list2 = [int(x) for x in list1]
但這題因為字串太長,在第一步驟時就產生 MemoryError的訊息
可是我又得判斷出字串中所有數字(任取三個) "是否有機會形成一個三角形的邊長"
像這樣的狀況 各位前輩們有什麼較好的策略嗎? 感謝!!
(新手自學中 問題若太嫩還請包涵...)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.241.113
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1505516658.A.14E.html
1F：→ Aerials: try 64-bit python? or use chunking or sqlite 09/16 08:57
2F：推 Django: 每個數字的範圍有上限嗎? 09/16 11:44
3F：→ Django: 當數字多的時候 如果要任取三個數都無法形成三角形的話 09/16 11:44
4F：→ Django: 代表第3小的數至少是第1小的2倍 第5又至少是第3小的2倍 09/16 11:45
5F：→ Django: 所以如果有n個數任取三個都無法形成三角形 代表最大的數 09/16 11:45
6F：→ Django: 至少是最小的2^((n-1)/2)倍 09/16 11:46
7F：→ Django: 所以字串內含的數如果是int大小的話 n=70就已經肯定可以吧 09/16 11:47
8F：→ Django: 64bit也n=130左右就肯定可以了 09/16 11:47
9F：→ Django: n=10^7如果還不行的話 裡面不知是啥天文數字XD 09/16 11:48
10F：→ Django: 所以應該可以根據input限制 短於某個長度才來判別 09/16 11:48
11F：→ Django: 太長的就直接輸出可以 09/16 11:48
挖 居然是是Django本人!(學習ing)
抱歉回晚了 每個數字範圍 1~10^9, 然後數字可以重複,字串未做排序
D大的方式是不是只適用於數字沒有重複呢?
附上題目連結
https://zerojudge.tw/ShowProblem?problemid=c268
後來想到好像可以使用 for 迴圈 + string = sys.stdin.read(size) 存取片段字串
只是卡在那個size不知道要多大...(不知道每個數字位數,每次斷點不同 orz)
※ 編輯: ddchris (118.166.241.113), 09/16/2017 17:01:44
12F：→ uranusjr: 可以一次讀一個再出來自己組, 讀到不是數字就代表要斷 09/16 22:15
13F：→ uranusjr: 問題應該不是單一數字的大小, 是有很多個數字 09/16 22:15
14F：推 Django: 有重複還是一樣可以那樣bound吧 09/17 00:47
15F：→ Django: n超過100在那個範圍內就不可能找不出三條湊三角形了 09/17 00:49
16F：推 Django: 你也不用真的去排序 排序只是證明必存在3條湊三角形而已 09/17 00:50
17F：推 Django: 100*10也頂多1000位 所以例如不到1000位就全讀進來硬爆 09/17 00:52
18F：→ Django: 超過就直接輸出可以' 09/17 00:53
19F：→ uranusjr: 他的問題就是只會整行讀不知道怎麼只讀幾個數字啊 XD 09/17 00:55
20F：推 Django: 所以他是input()爆掉不是split()爆哦 09/17 00:59
21F：→ uranusjr: 看起來他只讀部分行或讀進來只拆部分項兩個都不會啊 XD 09/17 01:05
22F：→ uranusjr: 我的意思是他的問題不是演算法, 而是在 Python 的使用 09/17 01:06
23F：推 Django: 嗯應該是 09/17 01:08
感謝樓上兩位 其實我兩方面都不是很清楚
後來有問別人提供了解法:
任選3不能成為三角形的組合會是 1 1 2 3 5 8...(費氏數列?)
所以當 f(44)時超過10^9,故超過44組以上皆可排成三角形(應該是這樣沒錯?)
if n > 44:
s = 'x' (為了讓迴圈可以跑設的任意字串?)
while s[-1] != '\n': ( readline 當讀到檔案末端送出\n來結束迴圈?)
s = sys.stdin.readline(500000) (在記憶體限制內讀取適當大小?)
print('YES')
有錯還請告知 ^^"
24F：推 CaTom: (偷偷筆記) 最近改用python解zerojudge也對整行讀取再切空 09/17 09:21
25F：→ CaTom: 格這點很苦惱(上週才問過類似問題)但相對的大數運算排列求 09/17 09:22
※ 編輯: ddchris (118.166.241.113), 09/17/2017 09:23:04
26F：→ CaTom: 冪那些全都可以輕鬆秒殺XD 09/17 09:22
27F：推 oToToT: 個人覺得python不適合做演算法題 09/18 16:30
28F：→ s860134: 樓上怎麼說＠＠ 09/19 03:59
29F：推 CaTom: 應該是python運行速度的問題硬傷吧? 像for相比C++慢了兩個 09/19 08:41
30F：→ CaTom: 數量級 偏偏演算法題為了考演算法都是用大量測資要短時間內 09/19 08:42
31F：→ CaTom: 完成 其他語言可能用稍好的演算法就能達成的py要苦思更精 09/19 08:43
32F：→ CaTom: 簡快速的方式.. 09/19 08:43