kenby
- 浏览: 725397 次
- 性别:
- 来自: 北京
-
最新评论
-
wxweven：
Surmounting 写道既然 Java 的跳表那么少，我决 ...
SkipList 跳表 -
暮雪云然：
写的不错，很透彻
Java静态内部类 -
bzhao：
好，赞扬！
Linux信号详解 -
jacktao219：
赞一个~！ ，现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon：
vote--后还要判断是否为0吧，如果为0则废掉重新置位can ...
现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数
文章列表
#!/usr/bin/python
#-*- encoding:utf-8 -*-
import tornado.ioloop
import tornado.web
import shutil
import os
PORT = 8091
class UploadFileHandler(tornado.web.RequestHandler):
def get(self):
self.write('''
<html>
<head><title>Upload File</title>< ...
表结构
按照grp分组，按照num排序，每组取Top 3，输出结果如下：
源代码：
SELECT * FROM score AS t3
WHERE (
SELECT COUNT(*) FROM score AS t1
LEFT JOIN score AS t2
ON t1.grp = t2.grp AND t1.num < t2.num
WHERE t1.id = t3.id
) < 3
ORDER BY t3.grp ASC, num DESC
在where中可以通过子查询创造一个新的变量来过滤。
# Set default encoding using utf8
defutf8 on
## 解决中文乱码,这个要按需配置
defencoding utf8
encoding utf8 utf8
#兼容shell 使得.bashrc .profile /etc/profile等里面的别名等设置生效
shell -$SHELL
#set the startup message
startup_message off
#term linux
## 解决无法滚动
termcapinfo xterm|xterms|xs ti@:te=\E[2J
# 屏 ...
Yaf源码阅读之请求的处理（二）
- 博客分类：
- web
上一篇文章 我们分析了Yaf框架的启动，包括配置文件的初始化以及框架类的加载。本文将分析Yaf
处理一次Web请求的详细过程，这是一个Web框架最核心的部分，理解了这点，就理解了Yaf的实现原理。
（一）框架类的实例化
在上一篇文章提到了Yaf框架类的加载，类加载完成后，还要实例化，
我们逐一分析Yaf各个框架类的构造函数。
不急于分析各种调用关系，我们先看下Application启动后，Yaf的对象关系如图1-1所示。
图1-1 ...
（一）Yaf是什么
Yaf，全称 Yet Another Framework，是一个C语言编写的、基于PHP扩展开发的PHP框架，
相比于一般的PHP框架，它更快，快到被誉为最快的PHP开发框架。
它提供了Bootstrap、路由、分发、视图、插件功能。
Yaf由惠新宸 ...
两种内部类
Java的内部类有两种，一种是静态内部类，另一种是普通内部类，普通内部类可以获得外部对象的引用，
所以在普通内部类能够访问外部对象的成员变量 ，也就能够使用外部类的资源，可以说普通内部类依赖
于外部类，普通内部类与外部类是共生共死的，创建普通内部类的对象之前，必须先创建外部类的对象。
创建普通内部类的代码如下：
Outer o = new Outer();
Outer.Inner inner = o.new Inner();
Outer.Inner inner = new o.Inner(); /* 错误 */
Outer.Inner inner ...
1 Windows安装好Linux虚拟机
2 在Linux下运行一个 Python 实现的http服务器，代码如下：
#!/usr/bin/env python
"""Simple HTTP Server With Upload.
This module builds on BaseHTTPServer by implementing the standard GET
and HEAD requests in a fairly straightforward manner.
"""
_ ...
Paxos算法
- 博客分类：
- algorithms
分布式系统的核心问题是数据一致性，解决一致性有很多算法，而 Paxos 算法
无疑是最著名的，Google 工程师曾说，所有一致性算法都可以归结为 Paxos 算法
的一个特列。可见，很有必要学习 Paxos 算法。
Paxos 算法是由 Lamport 提出来的，他得论文 Paxos made simple 是最好的
学习资料。我在阅读的过程中遇到很多困难，文中的一些逻辑推论隐藏得比较深，
需要反复研读，这里对算法的描述就不写了，只是记录一些个人的理解。
论文首先指出一致性最核心的要求是，Only a single value is chosen，就是说，
协商的结果 ...
编程之美3.1 字符串移位包含的问题
- 博客分类：
- algorithms
题目
给定两个字符串 s1 和 s2, 要求判定 s2 是否能够被通过 s1 作循环移位 ( rotate )
得到的字符串包含. 例如, 给定 s1 = AABCD 和 s2 = CDAA, 返回 true; 给定
s1 = ABCD 和 s2 = ACBD, 返回 false.
解法1
直接模拟, 对 s1 进行循环移位, 在 ...
memcached 采用多线程的工作方式, 主线程接收连接, 然后把连接平摊给
工作线程, 工作线程处理业务逻辑, memcached 使用 libevent 处理网络
事件, 主线程和工作线程都有一个 event base, 这是 libevent 的核心数据
结构, event base 能够监听多个 socket 的网络事件, 概括起来,
memcached 大体框架如 图1 所示.
图1 memcached的多线程模型
主线程的初始化
主线程首先初始化 libevent 的核心数据结构 main base, 然后创建监听
socke ...
使用命令 set(key, value) 向 memcached 插入一条数据, memcached 内部是如何组织数据呢
一 把数据组装成 item
memcached 接受到客户端的数据后, 把数据组装成 item, item 的格式如下:
图1 struct item 的结构
源码中这样定义 struct item ...
volatile 修饰的变量表示改变量的值是易变的，编译器不对其进行优化，
访问该变量的时候不会从寄存器读取， 而是直接从内存读取变量。
在多线程环境下，每个线程都有一个独立的寄存器，用于保存当前执行的指令。
假设我们定义了一个全局变量，每个线程都会访问这个全局变量，这时候线程的
寄存器可能会存储全量变量的当前值用于后续的访问。当某个线程修改了全局变
量的值时，系统会立即更新该线程寄存器中对应的值，其他线程并不知道这个全局
变量已经修改，可能还是从寄存器中获取这个变量的值，这个时候就会存在不一致
的情况。
针对多线程访问共享变量而且变量还会经常变化的情况，利用vol ...
memcopy 和 memmove 的实现
- 博客分类：
- c
一 memcopy 的实现
memcopy 不考虑源内存和目标内存之间的重叠, 逐字节地拷贝, 代码比较简单
void my_memcopy(void *src, void *dst, int size)
{
char *psrc, *pdst;
psrc = (char *)src;
pdst = (char *)dst;
while (size--) {
*pdst++ = *psrc++;
}
}
二 memmove 的实现
memmove 要考虑源内存和目标内存之间的重叠, 概括起来, 有 3 种情况:
(1) sr ...
cookie 实现验证码的原理
- 博客分类：
- web
验证码技术用来解决网络中的恶意注册或者 DDOS 攻击，主要原理是，让用户
输入图片中的文字，如果通过了验证，服务器就在客户端浏览器保存一个验证 cookie，
比如叫做 <secure_session, 9HcxOGJMhn5j7UpmguyA4ABD>
以后用户访问服务器其他页面的时候，服务器先获取这个 cookie， 如果存在，
说明验证通过，
不存在则让用户输入验证码。
事先制作验证码图片
服务器生成 n 张验证码图片，文件名就是验证码对应的字符串。比如 nBxY.jpg
服务器使用一个 map，用来保存 <i ...
SkipList 跳表
- 博客分类：
- algorithms
为什么选择跳表
目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。
想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树
出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，
还要参考网上的代码，相当麻烦。
用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，
它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，
就能轻松实现一个 SkipList。
有序表的搜索
考虑一个有序表：
...