作者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/cn.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