算法 -- IT技术博客大学习 -- 共学习共进步！

• 最近几个容易错的地方总结(hash_map迭代删除,localtime(),线程状态)

一.有关hash_map的使用 map中可以用 map.erase(it++)或者it = map.erase(it);来实现迭代删除但是在hash_map中 iterator erase(iterator it); 这个函数声明和定义是不存在的取而代之的是 void erase(iterator it); 但它本...

• 一致性hash算法

memcach中一个具体实现算法：初始化：已有server m个和各自权重，构建 40*server个数*4个bucket，每个bucket实际上就是一个long值，按照权重分配给各个server，所有的bucket会分布在2的32次方的空间中，用一个TreeMap来存储。

• C/C++循环获取文件中的每行数据（别以为很简单！）

想必大家在学C/C++编程的一开始就会学习如何在文件中循环获取没一行的数据，但是我得以切身经历来告诉大家，有时候，课本真的不一定是对的……

• 从140秒到2秒的优化

从2亿个0~2,000,000,000之间的数字样本中找出不重复的记录总数，首先想到的是bloom filter，转念一想既然全都是数字，bloom filter有点太重，bitarray也许更有效，于是第一个版本出来，部分代码如下： ba = bitarray(212**4) cnt = 0 for i in data: if (not ba[i]): cnt += 1 ba[i] = True print cnt 大概需要140s左右，觉得if (not ba[i]):这个比较费，改了第二版： for...

• 倒置字符串中的单词

输入：一个字符串，单词用某个特定符号分割（比如空格）输出：一个字符串，单词顺序和原串相反看到倒置，一般的做法是用栈，要么自己建个数组、要么STL，或者递归用程序栈。

• 快速排序详细分析

看了编程珠玑Programming Perls第11章关于快速排序的讨论，发现自己长年用库函数，已经忘了快排怎么写。于是整理下思路和资料，把至今所了解的快排的方方面面记录与此。纲要算法描述时间复杂度分析具体实现细节划分选取枢纽元固定位置随机选取三数取中分割单向扫描双向扫描 Hoare的双向扫描改进的双向扫描双向扫描的其他问题分治尾递归参考文...

• 求任意自然数内的素数

用6N±1法求素数任何一个自然数，总可以表示成为如下的形式之一： 6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…) 显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。根据上述分析，我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速...

• 算法复杂度求法初学

有空演习了一点点。递归方程算法复杂性求法之：迭代法注：T()函数等于php中的floor()函数

• 从一道题目谈计算机和数学

统计从1至400亿之间的自然数中含有多少个1？比如1-11中，有1，10，11这三个自然数有4个1。拿到这道题目，您会如何去计算呢？如果是计算机方面的面试，你又该如何去思考呢？也有同事拿这道题目谈到了“数学”与“数感”的理解，不过笔者却想谈一些更实际一些东西。如果是计算机方面的出现这道题目，我们可能首先想到的是挨个去找。比如1含有一个1,然后2不含有1，…10含有1个1, 11含有2个1，….直到4亿。实际...

• c/c++访问超过2G的文件

每次用的时候就找不见，记录到这里~

• 实时排名，其实很简单

前两天写用skip list实现实时排名，搞得挺复杂，显得挺有学问的。嘿嘿，其实没必要搞那么复杂，对于博客这种积分取值范围很小（在较长一段时期内可能都只在0-10000之间）的，只需要用一个数组记录每个分值有多少人就够了，计算排名的时候只要对这个数组做下遍历，代价小很多了。初步的实现呢，只需要用以下的一张数据库表可能就行了。CREATE TABLE BlogScoreSummary ( Score INT, -- 分值 Count INT, -- 积分为这一分值的人数 IDX ...

• 用skip list实现实时排名?

博客有积分了，根据积分要排名了，有人希望这个排名是实时的吗？可能会有的吧，这样就可以发一篇文章，马上看下我的排名上升了多少位，由于用博客的人多，可能会发现写一篇文章，就有几万个人被抛在身后，或者原来排名是Top 3.27%，写篇文章后就变成Top 3.16%了，这等感觉多爽啊，我想至少对晓文哥这种试图通过狂发test日志赶上名博的人是有吸引力的吧。问题是，怎么实现实时排名呢，对于有超过一亿用户，每天登录也有好几百万的博...

• Paxos在大型系统中常见的应用场景

在分布式算法领域，有个非常重要的算法叫Paxos, 它的重要性有多高呢，Google的Chubby [1]中提到 all working protocols for asynchronous consensus we have so far encountered have Paxos at their core. 关于Paxos算法的详述在维基百科中有更多介绍，中文版介绍的是choose value的规则[2]，英文版介绍的是Paxos 3 phase commit的流程[3]，中文版不是从英文版翻译而是独立写的，所以非常具有互补性。Paxos算法是由Leslie Lamport...

• 一次简单C程序的性能优化

下午居然想到要来优化这段程序, 并且写出了更好的程序, 性能提升了30%, 从18秒提升到了12秒.

• 关于音乐搜索

音乐搜索属于垂直搜索的一种，但它又有着自己独特的一些需求。首先，几乎所有的音乐搜索都实现了用户输入时的关键词提示功能。但在网上搜索相关的技术文章，大多是讲如何用 Js 实现前台表现层的功能，少有的几篇关于后台技术实现的文章，也都太过简单。标准的办法是使用 Trie 树，但太过晦涩，不够直观。我们打算直接使用 Lucene 的前缀查询来实现，并且计划在项目上线后写一个比较详细的说明。其次，很多的音乐搜索都提供了拼音...

• 关于 getter 和 setter

网友 "sjinny" 在上篇评论里写：云风对那种所有成员数据都写setter/getter的做法有什么看法吗……这两天试图精简三个太庞大的类，但是单单setter/getter就让接口数目变得非常多了……我谈谈我的看法吧。首先，几乎任何设计问题都没有标准答案。如果有，就不需要人来做这件事了。无论多复杂的事情，只要你能定义出精确的解决方案，总可以用机器帮你实现。下面谈谈我的大体设计原则。记住、一切皆有例外，但这里少谈例外。因为这涉及...

• 闲谈STL容器之size()成员函数

             我们一般人写程序，不可避免要使用别人开发的库来搭积木。其实也讲究这个“知己知彼”：
         知己----对自己程序要实现的业务逻辑分析清楚，时间上、空间上的复杂度等；
         知彼----对我们所使用的库也要有一定的了解，了解的越清楚越好；当然我们可能不会去完全了解各个库，这要看个人的修养方向了。

• PHP中的Hash算法

Hash Table是PHP的核心,这话一点都不过分. PHP的数组,关联数组,对象属性,函数表,符号表,等等都是用HashTable来做为容器的. PHP的HashTable采用的拉链法来解决冲突, 这个自不用多说, 我今天主要关注的就是PHP的Hash算法, 和这个算法本身透露出来的一些思想.

• IT人员的必经之路(图解)

IT人员的必经之路(图解)

• 在js中做数字字符串补0

算法永远都是如此，要不是时间换空间，要不就是空间换时间。