一些有意思的算法代码

2011年12月6日 jadiysontaki 没有评论

 

Keith Schwarz是一个斯坦福大学计算机科学系的讲师。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构,http://www.keithschwarz.com/interesting/, 目前这个网页上有88个(见下面的列表),但这位大哥要干135个,你可以看看他的To-Do List

从这个列表上,我们可以看到,他从去年7月份就在自己实现这些东西了,我把他实现的这些算法转过来,

 

Name Link Date Added Language Description
Binomial Heap (link) 7‑24‑2010 C++ An implementation of a binomial heap data structure for use as a priority queue.
Bounded Priority Queue (link) 7‑24‑2010 C++ An implementation of a priority queue with a fixed upper limit to its size..
Matrix (link) 7‑24‑2010 C++ A collection of classes for manipulating matrices.
VList (link) 8‑16‑2010 Java An implementation of the List abstraction backed by a VList.
Function Wrapper (link) 8‑16‑2010 C++ A C++ wrapper class around unary functions.
String (link) 8‑17‑2010 C++ An implementation of a string abstraction that uses the small string optimization.

 

 

阅读全文…

Share
分类: 算法相关 标签: ,

Linux相关书籍

2011年8月14日 jadiysontaki 2 条评论

 

上有100多本关于Linux的免费书籍,书籍涉及到多Linux编程的领域
包括
  • WEB开发书籍
  • 桌面GUI开发
  • 数据库方面的书籍
  • Linux安全方面
等等,还有其他众多脚本语言的开发书籍。
更多内容请查看:这里
 
另外在这里,向大家推荐20本最好的Linux免费书籍,当然,也是英文版的。
 
1. Ubuntu Pocket Guide and Reference
一本介绍关于Ubuntu 8.04和8.10的使用书。
Website www.ubuntupocketguide.com
Author Keir Thomas
Format PDF
Pages 152

阅读全文…

Share
分类: 开发资源 标签:

如何学好C语言

2011年8月14日 jadiysontaki 1 条评论

 

我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既不深,也不扎实,半吊子。比如:你长期地使用Java和.NET ,这些有虚拟机的语言对于开发便利是便利,但是对于程序员来说可能并不太好,原因有两个:
  1. 虚拟机屏蔽了操作系统的系统调用,以及很多底层机制。
  2. 大量的封装好的类库也屏蔽了很多实现细节。
 
一段时间后,你会发现你知其然,不知所以然。。我以前在CSDN上写过一篇《Java NIO类库Selector机制解析(》,在那篇文章中我说提到过(有讥讽的语气)Java的程序员不懂底层实现,所以很难把技术学得更扎实。此时,一部分程序员会不自然地想学学底层的技术,很自然的,C语言就被提了上来。
 
下面是我给这位朋友的一些建议:
  • 鼓励并为你叫好。我鼓励你想要去学C语言的想法和精神,很多人都觉得C语言好学,其实并不然。(你可以看看《C语言的迷题》)现在的这个社会更多地去关注那些时髦的技术,而忽略了这个流行了40+年的C语言。一门技术如果能够流行40多年,这才是你需要去关注和学习的技术,而不是那些刚出来的技术(过度炒作的技术Windows编程史)。这才是踏踏实实的精神。
  • 不要找借口。这一条路走下来并不容易,不要给自己找借口。我最不喜欢听到的就是“很忙,没有时间”这样的借口。我以前在银行做项目,早9点到晚10点,周一到周六,我一样可以每天抽1个小时来看书和专研,一年下来也能精读5、6本书。 阅读全文…
Share
分类: C/C++ 标签: ,

算法和数据结构词典

2011年8月14日 jadiysontaki 2 条评论

 

我们知道,在编程的世界里,主要就是两个事,用一定的算法去处理一定的数据。算法可以理解为业务逻辑流程,而数据自然一定是按某种结构来存放,这就是数据结构。我们知道,数据结构的修改一定会导致算法的修改,我们也知道,数据结构直接关系到了整个程序的繁简性,高效性。而算法则是关系到数据处理的时间、空间性能,以及日后的扩展和维护。这两个东西是计算机科班出生的人或是需要学习编程的人必需要注意的两件头等大事。
这是一个关于算法,算法技术,数据结构,系统架构等相关问题的一个词典。其中,算法包括了一些常见的算法,比如: Ackermann’s function ,一些算法问题包括了 traveling salesman(销售员出差问题) and Byzantine generals(拜占庭将军问题),还有一些关于这些问题,算法的 实现链表 以及更多的信息。而索引页包括 领域索引 和 类型索引.
希望这个网站对有你用。当然,这个网站是英文的。
Share

一些有意思的文章和资源

2011年8月14日 jadiysontaki 9 条评论

 

又到了向大家介绍一些最近我在网上发现的有价值的东西的时候了。(下面的链接中很多都被墙)
  • 本站的关于排序的文章有很多,对于排序算法来说,其受到要排序的个数和数据的杂乱程度的影响,我们知道比较稳定的排序算法是快速排序和归并排序,归并排序对于大量的数据排序效果是非常好的,尤其是我们可以进行并行的排序。这里有一个并行归并排序的算法的源代码,你可以参考一下 – “Parallel Merge Sort”。
  • 说到“奇技淫巧”和算法,这里有一个文章向你展示了C语言中使用位操作可能完成的各种算法,很有意思。请参看 – “The Aggregate Magic Algorithms
  • 这里有篇文章教你如何取得一个在线的哈佛大学的硕士学位,文章中说了一些相关的事宜,包括一些收费情况,并且展示了一张文凭。这里有一个网页说明了哈佛软件工程学位(Software Engineering)的所需要学习的科目,比如:Java和分布式计算,分布式/企业级计算,设计模式和Java,通讯协议,高级数据网络,Web开发,计算理论,Perl实践,Unix系统编程……我不知道我们的国家各个大学的硕士在学什么,因为我没有读过硕士,但好像现在的计算机研究生只是导师用来挣钱的免费资源,而且,实在不知道研究生在校研究什么。不管怎么样,从这看来,我们的大学好像并没有教给学生计算机的技术。比如在“如何学好C语言”和“如何学好C++语言”中我提到的那些书,那些才是大学里应该学的。我国的教育还真不是一般的落后,不过你不妨试试哈佛的在线学位。 阅读全文…
Share
分类: 开发资源 标签: ,

一些有意思的贴子和工具

2011年8月14日 jadiysontaki 2 条评论

 

又到了介绍各种杂项的时候了,正如以前的这三篇(这篇这篇,和这篇)文章一样,本篇文章也给你介绍一些最近出现的一些有趣的东西。希望你能喜欢。

先说找工作吧,电影《该页无法显示》里的那个facebook主页上的招聘网页上是列了一堆问题,你可以去看看,你可以使用c/c++,Erlang,Haskell,Java,Perl,Python,PHP,Ruby来解题,不过只接受Unix/Linux下的版本, 不接受Windows的版本。无独有偶,DropBox招聘网页上也是些算法题,大家可以过去看看,不过需要翻墙。(现在,对于美国互联网企业来说,如果你没有被C2C,说明你根本不存在,如果你没有被墙,说明你还不算成功)
 
接下来给大家介绍一些文档和教程吧,都是英文的。
  • Java和C#的完整比较。这是一个相当完整的比较Java和C#语言的网页。很有意思,有助于你了解Java和C#的各种特性和不同。
  • SQL 性能调优。这个文档覆盖了IBM DB2MySQLOracle,PostgreSQL 和 Microsoft SQL Server。不过这个电子书还没有写完,你可以使用其RSStwitter 或 Facebook 来跟踪其进度。
  • Clever Algorithms。这个电子书也是免费的。其主要面向一些AI和面向自然的算法,一共45个。其包括概率随机算法,迭代进化算法,物理算法,可能性算法,蚂蚁蜜蜂式算法,免疫算法,神经算法等。里面大量的高等数学公式对我来说我已经看不懂了。不过,我相信这个电子书非常适合搞理论研究的人,或是需要抄袭一篇论文以顺利毕业的人使用。
  • HTML5 Audio & Video 处理。这是一组在线的幻灯片,请使用键盘光标键翻页。这是一组带着各种演示的幻灯片,对于你要学习HTML5的声音和视频相关的知识很有帮助。
  • C 语言的宏。你想知道C语的宏有哪些有些意思的用法吗?这篇文档不会让你失望的。其由浅入深地向你介绍了宏的各种用法。 阅读全文…
Share
分类: 开发资源 标签: ,

一些重要的算法

2011年8月14日 jadiysontaki 2 条评论

 

下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部份摘自Wikipedia,因为维基百科描述的很专业了)。
 
  1. A*搜寻算法
    俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。
  2. Beam Search
    束搜索(beam search) 方法是解决优化问题的一种启发式方法,它是在分枝定界方法基础上发展起来的,它使用启发式方法估计k 个最好的路径,仅从这k 个路径出发向下搜索,即每一层只有满意的结点会被保留,其它的结点则被永久抛弃,从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70 年代中期首先被应用于人工智能领域,1976 年Lowerre 在其称为HARPY的语音识别系统中第一次使用了束搜索方法,他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解。
  3. 二分取中查找算法
    一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。 阅读全文…
Share
分类: 算法相关 标签:

五个编程语言设计的失误

2011年8月14日 jadiysontaki 1 条评论

 

在近几年来,编程语言的设计正在经历着类似于“文艺复兴”的过程,这么说主要是基于下面两个事实:1)多核技术推动着PC消费者更多的关注并行程序。2)动态语言的性能越来越好,其性期已经可以足够用来实现互联网服务,并且它们正在走出“脚本语言”阴影。
这篇文章试图收集最重要的编程语言的设计错误,以便让那些程序语言设计者们在设计新型的编程语言时避免。我避免了一些纠缠不清的有好有坏的问题,如:动态类型或是静态类型。我也省略了那些看起来并不严重,很容易被修改的错误。例如,加入“参量”(Parametric Type),这在Java中已经有了。Sun在发布Java 1.0版后的第八年才加入了这一功能。还有一个最近的例子是 Google Go Language Design FAQ 中说到的:: “Generics may well be added at some point. We don’t feel an urgency for them, although we understand some programmers do.”
 
0. Null 指针
几乎在所有的主流编程语言中,对一个对像的引用可能会是一个空指针,这个错误会引发运行时错误。 C.A.R. Hoare 最近声明向这一“发明”负责,尽管如此,其它许多的设计者们都应该对这样的设计受到批评。下面是 C.A.R Hoare 的“忏悔”:
I call it my billion-dollar mistake. It was the invention of the null reference in 1965. [...] More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965. - C.A.R. Hoare
我把它叫做“亿万美元错误”。这个空指针的发明创造来自1965年。…… 现在的编程语言引入了“非空引用”的声明规格。这个方案被我在1965年给拒绝了。 阅读全文…
Share
分类: 程序员 标签:

提高编程技能最有效的方法

2011年8月14日 jadiysontaki 1 条评论

 

StackExchange.com上有两个贴子(贴子一贴子二),贴子名叫“What is the single most effective thing you did to improve your programming skills?” – 对你的编程技术提高最有效的一件事是什么?回复的人中给了很多很不错的建议,我把他们总结了一下,十条,相信一定会对你有用。(注意:顺序是我自己按我的个人经验排的)
  • 和比自己聪明的能力比自己强的人工作。学习他们的代码,他们的做事方法,看一看那些人是怎么处理错误的。
  • 总是倾听别人怎么说,无论那个的资历和职位是什么样的。
  • 实践,实践,实践,总是不满意于一开始出来的事。
  • 多问问自己,现在在写什么代码?为什么要这样写成这样?还有没有更好的方法?
  • 学习多样的技术,多多比较他们,并一定要了解各种技术的优缺点。
  • 总是问别人问好的问题。
  • 多回头看看走过的路,做过的事,写过的程序,感觉一下他们有多烂。
  • 多读读那些大师写的书。
  • 不要总坐在电脑前编程序,多做做运动,多到户外走走,和非技术人多接触,向他们学习。
  • 把你的想法说出去,看看别人怎么回应的。从别人的回应中学习。
除了这些,下面是我个人想给你的建议—— 阅读全文…
Share
分类: 程序员 标签: ,

Facebook 的系统架构

2011年8月14日 jadiysontaki 2 条评论

 

来源http://www.quora.com/What-is-Facebooks-architecture (由Micha?l Figuière回答)

根据我现有的阅读和谈话,我所理解的今天Facebook的架构如下:
  • Web 前端是由 PHP 写的。Facebook 的 HipHop [1] 会把PHP转成 C++ 并用 g++编译,这样就可以为模板和Web逻贺业务层提供高的性能。
  • 业务逻辑以Service的形式存在,其使用Thrift [2]。这些Service根据需求的不同由PHP,C++或Java实现(也可以用到了其它的一些语言……)
  • 用Java写的Services没有用到任何一个企业级的应用服务器,但用到了Facebook自己的定制的应用服务器。看上去好像是重新发明轮子,但是这些Services只被暴露给Thrift使用(绝大所数是这样),Tomcat太重量级了,即使是Jetty也可能太过了点,其附加值对Facebook所需要的没有意义。
  • 持久化由MySQL, Memcached [3], Facebook 的 Cassandra [4], Hadoop 的 HBase [5] 完成。Memcached 使用了MySQL的内存Cache。Facebook 工程师承认他们的Cassandra 使用正在减少,因为他们更喜欢HBase,因为它的更简单的一致性模型,以到其MapReduce能力。
  • 离线处理使用Hadoop 和 Hive。
Share
分类: 架构相关 标签: