这个存储问题有没有什么技巧么

kkmm0105

一个node节点有2个字段，
int id,
int count,

其中，到了一定阶段时，count就可以存储别的内容，新内容类型为float。由于我机器上float和int都是4字节，我想直接把新的信息填到count字段，以节省存储空间。
有什么好的方法和建议吗

hbmhalley

union?
ps:算上空格的字数限制真是蛋疼

kkmm0105

hbmhalley 发表于 2012-05-12 18:20
union?
ps:算上空格的字数限制真是蛋疼

明白了，谢谢，我用结构体内嵌套union定义实现了

wolf5729

只是通过共用int, float来节省存储空间，可以考虑用union；但很可能需要新增一个字段来表示当前节点存的是int还是float。之所以说很可能，是因为目前不知道数据的特点，有的可以做到不用新增字段，有的必须新增。

如果还想进一步节省存储空间，一定得分析数据特点，甚至抠到每个节点里的每个字节做什么？
打个比方，如果int的值只有离散的十个，那么这里定义一个4字节的int没有必须，可转为定义4个bit，2^4 = 16，存得下十个离散值了。

------------------------------------
欢迎光临我的博客：www.danoking.com [DNK的博客]

OwnWaterloo

回复 3# kkmm0105

嗯，union可行，但还需要一个标志表示存储的是int还是float。
也许你的case有更专门的方法存储这个标志，那样更好。

下面的是与具体case无关的常用方法。

1. 最朴素的方式 —— 一个单独的域

1. 
   
2. struct node {
   
3.       int id;
   
4.       int type;
   
5.       union {
   
6.             int i;
   
7.             float f;
   
8.       } count;
   
9. };
   

复制代码

用一个成员，表示union中存储的实际类型。但这样其实没能节省空间。
在 union { int i; long long ll; float f; double d; } 的情况下可以节省空间。


2. 嵌入到id

1. 
   
2. struct node {
   
3.       int id_type;
   
4.       union {
   
5.             int i;
   
6.             float f;
   
7.       } count;
   
8. };
   

复制代码

从id中借一个bit用作type。 自然id能保存的范围就会缩小了。


下面两种方法就超出C语言定义了，但许多脚本语言实现都使用了这些技巧。
不过不一定符合你的需要，因为它们没将信息存储在node自身当作，于是没法in-place的改变（稍后会继续解释）。


3. 嵌入到指向node的指针
每一个node的对象都需要对齐， 通常来说指针的低位是0。
于是可以将type存储在node* p的低位中。

不能in-place修改是指type信息是存储在所有指向这个节点的那些被tagged的指针当中的。
对比第1、2种方案，如果需要将某个节点的count从int改为float，可以修改id域或者id_type域，然后再是count域。所有指向这个节点的指针不需要改变。
而3（还包括下面要说的4）这方案就不行。如果想让某个节点的count从int改为float，需要修改所有指向这个节点的指针，这是很难做的。


4. 嵌入到"场所"
不同类型的节点从不同的分配场所中获取。通过"节点->节点所在场所"的查询获得类型信息 —— 不过这步要做高效很麻烦。
很多gc算法因为要自己实现分配，就"顺带"将这个功能做了。而单独这么使用就很繁琐了。
同样，如果想让count从int变为float，需要从另一个场所分配，并且替换所有原本指向该节点的指针域。