2016-06-09 4 views
1

큰 txt 파일 (100MB의 23 milion lines)이 있습니다.이 파일을 한 줄씩 열어서 linux에서 GNU shuf 명령처럼 섞으려고합니다. 나는 Windows 플랫폼에서 작업하고, 나는 Visual Studio 2015을 설치하고 C++에서 프로그래밍을 시작합니다. 나는 오래된 C++ 코드를 사용하여 처음 시도했지만 너무 느리며 boost 라이브러리로 전환했다. 나는 그것을 인정해야한다, 그것은 정말로 빠르다. 그러나 나는 결과를 배열에 넣고 그것들을 섞는 것을 모른다 (배열은 100.000.000 인덱스까지 유지해야한다).텍스트 파일 읽기 및 셔플

이 내가

#include <boost/iostreams/device/mapped_file.hpp> // for mmap 
#include <algorithm> // for std::find 
#include <iostream> // for std::cout 
#include <cstring> 

#include <fstream> 
#include <sstream> 
#include <string> 

int main() 
{ 
    boost::iostreams::mapped_file mmap("input.txt", boost::iostreams::mapped_file::readonly); 
    auto f = mmap.const_data(); 
    auto l = f + mmap.size(); 

    uintmax_t m_numLines = 0; 
    int inc1 = 0; 

    char ** ip = NULL; 

    boost::array<char, sizeof(int)> send_buf; <-- error here 
    /* 
    Severity Code Description Project File Line Suppression State 
    Error (active)  namespace "boost" has no member "array" hshuffle c:\path_to_the\main.cpp 21 
    Severity Code Description Project File Line Suppression State 
    Error (active)  type name is not allowed hshuffle c:\path_to_the\main.cpp 21 
    Severity Code Description Project File Line Suppression State 
    Error (active)  identifier "send_buf" is undefined hshuffle c:\path_to_the\main.cpp 21 
    Severity Code Description Project File Line Suppression State 
    Error (active)  a value of type "const char *" cannot be assigned to an entity of type "char *" hshuffle c:\path_to_the\main.cpp 29 
    */ 

    while (f && f != l) 
    { 
     if ((f = static_cast<const char*>(memchr(f, '\n', l - f)))) 
     { 
      if ((m_numLines % 1000000) == 0) 
      { 
       ip[m_numLines] = l; 
       std::cout << m_numLines << "\n"; 
      } 


      m_numLines++, f++; 
     } 
    } 

    std::cout << "m_numLines = " << m_numLines << "\n"; 




    printf("endfille\n"); 

    char a; 
    std::cin >> a; 
} 

OLD C++ 프로그램

puts("reading ips file [./i]"); 

if((fp=fopen("i","r")) == NULL) 
{ 
    printf("FATAL: Cant find i\n"); 
    return -1; 
} 

int increment_ips = 0; 
indIP = 0; 
while (fgets(nutt,2024,fp)) 
{ 
    while (t = strchr (nutt,'\n')) 
     *t = ' '; 

    temp = strtok (nutt, " "); 

    if (temp != NULL) { 
     string = strdup (temp); 
     indIP++; 

     while (temp = strtok (NULL, " ")) 
     { 
      indIP++; 
     } 
    } 

    increment_ips++; 
} 
fclose(fp); 




if((fp=fopen("i","r")) == NULL) 
{ 
    printf("FATAL: Cant find i\n"); 
    return -1; 
} 

increment_ips = 0; 
ip = new char*[indIP]; 
indIP = 0; 

while (fgets(nutt,2024,fp)) 
{ 
    while (t = strchr (nutt,'\n')) 
     *t = ' '; 

    temp = strtok (nutt, " "); 

    if (temp != NULL) { 
     string = strdup (temp);  
     ip[indIP++]=string; 

     while (temp = strtok (NULL, " ")) 
     { 
      string = strdup (temp); 

      ip[indIP++]=string; 
     } 
    } 

    increment_ips++; 
} 
fclose(fp); 

// shuffle 
printf("Loaded [%d] ips\n",increment_ips); 

puts("Shuffeling ips"); 
srand(time(NULL)); 
for(int i = 0; i <= increment_ips; i++) 
{ 
    int randnum = rand() % increment_ips + 1; 
    char* tempval; 
    tempval = ip[i]; 

    ip[i] = ip[randnum]; 
    ip[randnum] = tempval; 
} 
puts("Shuffeled"); 

모든 해결 방법을 시도해보십시오 무엇인가? 내가 preffer boost 따라서 정말 빠릅니다.

감사합니다.

+0

당신은 얼마나 알고 싶어 배열에 임의의 정렬을 수행하려면 어떻게해야합니까? (bogo가 아니라 정말 무작위로 만듭니다.) – turoni

+0

큰 텍스트 파일을 임의로 뒤섞어서 배열을 정의하고 거기에 변수를 저장하는 방법을 모르는 경우 배열에 100 만 개 이상의 줄이 있어야합니다. –

+0

나 자신을 한 번도 해본 적이 없지만 나는 네가 최선이라고 생각한다. 그 많은 색인을 보유하는 [메모리 기반의 B + 나무] (http://stackoverflow.com/questions/1720738/looking-for-a-disk-based-b-tree-implementation-in-c-or-c). – turoni

답변

1

"오래된"프로그램은 입력 파일을 두 번 읽습니다. 첫 번째는 공백으로 분리 된 단어 (라인이 아닌 것 같습니다)를 실제로 두 번째로 계산하여 실제로 배열에 데이터를 저장합니다. std::vectorstd::string을 사용하면 정확한 요소 수를 미리 알 필요가 없으며 일부 공간을 예약하고 메모리 관리를 표준 라이브러리에 맡길 수 있습니다.

C++ 11 이후로 OP가 필요한 작업을 수행하는 데 std::shuffle을 사용할 수도 있습니다. 그러나 이러한 대규모 배열 (수백만 개의 요소)에 대해 Fisher-Yates (또는 Knuth) 셔플 알고리즘의 캐시 친화적 인 구현을 상상하는 것은 어렵습니다.

내가 할 수있는 배열로 결과를 넣어하는 방법을 알고 (부스트없이) 그들에게

가능한 솔루션을 셔플하지 않습니다

#include <iostream> 
#include <fstream> 
#include <vector> 
#include <string> 
#include <algorithm> 
#include <random> 

using std::string; 
using std::vector; 
using std::cout; 

int main() { 
    // initialize random number generator 
    std::random_device rd; 
    std::mt19937 g(rd()); 

    // open input file 
    string file_name{"input.txt"}; 
    std::ifstream in_file{file_name}; 
    if (!in_file) { 
     std::cerr << "Error: Failed to open file \"" << file_name << "\"\n"; 
     return -1; 
    } 

    vector<string> words; 
    // if you want to avoid too many reallocations: 
    const int expected = 100000000; 
    words.reserve(expected); 

    string word; 
    while (in_file >> word) { 
     words.push_back(word); 
    } 

    std::cout << "Number of elements read: " << words.size() << '\n'; 
    std::cout << "Beginning shuffle..." << std::endl; 

    std::shuffle(words.begin(),words.end(),g); 

    std::cout << "Shuffle done." << std::endl; 

    // do whatever you need to do with the shuffled vector... 

    return 0; 
}