Q库generator和co库

Promise模式的q库

promise 是一种让异步代码写起来更舒服的模式。
q库可运行node下,它是一种promise的实现
npm i q 来安装它

下面采用回调方式编写

1
2
3
4
5
6
7
8
9
10
11
12
var fs = require('fs');
fs.readdir('.', function(err, rs){
fs.readFile(rs[0], function(err, f1){
console.log(f1);
fs.readFile(rs[1], function (err, f2) {
console.log(f2);
fs.readFile(rs[2], function (err, f3) {
console.log(f3);
})
})
})
})

采用q库的解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var Q = require('q'),
fs = require('fs');

Q.nfcall(fs.readdri, '.').then(function(ns){
var promises = [];
ns.forEach(function (filename) {
promises.push(Q.ncall(fs.readFile, filename, 'utf-8'));
});
Q.all(promises).then(function(results){
console.log(results);
})
})
.fail(function(err){
console.log(err);
})

通过Q.ncall方法调用异步方法,返回一个promise对象,promise对象具有一个then方法,
可以运行得到结果。
这里var promises = []; 变量用于存储promise数组,把这个参数加入Q.all中,会得到一个promise对象,调用then方法会得到一个数组,这个数组就是所有promise运行的结果。
一切都围绕promise对象,它有一个then方法用于返回回调函数的结果,还有一个fail函数,用于返回异常对象,then 和fail不会被同时调用,就好比一个普通函数,如果抛出异常就不会有返回值一样。

then代表无异常情况下的返回值,fail表示抛出异常,如果过程中有任何异常,promise.then的函数就不会被调用,而是会调用fail,表示抛出异常。


generator

  • 运行generator代码需要node version>4
    1
    2
    3
    function * f(){}
    function *f() {}
    function* f() {}

以上三种方式都对

1
f.constructor; //function GeneratorFunction(){native code}

调用生成器函数就会产生一个生成器对象,生成器对象拥有next()方法,用来迭代

1
2
3
4
function * f() {
console.log('hello');
}
f();

运行代码后,终端没有打印出“hello”, 这是因为调用生成器函数产生一个生成器对象,但是不会执行里面的代码,需要调用next()函数.

1
2
3
4
5
6
function * f() {
console.log('hello');
}
f();
var g = f();
g.next();

g是一个gnerator对象,调用next方法后,将真正进入f的函数体。
根据上面的例子,会发现generator有个断点效果,就是在执行方法体之前, 等待next方法。
通常generator函数和yeild关键词一起使用。yeild可以理解为一个断点

1
2
3
4
5
6
7
function * gf() {
console.log("start");
var str = yield "hello";
console.log("result: ", str);
}
var g = gf();
g.next();

调用一次next,进入函数,打印出start,这时遇到yied所以中断了,我们后面继续一个next方法
打印出

1
2
3
g.next()
==> start
==> result: undefined

这好像和我想的不一样,第一感觉应该 result: hello 而不是result: undefined, 这是因为yield后面跟着的语句确实返回了, 只不过返回的hello值不是给了str变量,而是在第一次调用g.next(),它会返回一个对象({ value: ‘hello’, done: false }), 这个对象里有个value属性, 这个属性的值就是hello

so change the code

1
2
3
4
5
6
7
8
function * gf() {
console.log("start");
var str = yield "hello";
console.log("result: ", str);
}
var g = gf();
var value = g.next().value;
console.log("yield value-> ", value);

第一次调用next后,进入函数体, 遇到yield对象,中断了,就是: 中断并把yield的右侧的值, 写入本次调用next生成的对象中, 这个对象的value值就是右侧的值。
第二次调用next方法后,yield会把next(args)方法的args值赋予左侧变量, 并继续执行语句,下面的代码是我们想要的结果

1
2
3
4
5
6
7
8
function * gf() {
console.log("start");
var str = yield "hello";
console.log("result: ", str);
}
var g = gf();
var value = g.next().value;
g.next(value);

Then we get the result what we want…

1
2
start
result: hello

next 方法返回的对象有两个值{value, done}, value 表示yeild右侧的值也可能是generator的返回值; done如果为false,表示后面还有未执行的yeild语句。


CO库的介绍

co 用于优化异步函数调用方式, 支持promise和thunkify

npm i co thunkify

不采用co的代码:

1
2
3
4
5
6
7
8
9
10
11
12
var fs = require('fs');
fs.readdir('.', function(err, rs){
fs.readFile(rs[0], function(err, f1){
console.log(f1);
fs.readFile(rs[1], function (err, f2) {
console.log(f2);
fs.readFile(rs[2], function (err, f3) {
console.log(f3);
})
})
})
})

查看当前目录下有多少文件, 然后逐个读取, 把读取的数据打印到终端, 可笑的是我必须知道,这个目录下有多少文件。。。。

- 留有问题。。。

co 顺序执行下列代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var co = require('co'),
thunkify = require('thunkify');

function fun(time, callback){
setTimeout(function () {
callback(null, "setTimeout time is - " + time);
}, time);
}

var func = thunkify(fun);

co(function * () {
console.log(yield func(2000));
console.log(yield func(1000));
console.log(yield func(5000));
}).then(function () {
console.log('ok');
}).catch((err) => {
console.log(err);
});

异步与同步

异步与同步

从调用方式上,可以把他们分为3类: 同步调用,回调和异步调用。同步调用是一种阻塞式的调用,调用要等待对方执行完毕才返回,他是一种单向调用;回调是一种双向调用模式,也就是说,被调用方在接口被调用时也会调用对方的接口;异步调用是一种类似消息或事件机制,不过他的调用方向刚好相反, 接口的服务在收到某种讯息或发生某种事件时,会主动通知客户方(就是调用客户方的接口)。

  • 实例
    1
    2
    3
    var fs = require('fs');
    var data = fs.readFileSync('new.txt');
    console.log(data.toString());

readFileSync是同步方法,会阻塞直接得到结果后,才继续执行之后的语句。

1
2
3
4
5
var fs = require('fs');
fs.readFile('new.txt', function callback(err, data){
console.log(data.toString());
});
console.log('first me run');

会发现console.log(‘first me run’)先执行。因为readfile是异步函数,不会阻塞之后的语句。callback是回调函数,等到底层读完数据后, 会调用该函数。
node.js中回调的函数的规范是:

1
2
3
function callback(err, args0, args1...) {

}

下面模拟一个异步函数,和回调函数,加深理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function sumAsyn(a, b, callback) {
setTimeout(
function () {
if(typeof a === 'number' && typeof b === 'number'){
callback(null, a + b);
}else{
callback(new Error('must be number'));
}
}
, 200)
}
sumAsyn(2, 3, function callback(err, rs) {
console.log(rs);
});
console.log('first run!!');

我们定义一个sumAsyn异步函数,运行后先执行console.log(‘first run!!’)。

在node开始所有i/o应该用异步。

异步

所谓”异步”,简单说就是一个任务分成两段,先执行第一段,然后转而执行其他任务,等做好了准备,再回过头执行第二段。

回调函数

JavaScript语言对异步编程的实现,就是回调函数。所谓回调函数,就是把任务的第二段单独写在一个函数里面,等到重新执行这个任务的时候,就直接调用这个函数。它的英语名字callback,直译过来就是”重新调用”。
一个有趣的问题是,为什么Node.js约定,回调函数的第一个参数,必须是错误对象err(如果没有错误,该参数就是null)?原因是执行分成两段,在这两段之间抛出的错误,程序无法捕捉,只能当作参数,传入第二段。

Promise

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// function asyncFun(a, b, cb) {
// setTimeout(function () {
// cb(a + b);
// }, 200);
// }
// //异步的
// asyncFun(1, 2, function (result) {
// if(result > 2){
// asyncFun(result, 2, function (result) {
// if(result > 4){
// asyncFun(result, 2, function (result) {
// console.log('ok');
// });
// }
// });
// }
// });
// console.log(2);
function asyncFun(a, b) {
return new Promise(function (resolve, reject) {
setTimeout(function () {
resolve(a + b);
}, 200);
});
}
asyncFun(1, 2)
.then(function (result) {
if(result > 2){
return asyncFun(result, 2);
}
})
.then(function (result) {
if(result > 4){
console.log('ok');
}
});

可以看到,Promise 的写法只是回调函数的改进,使用then方法以后,异步任务的两段执行看得更清楚了,除此以外,并无新意。

Promise 的最大问题是代码冗余,原来的任务被Promise 包装了一下,不管什么操作,一眼看去都是一堆 then,原来的语义变得很不清楚。

connect.md

connect 中间件 实现一个登录网站


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
var connect = require('connect')
, users = require('./users')


var server = connect(
connect.logger('dev'),
connect.bodyParser(),
connect.cookieParser(),
connect.session({secret: 'my app secret'}),
function(req, res, next){
if('/' == req.url && req.session.logged_in){
res.writeHead(200, {'Content-Type': 'text/html'});
res.end(
'welcome back, <b>' + req.session.name + '</b>'
+ '<a href="/logout">LogOUT</a>');
}else{
next();
}
},
function(req, res, next){
if('/' == req.url && 'GET' == req.method){
res.writeHead(200, {'Content-Type': 'text/html'});
res.end([
'<form action="/login" method="POST">',
'<fieldset>',
'<legend>Please log in</legend>
',
'<p>User: <input type="text" name = "user"></p>
',
'<button>submit</button>

',
'</fieldset>','</form>'
].join(''));
}else{
next();
}
},
function(req, res, next){
if('/login' == req.url && 'POST' == req.method){
res.writeHead(200);
if(!users[req.body.user] || req.body.password != users[req.body.user].password){
res.end('bad user name/password!');
}else{
req.sessoin.logged_in = true;
req.session.name = users[req.body.user].name;
res.end('Authenticated!')

}else{
next();
}
}
},
function(req, res, next){
if('/logout' == req.url){
req.session.logged_in = false;
req.writeHead(200);
res.end('logged out');

}else{
next();
}
}
)

简单的web服务器

一个简单的web服务器

创建模块

输出表单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var http = require('http');
var qs = require('querystring');

http.createServer(function(req, res){

if('/' == req.url){
res.writeHead(200, {'Content-Type': 'text/html'});
res.end([
'<form method = "POST" action="/url">',
'<h1>My form</h1>',
'<fieldset>',
'<label>Personal Information</label>',
'<p>What is your name?</p>',
'<input type="text" name = "name">',
'<p><button>Submit</button></p>',
'</form>'
].join(''));
}else if('/url' == req.url && 'POST' == req.method){
var body = '';
req.on('data', function(chunk){
body += chunk;
});
req.on('end', function(){
res.writeHead(200, {'Content-Type': 'text/html'});
// res.end('<p>Content-Type: ' + req.headers['content-type'] + '</p>'
// +'<p> Data: </p><pre>' + body + '</pre>'
// );
res.end('<p>Your name is <b>' + qs.parse(body).name + '</b></p>');
})
}else{
res.writeHead(404);
res.end('Not Found');
}
// }else if('/url' == req.url){
// res.writeHead(200, {'Content-Type': 'text/html'});
// res.end('You sent a <em>' + req.method + '</em> request!');
}).listen(3000);

一个twitter的web 客户端

  1. 发送一个简单的HTTP请求
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    require('http').request({
    host: '127.0.0.1',
    port: 3000,
    url: '/',
    method: 'GET',
    }, function(res){
    var body = '';
    res.setEncoding('utf8');
    res.on('data', function(chunk){
    body += chunk;
    });
    res.on('end', function(){
    console.log('\n We got: \033[96m' + body + '\033[38m\n');
    });
    }).end();

一个简单的http web服务器

//回到createServer的回调函数,我们需要检查URL是否和服务器的目录下的文件匹配,如果匹配,则读取该文件并展示出来。以后,可能会添加更多的图片,所以要确保灵活以支持这种情况。
// 首先 要检查请求方法是GET并且URL以/images开始,.jpg结束。如果URL 为/的话,则响应index.html(调用后面要实现的serve函数)。否则,发送404 not found。接着,使用fs.stat来检查文件是否存在。者里使用NODE中全局常量__dirname来获取当前服务器所在的路劲。在首个if语句后,添加如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var http = require('http');

var fs = require('fs');

var server = http.createServer(function(req, res){
if('GET' == req.method && '/images' == req.url.substr(0, 7) && '.jpg' == req.url.substr(-4)){
fs.stat(__dirname + req.url, function(err, stat){
if(err || !stat.isFile()){
res.writeHead(404);
res.end('not found');
return;
}
serve(__dirname + req.url, 'application/jpg');
});

}else if('GET' == req.method && '/' == req.url){
serve(__dirname+'/index.html', 'text/html');
}else{
res.writeHead(404);
res.end('not found');
}
function serve(path, type){
res.writeHead(200, {'Content-Type': type});
fs.createReadStream(path).pipe(res);
}
})

server.listen(3000);
console.log('server listening in 3000...');

中间件
通过connect来实现一个简单的网站

  • 托管静态文件
  • 处理错误以及损坏的的URL
  • 处理不同类型的请求

基于http模块api上的connect,提供了一些工具方法能够让这些重复性的处理便于实现。DRY

引入模块
var connect = require(‘connect’);
var server = connect.createServer();
使用use()方法来添加static中间件。下一部分会介绍中间件的概念
中间件其实就是一个简单的javascript函数。本例中,我们这样配置static中间件—通过传递一些参数给connect.static方法,该方法本身会返回一个方法。

处理静态文件

serve.use(connect.static(__dirname + ‘/website’));
将index.html以及images目录放到/website下,确保没有将不想托管的文件放进去

server.listen(3000);

中间件

if(‘GET’ == req.method …){

}else if(‘GET’ == req.method){

}else{
res.writeHead(404);
res.end();
}
如上述代码描述,针对每个请求应用都只会做三件事情中的一件,比如: 若还要记录请求日志,就在顶部加上如下代码:
console.error(‘ %s %s ‘, req.method, req,url);
下面让我来设计一个大型应用,它能够根据每个请求的不同情况下处理以下者集中不同的任务:

  • 记录请求处理的时间
  • 托管静态文件
  • 处理授权

当然,这些任务的处理代码可以放在一个事件处理器中(createServer的回调函数中),这将是一个非常复杂的处理过程。
简单来说,中间件由函数组成,它除了处理req和res对象之外,还接收一个next函数来做流控制。
若用中间件模式来书写上述要求的应用,会是这样子
server.use(function(req, res, next){
//记录日志
console.error(‘ %s %s ‘, req.method, req.url);
next();
});

server.use(function(req, res, next){
if(‘GET’ == req.method && ‘/images’==req.url.substr(0, 7)){
//托管图片
}else{
//交给其他中间件
next();
}
});

server.use(function(req, res, next){
if(‘GET’ == req.method && ‘/‘ == req.url){
//响应index文件
}else{
//交给其他中间件
next();
}
});

server.use(function(req, res, next){
//最后一个中间件,如果到了这里,就意味着无能为力,只能返回404了
res.writeHead(404);
res.end(‘not found’);
});

使用中间件,不仅能够让代码有更强大的表啊能力(将应用拆分为更小的单元)
能够实现很好的重用性。我们马上就会看到,Connect已经为处理常见的任务提供了对应的中间件。例如: 要对请求进行日志记录,就可以简单的通过下面一行代码完成:

app.use(connect.logger(‘dev’));
帮你完成日志记录
下一部分会介绍如何书写一个当请求处理时间长而进行警告的中间件

书写可重用的中间件

一个用于当请求时间过长而进行提醒的中间件在很多场景下都非常有用。比如:
当页面会向数据库发起一系列的请求。在测试过程中,所有响应都在100ms内完成,但是你要确保能够将响应大于100ms的请求记录下来。
为此,我们在一个名为request-time.js的独立模块中创建一个中间件。
这个模块暴露一个函数,此函数本身又返回一个函数。这对于可配置的中间件来说是很常见的写法。在前面的例子中,我们调用connect.logger时传递一个参数,然后他自身会返回一个函数,最终来处理请求。

目前,模块就接收一个超时时间阀值选项,该选项用来界定什么时候将其记录下来。

/**

  • 请求时间中间件
  • 选项
  • -’time’(‘Number’): 超市阀值
  • @param (object) options
  • @api public
    */

module.exports = function(){
//….
};

首先将阀值设为100
var time = opt.time || 100;
随后返回一个中间件函数
return function(req, res, next){
//中间件本身创建一个计时器,并在指定时间的内触发
var timer = setTimeout(function(){
console.log(
‘\033[90m%s %s\033[39m \033[91m mis taking too long’, req.method, req.url
);
}, time);
//这里确保当响应时间在100ms以内时要清除(停下来或者取消)计时器。另外一个中间件中常用的模式叫做重写方法(猴子补丁), 能够在其他中间件调用它时,执行指定的行为。
//在本咧中,当响应结束时,我们需要清除计时器
var end = res.end;
res.end = function(chunk, encoding){
res.end = end;
res.end(chunk, encoding);
clearTimeout(timer);
};
//首先保持对原始函数的引用(var end = res.end) 然后在重写函数中,在恢复原始函数,并调用它,最后清除计时器。
//最后,总是要其他中间能够处理请求,所以得调用next,否则,程序不会做任何事情去。
next();

}

javaScript_Design

原型模式

文字方式

  • 原型模式(prototype)是指原型实例指向创建对象的种类,并且通过拷贝这些
    原型创建新对象。
    Object.create(prototype, OptionnalDes)

拟物化

袋鼠和袋鼠崽子

作用
1.原型对象本身就是有效利用了每个构造创建的对象
注意事项:
1.注意浅拷贝和深拷贝

代码实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
  <!DOCTYPE html>
<html>
<head>
<title>test</title>
</head>
<body>
<script type="text/javascript">
//原型
var myobj = {
str: "mysting",
num: 1,
myarr: [],
myobj: {
innerobj: {
test: 25
}
}
};
function clone(obj){
// var ret = {}, k;
// for(k in obj){
// ret[k] = obj[k];
// }
var ret, k, b;
if((b = (obj instanceof Array))|| obj instanceof Object){
console.log('init');
ret = b?[]: {};
for(k in obj){
if(obje[k] instanceof Array || obj[k] instanceof Object){ret[k] = clone(obj[k]);}else{
ret[k] = obj[k];
}

}
}

return ret;
}
//浅拷贝
var result = clone(myobj);
result.myobj.innerobj[test] = 12;
console.log(result);
</script>

装饰者模式

装饰者用于包装同接口的对象,向方法添加行为,还可以设置为引用。

装饰着用于通过重载方法的形式添加新功能,该模式可以在被装饰者前面或者后面
加上自己行为以达到特定的目的。

装饰家居
给门上加上花边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var home = function (){

}
home.prototype.space = function (){
console.log('我是一个空房子');
},

var zhuangshi = function(home){
this.zfangzi = home;
};

zhuangshi.prototype.space = function(){
this.zfangzi.space();
conosole.log('我添加了一个家居');
}
var _fangzi = new home();
var _zhuangshi = new zhuangshi(_fangzi);
_zhuangshi.space();

组合模式

将对象组合成树形结构以表示“部分-整体 ”

TCP

1
2
3
4
5
var http = require('http');
http.createServer(function(req, res){
res.writeHead(200, {'Content-Type', 'text/html'});
res.end('<h1>Hello, world!!!</h1>');
});

$ telnet 127.0.0.1

GET /HTTP/1.1

  • 成功建立一个tcp连接
  • 创建一个HTTP请求
  • 接收到一个HTTP响应
  • 测试了一些TCP的特性。到达数据和在node中写的一样: 先写Content-Type响应头,然后是响应体
    ,最后所有信息都按序到达。

基于TCP的聊天程序

下面创建一个基本的TCP服务器,并要求输入用户名。同事还回告诉你协议和指令。

  • 成功连接到服务器后,服务器会显欢迎信息,并要求输入用户名。同时,还会告诉你当前还有多少其他客户端
    也连接上该服务器。
  • 输入用户名,按下回车键后,就认为成功连接上。
  • 连接后,就可以输入信息在按下回车键,来项其他客户端进行消息的收发。

为什么输入回车,在node中,通过\n来判断消息是否已将完到达。所以,作为一个分割符使用。

  1. 创建模块
    npm init

  2. 理解NET.SERVER API
    接下来,创建index.js

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    var net = require('net');
    //createServer
    var server = net.createServer(function(conn){
    //handle connection
    console.log('\033[90m new Connections!\033[39m');
    });
    //listen
    server.listen(3000, function(){
    console.log('\033[96m server listening on *:3000\033[39m');
    })

python算法

python 数据结构

一端开口,一端封闭的容器,栈只能对其栈顶的数据进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Stack():

def __init__(st, size):
st.stack = []
st.size = size
st.top = -1

def push(st, content):
if st.Full():
print "Stack is full."
else:
st.stack.append(content)
st.top += 1
def pop(st):
if st.Empty():
return False
else:
st.top -= 1

def Full(st):
if st.top == st.size:
return True
else:
return False

def Empty(st):
if st.top == -1:
print "Stack is Empty!"

队列

两端都通的容器, 一端只能删, 一端只能进
数据流向是单向的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Queue():
def __init__(qu, size):
qu.queue = []
qu.size = size
qu.head = 1
qu.tail = -1

def Empty(qu):
if qu.head == qu.tail:
return True
else:
return False
def Full(qu):
if qu.tail - qu.head + 1 == size:
return True
else:
return False
def enQueue(qu, content):
if qu.Full():
print "Queue is Full!!"
else:
qu.queue.append(content)
qu.tail += 1
def outQueue(qu):
if qu.Empty():
print "queue is empyt..."
else:
qu.head += 1

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node():
def __init__(self, data, next=None):
self.data = data
self.next = next

def LinkList():
def __init__(self, node):
self.head = node
self.head.next = None
self.tail = self.head
def add(self, node):
self.tail.next = node
self.tail = self.tail.next
def view(self):
node = self.head
link_str = ' '
while node is not None:
if node.next is not None:
link_str = link_str + str(node.data) + "-->"
else:
link_str += str(node.data)
node = node.next

print link_str

二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class BtreeNode():
def __init__(self, lft=None, rgh=None, data=0):
self.lft = lft
self.rgh = rgh
self.data = data

class Btree():
def __init__(self, base=None):
self.base = base
def empty(self):
if self.base is None:
return True
else:
return False
def qout(self, node):
if node is None:
return
print node.data
self.qout(node.lft)
self.qout(node.rgh)
def mout(self, node):
if node is None:
return
self.mout(node.lft)
print node.data
self.mout(node.rgh)

def hout(self, node):
if node is None:
return
self.hout(node.lft)
self.hout(node.rgh)
print node.data
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

##bitmap
class Bitmap():
def __init__(self, max):
self.size = int((max + 31 -1) / 31)
self.array = [0 for i in range(self.size)]
def bit_index(self, num):
return num % 31
def set(self, num):
elem_index = num / 31
byte_index = self.bit_index(num)
elem = self.array[elem_index]
self.array[elem_index] = elem | (1 << byte_index)

def test(self, i):
elem_index = i / 31
byte_index = self.bit_index(i)
if self.array[elem_index] & (1 << byte_index):
return True
else:
return False

if __name__ == "__main__":
MAX = ord('z')
suffle = [x for x in 'coledraw']
res = []
bitmap = Bitmap(MAX)
for c in suffle:
bitmap.set(ord(c))
for i in range(MAX + 1):
if bitmap.test(i):
res.append(chr(i))
print '%s' %suffle
print 'ordered %s' %res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#图的视线
chart = {'A':["B", "D"], 'C':['E'], 'D':['C', 'E']}

def path(chart, x, y, pathd=[]):
pathd = pathd + [x]
if x == y:
return pathd
if not chart.has_key(x):
return None
for node in chart[x]:
if node not in pathd:
new_node = path(chart, node, y, pathd)
if new_node:
return new_node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#quicksort

def quicksort(array, i, j):
if i < j:
base = find_sorted_index(array, i, j)
quicksort(array, i, base)
quicksort(array, base+1, j)

def find_sorted_index(array, i, j):

base = array[i]
while i < j:
while i < j and array[j]>=base:
j -= 1
while i < j and array[j] < base:
array[i] = array[j]
i += 1
array[j] = array[i]
array[i] = base
return i
1
#select sorted
1
# mergesort