C语言逗号运算符的一些问题

2011年10月16日 sigma 6 条评论 8,686 views

前段时间,某童鞋碰到一个和逗号运算符相关的诡异问题,当时我也查了下运算符优先级,仔细想了半天才想明白,当时就想把关于逗号运算符的一些东西写一下,但由于比较忙,一直没写,现在补上。

在这里,为了省事,直接把邮件内容附上(假如那位童鞋你看到了,侵犯了你的版权,别生气哈~),我承认我真的很懒。。。

===============================================

对了能解释下这个问题么?

 void main ()
{
    bool test=false;
    int a = 1;

    test == true ? printf("hello\t"), printf("world\n"),a++ :
    printf("Ha\t"), a++, a++;

    printf("%d", a);
}

Test = false 的时候 a = 3;

Test = true 的时候 a = 4;

阅读全文…

箭扣野长城游记

2011年10月6日 sigma 4 条评论 7,856 views

起了这么个唬人的标题,但事实上,可能名不副实。因为事实上很可能就是几张图片。

在怀柔吃午饭时,餐厅内的涂鸦,有点意思。

阅读全文…

分类: life 标签: , , ,

写在博客一周年,裤子大53周年

2011年9月20日 sigma 14 条评论 6,398 views

今天打开微博,一堆关于裤子大的历史的微博迎面扑来,我才意识到,今天是9月20日,我们裤子大的生日。

很荣幸的,我的这个博客开通日期也是这一天(纯属巧合~~),我的博客也有一周年了!下面列出博客一周年的一些静态参数,以便一年后再来比较:

  1. 我博客总共写了123篇日志(包括从Live Space导入的几篇日志)。
  2. 遵循码农传统,本博客的第一篇日志是《hello world》,地址http://www.sigma.me/?p=1
  3. 一年来,据flagcounter,博客的独立访客数为32648,访客来自86个国家与地区。
  4. 今天博客的RSS订阅量为114,之前出现的峰值为119
  5. 据flagcounter,博客总点击数为63030
  6. 点击最多的文章点击数为5600
  7. 评论最多的文章评论数为67
  8. 友情链接数为19(貌似有点多。。。)。
  9. 博客主题改版次数为x(我也记不清了…不过都是小改动)
  10. 最近一个月,日平均访客为180(据我观察,周末访客量大大减少)。
  11. 博客的PR值为4
  12. 博客Google收录量为722,百度收录量为106

附上一张FlagCounter的截图:

FlagCounter 阅读全文…

Hash和Bloom Filter

2011年9月13日 sigma 11 条评论 37,428 views

这几天的“科研”中涉及到了一个概念,Bloom Filter(有的中文翻译为布隆过滤器,不知道正确否),今天看了下相关的资料,发现这东西和Hash还挺有关系的,在这里一并讲下。

Hash(函数/表)

Hash (中译为哈希,或者散列)函数在计算机领域,尤其是数据快速查找领域,加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面(这些小的数据集叫做哈希值,或者散列值)。Hash table(散列表,也叫哈希表),是根据哈希值(Key value)而直接进行访问的数据结构。也就是说,它通过把哈希值映射到表中一个位置来访问记录,以加快查找的速度。下面是一个典型的hash函数/表示意图:

哈希函数有以下两个特点:

  • 如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。
  • 散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的。但也可能不同,这种情况称为“散列碰撞”(或者“散列冲突”)。上图中,John Smith和Sandra Dee就存在hash冲突。

Hash一个应用就是对数据集分类,比如上图,Hash值为0的表示可能在A集合中,Hash值为2的表示B集合中,依次类推,值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题,对于一个未知的新值,其可能不属于上面任何一个集合,但由于冲突,其Hash值和上面的某一个相同,导致误报(因为事先我们不可能做一个含有无限多项输入的完整的Hash表,也就是原来的Hash函数不可能是完美的)。并且,hash冲突也会导致查找效率低下。

Bloom Filter

Bloom Filter是1970年由Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(Hash函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中,如Orocle的数据库,Google的BitTable也用了此技术。

如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。

这时候就可以利用哈希表这个数据结构(它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点)。这样一来,我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是Bloom Filter的基本思想。

但这时,哈希冲突会是一个问题:假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m/100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们都在说谎,不过直觉上判断这种事情的概率是比较低的。这种多个Hash组成的数据结构就叫Bloom Filter。

一个Bloom Filter是基于一个m位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…hk),这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图:

 

上图中,m=18,k=3;插入x是,三个hash函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入y,z时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找x时,三个hash值对应的位向量都为1,因此判断x在此数据集中。y,z也是如此。但是查找w时,w有个hash值对应的位向量为0,因此可以判断不在此集合中。但是,假如w的最后那个hash值比上图中的大1,这是就会认为w在此集合中,而事实上,w可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,当k比较大时,误报概率还是比较小的,因此这存储还是很空间有效滴。

Bloom Filter有以下几个特点:

  1. 不存在漏报(False Negative),即某个元素在某个集合中,肯定能报出来。
  2. 可能存在误报(False Positive),即某个元素不在某个集合中,可能也被爆出来。
  3. 确定某个元素是否在某个集合中的代价和总的元素数目无关。

优点:

相比于其它的数据结构,Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。Bloom Filter不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点:

另外,一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

参考资料:

  1. http://en.wikipedia.org/wiki/Hash_function
  2. http://en.wikipedia.org/wiki/Bloom_filter
  3. http://antognini.ch/papers/BloomFilters20080620.pdf

开始阅读并修改SESC模拟器代码,开始写关于SESC的日志

2011年9月5日 sigma 2 条评论 8,085 views

这段时间由于“科研”需要,需要改模拟器,经过和师兄们商量,最后基本定了用SESC(SuperESCalar Simulator)。但是,在使用SESC的过程中,发现文档极少(甚至完整的安装文档都没有),唯一比较好的参考来源就是偶尔有一两个更新的SESC邮件列表。

而这些天,我要开始看SESC模拟器代码,并且需要根据实验需求改一些SESC模拟器的结构,趁这个机会,我打算有空的话,把一些阅读的文摘写到这里,也算是对SESC的一些“贡献”吧。

先把官方的SESC介绍简要翻译下吧:

什么是模拟器

在微体系结构领域,经常会有一些新的结构提出,这些结构相比于老的处理器结构,可能(注意,仅仅是可能)性能更高,功耗更小,更可靠,等等。但是,直接将这些结构用硬件实现的代价是昂贵的,因此,出现了微体系结构的模拟器,通过模拟器,不仅能模拟一个微体系结构设计对应的性能,还能模拟面积,功耗等等。

什么是SESC

SESC是最早由UIUC的一些研究单位开发并使用的微体系结构的模拟器。它可以对不同类型的处理器建模,包括单核处理器,片上多核处理器,以及PIM(processors-in-memory)。其可以模拟支持乱序发射,转移猜测的流水线,以及各种其他的现代处理器所有的单元,如cache层次,总线等等。

SESC是一个事件驱动的模拟器,这是一个从MINT衍生而来的,MINT是一个古老的模拟MIPS处理器的项目。处理器核中大部分的功能函数都是每一拍都会执行,不过也有少部分的函数只有需要的时候执行(通过事件驱动)。

阅读全文…

分类: 芯片设计 标签: ,

无觅相关文章插件,快速提升流量