Crossin的编程教室

标题: 小世界效应：从凯文·贝肯到六度分隔理论（2） [打印本页]

作者: 性感上帝 时间: 2013-12-5 12:14
标题: 小世界效应：从凯文·贝肯到六度分隔理论（2）

/*接上一篇文章*/

数据存储方式：

现在我们知道actorFile与movieFile这两个字段都将占用大量的内存空间，它们均提取至相互关联的数据集合，它们的数据形式将在下面作详细说明。首先声明的是imdb的构造函数内部已经为我们初始化了这两个指针，所以我们只需要关注具体的实现。

为了简明起见，我们假设好莱坞发行了三部电影，并且这三部电影还是由三个固定的演员随机组合主演的。下面是假设情况：

Clerks 在 1993 年主演了 Cher 和Liberace

Monnstruck 在 1988 年主演了 Cher、Liberace 和 Madonna

Zoolander 在 1999 年主演了 Liberace 和 Madonna

当然，大家不要太过纠结于这里的一些逻辑错误，我们仅仅是为了展示做了些很没节操的假设而已。

如上所示，你可以发挥一下想象力，我已经实现好的构造函数会将actorFile于movieFile初始化成如下的样子：

但是问题也是显而易见，这样的格式会造成很低的利用率。无论是演员信息还是电影信息，它们的数据大小都是不可预估的。有些电影的名字远远长于其他电影，有些电影光参演的演员就有75人，而有些电影则只有少量演员。演员之间也是千差万别，有些是名副其实的多产户，有些仅仅有几部作品。看来仅仅通过定义一个结构体或类是解决不了数据内存分配的问题的，这样做很明显会造成大量的内存空间浪费。

但，如果我们采用了可变大小的内存分配方式，二分搜索法可能就不能在这里施展魔力了。试想一下，演员总数超过了300000，电影总数超过了124000，在这种情况下使用线性搜索是非常低效的。但假如所有的演员和电影都按照名字排好序，并且同名的电影可以按照年份排序，那么二分搜索仍然能够被采用。所以在这样一种意念的驱动下，我将数据的格式变成了下面这样：

可以看到，在记录数目与记录数据中间是一个记录偏移量的数组。图中它们被画成了指针，实际上并非如此。设计之初的愿景是能为记录的数据灵活的分配内存大小---这也直接衍生出了现在这样的解决方案：我们希望actorFile和movieFile所指向的数据能够更易于操作，它们具体存在什么地方，我们是不关心的。通过存储偏移量，我们可以分别手动的计算出Cher、Madonna和Clerk的记录位置，方法就是在actorFile和movieFile的实际存储位置上加上它们各自的偏移量。为了更形象的展示出来，请看下方的图：

按照如图所示的表示方法，我们可以很容易的得出：

Cher有16字节的数据并且偏移量为16

Liberace有24字节的数据并且偏移量为32

Moonstruck有28字节的数据并且偏移量为36

这里的数据大小可以根据之后数组单项的的偏移量与当前数组单项的偏移量之差得出。

由于偏移量是由四字节的整型数据构成的，加之数据本身的索引也被排好序，因此二分搜索法在这儿依然适用。

总结：

actorFile指向了一大块装载着所有演员信息的内存块，最开始的四个字节存储的是演员的总数，接下来的四字节存储的是第0号演员的数据偏移量，紧接着是第1个，第2个，第3个，以此类推。最后一个存储偏移量值的四字节之后跟着的是第0号演员的信息记录实际数据，紧接着是第1个、第2个等等。目前看来，尽管演员的名字长度不同，存储的大小也不同，但它们被按照名字做了排序。

movieFile也指向了一大块内存，它存储的是所有电影的信息。最开始的四个字节存储的是电影的总数，接下来的格式与actorFile类似。这些电影会按照名字进行排序，当然相同名字的电影会按照年份排序。

上面描述了拥有300000演员信息以及100000电影信息的文件存储方式，这样的做法同样适用于其他不同大小的数据。

//由于发帖字数限制，请继续看下一篇文章

//我的联系方式

＝＝＝只做最真实的自己＝＝＝

微信公共号IT百问

关注方式：

1、打开微信搜索微信号ID：itbaiwen

2、或者扫描下方的二维码

4.png (31.98 KB, 下载次数: 414)

欢迎光临 Crossin的编程教室 (https://bbs.crossincode.com/)