分类目录: 算法数据结构

基于C语言的hash table实现进程内缓存

最近遇到一个问题需要做本地缓存,首先想到就是hash表。如果是java,太easy了。C语言就是需要不停的造轮子,实在不想写这个面试题样的东西了,求助于万能的Google了。找到一个不错的hashtable开源实现:http://troydhanson.github.io/uthash/,BSD的许可,赞。也找到了一篇文章介绍详细的用法:http://blog.csdn.net/hongqun/article/details/6103275

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 9票) Loading ... Loading ... | 同时归档在:C/C++, 语言基础 | 标签: , , |

广度优先搜索解决“营救公主”问题

在之前的一篇文章(迷宫营救公主算法)中提供了一个半成品的解决方案,之所以说他是半成品,是因为首先选择的算法就不对,采用的是深度优先搜索,其次也没有真正的用对深度优先算法,走过的点应该标记为已经走过,而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。

文章链接:【图论】广度优先搜索和深度优先搜索

就营救公主的问题而言,这里不再重复描述问题了,请点击这里查看题目分析:链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码:

这里每个节点有三种状态:

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 同时归档在:Java | 标签: , , , , , |

Hacker News的排名算法–越是简单的越是有用

从dbanotes.net的startup news知道了hacker news,关注了一段时间,发现排名确实能反映绝大多数用户的喜好,并且也不至于让比较热的文章永远出现在前列,而导致没有新的内容被关注。因此对其算法比较好奇,在网络上搜索了一下,看到实际的算法,有点不敢相信,整个系统只需要依赖这样一个简单的算法,不需要任何人工干预(也许链接是否发布出来需要审核)。hacker news的原理很简单,任何人都可以提交链接到网站首页,然后大家可以阅读其他人提交的链接,当发现该链接对自己有意义或者非常好时可以点击一个类似赞的按钮,给该文章投上一票。最终首页上会按照文章的票数多少和发布时间对文章进行热度排序。

整个算法就是基于下面这个表达式:

r=(P – 1) / (t + 2)^1.8

P是得票数,t是时间,天为单位。因此时间越短得票数越多的文章排名靠前,得票数一定,随着时间的增加,文章的排名也会慢慢降低。

已经有人画出了不同的P值对应的r与t的函数曲线图:

bg2012022405

参考链接:基于用户投票的排名算法(一):Delicious和Hacker News

| 1 分2 分3 分4 分5 分 (5.00- 5票) Loading ... Loading ... | 同时归档在:移动互联 | 标签: , |

一道基础的词法解析题

原日志信息
标题:《计算单词数目的小程序-2009-05-24考试》
发布时间:5/24/2009
作者:童燕群

2009年,公司开始推行技能鉴定考试,这是我第一次参加的技能鉴定考试,那次考试最终以成绩不作为技术等级评定的依据收场。据说有的部门直接以金钱来奖励考分高者,在天涯论坛上面闹得沸沸扬扬。当年做这道题目时用完了所有考试时间,但是仍然没有调通,晚上回家后又接着奋战几个小时,重新写了这份代码。在现在看来,当时那个迫切想写代码的心情真的是难以理解。软件维护工作做多了,好像是会有这样的感觉。

直接贴代码,题目在代码头部的注释中。

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.86- 7票) Loading ... Loading ... | 同时归档在:C/C++, 职业发展 | 标签: , |

迷宫营救公主算法

今天下班前在公司的技术题库中看到这道题目,思路很快就有了,递归遍历每一条可能的路径,然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了,在矩阵较小的时候还好,当矩阵稍微大一点时根本算不过来,感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了,也完全没有意义。公主等到花儿都谢啦。。

貌似这位同学的算法还不错,还没来得及研究,先做个链接:http://blog.csdn.net/joseph_1118/article/details/9390301

应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里,后面再继续研究优化。题目和代码都在一起:

/**
* 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。
* 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只
* 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步。地图由’S’,’P’,’.’,’*’
* 四种符号构成,’.’表示王子可以通过,’*’表示墙,王子不能通过;’S’表示王子的位置;’P’表示公主
* 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:
*/

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 9票) Loading ... Loading ... | 同时归档在:Java | 标签: , |

分布式存储知识学习清单(完善中)

分布式存储是云存储和云计算的基石。没有特别深入的存储基础知识,但是对分布式存储比较感兴趣。希望以不同的开源存储系统的架构特点和细节组成一条学习的主线,以点带面的掌握主流的架构、算法和适用场景。

1、DRBD

1)磁盘IO的截获和处理流程;
2)同步和异步IO复制流程
3)内核态与用户态交互流程
4)文件系统、VFS和块IO之间的关系

2、Ceph

1)对象接口
2)分布式存储的元数据与数据节点分离架构

3、VFS

1)内核知识点
2)本地文件系统

4、关系数据库

1)PostgreSQL、Sqlite,SQL语法,DB文件组织的数据结构

5、算法

1)PAXOS算法:Chubby、BigTable、GFS论文
2)NoSQL、Cassandra、Voldemort,节点间消息通讯模型,多副本一致性保障。
3)CAP定理相关

| 1 分2 分3 分4 分5 分 (4.80- 10票) Loading ... Loading ... | 同时归档在:C/C++, Java, Linux内核 |

大整数乘法

很长时间都没写过代码了,试着写了这个常见的题目。整体思路:采用整形链表记录大整数的每一位,然后分别遍历乘数和被乘数的每一位,将每两个数字的乘积累加到结果的相应位上面。针对大整数类型,重载输入和输出流,重载乘法。

输出部分实现不是特别好。用STL的容器实现链表也许会简单的多。重载乘法的实现不合常理,本应该返回一个新的对象,为了简单起见,直接返回了新对象的指针;在计算乘法结果时使用了一个递归,理论上来说有可能深度过大,导致栈溢出;另外对于指针和应用的使用不规范。

具体代码:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.83- 6票) Loading ... Loading ... | 同时归档在:C/C++ |

试写atoi函数

int atoi(const char* strNum);

思路:首先对输入指针判空,然后取出每一位的权值a,用类似下面的算法:Math.pow(10, i) * a 这样的算法实现。用到了乘方算法,似乎不是特别好。另外用一个类似递归的思想:sum = sum * 10 + digitnum; ,下面就后者给出实现代码。

在接口中用到了const char*,想了半天,到底是指针是const还是指向const char的指针呢,在The C++ Programming Language里面给出过一个助记的方法:把一个声明从右向左读。因此const char*是指后者。
 
atoi函数库文件编写:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.71- 7票) Loading ... Loading ... | 同时归档在:C/C++ |

《求a & x 的取值集合》解答改进版

按照上一篇中提到的思路,最后问题的焦点在于:怎样快速找到tmp中的为1的bit位在x中的实际位置。这样在计算N值的同时将每一位的权值与索引位置的关系用数组对照起来,最后只需要在遍历tmp的值为1的bit位时作相应的加权累加即可。
也综合评论中提到的递归方案,重新补充了各个方案的代码和性能测试代码。

见“方案1”的代码处:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.40- 5票) Loading ... Loading ... | 同时归档在:C/C++, Java, 职业发展 |

给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合

给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合,结果放入ArrayList中。

思路,x先转换为bit数组,得出其中元素值为1的总数为n,则所有取值的总数为2的n次方,记为N。
在0~N的闭区间中,依次取出各个数值,记为tmp,将tmp也转换为bit数组,依次遍历x的每一个bit位,当x的bit位为1时,到tmp中去取出相应的bit位,如果也为1,则将该位为1时,其他所有位为0时所代表的数值累加到结果中。
遍历完所有的bit位后,得到的结果即为所需要的数值。

整个思路有点复杂,性能也不高,从数值本身的与或运算上面着手,肯定还有更简单的方法。

代码:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.75- 4票) Loading ... Loading ... | 同时归档在:Java, 职业发展 |
返回顶部