演算法讀取大文件

1. C++如何讀取一個大文件，並識別各個字元串出現的次數，找到次數最多的。輸出這個字元

#include <stdio.h>
#include <string.h>

int main()
{
char s[4]="abc",sc='d';//比較的字元串和字元
FILE *fp;
char filename[100],c;
int i=0,n1=0,n2=0;
long fpos,len;

printf("input filename:\n");
gets(filename);//輸入文件名稱

if((fp=fopen(filename,"r"))==NULL)//打開文件
{
printf("open %s error!\n",filename);
return 1;
}

len=strlen(s);
c=fgetc(fp);
while(!feof(fp))
{
if(c==s[0])//如果第一個字元相等,比較剩下的字元串
{
fpos=ftell(fp);//記住當前文件指針位置
for(i=1;i<len;i++)
{
if(fgetc(fp)!=s[i])//如果不匹配,跳出循環
{
fseek(fp,fpos,0);//重新設置指針位置
break;
}
}
if(i==len)//如果匹配成功,累加數目
n1++;

}
if(c==sc)//與字元sc匹配,累加數目
n2++;
c=fgetc(fp);
}

printf("\n與字元串%s匹配的有%d個\n",s,n1);//輸出匹配個數
printf("與字元%c匹配的有%d個\n",sc,n2);
getchar();
return 0;
}

2. c語言按塊讀取大文本文件，但是最後一段不定長，求代碼，懸賞100，能用給分

fread和fwrite函數參數1和8寫反了，請查閱這兩個函數的定義。

int nCount = fread(mingwen1,1,8,f); //返回nCount實際讀取到的字元個數，每一次能讀滿就是8否則按讀到的數來
fwrite(mingwen1,1,nCount,f); //要寫入實際讀取的長度，而不是統一的8，至於你密文長度是多少就得你自己計算了，因為不知道你加密演算法有沒有增加原來字元串長度。

你用如下代碼覆蓋你源代碼中的類似部分試試：
while(int nCount = fread(mingwen1,1,8,f))
{
//int se = CDes(mingwen1,miwen,mm,0);//暫時屏蔽，要加密請加上這句並把下一句變數改為miwen
fwrite(mingwen1,1,nCount,g);
}

同時在while循環之前，和每一次fwrite之後應該使用
memset(mingwen1,0,8);
memset(miwen,0,8);
將mingwen1和miwen置0，不然最後一次雖然沒有讀取滿，但是會保留前一次的字元在裡面。

3. 尋找java提取大文件中一段字元串的最快的演算法

字元串.substring(start,end);
字元串.replace("\n","");

4. VC 讀寫大文件

先讀一段比如100K，然後在這個100K的內存總查找"begin"，如果查不到，再讀下一個100K，直到找到為止，如果相應的"end"不在這個段中，那麼再繼續讀下面的段，直到找到結束標簽為止。

----------------------------------------------------- 補充1
這個問題不難解決，在讀數據的時候，需要多讀一點，但是下次再讀取的時候，不能僅接著上次的尾部讀取了，而是應該倒退幾個字元，倒退的數目應該是：最大特徵字元長度 - 1。
下面是個簡單的圖解：
------------------|xxx 3 xxx|
---------|xxx 2 xxx|
|xxx 1 xxx|
################################################
一次性的new出一個特別巨大的內存，是一個愚蠢的做法，如果是一個大於4G的文件，那麼你就會更加困難。雖然系統會自動的申請虛擬內存，但是這將極大的影響函數處理的速度，這也是我們國家軟體行業所存在的通病，雖然很多程序也能夠運行，但是效率與速度都相當的落後，我們應該把軟體做的盡可能的快、智能、便捷、清麗。

5. J2ME怎麼讀取大文件TXT

一般是先定位再讀取。
如果是閱讀器，讀取任意文本文件，那建議設定一個字元緩沖區大小，比如n，那麼上來就先讀取這n個字元，夠你全屏顯示的。然後根據用戶輸入，比如翻頁，或者定位到百分比，再計算出位置，以及根據位置計算出跳過的位元組數，然後skip過去。
如果是你的軟體自己保存文件，可以在文件中加上「里程碑」一樣的標記，和樓上說的一樣，這樣可以快速定位到一個小節，再做後續操作。
讀取方法還是無外乎那幾種方式getClass().getResourceAsStream(String str)；或用jsr75

6. 讀取大量數據時數據時內存溢出怎樣分批讀取該怎麼處理

眾所周知，java在處理數據量比較大的時候，載入到內存必然會導致內存溢出，而在一些數據處理中我們不得不去處理海量數據，在做數據處理中，我們常見的手段是分解，壓縮，並行，臨時文件等方法;例如，我們要將資料庫(不論是什麼資料庫)的數據導出到一個文件，一般是Excel或文本格式的CSV;對於Excel來講，對於POI和JXL的介面，你很多時候沒有法去控制內存什麼時候向磁碟寫入，很惡心，而且這些API在內存構造的對象大小將比數據原有的大小要大很多倍數，所以你不得不去拆分Excel，還好，POI開始意識到這個問題，在3.8.4的版本後，開始提供cache的行數，提供了SXSSFWorkbook的介面，可以設置在內存中的行數，不過可惜的是，他當你超過這個行數，每添加一行，它就將相對行數前面的一行寫入磁碟(如你設置2000行的話，當你寫第20001行的時候，他會將第一行寫入磁碟)，其實這個時候他些的臨時文件，以至於不消耗內存，不過這樣你會發現，刷磁碟的頻率會非常高，我們的確不想這樣，因為我們想讓他達到一個范圍一次性將數據刷如磁碟，比如一次刷1M之類的做法，可惜現在還沒有這種API，很痛苦，我自己做過測試，通過寫小的Excel比使用目前提供刷磁碟的API來寫大文件，效率要高一些，而且這樣如果訪問的人稍微多一些磁碟IO可能會扛不住，因為IO資源是非常有限的，所以還是拆文件才是上策;而當我們寫CSV，也就是文本類型的文件，我們很多時候是可以自己控制的，不過你不要用CSV自己提供的API，也是不太可控的，CSV本身就是文本文件，你按照文本格式寫入即可被CSV識別出來;如何寫入呢？下面來說說。。。在處理數據層面，如從資料庫中讀取數據，生成本地文件，寫代碼為了方便，我們未必要1M怎麼來處理，這個交給底層的驅動程序去拆分，對於我們的程序來講我們認為它是連續寫即可;我們比如想將一個1000W數據的資料庫表，導出到文件;此時，你要麼進行分頁，oracle當然用三層包裝即可，mysql用limit，不過分頁每次都會新的查詢，而且隨著翻頁，會越來越慢，其實我們想拿到一個句柄，然後向下游動，編譯一部分數據(如10000行)將寫文件一次(寫文件細節不多說了，這個是最基本的)，需要注意的時候每次buffer的數據，在用outputstream寫入的時候，最好flush一下，將緩沖區清空下;接下來，執行一個沒有where條件的SQL，會不會將內存撐爆？是的，這個問題我們值得去思考下，通過API發現可以對SQL進行一些操作，例如，通過：PreparedStatementstatement=connection.prepareStatement(sql)，這是默認得到的預編譯，還可以通過設置：PreparedStatementstatement=connection.prepareStatement(sql，ResultSet.TYPE_FORWARD_ONLY，ResultSet.CONCUR_READ_ONLY);來設置游標的方式，以至於游標不是將數據直接cache到本地內存，然後通過設置statement.setFetchSize(200);設置游標每次遍歷的大小;OK，這個其實我用過，oracle用了和沒用沒區別，因為oracle的jdbcAPI默認就是不會將數據cache到java的內存中的，而mysql里頭設置根本無效，我上面說了一堆廢話，呵呵，我只是想說，java提供的標准API也未必有效，很多時候要看廠商的實現機制，還有這個設置是很多網上說有效的，但是這純屬抄襲;對於oracle上面說了不用關心，他本身就不是cache到內存，所以java內存不會導致什麼問題，如果是mysql，首先必須使用5以上的版本，然後在連接參數上加上useCursorFetch=true這個參數，至於游標大小可以通過連接參數上加上：defaultFetchSize=1000來設置，例如：jdbc：mysql：//xxx.xxx.xxx.xxx：3306/abc？zeroDateTimeconvertToNull&useCursorFetch=true&defaultFetchSize=1000上次被這個問題糾結了很久(mysql的數據老導致程序內存膨脹，並行2個直接系統就宕了)，還去看了很多源碼才發現奇跡竟然在這里，最後經過mysql文檔的確認，然後進行測試，並行多個，而且數據量都是500W以上的，都不會導致內存膨脹，GC一切正常，這個問題終於完結了。我們再聊聊其他的，數據拆分和合並，當數據文件多的時候我們想合並，當文件太大想要拆分，合並和拆分的過程也會遇到類似的問題，還好，這個在我們可控制的范圍內，如果文件中的數據最終是可以組織的，那麼在拆分和合並的時候，此時就不要按照數據邏輯行數來做了，因為行數最終你需要解釋數據本身來判定，但是只是做拆分是沒有必要的，你需要的是做二進制處理，在這個二進制處理過程，你要注意了，和平時read文件不要使用一樣的方式，平時大多對一個文件讀取只是用一次read操作，如果對於大文件內存肯定直接掛掉了，不用多說，你此時因該每次讀取一個可控范圍的數據，read方法提供了重載的offset和length的范圍，這個在循環過程中自己可以計算出來，寫入大文件和上面一樣，不要讀取到一定程序就要通過寫入流flush到磁碟;其實對於小數據量的處理在現代的NIO技術的中也有用到，例如多個終端同時請求一個大文件下載，例如視頻下載吧，在常規的情況下，如果用java的容器來處理，一般會發生兩種情況：其一為內存溢出，因為每個請求都要載入一個文件大小的內存甚至於，因為java包裝的時候會產生很多其他的內存開銷，如果使用二進制會產生得少一些，而且在經過輸入輸出流的過程中還會經歷幾次內存拷貝，當然如果有你類似nginx之類的中間件，那麼你可以通過send_file模式發送出去，但是如果你要用程序來處理的時候，內存除非你足夠大，但是java內存再大也會有GC的時候，如果你內存真的很大，GC的時候死定了，當然這個地方也可以考慮自己通過直接內存的調用和釋放來實現，不過要求剩餘的物理內存也足夠大才行，那麼足夠大是多大呢？這個不好說，要看文件本身的大小和訪問的頻率;其二為假如內存足夠大，無限制大，那麼此時的限制就是線程，傳統的IO模型是線程是一個請求一個線程，這個線程從主線程從線程池中分配後，就開始工作，經過你的Context包裝、Filter、攔截器、業務代碼各個層次和業務邏輯、訪問資料庫、訪問文件、渲染結果等等，其實整個過程線程都是被掛住的，所以這部分資源非常有限，而且如果是大文件操作是屬於IO密集型的操作，大量的CPU時間是空餘的，方法最直接當然是增加線程數來控制，當然內存足夠大也有足夠的空間來申請線程池，不過一般來講一個進程的線程池一般會受到限制也不建議太多的，而在有限的系統資源下，要提高性能，我們開始有了newIO技術，也就是NIO技術，新版的裡面又有了AIO技術，NIO只能算是非同步IO，但是在中間讀寫過程仍然是阻塞的(也就是在真正的讀寫過程，但是不會去關心中途的響應)，還未做到真正的非同步IO，在監聽connect的時候他是不需要很多線程參與的，有單獨的線程去處理，連接也又傳統的socket變成了selector，對於不需要進行數據處理的是無需分配線程處理的;而AIO通過了一種所謂的回調注冊來完成，當然還需要OS的支持，當會掉的時候會去分配線程，目前還不是很成熟，性能最多和NIO吃平，不過隨著技術發展，AIO必然會超越NIO，目前谷歌V8虛擬機引擎所驅動的node.js就是類似的模式，有關這種技術不是本文的說明重點;將上面兩者結合起來就是要解決大文件，還要並行度，最土的方法是將文件每次請求的大小降低到一定程度，如8K(這個大小是經過測試後網路傳輸較為適宜的大小，本地讀取文件並不需要這么小)，如果再做深入一些，可以做一定程度的cache，將多個請求的一樣的文件，cache在內存或分布式緩存中，你不用將整個文件cache在內存中，將近期使用的cache幾秒左右即可，或你可以採用一些熱點的演算法來配合;類似迅雷下載的斷點傳送中(不過迅雷的網路協議不太一樣)，它在處理下載數據的時候未必是連續的，只要最終能合並即可，在伺服器端可以反過來，誰正好需要這塊的數據，就給它就可以;才用NIO後，可以支持很大的連接和並發，本地通過NIO做socket連接測試，100個終端同時請求一個線程的伺服器，正常的WEB應用是第一個文件沒有發送完成，第二個請求要麼等待，要麼超時，要麼直接拒絕得不到連接，改成NIO後此時100個請求都能連接上伺服器端，服務端只需要1個線程來處理數據就可以，將很多數據傳遞給這些連接請求資源，每次讀取一部分數據傳遞出去，不過可以計算的是，在總體長連接傳輸過程中總體效率並不會提升，只是相對相應和所開銷的內存得到量化控制，這就是技術的魅力，也許不要太多的演算法，不過你得懂他。類似的數據處理還有很多，有些時候還會將就效率問題，比如在HBase的文件拆分和合並過程中，要不影響線上業務是比較難的事情，很多問題值得我們去研究場景，因為不同的場景有不同的方法去解決，但是大同小異，明白思想和方法，明白內存和體系架構，明白你所面臨的是沈陽的場景，只是細節上改變可以帶來驚人的效果。

7. C語言快速讀取超大數組的問題

關鍵不在於你要把它讀進去。
而在於：
1.文件哪來的，有辦法不用那麼大的文件么？建立文件的時候不能建立一個索引么？或者用一個便於訪問的格式么？
2.文件要用來干什麼？CPU一次只能處理幾個位元組，你為什麼要把它全讀到內存里呢？

如果第1條不能解決，也就是最壞的情況，那麼建議：
做一個轉換器，把原始文件轉換成便於操作的文件再進行處理。所謂便於操作，就是說，每一行數據的大小固定，因而可以對數據進行快速訪問。轉一行存一行，不會花太多內在。需要一定的轉換時間，但是因為可以預估，所以界面上可以做一個轉換進度來降低用戶的主觀等待時間。

PS:至於你是把轉換後的數據存到文件進行訪問，還是用映射的方式把文件映射到內存來讀寫，實質上差不多，不過後者可能有系統提供的緩存機制來提高效率。但是本質上一樣的：轉換成臨時文件、使用；或者乾脆就是用專門的程序轉換出新文件，再用處理程序去處理。看場合了。

如果你的文件是存儲在順序存儲器中，比如磁帶上：
那麼差不多意思，想辦法把數據轉存到你的磁碟上，然後再進行隨機訪問。

補充：：：：關於內存映射：見上面的PS內容，先把文件轉成可隨機訪問格式（比如我說要哪一行數據，你就立刻能找到/算出，而不是從頭一行一行去找），然後再做內存映射。
另外，Windows下和Linux下的內存映射有所不同，但是基本上不難，可以直接搜索找到照搬。

8. 文件讀寫操作，排序演算法

1、 堆排序定義 n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ ) 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。 【例】關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。 根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。 注意： ①堆中任一子樹亦是堆。 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。 3、堆排序特點 堆排序(HeapSort)是一樹形選擇排序。 堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系【參見二叉樹的順序存儲結構】，在當前無序區中選擇關鍵字最大(或最小)的記錄。 4、堆排序與直接插入排序的區別 直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重復執行了這些比較操作。 堆排序可通過樹形結構保存部分比較結果，可減少比較次數。 5、堆排序 堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。 （1）用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區 ② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 …… 直到無序區只有一個元素為止。 （2）大根堆排序演算法的基本操作： ① 初始化操作：將R[1..n]構造為初始堆； ② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。 注意： ①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。 ②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。 （3）堆排序的演算法： void HeapSort(SeqIAst R) { //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int i； BuildHeap(R)； //將R[1-n]建成初始堆 for(i=n;i>1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。 R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最後一個記錄交換 Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質 } //endfor } //HeapSort （4） BuildHeap和Heapify函數的實現 因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。 ① Heapify函數思想方法 每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換後，新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其餘任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。 "篩選法"調整堆 R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小於這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換後又可能使結點R[large]違反堆性質，同樣由於該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。 具體的演算法【參見教材】 ②BuildHeap的實現 要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。 顯然只有一個結點的樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ， -1，…，1的結點作為根的子樹都調整為堆即可。 具體演算法【參見教材】。 5、大根堆排序實例 對於關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見【動畫演示】。 6、 演算法分析 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。

9. 超大文件如何計算md5

首先，至少沒必要先把整個文件讀到內存里。比如在 php 里，如果有人 md5(file_get_contents(big_file_name)) 就確實非常不妥當。因為 md5 是每 512 bit 作為一個 chunk 進行計算的。所以可以每次讀取一部分的內容（最少 512 bit，比較合適是 st_blksize），進行那些 chunk 部分的計算，之後再讀取下一部分內容繼續計算。簡單先說下，md5是有規范的，提供了現成的演算法（規范的名字就是md5演算法。RFC 1321 The MD5 Message-Digest Algorithm），我們只需要翻譯成c、java、python、js等等代碼。前端算超大文件可以取頭跟尾chunk內容及整個文件的name + update 時間一起算md5值就比較快了，只是為了做唯一標識來做斷點續傳，從業務邏輯上應該夠用了。推薦使用 js spark-md5 開源庫，支持直接append各個部分然後算出md5。我做的斷點續傳功能就是用它在前端算的md5. 各大網盤 TB級別 md5演算法應該是這樣的，樓上幾位都說了文件md5是文件流分塊算出來的，那麼網盤想獲得TB級別文件的md5就必須讀取整個文件的文件流才能得到，但是這么做效率十分低下，運算時間是個問題。但是大家忽略了一個問題，文件在上傳的過程也是分塊上傳的，這些上傳的碎片其實也是文件流。那麼可以把計算md5的時間分攤到每一個碎片上。這樣每上傳一個片段就計算一點等上傳完成了，文件的md5也就算出來了。okTB級別MD5不是問題了。上傳完成md5自然就出來了。 不知道我的猜測大家有其他看法沒有。剛才提出都傳完了就還怎麼秒傳。秒傳最基本的是先要前端算出md5然後傳給後端（可能需要更多種哈希值）我研究了很久前端沒有辦法秒內完成超大文件MD5的，現在用html5 的api 可以算出任意大小文件的 md5 但是耗時相當長。我沒有解決辦法。也沒有想到那些網盤怎麼在前端快速獲取md5的。

10. 怎麼獲取大文件的MD5

原理 對MD5演算法簡要的敘述可以為：MD5以512位分組來處理輸入的信息，且每一分組又被劃分為16個32位子分組，經過了一系列的處理後，演算法的輸出由四個32位分組組成，將這四個32位分組級聯後將生成一個128位散列值