Thursday, April 28, 2005

C++ STL 参考书

今天给很多人发信请教推荐一本STL的教程,结果很快就得到了大家的回应.
这里我觉得有两本书比较不错,一本是1《The C++ Standard Library》, 另一本是
2《Effective STL》,这两本都有中文版。很适合我们阅读。
2的下载链接:http://stl.winterxy.com/download/Eff_STL_CN.pdf
1是我的同学直接用email发送给我的,所以没有下载链接。

真要好好感谢我的这些热心的同学和弟兄们!

在C++中用list容器实现LRU cache

Cache从本质上是个数组,但是LRU cache则似乎不太相同,它有一种内在的顺序,
也就是被淘汰的顺序.

考虑LRU cache的如下操作:

1.添加 Add item
向LRU Cache中添加永远只需要向队列尾部添加

2.删除 Delete item
对应尾部添加,则删除应该发生在队列头部.

3.查找 Search item
查找应该做两件事,一是真正的查找,返回一个True or False.
但是如果命中,则还应该把命中的item移动到尾部,使它不容易被删除.

4.替换-Replace item
Replace可以被看成是两个操作的合并:Replace = Add + Delete,
其中add发生在尾部,delete发生在头部。

5.是否还应该加上有效位,valid bit,以及对应的修改该位的功能?
set_invalid(),set_valid(),is_valid()

可能会需要的参数,
1. Cache size (number of items, Cache 容量)
2. Cache item Data Type (每个item是一个文件,一个block,还是...?)
3. 好像没有了吧?^_^

一下是我的LRU Cache实现的主要代码片断:
class LRU_Cache
{
public:
void _add(int id);
void _del(int id);
bool _find(int id);
bool search(int id);
private:
list lru;
}

void LRU_Cache::_add(int id)
{
lru.push_back(id);
}
void LRU_Cache::_del(int id)
{
lru.remove(id);
}
bool LRU_Cache::_find(int id)
{
list::iterator it;
for (it=lru.begin(); it!=lru.end(); it++)
if ((*it)==id)
return true;
return false;
}

KB MB GB TB PB EB ZB YB

KB Kilobyte 1,024 Bytes
MB Megabyte 1,048,576 Bytes
Gb Gigabit 1 billion bits
GB Gigabyte 1,073,741,824 Bytes | One billion Bytes
TB Terrabyte 1024 GB, 1,048,576 MB, 8,388,608 KB, 1,099,511,627,776 Bytes and 8,796,093,022,208 bits.
PB Pettabyte 1024 TB, 1,048,576 GB, 1,073,741,824 MB, 1,099,511,627,776 KB, 1,125,899,906,842,624 Bytes and 9,007,199,254,740,992 bits.
EB Exabyte 1024 PB, 1,048,576 TB, 1,073,741,824 GB, 1,099,511,627,776 MB, 1,125,899,906,842,624 KB, 1,152,921,504,606,846,976 Bytes and 9,223,372,036,854,775,808 bits.
ZB Zettabyte 1024 EB, 1,048,576 PB, 1,073,741,824 TB, 1,099,511,627,776 GB, 1,125,899,906,842,624 MB, 1,152,921,504,606,846,976 KB, 1,180,591,620,717,411,303,424 Bytes and 9,444,732,965,739,290,427,392 bits
YB Yottabyte 1024 ZB, 1,048,576 EB, 1,073,741,824 PB, 1,099,511,627,776 TB, 1,125,899,906,842,624 GB, 1,152,921,504,606,846,976 MB, 1,180,591,620,717,411,303,424 KB 1,208,925,819,614,629,174,706,176 Bytes and 9,671,406,556,917,033,397,649,408 bits

Wednesday, April 27, 2005

找paper的好地方

看看这个网站,这里有众多的文章库,包括:
google,google scholar,siteceer, sciurs, IEEE Xplore,
ACM Digital Library, SlugLink, O'Reilly Network Safari Bookshelf
Research Resources on the Web and at UCSC

安装Cygwin的步骤

这个站点告诉你如何在你的笔记本windowsXP上一步一步地安装cygwin
我没有试过,但是应该会有帮助Installing Cygwin

Linux支持的最大文件

刚才读了一个帖子,了解了linux下面支持的文件的最大size:http://www.suse.de/~aj/linux_lfs.html

从这里我们看到,在32位的系统上,一般而言,最大文件size是2GB,除非使用了Large File Support (LFS)支持。而64位的系统则自动最大支持2^63 Bytes的大文件。

使用LFS支持需要对内核以及C libary做大量的修改。

64位的系统也可以使用LFS支持,但是并没有任何实际意义,因为在这些系统上,LFS的API仅仅是老的API的一个别名。

下面是一个简单的列表,也是从这个网站上拷贝过来的,该网站上还有更多更详细的说明:http://www.suse.de/~aj/linux_lfs.html

FilesystemFile Size LimitFilesystem Size Limit
ext2/ext3 with 1 KiB blocksize16448 MiB (~ 16 GiB)2048 GiB (= 2 TiB)
ext2/3 with 2 KiB blocksize256 GiB8192 GiB (= 8 TiB)
ext2/3 with 4 KiB blocksize2048 GiB (= 2 TiB)16384 GiB (= 16 TiB)
ext2/3 with 8 KiB blocksize (Systems with 8 KiB pages like Alpha only)65568 GiB (~ 64 TiB)32768 GiB (= 32 TiB)
ReiserFS 3.52 GiB16384 GiB (= 16 TiB)
ReiserFS 3.6 (as in Linux 2.4)1 EiB16384 GiB (= 16 TiB)
XFS8 EiB8 EiB
JFS with 512 Bytes blocksize8 EiB512 TiB
JFS with 4KiB blocksize8 EiB4 PiB
NFSv2 (client side)2 GiB8 EiB
NFSv3 (client side)8 EiB8 EiB