存档

文章标签 ‘哈希’

兄弟单词 — 两种算法实现

2013年2月28日 2 条评论

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

阅读全文...

从《The C Programming Language》中学到的那些编程风格和设计思想

2012年3月20日 2 条评论

---

读书不是目的,关键在于思考。

很早就在水木上看到有人推荐《The C Programming Language》这本书,一直都没看,开学一个月就专心拜读了一下,并认真做了课后习题。读来收获不少,主要有两点:一是加深了自己对一些基础知识的理解和感悟;二是从中学到了一些不错的编程风格和设计思想,这些东西虽看起来不起眼但细细嚼来还是很值得学习的。下面就从四个方面做一个小总结,水平有限,加之刚读第一遍,难免有疏漏和错误,非常欢迎批评补充。

===读书感悟===

===设计思想===

===编程风格===

===经典例程===

读书感悟

首先,不得不说这不愧为大师之作(网上将其誉为C圣经),一本薄的不能再薄的书,200多页,却涵盖了C语言的大部分精粹;值得一提的是,该书仅仅定价30元,这在计算机类书籍中可以说是很便宜了,与市面上充斥的各种C语言教程在性价比上形成了很大的对比。不过不得不承认,个人感觉这不是一本入门书,读起来是需要一定基础的。

其次,说一下该书的撰写风格和读书建议。书中不是成篇幅地罗列一个个语法和知识点,而是以例程驱动,大部分知识点都是以一个小程序来说明,所以建议读的过程中也将例程当做习题来做,然后与作者给出的程序进行对比,会发现自己的思维是多么的不缜密,考虑问题是多么的欠缺,等你慢慢“上道”了,写出一个和作者类似甚至觉得比他给出的答案要好的时候,兴趣和成就感便会促使你良性循环。

也许有人会说,书中的例子很简单,但我想说尽管很简单,但每个例子都是经典之作,而且能有效地治理眼高手低,在编写代码的过程中,太多的细节让人醍醐灌顶,可谓处处珠玑,书中一些精巧的程序段不禁会让人感觉:啊哈,原来是这样,原来还可以这样写。这样读来能明白之前好多不知所以然的地方。

最后,说一下这一本不到300页的书都包含了什么内容。书中从经典的hello world开始,可以说是手把手编写并讲述了C语言的大部分语法,不仅如此,更实现了二分查找快排希尔排序(这个的实现比我们数据结构中学习的要巧妙不少)、链表二叉树哈希这些重要的数据结构和算法。书中的大部分例程不仅能让你了解C,不仅能教你如何编写有效率且易读的代码,更能让你了解一些底层的设计思想,例如getchar,strcpy,fopen,printf等众多库函数的实现思想都有体现,帮助你探索源码,追根溯源。另外书中还包含了一些系统调用接口,编译原理(一个递归下降的语法分析,这部分没看懂,还要再读啊)的实现等。

阅读全文...

二进制思考(三):位排序、位索引(bit-map)简单举例

2012年3月1日 3 条评论

---

本节目的是利用上一节的知识加深理解《编程珠玑》中的一道位排序题目,位排序的思想比较简单,具体代码见参考文献吧,这里就不罗列了。

本文主要是写一下《The C Programming Language》第二章中一道非常简单的小题目,文中使用了三种方法,可以对比一下。

题目:编写函数squeeze(s1,s2),将字符串s1中任何与字符串s2中字符匹配的字符都删除。

分析:这道题目的注意点主要有两个,一是搜索匹配的字符,二是删除字符时后续字符的前移。这两方面都是有技巧在里面的,见代码

方法一:暴力搜索

#include<stdio.h>

void squeeze(char *s1, char *s2);
int ishave(char *s2, char c); // 判重

void main()
{
	char s1[] = "abcdefghigklmn";
	char s2[] = "helloworld";
	squeeze(s1,s2);
	printf("%s\n",s1);
}

void squeeze(char *s1, char *s2)
{
	int i = 0, j = 0;
	for(; s1[i] != '\0'; ++i)
	{
		if(!ishave(s2,s1[i]))
		{
			s1[j++] = s1[i];
		}
	}
	s1[j] = '\0';
}

int ishave(char *s2, char c)
{
	int i = 0;
	while(s2[i] != '\0')
	{
		if(s2[i] == c)
			return 1;
		++i;
	}
	return 0;
}

阅读全文...

Bloom Filter(一),引子:从哈希到布隆过滤器

2011年11月13日 5 条评论

---

布隆过滤器(Bloom Filter)系列博文总览

信息指纹那篇博文我们提到,使用哈希时,利用信息指纹将字符串转为128位整数既可以降低内存需耗,又可以节省查找时间;但是如果要处理的信息量特别大时,哈希表存储效率低的问题就显现出来了,此时就需要考虑其他数据结构了:Bloom Filter。

本篇文章要解决的问题:什么是布隆过滤器?为什么要使用布隆过滤器?

我们经常会遇到要判断一个元素是否在一个集合中这样的问题,例如以下情景:

  • 字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中)
  • 网络爬虫里,一个网址是否被访问过等等

最直接的方法就是将集合放入内存,使用哈希的方法,好处是快速、准确;缺点是费空间。请注意,这件事情是在内存中完成的,所以空间问题必须作为考虑因素。当要哈希的集合比较小时,这个问题不显著,但是当集合巨大时,对于有限的内存来说,哈希表存储效率低的问题就显现出来了,这里借数学之美中的案例说明一下bloom Filter的思想及使用它的必要性:

Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址,全世界少说也有几十亿个发垃圾邮件的地址。如果用哈希表,每存储一亿个 email 地址, 就需 1.6GB 的内存(十亿字节为1G。用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存,一般服务器是无法存储的。

一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

布隆过滤器实际上是一个很长的二进制向量一系列随机映射函数

按我的理解:说白了,bloom filter就是将集合元素进行位编码存储

阅读全文...

信息指纹 [数学之美学习笔记]

2011年10月27日 没有评论

---

Hash与信息指纹有什么关系?为什么要用信息指纹?

最近在整理布隆过滤器相关资料的时候,觉得有必要提一下信息指纹和MD5.

不得不承认,自己以前使用hash的方法弱爆了,借《数学之美》的文章记录一下从哈希到信息指纹的缘由。

回忆一下以前使用hash的时候:

情景一:


Java: HashTable<string,int> ht = new HashTable<string,int> ();

C++: map<string,int> m;

其实平时这样用也无所谓,但是数据量大了,string就不好办了。

情景二:

以前自己写过一个爬虫,当时存储URL的时候直接就是以字符串的形式存储的,测试时有的url非常长,当时虽然感觉挺费空间的,但还是偷懒了,逃避困难逃避改变导致了今天的幼稚,所以直面问题,加紧充电,爬虫的重写也在最近的计划中,MD5,布隆过滤器应该都能用到。

入正题,hash为什么要用信息指纹?请看下面的例子

任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的“指纹”。

在爬虫中网址的消重上,需要在哈希表中纪录已经访问过的网址(URL)。假设现在要存储在哈希表中如果以字符串的形式直接存储网址,既费内存空间,又浪费查找时间。

阅读全文...