多層回圈遍歷求解，如何實作？

【問題】
有15個txt檔案，每個檔案里面有200行，每一行有500個都是由0或1的數字組成。
形式如下：
1110000001110101101001001110000000000000000000000000110001...
1110101101001001110000000000000000000000000110001101101001...
0000000000000000011000110110100100000000000000000110001101...
...
...
【求解】
想從15個檔案里面，每個檔案選一行出來，把15行數字按照對應的位數相加。想找到疊加后，數字是0或1組成的那一個組合。
比如下面這兩行疊加：
1110000001110101101001001110000000000000000000000000110001...
1110101101001001110000000000000000000000000110001101101001...
生成：
2220101102111102211001001110000000000000000110001101211002...
這是不符合要求的，我想要的是疊加之后的數字也全是1或0。

【實驗】
一開始，生成了15個二維陣列， 500x200的二維陣列，可是要做15層回圈遍歷，而且還要做陣列加法運算，太耗時了。超過4層回圈，系統基本就算不過來。

請問大家有什么好方法，做這些遍歷呢？

uj5u.com熱心網友回復：

一次讀取兩個檔案，進行計算，將符合要求的結果寫入新的檔案，記錄好資料來源。手動釋放記憶體，再次讀取兩個檔案。

uj5u.com熱心網友回復：

每個檔案只讀一行？隨機讀一行？那只要15個變數記錄一行的資料就行了。
按照你的要求，相加后，就要只有0或1的一行資料，那么，兩行資料，相同位置上不能同時為1
記錄每行為1的位置，兩行為1的資料進行比對，位置相同肯定結果不是你想要的。
演算法上，用用二分查找，可能會有提升

uj5u.com熱心網友回復：

把算得的字串再轉化一下就好了，奇數為1，偶數為0，不過15個加一起，有可能會出現15喲，好好想想怎么弄吧，或者兩行一加一轉換

uj5u.com熱心網友回復：

計算比較  的演算法，我有一點想法, 供參考：

仔細看這個問題，發現數全是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[i] 和 g2[j], 如果"按位與"g1[i] & g2[j] 不等于零，
那個 后面的13組無論取什么，包含g1[i] 和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組完，剩下的就是想要的結果。

       計算機做 按位與或運算 非常快的

遍歷的演算法，可能需要用到 深度優先搜索（ＤＦＳ）演算法，研究一下ＤＦＳ看看行不行

個人拙見，不知對否。

uj5u.com熱心網友回復：

15個檔案每個200行，我覺得這個資料量不大啊，可以直接暴力做。你可不可以把資料發上來給大家試一下？

uj5u.com熱心網友回復：

你這個我就當成500位二進制數來考慮了，15組數，每組200個

如果15個數a1, a2, ..., a15滿足你的要求，那么肯定a1, a2、a2, a3，……，a14, a15兩兩都滿足你的要求

所以你可以先兩個檔案兩個檔案這樣初始化一下，能篩掉不少

uj5u.com熱心網友回復：

感謝大家的回帖，我把問題重新整理了一下：
 我把資料匯入到了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.0 MB。

第二步，新建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 個小時，也就是等了一天多的時間，可是不能再往下做了，那樣一等就是很多天了，而且資料庫大小也極速飆升。

【開發環境】
Intel i5-3470 3.20GHz，8GB記憶體，Win7 SP1 64位 + Jupyter Lab ，Python 3.7.6，FireFox瀏覽器。

【回圈代碼】

# 創建 AB 表 ，欄位 A 存放 A 序號， 欄位 B 存放 B 序號， 欄位 DATAS 存放 A+B 的 DATAS

import sqlite3

conn = sqlite3.connect('KML_AB.db')

print("Opened database successfully")

c = conn.cursor()

c.execute('''CREATE TABLE AB (A CHAR(4),B CHAR(4),DATAS TEXT);''')

print("Table AB created successfully")

conn.commit()

conn.close()

print("# Datebase closed")



#回圈求解 KML00.db 與KML01.db 是內容完全一樣的檔案

import time

t1 = time.perf_counter()

import sqlite3

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("# Opened database successfully")



try:

    for x in range(24):

        c0.execute("select rowid,name,datas from A where rowid =" + str(x+1))

        result0 = c0.fetchone()

        for y in range(72):

            c1.execute("select rowid,name,datas from B where rowid =" + str(y+1))

            result1 = c1.fetchone()



            sData =""

            for z in range(729):

                sData = sData + str(int(result0[2][z])+int(result1[2][z]))



            if('2' in sData):

                #print(sData)

                continue 

            else:

                sqlAB = "INSERT INTO AB (A,B,DATAS) VALUES ('" + result0[1]+"','"+result1[1] + "','" + sData + "');"

                c2.execute(sqlAB)

                #print("exe")



        conn2.commit()

    print ("# Operation done successfully")    

finally:     

    conn0.close()

    conn1.close()

    conn2.close()

    print("# Datebase closed")

    print('# IniaSec:',time.perf_counter()-t1)



# IniaSec: 1.6601536639991537

   

=========================
歡迎大家提出建議！

uj5u.com熱心網友回復：

提供一個思路.
每行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分三組進行回圈.

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/16584.html

標籤：腳本語言(Perl/Python)

上一篇：卸載PyCharm2019 以后，運行PyCharm2020 解壓檔案中的pycharm.sh出錯

下一篇：Anaconda創建環境下載scrapy出錯