Python

Python [[Web Crawler]] scrapy 框架初使用及爬取 LOL 信息 零、真前言 这篇文章是由 2018 年 4 月 16 日首次发布于 csdn，后来由于 “逃离csdn” 的想法中，将之前发布的文章重新排版，发表在个站中。 一、前言 了解到爬虫技术大概有 18 个月了，这期间自己写过几个爬虫，也 fork 过几个流行的爬虫 repo，包括 bilibili-user、iquery、WechatSogou 等，但一直没系统的写过爬虫，上一次心血来潮（17 年 10 月），想要爬下关于英雄联盟的数据，主要想获得皮肤原画数据。 当时决定的目标网站是英雄联盟中文官网，数据准确且更新快。LOL 数据库，但苦于该网页全篇使用 js 载入数据，无法直接读取，就退而求其次，改变目标网址多玩-英雄联盟-英雄数据库。 技术使用混杂，主要利用 requests+bs4 完成爬取，部分内容使用 scrapy 抓取，逻辑结构混乱，代码可见 spider-on-lol/v1.0/，功能基本实现，但不够美。七天之前，看到了这些代码，决定用 scrapy 重新实现功能，完成整个逻辑设计，这中间遇到了很多问题，从中得到了学习，完整代码可见 spider-on-lol。 二、爬虫设计全思路 目标网站：LOL 数据库 爬取内容： 英雄姓名 英雄头像 物品名称、id 物品图片 英雄皮肤原画 英雄背景故事 技术：scrapy，splash，docker 难点 图片获取 js 页面数据的获取 中文编码 三、环境搭建 工欲善其事，必先利其器。 1、 开发语言：python v3.6.5 2、开发语言环境：anaconda v1.6.9 （非必须，但隔离环境是一个好习惯） 3、docker 安装 deepin 下安装 docker 其他系统安装 docker 4、splash 安装方法 5、一些第三方库： scrapy：conda install Scrapy scrapy_splash: conda install scrapy_splash 四、什么是 Scrapy？什么是 Splash？ 1、Scrapy Scrapy 是一个为了爬取网站数据，提取结构性数据而编写的应用框架。 可以应用在包括数据挖掘，信息处理或存储历史数据等一系列的程序中。 ...

Python Web Crawler Scrapy with bilibili 一、前言 在一个月前，我写了一篇scrapy 框架初使用及爬取 LOL 信息记录了爬取 lol.qq.com 获取英雄联盟数据及英雄皮肤原画的过程。第一次使用 scrapy 后，了解了大致的爬取流程，但在细节上（例如防 ban 策略，奇怪数据处理）没太在意，处于编码第一阶段（能跑就行）。 中间学了半个月的 Qt5 和 pygame，（没学出个什么样子，了解了大致概念，翻指南能上手了），之后，看到 github 中早期 fork 了一个库，airingursb 写的bilibili-user，深有所悟，在此先感谢他的源码及他的开源精神。 但最近一段时间，BiliBili 的网站结构有了些许的变化，我就尝试着用 scrapy 重写这个功能，以只修改 item 的方式保证这个爬虫的生命（理论上，更换 item 对应的 xpath 位置就可以应对页面元素更改）。并在此基础上增加一些防 ban 策略，深化对爬虫的编写能力，以及应对可能过大的数据处理任务（单纯的构造 url，截止 5 月 3 日，b 站已经有了 323000449 账号详情界面，之前的 lol 爬虫上千条数据就把路由器撑爆了，这次可能要应付 3 亿条数据）。完整代码可见bilibili-user-scrapy 二、爬虫设计全思路 1、目标网站 账户详情页 2、爬取内容: uid 用户id，int mid 用户id，str name 用户姓名，str sex 用户性别，str regtime 用户注册时间，str birthday 用户生日，str place 用户住址，str fans 用户粉丝数，int attention 用户关注数，int level 用户等级，int 3、技术：scrapy，splash，docker，mysql 4、难点 数据库设计及数据插入 js 页面数据的获取 特殊数据的处理 防 ban 策略 三、环境搭建 1、开发语言：python v3.6.5 2、开发语言环境：anaconda v1.6.9 （非必须，但这是一个好习惯） 3、docker 安装 deepin 下安装 docker 其他系统安装 docker ...

Python Python Module timeit模块的使用 timeit 主要是为了测试代码运行速度。 它主要有两个方法，即 timeit 和 repeat。 测试一段代码的运行时间，在 python 里面有个很简单的方法，就是使用 timeit 模块，使用起来超级方便 下面简单介绍一个 timeit 模块中的函数。 主要就是这两个函数： timeit(stmt='pass', setup='pass', timer=<defaulttimer>, number=1000000) 返回： 返回执行stmt这段代码number遍所用的时间，单位为秒，float型 参数： stmt：要执行的那段代码 setup：执行代码的准备工作，不计入时间，一般是import之类的 timer：这个在win32下是time.clock()，linux下是time.time()，默认的，不用管 number：要执行stmt多少遍 repeat(stmt='pass', setup='pass', timer=<defaulttimer>, repeat=3, number=1000000) 这个函数比 timeit 函数多了一个 repeat 参数而已，表示重复执行 timeit 这个过程多少遍，返回一个列表，表示执行每遍的时间。 当然，为了方便，python 还用了一个 Timer 类，Timer 类里面的函数跟上面介绍的两个函数是一样一样的 class timeit.Timer(stmt='pass', setup='pass',timer=<timer function>) Timer.timeit(number=1000000) Timer.repeat(repeat=3,number=1000000) 看懂了吧，一样的，使用的时候哪种方便用哪种。 就相当于 timeit(stmt='pass', setup='pass', timer=<defaulttimer>, number=1000000) = Timer(stmt='pass', setup='pass', timer=<timerfunction>).timeit(number=1000000) repeat(stmt='pass', setup='pass', timer=<defaulttimer>, repeat=3, number=1000000) = Timer(stmt='pass', setup='pass', timer=<timerfunction>).repeat(repeat=3, number=1000000)

Python Python Module virtualenv 实际场景使用 virtualenv 是一个用来创建“独立” python 环境的工具，网上相关的资料相当多，但是很少有基于实际场景来叙述的，而且这个双引号独立也另有所指。 下载 virtualenv virtualenv 已经集成在 python3.3 之后标准库的 venv 模块下，这里只说 3.3 之前的版本，着重说 python2.6 和 python2.7 两个版本下的 virtualenv 使用。 下载方式: pip install virtualenv tips:虽然理论上可以通过 python2.6 直接装 2.7 甚至 3.x 的python，但是由于版本古老，可能（大概率）python2.6 下的 virtualenv 工具无法使用，因为 python2.6 不支持字典推导式，会报语法错误。尽量使用 python2.7 以上的版本。 tips2: centos6.x 系统使用的是 python2.6.6，centos7 系统使用的是 python2.7.5。 python2.6 安装 pip，可以直接 wget https://bootstrap.pypa.io/2.6/get-pip.py 下载 get-pip.py 文件，然后 python get-pip.py 来安装 直接使用 virtualenv 用法： virtualenv [OPTIONS] DEST_DIR 可选项(基于virtualenv version：15.2.0)： 指令 说明 备注 –version 显示版本 - -h, –help 输出帮助文本 - -v, –verbose 结果详细输出 - -q, –quiet 结果简略输出 - -p PYTHON_EXE, –python=PYTHON_EXE 指定 python 版本，例如：–python=python3.5 将会使用 python3.5 创建虚拟环境。如不指定该选项，则默认指定 python 解释器为(/usr/bin/python) 用得最多的选项。 –clear 清除非root用户安装并从头开始。 注：我没用过这个选项，一般装错直接删除目录。 –no-site-packages 已过时。仅保留向后兼容性。已成为默认选项。 很多资料显示使用这个参数，在当前版本下已经不需要指定该参数 –system-site-packages 为虚拟环境提供 目标python环境 已安装的包 - –always-copy 总是复制文件而不是符号连接。 用的比较多的选项，后面会详细说 –relocatable 使一个现有的 virtualenv 环境可重定位。这会修复脚本，并生成相对的所有.pth文件 没用过，但应该会重新适配pth，之前遇到过一个环境路径问题，但只影响pip安装，不影响python使用（前提配置了路径） –no-setuptools 不要在新的virtualenv中安装setuptools - –no-pip 不要在新的virtualenv中安装pip - –no-wheel 不要在新的virtualenv中安装wheel - –extra-search-dir=DIR 此选项允许您提供自己的setuptools或pip版本，而不是virtualenv附带的嵌入式版本。可多次使用。 - –download 从PyPI下载预安装的软件包。 没用过。 –no-download, –never-download 不要从PyPI下载预安装的软件包。 没用过。 –prompt=PROMPT 为此环境提供备用提示前缀。 激活环境时的显示前缀 –setuptools 已过时。仅保留向后兼容性。该选项无用。 - –distribute 已过时。仅保留向后兼容性。该选项无用。 - –unzip-setuptools 已过时。仅保留向后兼容性。该选项无用。 - 常用方法和实例 virtualenv test 安装截图： ...

Python [[Django]] 使用 Django 创建一份在线简历 一、开篇 去年十二月的时候，我曾跟着追梦人物的Django博客教程葫芦依样，开发出了一个自己的博客 Black&White，那时候的我对网站的结构，网站运行的模式懵懵懂懂，只会跟着教程一步步做下去，遇到问题去找解决方案的过程也很艰辛，找不到出现问题的关键点，最后成品做了出来，但因为只是模仿，没能力创新，使得最后自己的博客 url 是 demo.lightl.fun/，连二级域名都不会修改。之后几个月因为其他事缠身，也就没继续 Django 的学习。适逢将要毕业，我花了几个月将本科知识全部回顾了一遍，对计算机网络的认识更上一层楼，乘着将要找工作，不如重新实践，利用 Django 创建一份在线简历。 二、设计思路 由于做过的工程太少，很多时候设计思路只是一个方向，具体实现过程会对需求做各种变动，随机应变吧。 简单的设计思路就是，开始一个 Django 项目，开始一个新的简历应用，从网上找到前端界面模板，然后作为 static 文件放到简历应用中，根据模板可以提供的数据输出位置设计模型（数据库），然后生成数据库，存入真实数据，用 Django 提供的数据库接口获得数据，在视图函数中作为参数传给前端界面，再在前端界面中使用模板渲染的方法给传来的数据进行渲染，最后使用 nginx 部署在公网服务器上，实现在线简历功能。 三、具体实现及遇到的问题 具体实现过程中，参考自强学堂-Django 基础教程以及追梦人物的 Django 博客教程。此时的实现，会考虑每一步做的意义以及能实现的效果，同时 Django 已经升级到了 2.0.5，而网上教程多集中在 1.8，有少许区别，参照自强学堂提出的以及 google 可以解决，（同时 Django2.0.5 可以兼容Django1.8创建的项目，但在模型部分有修改）。 先是常规的建立项目，建立应用，添加应用信息到 settings.py，给 view.py 添加一个 index 方法，给 urls.py 配置 url 导向，这里没什么太多可说的。 # JL/settings.py INSTALLED_APPS = [ 'django.contrib.admin', 'django.contrib.auth', 'django.contrib.contenttypes', 'django.contrib.sessions', 'django.contrib.messages', 'django.contrib.staticfiles', 'jianli', ] # JL/urls.py from django.contrib import admin from django.urls import path from jianli import views as jianli_views urlpatterns = [ path('admin/', admin.site.urls), path('', jianli_views.index, name='jianli_view'), # 新版 url 写法更舒服了 ] 之后找简历模板，最后选择了简历模板，下载，放入应用的 static 文件夹中，将 index.html 放入 templates 文件夹中，给 html 文件中指向的 css、js 位置进行修改，此时出现了第一个渲染的数据 base_dir，它指向应用的 static 文件夹，如果今后移动该文件夹，只需要修改 base_dir 内容，index.html 就可以正常工作。 ...

单元测试浅析 1、何为单元测试 在计算机编程中，单元测试（英语：[[Unit Testing]]）又称为模块测试, 是针对程序模块（软件设计的最小单位）来进行正确性检验的测试工作。程序单元是应用的最小可测试部件。在过程化编程中，一个单元就是单个程序、函数、过程等；对于面向对象编程，最小单元就是方法，包括基类（超类）、抽象类、或者派生类（子类）中的方法。 2、单元测试的优势 - 适应变更 单元测试允许程序员在未来重构代码，并且确保模块依然工作正确（复合测试）。这个过程就是为所有函数和方法编写单元测试，一旦变更导致错误发生，借助于单元测试可以快速定位并修复错误。 可读性强的单元测试可以使程序员方便地检查代码片断是否依然正常工作。良好设计的单元测试案例覆盖程序单元分支和循环条件的所有路径。 - 简化集成 单元测试消除程序单元的不可靠，采用自底向上的测试路径。通过先测试程序部件再测试部件组装，使集成测试变得更加简单。 - 文档记录 单元测试提供了系统的一种文档记录。借助于查看单元测试提供的功能和单元测试中如何使用程序单元，开发人员可以直观的理解程序单元的基础 API。 单元测试具体表现了程序单元成功的关键特点。这些特点可以指出正确使用和非正确使用程序单元，也能指出需要捕获的程序单元的负面表现（译注：异常和错误）。尽管很多软件开发环境不仅依赖于代码做为产品文档，在单元测试中和单元测试本身确实文档化了程序单元的上述关键特点。 - 表达设计 在测试驱动开发的软件实践中，单元测试可以取代正式的设计。每一个单元测试案例均可以视为一项类、方法和待观察行为等设计元素。 3、单元测试的局限 测试不可能发现所有的程序错误，单元测试也不例外。按定义，单元测试只测试程序单元自身的功能。因此，它不能发现集成错误、性能问题、或者其他系统级别的问题。单元测试结合其他软件测试活动更为有效。与其它形式的软件测试类似，单元测试只能表明测到的问题，不能表明不存在未测试到的错误。 4、单元测试的要求 4.1 代码可测性 这种情况可能是你代码本身导致的，首先你要写具有“可测性”的代码，这意味着你不能写面向过程的，流水式的，几百行逻辑堆一起的代码（也叫意大利面代码，就像一盘意大利面一样搅在一起的代码。），你要学一些模块化技巧，面向对象和函数式编程理念，还有很多其它具体方法，比如能用本地变量，就不要用全局变量等等，让你的代码具有可测性，这些知识的学习应该放在单元测试之前。 4.2 测试独立性 每个理想的测试案例独立于其它案例；为测试时隔离模块，经常使用 stubs、mock 或 fake 等测试马甲程序。不与外部（包括文件、数据库、网络、外部服务）直接相依。 4.3 测试有效性 测试代码和功能代码同时提交。 4.4 测试及时性 单元测试的目的是，针对修改的每个函数或方法，进行快速的测试，观察结果是否如预期。不说代码改动的效果如何（性能，规范等），至少可以正常运行。 4.5 一个测试案例只测一个方法 单元测试注重快速，小而美，针对一个实例方法，可能会有很多不同方向的测试，将这些测试方法分开。假设测试账户有效性，账户有效写个方法，账户无效写个方法。 5、单元测试之stub,mock,fake 这三个概念来源自面向对象设计语言在 TDD 方法下的实践。 stub 检测回调值return。我们用 pytest 或者 unittest 替代。 mock 模拟和外界的连接。我们用 python mock 替代。 fake 虚拟环境。我们可以显式修改临时变量。 6、python 常见单元测试框架 6.1 unittest python 标准库自带的单元测试框架。 6.2 pytest 非常简洁好用的单元测试框架。简单使用方法可以参加博客pytest的简单学习 6.3 mock 单元测试应该只针对当前单元进行测试, 所有的内部或外部的依赖应该是稳定的, 已经在别处进行测试过的。 ...

Python Data Structure 单链表的 Python 实现 一、节点 节点，即 C 语言里使用 struct 语句定义的一种非基础数据类型，在 Python 中，定义一个class 类。 class Node(object): def __init__(self, data, next=None): """包含一个数据域，一个 next 域的节点，next 是对下一个数据的引用 """ self.data = data self.next = next class TwoWayNode(Node): """继承 Node 类的双指针节点类，新包含一个 previous 的引用 """ def __init__(self, data, previous=None, next=None): Node.__init__(self, data, next) self.previous = previous def main(): pass if __name__ == "__main__": main() 二、单链表 单链表，指的是由多个节点形成的链式结构，一个节点包括一个数据域及一个 next 域。 除头结点外，每个节点都有且仅有一个前驱；除尾节点外，每个节点有且仅有一个后继。 ADT 思想（忽略）。 定义一个单链表类，依次给出以下的方法： 1、 在首部插入节点 2、在尾部插入节点 3、在任意位置插入节点 4、从首部删除节点 5、从尾部删除节点 6、从任意位置删除节点 7、遍历输出 8、根据数值查找单链表中是否存在项，返回 True or False 及索引位置 9、根据给出的索引替换掉相应位置的值 from node import Node class SingleList(object): """以节点的方式实现链表，默认实现空列表 """ def __init__(self): self.head = None # 在开始处插入 def add_node_first(self, data): self.head = Node(data, self.head) # 在末尾插入，若为空列表则直接插入，否则遍历到尾部 def add_node_last(self, data): new_node = Node(data) if self.head is None: self.head = new_node else: probe = self.head while probe.next is not None: probe = probe.next probe.next = new_node # 任意位置添加节点，若 index 小于零，加在首部，若 index 大于链表长度，加在尾部 def add_node_anywhere(self, index, data): if self.head is None or index <= 0: self.head = Node(data, self.head) else: probe = self.head while index >1 and probe.next is not None: probe = probe.next index -= 1 probe.next = Node(data, probe.next) # 从首部删除节点 def pop_node_first(self): if self.head is not None: removed_item = self.head.data self.head = self.head.next return removed_item else: return -1 # 从尾部删除节点 def pop_node_last(self): if self.head is None: return -1 elif self.head.next is None: removed_item = self.head.data self.head = None else: probe = self.head while probe.next.next is not None: probe = probe.next removed_item = probe.next.data probe.next = None return removed_item # 任意位置删除节点，若 index 小于零，则删除首部节点，若 index 大于链表长度，则删除尾部节点 def pop_node_anywhere(self, index): if index <= 0 or self.head.next is None: removed_item = self.head.data self.head = self.head.next return removed_item else: probe = self.head while index > 1 and probe.next.next is not None: probe = probe.next index -= 1 removed_item = probe.next.data probe.next = probe.next.next return removed_item # 遍历输出 def traverse(self): probe = self.head while probe is not None: print(probe.data) probe = probe.next # 根据数值查找链表有没有该数据 def search(self, data): probe = self.head cnt = 0 while probe is not None and data != probe.data: probe = probe.next cnt += 1 if probe is not None: return "In", cnt else: return "Not in", -1 # 根据索引位置替换数据 def replace(self, index, new_data): probe = self.head while index > 0 and probe is not None: probe = probe.next index -= 1 if probe is None: return -1 else: probe.data = new_data return "Done" # 测试用例 a = SingleList() a.add_node_first(1) a.add_node_first(2) a.add_node_first(3) print(a.search(2)) a.add_node_first(4) a.add_node_last(5) a.add_node_first(6) a.add_node_anywhere(100,33) a.pop_node_anywhere(2) a.traverse() print("--------")

Python [[Algorithm]] 常见排序算法的 Python 实现 选择排序 """ 选择排序，顾名思义，扫描全表，选最小值 外循环走size-1次，每一次确定当前一个最小的数 内循环走size-（已经确定的最小数），理解为当前位置之前的数字都已有序，从当前位置出发到结尾扫描确定当前最小的数字 时间复杂度：平均O(n**2)，最坏O(n**2)，最好O(n**2) 空间复杂度：O(1) 稳定性：不稳定 """ def select_sort(sort_list): for i in range(size-1): min = i for j in range(i, size): if sort_list[j] < sort_list[min]: min = j sort_list[min], sort_list[i] = sort_list[i], sort_list[min] print("选择排序结果是：",sort_list) 冒泡排序 """ 冒泡排序，逐个比较，将最大的数排到最后方 外循环走size-1次，每次确定一个最大的数 内循环走size-（当前已确定的数），理解为从头开始，两两比较，a(n)>a(n+1)，则交换 时间复杂度：平均O(n**2)，最坏O(n**2)，最好O(n) 空间复杂度：O(1) 稳定性：稳定 """ def bub_sort(sort_list): for i in range(size-1): for j in range(1, size): if sort_list[j] < sort_list[j-1]: sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j] print("冒泡排序结果是：",sort_list) 插入排序 """ 插入排序，类似于体育课排队列 外循环走size-1次，每次确定一个较小的数，一次内循环结束，当前位置的左侧是相对大小确定的 内循环走0次或者当前已确定数的次数，理解为当前数与之前的第一个数对比，若小于则交换，继而继续比较，所以最少0次，最多当前已确定数次 时间复杂度：平均O(n**2)，最坏O(n**2)，最好O(n) 空间复杂度：O(1) 稳定性：稳定 """ def insert_sort(sort_list): for i in range(1, size): j = i while j > 0 and sort_list[j]<sort_list[j-1]: sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j] j -= 1 print("插入排序结果是：",sort_list) 希尔排序 """ 希尔排序（该处指配合插入排序的希尔排序），由插入排序的定义可以看出来，当前的数想要确定位置必须与之前的数字逐个比较， 而希尔排序改成h个比较，这样做的好处是，针对数据量大的数组，排序的过程更轻松（构建h个不同的子数组，每个子数组逻辑相邻（相差距离为h）） 外循环的运算次数为（size = size//3循环，直到size等于1，每循环一次，运算次数加一 如size = 150,150//3=50（1次），50//3=16（2次），16//3=5（3次），5//3=1（4次）） 内循环为选择插入排序，次数由当前的外循环变量决定 时间复杂度：平均O(n**1.3)，其他情况不好分析 空间复杂度：O(1) 稳定性：不稳定 """ def shell_sort(sort_list): h = 1 while h < size//3: h = h*3+1 while h >=1: for i in range(h, size): j = i while j > h and sort_list[j]<sort_list[j-h]: sort_list[j], sort_list[j-h] = sort_list[j-h], sort_list[j] j -= h h = h//3 print("希尔排序结果是：",sort_list) 归并排序 """ 归并排序，分治算法思想，将一个大问题分解成若干个小问题，若问题类似可用递归完成 常见两种归并算法，自顶向下和自底向上 自顶向下的算法用递归的方法，先解决左边的排序，再解决右边的排序 自底向上的算法用拆解合并的思想，先拆成size/2个小数组进行归并排序，继而将结果拆成size/4个数组归并排序，当size/(2**n)<1时完成排序 时间复杂度：平均O(nlog2n)，最坏O(nlog2n)，最好O(nlog2n) 空间复杂度：O(n)（需要一个临时数组来保存） 稳定性：稳定 """ class merge(object): #原地归并抽象方法，方便复用，传入数组，左值，中值，右值 def merge_sort(self, sort_list, lo, mid, hi): i = lo j = mid+1 aux = copy.deepcopy(sort_list) for k in range(lo, hi+1): if i > mid: sort_list[k] = aux[j] j += 1 elif j > hi: sort_list[k] = aux[i] i += 1 elif aux[j] <= aux[i]: sort_list[k] = aux[j] j += 1 else: sort_list[k] = aux[i] i += 1 def sort(self, sort_list): self.sort1(sort_list, 0, size-1) #自顶向下的归并排序 def sort1(self, sort_list, lo, hi): if hi <= lo: return sort_list mid = lo + (hi-lo)//2 self.sort1(sort_list, lo, mid) self.sort1(sort_list, mid+1, hi) self.merge_sort(sort_list, lo, mid, hi) def sort2(self, sort_list): sz = 1 while sz < size: lo = 0 while lo < size-sz: self.merge_sort(sort_list, lo, lo+sz-1, min(lo+sz+sz-1, size-1)) lo += sz+sz sz = sz+sz print(sort_list) 快速排序 """ 快速排序，是常规条件下最快的排序算法，使用分治算法思想，利用递归完成 首先先改变数组内部顺序（消除输入依赖），然后通过切分函数找出一个值（二分切分中，该值越接近正确顺序的中值越好） 以该值为mid，递归调用自身，分而治之 重点在于切分函数，二分切分函数的思想是，以某子数组第一个数a为基准， 从左往右扫描找出一个大于a的数，再从右往左扫描找出一个小于a的数，两者交换 最后将a放到正确的位置，返回切分的数的索引 时间复杂度：平均O(nlog2n)，最坏O(n**2)，最好O(nlog2n) 空间复杂度：O(log2n)（需要一个临时数组来保存） 稳定性：不稳定 """ class quick(object): #消除输入依赖 def sort(self, sort_list): random.sample(sort_list, size) self.sort1(sort_list, 0, size-1) #递归主函数体，从切分函数得到切分索引，左右递归，递归结束不用归并 def sort1(self, sort_list, lo, hi): if hi <= lo: return sort_list j = self.partition(sort_list, lo, hi) self.sort1(sort_list, lo, j-1) self.sort1(sort_list, j+1, hi) #切分函数，左右指针，轮流扫描，交换位置，最后将切分元素放到正确的位置，返回切分索引 def partition(self, sort_list, lo, hi): i = lo j = hi+1 v = sort_list[lo] while True: i = i + 1 while sort_list[i]<v: if i==hi: break i += 1 j = j - 1 while v < sort_list[j]: if j==lo: break j -= 1 if i >= j: break sort_list[i], sort_list[j] = sort_list[j], sort_list[i] sort_list[lo], sort_list[j] = sort_list[j], sort_list[lo] return j 基数排序 """ 基数排序，不进行比较的整数排序算法，基数指的是整数的进制（默认为10）， 根据位数要做几次不同的桶排序，位数的计算为int(math.ceil(math.log(max(sort_list)+1, radix))) 每次循环完成当前位数（个位、十位、百位）的大小排序，理解过程可见http://bubkoo.com/2014/01/15/sort-algorithm/radix-sort/ 一共有十个桶，分别对应0-10，每个桶有若干数据，则桶可以用二维数组完成，记为a[index1][index2]， 对每一个sort_list里的数，index1 = sort_list_num%(radix**i)//(radix**(i-1)) 时间复杂度：平均O(k*n)，最坏O(k*n)，最好O(k*n)，k为最大数字的位数 空间复杂度：O(n) 稳定性：稳定 """ def radix_sort(sort_list, radix=10): """sort_list为整数列表， radix为基数""" K = int(math.ceil(math.log(max(sort_list)+1, radix))) for i in range(1, K+1): bucket = [[] for i in range(radix)] for val in sort_list: bucket[val%(radix**i)//(radix**(i-1))].append(val) del sort_list[:] for each in bucket: sort_list.extend(each) print(sort_list) 测试 import copy import random import math sort_list = [20,1,24,54,11,26,87,45,32,544,25,87,47,48,58,1024] global size size = len(sort_list) #select_sort(sort_list) #bub_sort(sort_list) #insert_sort(sort_list) #shell_sort(sort_list) #自顶向下归并排序测试 # a = merge() # a.sort(sort_list) # print(sort_list) #自底向上归并排序测试 # a = merge() # a.sort2(sort_list) # print(sort_list) #快速排序测试 # print(sort_list) # a = quick() # a.sort(sort_list) # print(sort_list) #基数排序测试 #radix_sort(sort_list)

Python [[Data Structure]] 栈的 Python 实现（列表） class Stack(object): """栈的 Python 列表实现 """ # 初始化对象，生成空列表 def __init__(self): self.item = [] # 判断栈是否为空，返回 True or False def isEmpty(self): return self.item == [] # 入栈方法，添加至列表尾部 def push(self, item): self.item.append(item) # 出栈方法，从队列尾部弹出，并返回弹出值 def pop(self): return self.item.pop() # 查栈顶元素方法，返回栈顶元素值，但不弹出 def peek(self): return self.item[len(self.item)-1] # 查看栈的大小方法，返回 int 值 def size(self): return len(self.item) def match_sympol(string): """ 利用栈的特性（后进先出），对三种常见括号进行匹配 对于左括号，直接压入栈，遇到右括号，弹出栈顶元素，若能一一对应，且最终栈为空，则完全匹配 """ s = Stack() flag = True index = 0 while index < len(string) and flag: symbol = string[index] if symbol in "({[": s.push(symbol) else: if s.isEmpty(): flag = False else: top = s.pop() if not matches_help(top, symbol): flag = False index += 1 if flag and s.isEmpty(): return True else: return False def matches_help(open, close): """ 匹配辅助函数 传入两个 char 参数，判断是否对应，返回 True or False """ opens = "({[" closes = ")}]" return opens.index(open) == closes.index(close) def ten2two(num): """ 十进制转二进制，原理是除二取余法 将十进制数除二取余数，将余数压入栈，直到十进制数为 0，然后栈逐个弹出 """ s = Stack() while num > 0: rem = num%2 s.push(rem) num = num//2 binString = "" while not s.isEmpty(): binString = binString + str(s.pop()) return binString def infixToPostfix(infixexpr): """ 中序表达式转后续表达式 中序表达式转换后续表达式有个简单的方法，先将中序表达式的每一次运算都加上括号，接着从右往左， 找到第一个算数符号替换掉最近的右括号，并将对应的左括号去除，继续往左执行，直到没有括号为止 具体过程： 1、创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。 2、通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。 3、从左到右扫描标记列表。 如果标记是操作数，将其附加到输出列表的末尾。 如果标记是左括号，将其压到 opstack 上。 如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。 如果标记是运算符，*，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。 4、当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。 理解过程可见：https://facert.gitbooks.io/python-data-structure-cn/3.%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/3.9.%E4%B8%AD%E7%BC%80%E5%89%8D%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/ """ prec = {} prec["*"] = 3 prec["/"] = 3 prec["+"] = 2 prec["-"] = 2 prec["("] = 1 opStack = Stack() postfixList = [] tokenList = infixexpr.split() for token in tokenList: if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789": postfixList.append(token) elif token == '(': opStack.push(token) elif token == ')': topToken = opStack.pop() while topToken != '(': postfixList.append(topToken) topToken = opStack.pop() else: while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]): postfixList.append(opStack.pop()) opStack.push(token) while not opStack.isEmpty(): postfixList.append(opStack.pop()) return " ".join(postfixList) def postfixEval(postfixExpr): """ 后缀表达式的算值 根据后缀表达式的特点，很容易可以想到，将运算数压入栈，当出现符号时，弹出栈顶两个元素，计算完成后压入栈， 等待下一个运算数或者运算符，最后栈顶元素就是后缀表达式的值。 """ operandStack = Stack() tokenList = postfixExpr.split() for token in tokenList: if token in "0123456789": operandStack.push(int(token)) else: operand2 = operandStack.pop() operand1 = operandStack.pop() result = doMath(token, operand1, operand2) operandStack.push(result) return operandStack.pop() def doMath(op, op1, op2): """ 后缀表达式运算值的辅助函数 输入三个参数（运算符，操作数1，操作数2），返回运算结果。 """ if op == "*": return op1 * op2 elif op == "/": return op1 / op2 elif op == "+": return op1 + op2 else: return op1 - op2 #栈的测试 # s= Stack() # print(s.isEmpty()) # s.push(4) # s.push('dog') # print(s.peek()) # s.push(True) # print(s.size()) # print(s.isEmpty()) # s.push(8.4) # print(s.pop()) # print(s.pop()) # print(s.size()) # 符号匹配的测试 # print(match_sympol('')) # 十进制数转二进制的测试 # print(ten2two(100)) # 中缀表达式转后缀表达式的测试 # print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )")) # 后缀表达式的求求值 # print(postfixEval('7 8 + 3 2 + /'))

Python [[Regular Expression]] 正则表达式及re库的使用 一、正则表达式 正则表达式要做的事简单地说就是字符串匹配，它由普通字符、非打印字符、特殊字符、限定符和定位符构成。理论上可以匹配一切字符串。 二、什么是正则表达式 正则表达式30分钟入门教程 正则表达式手册 三、在线正则表达式测试 regex101 在线正则表达式测试 三、常用的匹配规则 模式 描述 | 将下一个字符标记为一个特殊字符、或一个原义字符、或一个向后引用、或一个八进制转义符。例如，“n”匹配字符“n”。“\n”匹配一个换行符。串行“\”匹配“\”而“(”则匹配“(”。 ^ 匹配输入字符串的开始位置。如果设置了RegExp对象的Multiline属性，^也匹配“\n”或“\r”之后的位置。 $ 匹配输入字符串的结束位置。如果设置了RegExp对象的Multiline属性，$也匹配“\n”或“\r”之前的位置。 * 匹配前面的子表达式零次或多次。例如，zo*能匹配“z”以及“zoo”。*等价于{0,}。 + 匹配前面的子表达式一次或多次。例如，“zo+”能匹配“zo”以及“zoo”，但不能匹配“z”。+等价于{1,}。 ? 匹配前面的子表达式零次或一次。例如，“do(es)?”可以匹配“does”或“does”中的“do”。?等价于{0,1}。 {n} n是一个非负整数。匹配确定的n次。例如，“o{2}”不能匹配“Bob”中的“o”，但是能匹配“food”中的两个o。 {n,} n是一个非负整数。至少匹配n次。例如，“o{2,}”不能匹配“Bob”中的“o”，但能匹配“foooood”中的所有o。“o{1,}”等价于“o+”。“o{0,}”则等价于“o*”。 {n,m} m和n均为非负整数，其中n<=m。最少匹配n次且最多匹配m次。例如，“o{1,3}”将匹配“fooooood”中的前三个o。“o{0,1}”等价于“o?”。请注意在逗号和两个数之间不能有空格。 ? 当该字符紧跟在任何一个其他限制符（*,+,?，{n}，{n,}，{n,m}）后面时，匹配模式是非贪婪的。非贪婪模式尽可能少的匹配所搜索的字符串，而默认的贪婪模式则尽可能多的匹配所搜索的字符串。例如，对于字符串“oooo”，“o+?”将匹配单个“o”，而“o+”将匹配所有“o”。 . 匹配除“\n”之外的任何单个字符。要匹配包括“\n”在内的任何字符，请使用像“(. (pattern) 匹配pattern并获取这一匹配。所获取的匹配可以从产生的Matches集合得到，在VBScript中使用SubMatches集合，在JScript中则使用$0…$9属性。要匹配圆括号字符，请使用“\(”或“\)”。 (?:pattern) 匹配pattern但不获取匹配结果，也就是说这是一个非获取匹配，不进行存储供以后使用。这在使用或字符“(|)”来组合一个模式的各个部分是很有用。例如“industr(?:y|ies)”就是一个比“industry|industries”更简略的表达式。 (?=pattern) 正向肯定预查，在任何匹配pattern的字符串开始处匹配查找字符串。这是一个非获取匹配，也就是说，该匹配不需要获取供以后使用。例如，“Windows(?=95|98|NT|2000)”能匹配“Windows2000”中的“Windows”，但不能匹配“Windows3.1”中的“Windows”。预查不消耗字符，也就是说，在一个匹配发生后，在最后一次匹配之后立即开始下一次匹配的搜索，而不是从包含预查的字符之后开始。 (?!pattern) 正向否定预查，在任何不匹配pattern的字符串开始处匹配查找字符串。这是一个非获取匹配，也就是说，该匹配不需要获取供以后使用。例如“Windows(?!95|98|NT|2000)”能匹配“Windows3.1”中的“Windows”，但不能匹配“Windows2000”中的“Windows”。预查不消耗字符，也就是说，在一个匹配发生后，在最后一次匹配之后立即开始下一次匹配的搜索，而不是从包含预查的字符之后开始 (?<=pattern) 反向肯定预查，与正向肯定预查类拟，只是方向相反。例如，“(?<=95|98|NT|2000)Windows”能匹配“2000Windows”中的“Windows”，但不能匹配“3.1Windows”中的“Windows”。 (?<!pattern) 反向否定预查，与正向否定预查类拟，只是方向相反。例如“(?<!95|98|NT|2000)Windows”能匹配“3.1Windows”中的“Windows”，但不能匹配“2000Windows”中的“Windows”。 x|y 匹配x或y。例如，“z|food”能匹配“z”或“food”。“(z|f)ood”则匹配“zood”或“food”。 [xyz] 字符集合。匹配所包含的任意一个字符。例如，“[abc]”可以匹配“plain”中的“a”。 [^xyz] 负值字符集合。匹配未包含的任意字符。例如，“[^abc]”可以匹配“plain”中的“p”。 [a-z] 字符范围。匹配指定范围内的任意字符。例如，“[a-z]”可以匹配“a”到“z”范围内的任意小写字母字符。 [^a-z] 负值字符范围。匹配任何不在指定范围内的任意字符。例如，“[^a-z]”可以匹配任何不在“a”到“z”范围内的任意字符。 \b 匹配一个单词边界，也就是指单词和空格间的位置。例如，“er\b”可以匹配“never”中的“er”，但不能匹配“verb”中的“er”。 \B 匹配非单词边界。“er\B”能匹配“verb”中的“er”，但不能匹配“never”中的“er”。 \cx 匹配由x指明的控制字符。例如，\cM匹配一个Control-M或回车符。x的值必须为A-Z或a-z之一。否则，将c视为一个原义的“c”字符。 \d 匹配一个数字字符。等价于[0-9]。 \D 匹配一个非数字字符。等价于[^0-9]。 \f 匹配一个换页符。等价于\x0c和\cL。 \n 匹配一个换行符。等价于\x0a和\cJ。 \r 匹配一个回车符。等价于\x0d和\cM。 \s 匹配任何空白字符，包括空格、制表符、换页符等等。等价于[ \f\n\r\t\v]。 \S 匹配任何非空白字符。等价于[^ \f\n\r\t\v]。 \t 匹配一个制表符。等价于\x09和\cI。 \v 匹配一个垂直制表符。等价于\x0b和\cK。 \w 匹配包括下划线的任何单词字符。等价于“[A-Za-z0-9_]”。 \W 匹配任何非单词字符。等价于“[^A-Za-z0-9_]”。 四、python 里的 re模块 4.1 match 这里首先介绍第一个常用的匹配方法 —— match，向它传入要匹配的字符串以及正则表达式，就可以检测这个正则表达式是否匹配字符串。 ...