[問題] 超長字串的讀取?

看板Python作者 (克里斯)時間7年前發表 (2017/09/15 23:04), 7年前編輯推噓9(9推 0噓 23→)
留言32則, 6人參與, 最新討論串1/1
最近做 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://www.ptt.cc/bbs/Python/M.1505516658.A.14E.html
→
09/16 08:57, , 1F
try 64-bit python? or use chunking or sqlite
09/16 08:57, 1F
推
09/16 11:44, , 2F
每個數字的範圍有上限嗎?
09/16 11:44, 2F
→
09/16 11:44, , 3F
當數字多的時候 如果要任取三個數都無法形成三角形的話
09/16 11:44, 3F
→
09/16 11:45, , 4F
代表第3小的數至少是第1小的2倍 第5又至少是第3小的2倍
09/16 11:45, 4F
→
09/16 11:45, , 5F
所以如果有n個數任取三個都無法形成三角形 代表最大的數
09/16 11:45, 5F
→
09/16 11:46, , 6F
至少是最小的2^((n-1)/2)倍
09/16 11:46, 6F
→
09/16 11:47, , 7F
所以字串內含的數如果是int大小的話 n=70就已經肯定可以吧
09/16 11:47, 7F
→
09/16 11:47, , 8F
64bit也n=130左右就肯定可以了
09/16 11:47, 8F
→
09/16 11:48, , 9F
n=10^7如果還不行的話 裡面不知是啥天文數字XD
09/16 11:48, 9F
→
09/16 11:48, , 10F
所以應該可以根據input限制 短於某個長度才來判別
09/16 11:48, 10F
→
09/16 11:48, , 11F
太長的就直接輸出可以
09/16 11:48, 11F
挖 居然是是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
→
09/16 22:15, , 12F
可以一次讀一個再出來自己組, 讀到不是數字就代表要斷
09/16 22:15, 12F
→
09/16 22:15, , 13F
問題應該不是單一數字的大小, 是有很多個數字
09/16 22:15, 13F
推
09/17 00:47, , 14F
有重複還是一樣可以那樣bound吧
09/17 00:47, 14F
→
09/17 00:49, , 15F
n超過100在那個範圍內就不可能找不出三條湊三角形了
09/17 00:49, 15F
推
09/17 00:50, , 16F
你也不用真的去排序 排序只是證明必存在3條湊三角形而已
09/17 00:50, 16F
推
09/17 00:52, , 17F
100*10也頂多1000位 所以例如不到1000位就全讀進來硬爆
09/17 00:52, 17F
→
09/17 00:53, , 18F
超過就直接輸出可以'
09/17 00:53, 18F
→
09/17 00:55, , 19F
他的問題就是只會整行讀不知道怎麼只讀幾個數字啊 XD
09/17 00:55, 19F
推
09/17 00:59, , 20F
所以他是input()爆掉不是split()爆哦
09/17 00:59, 20F
→
09/17 01:05, , 21F
看起來他只讀部分行或讀進來只拆部分項兩個都不會啊 XD
09/17 01:05, 21F
→
09/17 01:06, , 22F
我的意思是他的問題不是演算法, 而是在 Python 的使用
09/17 01:06, 22F
推
09/17 01:08, , 23F
嗯應該是
09/17 01:08, 23F
感謝樓上兩位 其實我兩方面都不是很清楚 後來有問別人提供了解法: 任選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') 有錯還請告知 ^^"
推
09/17 09:21, , 24F
(偷偷筆記) 最近改用python解zerojudge也對整行讀取再切空
09/17 09:21, 24F
→
09/17 09:22, , 25F
格這點很苦惱(上週才問過類似問題)但相對的大數運算排列求
09/17 09:22, 25F
※ 編輯: ddchris (118.166.241.113), 09/17/2017 09:23:04
→
09/17 09:22, , 26F
冪那些全都可以輕鬆秒殺XD
09/17 09:22, 26F
推
09/18 16:30, , 27F
個人覺得python不適合做演算法題
09/18 16:30, 27F
→
09/19 03:59, , 28F
樓上怎麼說＠＠
09/19 03:59, 28F
推
09/19 08:41, , 29F
應該是python運行速度的問題硬傷吧? 像for相比C++慢了兩個
09/19 08:41, 29F
→
09/19 08:42, , 30F
數量級 偏偏演算法題為了考演算法都是用大量測資要短時間內
09/19 08:42, 30F
→
09/19 08:43, , 31F
完成 其他語言可能用稍好的演算法就能達成的py要苦思更精
09/19 08:43, 31F
→
09/19 08:43, , 32F
簡快速的方式..
09/19 08:43, 32F
‣ 更多 ddchris 的文章
文章代碼(AID): #1Pl5no5E (Python)