woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

大文件内数据排序问题:采用文件映射内存技术

 

http://archive.cnblogs.com/a/1773844/

 

对文件内数据排序时,如果文件较小,可以将文件内数据全部读入内存时,通过内排序方法如冒泡,快速排序等方法,可以很方便的实现。

但如果文件大小超过了内存大小,仅仅使用内排序就不能达到目标了。

解决这个问题,有一个方法是大名鼎鼎的外排序:将大文件分成若干个小文件,对小文件进行内排序,然后将各个有序小文件组合成大的有序文件。外排序方法需要反复的读写文件,时间复杂度较高。

下面的代码使用的是win32API提供的文件映射内存方法,能减少文件读写次数,提高效率。

/**

说明:程序首先生成由随机整数组成的文件,然后利用文件映射内存访问数据,将数据进行升序排序后输出的另一个文件。

*/

#include <iostream>

#include <ctime>

#include <vector>

#include <algorithm>

#include <Windows.h>

#include <string>

using namespace std;

 

#define ORIGIN_FILE_NAME  "data"  //数据文件名

#define NUMBER_COUNT 1024         //随机生成的整数数量

 

int GenerateOriginDataFile();//生成数据文件:由n个随机整数组成

int SortFile();//文件排序

 

int main()

{

        GenerateOriginDataFile();

        DWORD dwStart = GetTickCount();

        SortFile();

        DWORD dwEnd = GetTickCount();

        cout << "running time spend:" << dwEnd - dwStart << endl;

        return 0;

}

int SortFile()

{

        // 创建文件对象

        HANDLE hFile = CreateFile(ORIGIN_FILE_NAME, GENERIC_READ | GENERIC_WRITE,

               0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);

        if (hFile == INVALID_HANDLE_VALUE)

        {

               printf("创建文件对象失败,错误代码:%drn", GetLastError());

               return -1;

        }

        // 创建文件映射对象

        HANDLE hFileMap = CreateFileMapping(hFile, NULL, PAGE_READWRITE, 0, 0, NULL);

        if (hFileMap == NULL)

        {

               printf("创建文件映射对象失败,错误代码:%drn", GetLastError());

               return -1;

        }

        // 得到系统分配粒度

        SYSTEM_INFO SysInfo;

        GetSystemInfo(&SysInfo);

        DWORD dwGran = SysInfo.dwAllocationGranularity;

        // 得到文件尺寸

        DWORD dwFileSizeHigh;

        __int64 qwFileSize = GetFileSize(hFile, &dwFileSizeHigh);

        qwFileSize |= (((__int64)dwFileSizeHigh) << 32);

        // 关闭文件对象

        CloseHandle(hFile);

        // 偏移地址

        __int64 qwFileOffset = 0;

        // 块大小

        DWORD dwBlockBytes = 1000 * dwGran;

        if (qwFileSize < 1000 * dwGran)

               dwBlockBytes = (DWORD)qwFileSize;

        while (qwFileSize > 0)

        {

               // 映射视图

               LPBYTE lpbMapAddress = (LPBYTE)MapViewOfFile(hFileMap,FILE_MAP_ALL_ACCESS,

                       (DWORD)(qwFileOffset >> 32), (DWORD)(qwFileOffset & 0xFFFFFFFF),

                       dwBlockBytes);

               if (lpbMapAddress == NULL)

               {

                       printf("映射文件映射失败,错误代码:%drn", GetLastError());

                       return -1;

               }

               const int NUMBER_MAX_LENGTH = 6;

               // 对映射的视图进行访问

               char temp[NUMBER_MAX_LENGTH + 1] = {0};

               int number = 0;

               //直接操作内存lpbMapAddress,进行冒泡排序

               for(DWORD i = 0; i < dwBlockBytes; i+=NUMBER_MAX_LENGTH)

               {

                       for (int j=0;j<NUMBER_MAX_LENGTH;j++)

                       {

                               temp[j] = *(lpbMapAddress + i + j);

                       }

                       number = atoi(temp);

                       for (int j=i+NUMBER_MAX_LENGTH;j<dwBlockBytes;j+=NUMBER_MAX_LENGTH)

                       {

                               for (int k=0;k<NUMBER_MAX_LENGTH;k++)

                               {

                                      temp[k] = *(lpbMapAddress + j + k);

                               }

                               if (number > atoi(temp))

                               {

                                      for (int k=0;k<NUMBER_MAX_LENGTH;k++)

                                      {

                                              *(lpbMapAddress + j + k) = *(lpbMapAddress + i + k);

                                              *(lpbMapAddress + i + k) = temp[k];

                                      }

                                      number = atoi(temp);

                               }

                       }

               }

               // 撤消文件映像

               UnmapViewOfFile(lpbMapAddress);

               // 修正参数

               qwFileOffset += dwBlockBytes;

               qwFileSize -= dwBlockBytes;

        }

        // 关闭文件映射对象句柄

        CloseHandle(hFileMap);

        return 0;

}

int GenerateOriginDataFile()

{

        FILE* pFile = fopen(ORIGIN_FILE_NAME,"w");   

        srand((unsigned)time(0));

        for (int i=0;i<NUMBER_COUNT;i++)

        {

               long ran_num = rand();

               fprintf(pFile,"%-5d ",ran_num);                                     

        }

        fclose(pFile);

        return 0;

}

 

posted on 2011-02-16 18:01 肥仔 阅读(3024) 评论(5)  编辑 收藏 引用 所属分类: Windows开发

评论

# re: 大文件内数据排序问题:采用文件映射内存技术  回复  更多评论   

大哥 你的代码对我太有用了,我在考虑 spoolsv.exe的后台代码 这正是我需要的 延迟打印的程序 呵呵呵
2013-03-15 01:59 | 井廉超

# re: 大文件内数据排序问题:采用文件映射内存技术  回复  更多评论   

我正在寻找这样的代码,最后我找到了你的网站之内。谢谢你这段代码传授给我们,并继续发布一个有用和有益的内容。所有最优秀的。

# re: 大文件内数据排序问题:采用文件映射内存技术  回复  更多评论   

こんにちは!この記事では、はるかに良い書き込むことができませんでした!このポストを見てみると、私の以前のルームメイトのことを思い出す!彼は継続的にこのことについて話し続けた。私は最も確かに彼にこの記事をお送りします。かなり確信して彼は偉大な読み取りがあるでしょう。共有のための多くの感謝!

# re: 大文件内数据排序问题:采用文件映射内存技术  回复  更多评论   

は!この記事では、はるかに良い書き込むことができませんると、私の以前のルームメイトのことをでした!
2016-05-06 20:55 | Essays-shark.net

# re: 大文件内数据排序问题:采用文件映射内存技术  回复  更多评论   

あなたの教授が望んでいた紙を提供することができるので、あなたが期限と提出の期日を心配する必要はありません
2016-05-26 15:12 | best-custom-essays.com

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理