原帖的地址在stackoverflow.com List of Free Programming books (compiled): How to Design Programs: An Introduction to Computing and Programming 25 Free Computer Science Ebooks Free Tech Books MindView Inc (List of Free Books) Wikibooks: Programming Cheat Sheets (Free) CodePlex List of Free E-Books Book Training – On Video! Sofware Program Managers Network – Free EBooks EBook Share [...]
public class Memoizer implements Computable { private final ConcurrentMap cache = new ConcurrentHashMap(); private final Computable c; public Memoizer(Computable c) { this.c = c; } public V compute(final A arg) throws InterruptedException { while (true) { Future f = cache.get(arg); if (f == null) { Callable eval = new Callable() { public V call() throws [...]
一般来说，我们会使用正规表达式来做字符串匹配，今天在网上浏览的时候，看到了有人用正则表达式来检查一个数字是否为素数（质数），让我非常感兴趣，这个正则表达式如下所示： /^1?$|^(11+?)\1+$/ 要使用这个正规则表达式，你需要把自然数转成多个1的字符串，如：2 要写成 “11”， 3 要写成 “111”, 17 要写成“11111111111111111”，这种工作使用一些脚本语言可以轻松的完成。 一开始我对这个表达式持怀疑态度，但仔细研究了一下这个表达式，发现是非常合理的，下面，让我带你来细细剖析一下是这个表达式的工作原理。 首先，我们看到这个表达式中有“|”，也就是说这个表达式可以分成两个部分：/^1?$/ 和 /^(11+?)\1+$/ * 第一部分：/^1?$/， 这个部分相信不用我多说了，其表示匹配“非空串”以及字串中不只一个“1”的字符串。 * 第二部分：/^(11+?)\1+$/，这个部分是整个表达式的关键部分。其可以分成两个部分，(11+?) 和\1+$，前半部很简单了，匹配以“11”开头的并重复0或n个1的字符串，后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串1次或多次（这句话的意思是——剩余的字串的1的个数要是前面字串1个数的整数倍）。 通过上面的分析，我们知道，第二部分是最重要的，对于第二部分，举几个例子， 示例一：判断自然数8。我们可以知道，8转成我们的格式就是“11111111”，对于(11+?)，其匹配了“11”，于是还剩下“111111”，而\1+$正好匹配了剩下的“111111”，因为，“11”这个模式在“111111”出现了三次，符合模式匹配，返回true。取反（^），所以，得到false，于是这个数不是质数。 示例二：判断自然数11。转成我们需要的格式是“11111111111”（十一个1），对于(11+?)，其匹配了“11”（前两个1），还剩下“111111111”（九个1），而\1+$无法为“11”匹配那“九个 1”，因为“11”这个模式并没有在“九个1”这个串中正好出现N次。于是，我们的正则表达式引擎会尝试下一种方法，先匹配“111”（前三个1），然后把“111”作为模式去匹配剩下的“11111111”（八个1），很明显，那“八个1”并没有匹配“三个1”多次。所以，引擎会继续向下尝试……直至返回false。 通过示例二，我们可以得到这样的等价数算算法，正则表达式会匹配这若干个1中有没有出现“二个1”的整数倍，“三个1”的整数倍，“四个1”的整数倍……，而，这正好是我们需要的算素数的算法。现在大家明白了吧。 下面，我们用perl来使用这个正规则表达式不停地输出素数：（关于perl的语法我就不多说了） perl -e’$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print”$_ “while ++$_’ 另外，让我们来举一反三，根据上述的这种方法，我们甚至可以用正则表达式来求证某方式是否有解，如： * 二元方程：17x + 12y = 51 判断其是否有解的正则表达式是：^(.*)\1{16}(.*)\2{11}$ * 三元方程：11x + 2y + 5z = 115 判断其是否有解的正则表达式是：^(.*)\1{10}(.*)\2{1}(.*)\3{4}$ 大家不妨自己做做练习，为什么上述的两个正则表达式可以判断方程是否有解。如果无法参透其中的奥妙的话，你可以读读这篇英文文章。 转自 cool shell ： http://coolshell.cn/?p=2704
By Jonathan Ellis,系统架构师, Translated by Jametong 空前的数据量正在驱动商业寻找传统关系型数据库的替代方案,它已经为我们服务30多年了(今年5月份ACM刚刚给关系型数据庆祝40岁生日).总体来讲,这些替代方案就是目前知名的“NoSQL数据库.” 关系型数据库的基本问题是无法处理许多现代的工作负载.有三个具体的问题领域:向外扩展(Scale out)类似于Digg(3TB的绿色徽章 数据)或Facebook(50T 的收件箱搜索数据)或Ebay(总共2PB的数据)的数据集,单机性能限制以及僵化的概要设计. 商业上(包含Rackspace Cloud公司)需要寻找新的方式来存储并扩展大规模的数据.我最近写了一 篇关于Cassandra的文章,一个我们投入了资源的非关系型数据库.还有另外一些正在运作中的非关系型数据库,它们汇总在一起被我们称 为”NoSQL运动”. “NoSQL”这个术语实际上是由一个Rackspace 的员工Eric Evans最先提出的,当时来自Last.fm网站的Johan Oskarsson提议组织一次开源分布式数据库的研讨会. 这个名称与概念就一起流行了起来. 有些人反对NoSQL这个说法,因为它听起来像是仅仅表明了我们不做什么,而不是我们在做什么. 事实确实是这样,我也基本同意此说法,但是这个术语仍然有其价值,因为当关系型数据库是你所知道的唯一工具时,每个问题看起来都像个拇指(俗语, 如果你手里有一个锤子,你看到什么都是钉子,译者补充).NoSQL这个术语起码让 人们知道还有其他的选项可供选择.但是,当关系型数据库是解决问题的最佳工具时,我们并不是反关系型数据库者;它的涵义应该是“不仅仅有SQL(Not Only SQL)”而不是“不再有SQL(No SQL at all)”. 有关NoSQL名称的一个真实的忧虑是,它是如此大的一个概念,以致于差异巨大的设计都可以涵盖其中.如果在讨论各种产品时没有搞清楚这一点,就会 导致概念混乱.因此,我建议大家沿着下面三个维度来思考这些数据库选项: 可伸缩性(scalability)、数 据模型与查询模型(data and query model)以及持久化设计(persistence design). 我选择了10种NoSQL数据库作为示例.这不是一份详尽的清单,但是这里讨论的概念对于评估其他的NoSQL数据库也至关重要. 可伸缩性(Scalability) 通过使用复制, 就可以轻易扩展读的规模,因此,每当我在此文中谈到规模伸缩(scaling),都是表示通过自动分区将数据分布到多台机器以扩展写的规模.我们将做这种 事情的系统称为“分布式数据库”.它们包括Cassandra、HBase、Riak、Scalaris、Voldemort以及其他很多类似的系统.如果你的写容量或写数 据大小已经无法在一台机器上进行处理,如果你不想自己手工来管理分区的话,这些就是你的唯一选项了.(你 不会这么做吧?) 人们使用分布式数据库主要关注两件事情: 1) 是否支持多个数据中心以及2) 能否在对应用透明的前提下往正在运行的集群中添加新机器的能力. 非分布式NoSQL数据库包括CouchDB、MongoDB、Neo4j、Redis以及Tokyo Cabinet.它们可作为分布式系统的持久层; MongoDB提供了受限制的数据分片(Sharding)功能,CouchDB也有一个独立的Lounge项目来支持做类似的分片功能,Tokyo Cabinet可用作Voldemort的存储引擎. 数据模型与查询模型 NoSQL数据库之间的数据模型与查询API千差万别. (相关链接: [...]
翻译来自：唐福林 博客雨 http://blog.fulin.org/2010/05/vp8_first_in_depth_tech_analysis.html 注1：文章来自：http://x264dev.multimedia.cx/?p=377 ，一个 H264 开发者对 VP8 的深入分析。 注2：在Google翻译基础上试译，不足之处请多包涵，欢迎各种建议和意见 The first in-depth technical analysis of VP8 首次深入技术分析 Back in my original post about Internet video, I made some initial comments on the hope that VP8 would solve the problems of web video by providing a supposed patent-free video format with significantly better compression than [...]
本文翻译自Facebook员工在LADIS大会上发布的论文.Cassandra – A Decentralized Structured Storage System 这篇论文中,两位作者详细介绍了Cassandra的系统架构,它的设计初衷,设计应用时使用到的相关技术,以及设计/实现/使用过 程中得到的经验教训. Cassandra – 一个分散的非结构化存储系统 By Avinash Lakshman Facebook ,Prashant Malik Facebook; Translated By Jametong 概要 Cassandra是一个分布式的存储系统,可用来管理分布在大量廉价服务器上的巨量结构化数据,并同时提供没有单点故障的高 可用服务.Cassandra的设计目的是运行在由几百个节点(可能分布在多个不同的数据中心)组成的基础设施(infrastructure) 上.当节点达到这个规模时,大大小小的组件出现故障就可能经常发生了.Cassandra在管理持久状态时面临这些故障,这 种情况也驱动软件系统的可靠性(reliability)与可伸缩性(scalability)会依赖于Cassandra的服务. 虽然大部分情况,Cassandra看上去像一个数据库系统, 也与数据库系统共享大量的设计与实现手段,但是Cassandra并 不支持完整的关系数据模型;相反,它提供了一个简单数据模型的客户端,支持对数据布局与数据格式的动态控制.我们设计 Cassandra的初衷是,可以运行在廉价硬件上,并能在不牺牲读效率的情况下实现高的写吞吐量. 1. 导论 Facebook维护着世界上最大的社交网络平台,利用分布在世界各地的大量数据中心的成千上万台服务器,为上亿的用户提供服 务.Facebook平台有严格的业务要求,包含性能、可靠性、效率以及高度的可伸缩性以支持平台的持续增长.在一个包含 成千上万的组件的基础设施上处理故障是我们的标准运作模式;在任何时候,随时都可能出现相当数量的服务器或网络组件故障.这样,软 件系统在构建时就需要将故障当作一种常态而不是异常来处理.为了满足上面描述的这些可靠性与可伸缩性,Facebook开发了 Cassandra系统. 为了实现可伸缩性与可靠性,Cassandra组合了多项众所周知的技术.我们设计Cassandra的最初目的是解决收件箱搜索的 存储需要.在Facebook,这意味着这个系统需要能够处理非常大的写吞吐量,每天几十亿的写请求,随着用户数的规模而 增长.由于我们是通过在地理上分布的数据中心对用户进行服务的,因此支持跨越多个数据中心的数据复制对于降低搜索延时就非常关键了. 当我们在2008年6月发布收件箱搜索项目时,我们有1亿的用户,现在我们差不多有2.5亿的用户,Cassandra一直保持了其 对业务的承诺.目前,Facebook内部已经有多个服务部署了Cassandra作为其后端存储系统. 本文的结构如下.第2节讨论相关研究,其中的部分研究对我们的设计有很大影响.第3节介绍详细的数据模型.第4节简要介绍客户端 API.第5节介绍系统设计以及Cassandra中应用到的分布式算法.第6节介绍我们如何使用Cassandra部署 Facebook平台的一个应用. 2. 相关研究 对于为了性能、可用性与数据持久性对数据进行分布，文件系统与数据库社区已经进行了广泛的研究.与仅支持扁平命名空间 (namespace)的点对点(P2P)存储系统相比,分布式文件系统通常支持层次化(hierarchical)的命名空间.与 Ficus[14]与Coda[16]类似的系统都是通过牺牲一致性来复制文件以实现高可用(high availability).通常使用特别的冲突解决(conflict resolution)程序来管理更新冲突(update conflict). Farsite[2]是一个没有使用任何中心服务器的分布式文件系统. [...]
测试代码：http://code.google.com/p/fulin/source/browse/JAVA/lucene/imobile/search2/src/search/test/IndexTest.java 结论： 1。lucene 索引删除条目的时候（不 调用 optimize），会修改索引目录的以下文件：segments.gen, segments_N, ***.del 2。lucene 索引目录发生改变后，如果不 reopen index reader，则改变对于 searcher 来说是不可见的。（甚至可以将 idx 目录删除，searcher 仍然能返回结果。测试：idx 目录大小为 1.2G，删除目录后， searcher 搜索热门词仍然正常返回结果，返回结果条数超过4万条） 3。索引拆分大小库后，大库可以不用滚动，而是在同一个目录上进行 reopen ，以减少磁盘 IO 及搜索预热延迟
使用 Sockets API，我们可以开发客户机和服务器应用程序，它们可以在本地网络上进行通信，也可以通过 Internet 在全球范围内进行通信。与其他 API 一样，您可以通过一些方法使用 Sockets API，从而提高 Socket 的性能，或者限制 Socket 的性能。本文探索了 4 种使用 Sockets API 来获取应用程序的最大性能并对 GNU/Linux® 环境进行优化从而达到最好结果的方法。 在开发 socket 应用程序时，首要任务通常是确保可靠性并满足一些特定的需求。利用本文中给出的 4 个提示，您就可以从头开始为实现最佳性能来设计并开发 socket 程序。本文内容包括对于 Sockets API 的使用、两个可以提高性能的 socket 选项以及 GNU/Linux 优化。 为了能够开发性能卓越的应用程序，请遵循以下技巧： 最小化报文传输的延时。 最小化系统调用的负载。 为 Bandwidth Delay Product 调节 TCP 窗口。 动态优化 GNU/Linux TCP/IP 栈。 技巧 1. 最小化报文传输的延时 在通过 TCP socket 进行通信时，数据都拆分成了数据块，这样它们就可以封装到给定连接的 [...]
这个列表涵盖了软件工程知识体系中定义的大多数知识域。当然，如果你只想找出类拔萃的程序员，便只需涉及结构、算法、数据结构、测试这几个话题。如果想雇架构师，也可以只考虑需求、功能设计、技术设计这些地方。 不过不管你怎么做，都要牢记一点： 这里大多数问题的答案都没有对错之分！ 你可以把我的这些问题作为引子，展开讨论。例如下面有个问题是使用静态方法或是单例的缘由。如果那个面试的就此展开长篇大论，那他很有可能是个聪明能干的家伙！同样，想知道一个数是不是2的乘方也有很多方法，不过要是面试的人想用mod运算符，嗯……你知道我的意思吧。（你不知道也没关系，来根香蕉？） 需求 你能给出一些非功能性（或者质量）需求的例子么？ 如果客户需要高性能、使用极其方便而又高度安全，你会给他什么建议？ 你能给出一些用来描述需求的不同技术么？它们各自适用于什么场景？ 需求跟踪是什么意思？什么是向前追溯，什么是向后追溯？ 你喜欢用什么工具跟踪需求？ 你怎么看待需求变化？它是好是坏？给出你的理由。 你怎样研究需求，发现需求？有哪些资源可以用到？ 你怎么给需求制定优先级？有哪些技术？ 在需求过程中，用户、客户、开发人员各自的职责是什么？ 你怎么对待不完整或是令人费解的需求？ 功能设计 在功能设计中有哪些隐喻？给出几个成功的例子。 如果有些功能的执行时间很长，怎么能让用户感觉不到太长的等待？ 如果用户必须要在一个很小的区域内，从一个常常的列表中选择多个条目，你会用什么控件？ 有哪些方法可以保证数据项的完整？ 建立系统原型有哪些技术？ 应用程序怎样建立对用户行为的预期？给出一些例子。 如何入手设计一组数量庞大而又复杂的特性，你能举出一些设计思路吗？ 有一个列表，其中有10个元素，每个元素都有20个字段可以编辑，你怎样设计这种情况？如果是1000个元素，每个元素有3个字段呢？ 用不同的颜色对一段文本中的文字标记高亮，这种做法有什么问题？ Web环境和Windows环境各有些什么限制？ 技术设计 什么是低耦合和高聚合？封装原则又是什么意思？ 在Web应用中，你怎样避免几个人编辑同一段数据所造成的冲突？ 你知道设计模式吗？你用过哪些设计模式？在什么场合下用的？ 是否了解什么是无状态的业务层？长事务如何与之相适应？ 在搭建一个架构，或是技术设计时，你用过几种图？ 在N层架构中都有哪些层？它们各自的职责是什么？ 有哪些方法可以确保架构中数据的正确和健壮？ 面向对象设计和面向组件设计有哪些不同之处？ 怎样在数据库中对用户授权、用户配置、权限管理这几项功能建模？ 怎样按照等级制度给动物王国（包括各种物种和各自的行为）建模？ 程序设计 你怎样保证你的代码可以处理各种错误事件？ 解释一下什么是测试驱动开发，举出极限编程中的一些原则。 看别人代码的时候，你最关心什么地方？ 什么时候使用抽象类，什么时候使用接口？ 除了IDE以外，你还喜欢哪些必不可少的工具？ 你怎么保证代码执行速度快，而又不出问题？ 什么时候用多态，什么时候用委派？ 什么时候使用带有静态成员的类，什么时候使用单例？ 你在代码里面怎么提前处理需求的变化？给一些例子。 描述一下实现一段代码的过程，从需求到最终交付。 算法 怎样知道一个数字是不是2的乘方？怎样判断一个数是不是奇数？ 怎样找出链表中间的元素？ 怎样改变10,000个静态HTML页面中所有电话号码的格式？ 举出一个你所用过的递归的例子。 在散列表和排序后的列表中找一个元素，哪个查找速度最快？ 不管是书、杂志还是网络，你从中所学到的最后一点算法知识是什么？ [...]
复杂数据类型与指针 一、复杂类型说明 要了解指针,多多少少会出现一些比较复杂的类型,所以我先介绍一下如何完全理解一个复杂类型,要理解复杂类型其实很简单,一个类型里会出现很多运算符,他们也像普通的表达式一样,有优先级,其优先级和运算优先级一样,所以我总结了一下其原则: 从变量名处起,根据运算符优先级结合,一步一步分析. 下面让我们先从简单的类型开始慢慢分析吧: int p; //这是一个普通的整型变量 int *p; //首先从P 处开始,先与*结合,所以说明P 是一 //个指针,然后再与int 结合,说明指针所指向 //的内容的类型为int 型.所以P 是一个返回整 //型数据的指针 int p[3]; //首先从P 处开始,先与[]结合,说明P 是一个数 //组,然后与int 结合,说明数组里的元素是整 //型的,所以P 是一个由整型数据组成的数组 int *p[3]; //首先从P 处开始,先与[]结合,因为其优先级 //比*高,所以P 是一个数组,然后再与*结合,说明 //数组里的元素是指针类型,然后再与int 结合, //说明指针所指向的内容的类型是整型的,所以 //P 是一个由返回整型数据的指针所组成的数组 int (*p)[3]; //首先从P 处开始,先与*结合,说明P 是一个指针 //然后再与[]结合(与”()”这步可以忽略,只是为 //了改变优先级),说明指针所指向的内容是一个 //数组,然后再与int 结合,说明数组里的元素是 //整型的.所以P 是一个指向由整型数据组成的数 //组的指针 int **p; //首先从P 开始,先与*结合,说是P [...]