多层循环遍历求解,如何实现?

[复制链接]
查看11 | 回复8 | 2021-1-27 05:44:04 | 显示全部楼层 |阅读模式
【问题】
有15个txt文件,每个文件里面有200行,每一行有500个都是由0或1的数字组成。
形式如下:
1110000001110101101001001110000000000000000000000000110001...
1110101101001001110000000000000000000000000110001101101001...
0000000000000000011000110110100100000000000000000110001101...
...
...
【求解】
想从15个文件里面,每个文件选一行出来,把15行数字按照对应的位数相加。想找到叠加后,数字是0或1组成的那一个组合。
比如下面这两行叠加:
1110000001110101101001001110000000000000000000000000110001...
1110101101001001110000000000000000000000000110001101101001...
生成:
2220101102111102211001001110000000000000000110001101211002...
这是不符合要求的,我想要的是叠加之后的数字也全是1或0。
【实验】
一开始,生成了15个二维数组,500x200的二维数组,可是要做15层循环遍历,而且还要做数组加法运算,太耗时了。超过4层循环,系统基本就算不过来。
请问大家有什么好方法,做这些遍历呢?
分 -->
回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
一次读取两个文件,进行计算,将符合要求的结果写入新的文件,记录好数据来源。手动释放内存,再次读取两个文件。
回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
每个文件只读一行?随机读一行?那只要15个变量记录一行的数据就行了。
按照你的要求,相加后,就要只有0或1的一行数据,那么,两行数据,相同位置上不能同时为1
记录每行为1的位置,两行为1的数据进行比对,位置相同肯定结果不是你想要的。
算法上,用用二分查找,可能会有提升
回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
把算得的字符串再转化一下就好了,奇数为1,偶数为0,不过15个加一起,有可能会出现15哟,好好想想怎么弄吧,或者两行一加一转换
回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
计算比较的算法,我有一点想法,供参考:
仔细看这个问题,发现数全是0和1,很容易联想到二进制。
如果字符计算转到二进制的计算,可能计算会得到很多简化。
下面从这个角度考虑:
1.字符串与二进制数字之间的转换
#读取的字符串,转换成二进制数:
string='1001'
num=int(string,2)
#原字符串就转换成整数9或0b1001
#-------------------------------------
#数字转换回原来的字符串:
str(bin(9))
#数字就转回原串'0b1001'(需要删掉开头的0b两个字符)
2.分析你的要求,只有当1和1碰到一起的时候,数据不可用。其他0和1,0和0都可以。
这个跟二进制的按位’与'的真值表吻合。
所以,计算可以这样进行:
把字符串转换成数字,进行“按位与”操作,
如果结果等于0,那么数据可用,否则说明至少有两位同为1,所以不可用。
然后把等于零的数据对进行”按位或“,得到的结果继续与下一组的数进行”与“操作。
这是因为:从group1、group2取了两个数g1和g2[j],如果"按位与"g1&g2[j]不等于零,
那个后面的13组无论取什么,包含g1和g2[j]的组合都不可用。
比如:
g1[0]=0b1001
g2[0]=0b11000
g2[1]=0b110
g1[0]&g2[0]=8不等于零,g1[0]和g2[0]的组合就不可用
g1[0]&g2[1]=0所以g1[0]和g2[1]的组合可用
然后把g1[0]和g2[1]进行”或“操作,
即g1[0]|g2[1]=0b1111,这个值等待读入下一组进行迭代。

因此,计算比较的算法:
第一次读两个组的数据,
交叉“按位与&”
if等于零,进行“按位或|”操作,结果存起来
else:抛弃
迭代,读下组数据,继续“与”“或”操作
继续下去,直到15组完,剩下的就是想要的结果。
计算机做按位与或运算非常快的
遍历的算法,可能需要用到深度优先搜索(DFS)算法,研究一下DFS看看行不行
个人拙见,不知对否。

回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
15个文件每个200行,我觉得这个数据量不大啊,可以直接暴力做。你可不可以把数据发上来给大家试一下?
回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
你这个我就当成500位二进制数来考虑了,15组数,每组200个
如果15个数a1,a2,...,a15满足你的要求,那么肯定a1,a2、a2,a3,……,a14,a15两两都满足你的要求
所以你可以先两个文件两个文件这样初始化一下,能筛掉不少
回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
感谢大家的回帖,我把问题重新整理了一下:
我把数据导入到了sqlite文件,文件下载:http://u.163.com/nnnnnEwm提取码:8uQBfsJZ
里面有A、B、C....等13个表,每个表中的记录数为
A:24,B:72,C:72,D:72,E:48,F:48,G:96,H:96,I:48,J:24,K:96,L:96,M:72,
每个表中有name字段是为了标记每条记录的唯一性,datas字段是729个0或1组成的字符串。
我用Python的for循环:
第一步,新建AB表,把A、B的数据进行循环组合,去除不符合要求的记录,结果如下:
24*72=1728条,筛选之后剩1300条,循环时间:1.66秒,数据库大小:1.0MB。
第二步,新建ABC表,把AB表和C的数据进行循环组合,去除不符合要求的记录,结果如下:
1300*72=93600条,筛选之后剩53300条,循环时间:86.86秒,数据库大小:41.7MB
第三步,新建ABCD表,把ABC表和D的数据进行循环组合,去除不符合要求的记录,结果如下:
53300*72=3837600条,筛选之后剩1705600条,循环时间:3608秒,数据库大小:1.30GB
第三步已经需要1个小时才能循环完毕,而且数据库的大小已经上GB了。但是我又做了第四步。
第四步,新建ABCDE表,把ABCD表和E的数据进行循环组合,去除不符合要求的记录,结果如下:
1705600*48=81868800条,筛选之后剩28995200条,循环时间:119253秒,数据库大小:22.1GB
第四步花了大约33个小时,也就是等了一天多的时间,可是不能再往下做了,那样一等就是很多天了,而且数据库大小也极速飙升。
【开发环境】
Inteli5-34703.20GHz,8GB内存,Win7SP164位+JupyterLab,Python3.7.6,FireFox浏览器。
【循环代码】
#创建AB表,字段A存放A序号,字段B存放B序号,字段DATAS存放A+B的DATAS
importsqlite3
conn=sqlite3.connect('KML_AB.db')
print("Openeddatabasesuccessfully")
c=conn.cursor()
c.execute('''CREATETABLEAB(ACHAR(4),BCHAR(4),DATASTEXT);''')
print("TableABcreatedsuccessfully")
conn.commit()
conn.close()
print("#Datebaseclosed")
#循环求解KML00.db与KML01.db是内容完全一样的文件
importtime
t1=time.perf_counter()
importsqlite3
conn0=sqlite3.connect('KML00.db')
conn1=sqlite3.connect('KML01.db')
conn2=sqlite3.connect('KML_AB.db')
c0=conn0.cursor()
c1=conn1.cursor()
c2=conn2.cursor()
print("#Openeddatabasesuccessfully")
try:
forxinrange(24):
c0.execute("selectrowid,name,datasfromAwhererowid="+str(x+1))
result0=c0.fetchone()
foryinrange(72):
c1.execute("selectrowid,name,datasfromBwhererowid="+str(y+1))
result1=c1.fetchone()
sData=""
forzinrange(729):
sData=sData+str(int(result0[2][z])+int(result1[2][z]))
if('2'insData):
#print(sData)
continue
else:
sqlAB="INSERTINTOAB(A,B,DATAS)VALUES('"+result0[1]+"','"+result1[1]+"','"+sData+"');"
c2.execute(sqlAB)
#print("exe")
conn2.commit()
print("#Operationdonesuccessfully")
finally:
conn0.close()
conn1.close()
conn2.close()
print("#Datebaseclosed")
print('#IniaSec:',time.perf_counter()-t1)
#IniaSec:1.6601536639991537

=========================
欢迎大家提出建议!


回复

使用道具 举报

千问 | 2021-1-27 05:44:04 | 显示全部楼层
提供一个思路.
每行500个0和1数据可视为63个字节(后补四个0),这样每个文件有200*63个字节数组.
从15个文件中每个文件抽取一行可构成15*63个二维字节判断数组,逐列(0-62)对第i行(i=0-13)和第k行(k>i)中的字节进行按位与,如非零则说明这种选取不符合要求,退出重新选择判断数组.
判断数组共有200**15=3.2768E34种选择,这种量还是蛮大的,构造循环时可按200**5=32E10分三组进行循环.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

主题

0

回帖

4882万

积分

论坛元老

Rank: 8Rank: 8

积分
48824836
热门排行