[原创]“虚拟内存” -- 开辟“无限数组”(页 1) - C语言论坛 - C图形专区 - 编程论坛

jig 发表于 2006-8-6 14:42

[原创]“虚拟内存” -- 开辟“无限数组”

“虚拟内存” -- 开辟“无限数组” 作者：孙靖(Jig) 时间：2006 - 08 - 5 若要转贴或使用本文章介绍的技术，请在你发布的文章或作品中注明出处。
 虚拟内存，我也只在网上的文章里看过，是实在话我一直就不清楚WIN平台下的虚拟内存开辟使用过程是如何的，但一点我是可以肯定的，无非是在硬盘上开辟一个空间来储存数据。换言之就是对文件进行操作。也许有朋友会说，这样的话我自己随便临时建立文件存储数据就可以了啊。我这里所提高的“虚拟内存”其实就开辟文件来储存数据，可为了方便使用，这里按照数组的使用习惯集成了一套方法，这样可以很好的管理自己开辟的数据。 说到这，也许有朋友会不以为然，觉得这不就一小儿科。的确，这样的小伎俩其实就是小儿科。但作为学习的一种手段，我也只是提出自己的看法与大家共同探讨而已。 记得以前给别人写的一个智能五子棋，DOS下是 9X10 的棋盘，内存就耗费的不小。我打算做个 100X100 或更大棋盘，那就只能自己去建立链表来管理内存了。而我就不想费那事，老早就打算使用文件来存储数据。当然这样一来速度必然会受影响，但我觉得值得一试，也算是一种开发性思维的培养吧。
 一. 找寻数据 我们做这个文件操作的“虚拟内存”，最重要的就是要使其使用想数组那样，通过数组标号可以子好到任意一个数据。所以我们要做的就是指定这样的一些函数——只要输入“数组”标号，就可以在文件中找到恰当的位置读取或写入数据。那么，我们就得先温习一下真实的数组是怎么样找寻具体数据的。我们假设一个三维数组 buffer[10][11][12]。我们找到其实数组的元素在内存中是线性排列，那么 buffer[2][3][6] 应该是在第一个位置上呢？仔细计算一下，应该是 (2*11*12 + 3*12 + 6)对吧？所以归纳起来就是 buffer[n1][n2]...[nn] 的第 buffer[x1][x2]...[xn] 个元素的位置应该就是 (x1*n2*n3*...*nn + x2*n3*...*nn + ... + x(n-1)*nn + xn)。之所以要分析这个，是因为我们在文件中存储一个数组的元素一定是线性存储的，所以只有知道确定元素的算法才能准确的在文件中找到相应的位置。
 二. 可变参数 由于我们要建立一套有数组使用风格的函数，其中对数组的创建就必须是有可选参数的。（即可让用户根据需要开辟N维数组，所以参数必须是可选的）其实也很简单，只要把参数传入为 ... ，其使用函数的时候就可以传如任意个参数。但值得注意的是 ... 默认为 int 型的，所以要注意其中的转换。
 三. 函数简介 其实我做的这套函数包，也就只有4个函数而已，下面介绍一下。 1. 创建函数 f_ms creat_ms(unsigned char count, long fist, ...); /* 创建数组 */ count 为数组维数。fist 为第一维数。其后分别是第二，第三 ...... 第N维数。前面说了，由于 ... 是 int 型，取值范围 1 - 32767。也就是说如果开辟多维数组，那么从第二维开始以后的维数最大只能是 32767。此套函数最多能开辟 2147483648 个元素。因为 fist 为 long 型。也许朋友会说你不是无限数组吗？可什么东西都要有个界限啊。就这套函数开辟的一个数组就最大容量就是 2G 啊。够用了吧？此函数返回 f_ms 类型。
 2. 赋值函数 int input_ms(f_ms memory, float input, long fist, ...); /* 写入数据，成功返回1 */ memory 为用户自己开辟的“虚拟内存”结构。input 为写入的数据。大家看到了 input 是 flaot 型的，就是为了能较全面兼容数据类型，这样在的出数据后由用户自行转化就OK啦。其后的就是要输入第几个元素。此函数相当于 buffer[x1][x2]....[xn] = y;
 3. 取值函数 float output_ms(f_ms memory, long fist, ...); /* 取得数据，成功返回1 */ memory 为用户自己开辟的“虚拟内存”结构。其后的就是要输入第几个元素。可以看到与赋值函数向对应的 input，此函数的返回值即为 float 型。此函数相当于 y = buffer[x1][x2]....[xn];
 4. 销毁函数 void destroy_ms(f_ms memory); /* 销毁虚拟内存 */ 很简单，其实就是删除开辟的文件。若不是可以保留，一定要在使用完虚拟内存后，销毁内存，比如磁盘空间会降低。

 四. 函数实现 给出具体代码： /* ------------------------------------- * * 文件名：fms.h * * 功能：以文件形式开辟“虚拟内存” * * 作者：孙靖 * * 时间： 2006-8-4 * * ------------------------------------- */
typedef struct /* 文件内存结构 3/4E-38～3/4E+38，可一次开辟 2147483648 个元素，2G*/ { FILE *fp; /* 文件指针 */ char *file; /* 文件名 */ unsigned char count; /* 记录数组维数，最大可开辟255维数组 */ long fist; /* 记录数组第一维大小 */ } f_ms;
 f_ms creat_ms(unsigned char count, long fist, ...); /* 创建数组 */ int input_ms(f_ms memory, float input, long fist, ...); /* 写入数据，成功返回1 */ float output_ms(f_ms memory, long fist, ...); /* 取得数据，成功返回1 */ void destroy_ms(f_ms memory); /* 销毁虚拟内存 */
 void destroy_ms(f_ms memory) { fclose(memory.fp); remove(memory.file); }

float output_ms(f_ms memory, long fist, ...) { unsigned long sit_by = 1; unsigned long sit_by1 = 1; unsigned long sit_by2[255]; float number[1]; int every_max[255]; int *num; int i, j;
 fseek(memory.fp, 0, SEEK_SET); /* 设置为文件开始位置 */ if (memory.count > 1) { fread(every_max, 4, memory.count - 1, memory.fp); /* 获取各维数大小 */ num = ...; for (i = 0; i < memory.count - 1; i++) { sit_by *= (unsigned long)every_max[i]; } sit_by *= fist;
 sit_by2[0] = 0; for (i = 1; i < memory.count - 1; i++) { sit_by1 = sit_by2[i] = 1; for (j = i + 1; j < memory.count; j++) { sit_by1 *= every_max[j-1]; } sit_by2[i] = (*(num + i - 1)) * sit_by1; }
 for (i = 1; i < memory.count - 1; i++) { sit_by2[0] += sit_by2[i]; } sit_by += (sit_by2[0] + (*(num + memory.count - 2)));
 fseek(memory.fp, (long)(sit_by * 4), SEEK_CUR); /* 将文件指针移至正确位置 */ } else { fseek(memory.fp, (long)(fist * 4), SEEK_CUR); /* 将文件指针移至正确位置 */ }
 fread(number, 4, 1, memory.fp); return number[0]; }
 int input_ms(f_ms memory, float input, long fist, ...) { unsigned long sit_by = 1; unsigned long sit_by1 = 1; unsigned long sit_by2[255]; float number[1]; int every_max[255]; int *num; int i, j;
 number[0] = input; fseek(memory.fp, 0, SEEK_SET); /* 设置为文件开始位置 */ 
 if (memory.count > 1) { fread(every_max, 4, memory.count - 1, memory.fp); /* 获取各维数大小 */ num = ...; for (i = 0; i < memory.count - 1; i++) { sit_by *= (unsigned long)every_max[i]; } sit_by *= fist;
 sit_by2[0] = 0; for (i = 1; i < memory.count - 1; i++) { sit_by1 = sit_by2[i] = 1; for (j = i + 1; j < memory.count; j++) { sit_by1 *= every_max[j-1]; } sit_by2[i] = (*(num + i - 1)) * sit_by1; }
 for (i = 1; i < memory.count - 1; i++) { sit_by2[0] += sit_by2[i]; } sit_by += (sit_by2[0] + (*(num + memory.count - 2)));
 fseek(memory.fp, (long)(sit_by * 4), SEEK_CUR); /* 将文件指针移至正确位置 */ } else { fseek(memory.fp, (long)(fist * 4), SEEK_CUR); /* 将文件指针移至正确位置 */ }
 return fwrite(number, 4, 1, memory.fp); }

f_ms creat_ms(unsigned char count, long fist, ...) { f_ms memory; /* 开辟一个文件内存结构 */
 unsigned long count_by = fist; char *temfname; int *max; int every_max[255]; unsigned long i;
 if (count < 1) /* 数组维数出错判断 */ { printf("维数必须大于0"); return; }
 memory. fist = fist; memory.count = count; max = ...; /* 获取每维的维数 */
 for (i = 0; i < count - 1; i++) { if (*(max + i) < 1) { printf("维数不真确"); return; } every_max[i] = (*(max + i)); count_by *= (*(max + i)); }
 if (count_by > 2147483647) /* 内存益出错处理 */ { printf("内存益出"); return; } memory.file = tmpnam(temfname); /* 产生唯一文件名 */ memory.fp = fopen(memory.file, "wb+"); if (count > 1) { fwrite(every_max, 4, count - 1, memory.fp); } for (i = 0; i < count_by; i++) /* 创建虚拟内存 */ { fwrite(0, 4, 1, memory.fp); }
 return memory; }

 五. 具体实例 下面给个简单的例子对此套函数加以说明： #include <stdio.h> #include "fms.h"
int main(void) { f_ms buffer; /* 开辟虚拟内存 */ int key;
 buffer = creat_ms(3, 100, 110, 120); /* 开辟一个1320000大小的3维数组 */ input_ms(buffer, 24, 2, 9, 58); /* 把 24 写入 [2][9][58] 元素 */ key = output_ms(buffer, 2, 9, 58); /* 将上面存如的数据显示出来 */ printf("%d", key); getch(); destroy_ms(buffer); /* 销毁许内内存 */ 
 return ; }
 大家可以看看效果。其实这样方法最大缺憾就是在数组大了后，速度肯定就受较大影响，不过在很多时候这个方法也不失为一个巧办法。有纰漏处还请大家多多指点。我后面会介绍讨论人工智能——五子棋的算法。到时候一定回用到此种方法。若感兴趣的朋友请关注。 
[align=right][color=#000066][此贴子已经被作者于2006-8-6 14:44:16编辑过][/color][/align]

lianzerong 发表于 2008-4-2 21:01

相见恨晚！！！

页: [1]

编程论坛's Archiver

[原创]“虚拟内存” -- 开辟“无限数组”