Python3支持策略

Python3支持策略

关于迁移

关于移植应用的官方文档(http://zeromq.org/)是有的,但不建议不折不扣地参考它。

最好还是兼容py2和py3,然后有够用的单元测试。
通过tox,来测试两个版本。
tox -e py27, py35
根据提示的错误进行修改,重新运行tox,直到所有测试都通过为止。

语言和标准库

Porting to Python3这本书给出了要支持Python3所需做修改的良好概述。

支持Python的多版本时,应该尽量避免同时支持Python3.3和早于Python2.6的版本。Python2.6是第一个为向Python3移植提供足够兼容性的版本。

影响你最多的可能是字符串处理方面。在Python3中过去称为unicode,现在叫做str。这意味着任何字符串都是Unicode的。也就是说u’foobar’和’foobar’是同一样东西。

实现unicode方法的类应该将其重命名为str,因为unicode方法将不再使用。可以通过一个类装饰器自动完成这个过程。

# -*- encoding: utf-8 -*-
import six


def unicode_compat(klass):
    if not six.PY3:
        klass.__unicode__ = klass.__str__
        klass.__str__ = lambda self: self.__unicode__().encode('utf-8')
    return klass


class Square(object):
    def __str__(self):
        return u"" + str(id(self))

这种方式可以针对所有返回Unicode的Python版本实现一个方法,装饰器会处理兼容性问题。

另一个处理Python和Unicode的技巧是使用unicode_literals,它从Python2.6开始提供。

>>> 'foobar'
'foobar'
>>> from __future__ import unicode_literals
>>> 'foobar'
u'foobar'
>>>

许多函数不再返回列表而是返回可迭代对象(如range)。此外,字典方法(如keys或者iterms)现在也返回可迭代对象,而函数iterkeys和iteritems则已经被删除。 这是一个巨大的变化,但six将帮你处理这个问题。

显然,标准库也经历了从Python2到Python3的演化,但无需过分担心。一些模块已经被重命名或者删除,但最终呈现的是更为清晰的布局。我不知道是否有官方的清单,但是http://docs.pythonsprints.com/python3_porting/py-porting.html就有一份很好的清单,或者也可以用搜索引擎找到。

外部库

选择外部库时,最好一开始就兼容py3。如果已有库还不支持py3,没啥好办法。
另外用外部库时,最好自己有个中间层,这样将来换的时候也比较方便。

使用six

Python3破坏了与早期版本间的兼容性并且周边很多东西发生了变化。但是,这门语言的基础并没有发生变化,所以是可以实现一种转换层的,也就是一个能实现向前和向后兼容的模块–Python2和Python3之间的桥梁。

这样的模块是有的,名字就叫做six,因为2×3=6.
six首先要做的就是提供一个名为six.PY3的变量。它是一个布尔值,用来表明是否正在运行Python3。对于任何有两个版本(Python2和Python3)的代码库而言这都是一个关键变量。不过在用的时候要谨慎,如果代码中到处都是if six.PY3,那么后续会很难维护。

python3中,去掉了dict.iteritems,同时dict.items将返回一个迭代器而不是列表。显然,这会破坏你的代码。six对此提供了six.iteritems,使得所有要做的只是将

for k, v in mydict.iteritems():
    print(k, v)

替换为

import six

for k, v in six.iteritems(mydict):
    print(k, v)

看,Python3的兼容性立刻就解决了!six提供了大量类似的辅助函数以提升不同版本间的兼容性。

raise 在six中可以用 six.reraise。
如果正在使用abc抽象基类元类,则可以像下面这样使用six:

import abc
from six import with_metaclass

class MyClass(with_metaclass(abc.ABCMeta, object)):
    pass

six还有好多类似这样的模块,它是开源的,你也可以参与维护。

最后需要提及的是modernize模块。它是在2to3之上的一层很薄的包装器,用来通过迁移代码到Python3使其’现代化’。但是不同于单纯转化语法为Python3代码,它使用six模块。如要迁移,建议用用。

书籍阅读-Python高手之路

书籍阅读-Python高手之路

前言

笔者之前已经看过《Flask Web开发:基于Python的Web应用开发实战》、《Head+First+Python(中文版)》、《Python学习手册(第4版)》、《python绝技:运用python成为顶级黑客》。

Flask Web开发:基于Python的Web应用开发实战: 用于作网站不错。
Head+First+Python(中文版):入门最简单。
Python学习手册(第4版):语言讲解最详细丰富。
python绝技:运用python成为顶级黑客:可以了解下黑客怎么玩的。

而这本《Python高手之路》显然不是给初学者看的,它是给有经验的Python程序员关于Python世界的一个整体视野,并不太关注于语法细节。
作者是150万行Python代码量级的OpenStack项目 技术负责人之一。是值得一读的,不建议初学者读,初学者看了估计很难消化。

第1章 项目开始

这一章对技术管理岗有用,一线员工可能并不太关心。

Python版本

比较了2.5,2.6,2.7,3.1,3.2,3.3,3.4。
建议支持2.7和3.3。(备注:现在已经有了3.5)
如果想支持所有版本,有个CherryPy项目可以参考(http://cherrypy.org/),它支持2.3及以后的所有版本。

需要支持2.7和3.3的话,可以参考13章。

项目结构

项目结构应该保持简单,审慎地使用包和层次结构,过深的层次结构在目录导航时将如同梦魇,但过平的层次结构则会让项目变得臃肿。
一个常犯的错误是将单元测试放在包目录的外面。这些测试实际上应该被包含在软件的子一级包中,以便:

  • 避免被setuptools(或者其他打包的库)作为tests顶层模块自动安装。
  • 能够被安装,且其他包能够利用它们构建自己的单元测试。

setup.py是Python安装脚本的标准名称。

下面这些顶层目录也比较常见。

  • etc 用来存放配置文件的样例。
  • tools 用来存放与工具相关的shell脚本。
  • bin 用来存放将被setup.py安装的二进制脚本。
  • data 用来存放其他类型的文件,如媒体文件。

一个常见的设计问题是根据将要存储的代码的类型来创建文件或模块。使用functions.py或者exceptions.py这样的文件是很糟糕的方式。这种方式对代码的组织毫无帮助,只能让读代码的人在多个文件之间毫无理由地来回切换。
此外,应该避免创建那种只有一个__init__.py文件的目录,例如,如果hooks.py够用的话,就不要创建hooks/init.py。 如果创建目录,那么其中就应该包含属于这一分类/模块的多个Python文件。

版本编号

PEP 440针对所有的Python包引入了一种版本格式,并且在理论上所有的应用程序都应该使用这种格式。

PEP440定义版本号应该遵从以下正则表达式的格式:

N[.N]+[{a|b|c|rc}N]].postN][.devN]

它允许类似1.2或1.2.3这样的格式,但需要注意以下几点。

  • 1.2等于1.2.0, 1.3.4等于1.3.4.0, 以此类推。
  • 与N[.N]+相匹配的版本被认为是最终版本
  • 基于日期的版本(如2013.06.22)被认为是无效的。针对PEP440格式版本号设计的一些自动化工具,在检测到版本号大于或等于1980时就会抛出错误。
  • N[.N]+aN(如1.2a1)表示一个alpha版本,即此版本不稳定或缺少某些功能。
  • N[.N]+bN(如2.3.1b2)表示一个beta版本,即此版本功能已经完整,但可能仍有bug。
  • N[.N]+cN或N[.N]+rcN(如0.4rc1)表示候选版本(常缩写为RC),通常指除非有重大的bug,否则很可能成为产品的最终发行版本。尽管rc和c两个后缀含义相同,但如果二者同时使用,rc版本通常表示比c更新一点。

通常用到的还有以下这些后缀。

  • .postN(如1.4.post2)表示一个后续版本。通常用来解决发行过程中的细小问题(如发行文档有错)。如果发行的是bug修复版本,则不应该使用.postN而应该增加小的版本号。
  • .devN(如2.3.4.dev3)表示一个开发版本。因为难以解析,所以这个后缀并不建议使用。它表示这是一个质量基本合格的发布前的版本,例如,2.3.4.dev3表示2.3.4版本的第三个开发版本,它早于任何的alpha版本、beta版本、候选版本和最终版本。

编码风格与自动检查

Python社区提出了编写Python代码的PEP8标准.
这些规范可以归纳成下面的内容。

  • 每个缩进层级使用4个空格。
  • 每行最多的79个字符。
  • 顶层的函数或类的定义之间空两行。
  • 采用ASCII或UTF-8编码文件。
  • 在文件顶端,注释和文档说明之下,每行每条import语句只导入一个模块,同时要按照标准库、第三方库和本地库的导入顺序进行分组。
  • 在小括号、中括号、大括号之间或者逗号之前没有额外的空格。
  • 类的命名采用驼峰命名法,如Came1Case;异常的定义使用Error前缀(如适用的话);函数的命名使用小写字符,如separated_by_underscores;用下划线开头定义私有的属性或方法,如_private。

为了保证代码符合PEP8规范,提供了一个pep8工具来自动检查Python文件是否符合PEP8要求。

pip install pep8 可安装。
pep8 file.py可以检查。
我测试的一个

pep8 config.py
config.py:6:80: E501 line too long (82 > 79 characters)
config.py:23:30: E225 missing whitespace around operator
config.py:39:1: E303 too many blank lines (3)
config.py:57:49: E231 missing whitespace after ‘,’
config.py:59:61: E231 missing whitespace after ‘,’
config.py:59:80: E501 line too long (119 > 79 characters)
config.py:59:105: E231 missing whitespace after ‘,’
config.py:61:80: E501 line too long (81 > 79 characters)
config.py:85:1: E303 too many blank lines (4)

也可以使用–ignore选项忽略某些特定的错误或警告,如下所求。

pep8 –ignore=E2 config.py
config.py:6:80: E501 line too long (82 > 79 characters)
config.py:39:1: E303 too many blank lines (3)
config.py:59:80: E501 line too long (119 > 79 characters)
config.py:61:80: E501 line too long (81 > 79 characters)
config.py:85:1: E303 too many blank lines (4)

相对于上面那个,少了E2xx的错误提示。

还有一些其他的工具能够检查真正的编码错误而非风格问题。下面是一些比较知名的工具。

  • pyflakes,它支持插件。
  • pylint,它支持PEP8,默认可以执行更多检查,并且支持插件。

pyflakes是按自己的规则检查而非按PEP8,所以仍然需要运行pep8。为了简化操作,一个名为flake8的项目将pyflakes和pep8合并成了一个命令。
flake8也是OpenStack使用的工具。
flake8又扩展了一个新的工具hacking,它可以检查except语句的错误使用、Python2与Python3的兼容性问题、导入风格、危险的字符串格式化及可能的本地化问题。

第2章 模块和库

导入系统

sys模块包含许多关于Python导入系统的信息。首先,当前可导入的模块列表都是通过sys.module变量才可以使用的。
它是一个字典,其中键(key)是模块名字,对应的值(value)是模块对象。

sys.module['os']

许多模块是内置的,这些内置模块在sys.buildin_module_names列出。

导入模块时,Python会依赖一个路径列表。这个列表存放在sys.path变量中,并且告诉Python去哪里搜索要加载的模块。
你可以在代码中修改sys.path,也可以修改环境变量PYTHONPATH,从而修改路径列表。

>>>import sys
>>>sys.path.append('/foo/bar')

$ PYTHONPATH=/foo/bar python
>>>import sys
>>>'/foo/bar' in sys.path
True

在sys.path中顺序很重要,因为需要遍历这个列表来寻找请求的模块。

也可以通过自定义的导入器(importer)对导入机制进行扩展。
导入钩子机制是由PEP302定义的。
它允许扩展标准的导入机制,并对其进行预处理,也可以通过追加一个工厂类到sys.path_hooks来添加自定义的模块查找器(finder)。
模块查找器对象必须有一个返回加载器对象的find_module(fullname,path=None)方法,这个加载器对象必须包含一个负责从源文件中加载模块的load_module(fullname)方法。

通过Hy的源码可以学习到。

Hy模块导入器

class MetaImporter(object):
    def find_on_path(self, fullname):
        fls = ["%/__init__.py","%s.py"]
        dirpath = "/".join(fullname.split("."))

        for pth in sys.path:
            pth = os.path.abspath(pth)
            for fp in fls:
                composed_path = fp % ("%s/%s" % (pth, dirpath))
                if os.path.exists(composed_path):
                    return composed_path

    def find_module(self, fullname, path=None):
        path = self.find_on_path(fullname)
        if path:
            return MetaLoader(path)

sys.meta_path.append(MetaImporter)

Hy模块加载器

class MetaLoader(object):
    def __init__(self,path):
        self.path = path


    def is_package(self,fullname):
        dirpath = "/".join(fullname.split("."))
        for pth in sys.path:
            pth = os.path.abspath(pth)
            composed_path = "%s/%s/__init__.py" % (pth, dirpath)
            if os.path.exists(composed_path):
                return True
        return False

    def load_module(self,fullname):
        if fullname in sys.modules:
            return sys.modules[fullname]

        if not self.path:
            return

        sys.modules[fullname] = None
        mod = import_file_to_module(fullname,self.path)#貌似是用的py_compile

        ispkg = self.is_package(fullname)

        mod.__file__ = self.path
        mod.__loader__ = self
        mod.__name__ = fullname

        if ispkg:
            mod.__path__ = []
            mod.__package__ = fullname
        else:
            mod.__package__ = fullname.rpartition('.')[0]

        sys.modules[fullname] = mod
        return mod

标准库

标准库可以参考这里
下面是一些必须了解的标准库模块。
* abc 提供抽象基类等功能。
* atexit 允许注册在程序退出时调用的函数
* argparse 提供解析命令行参数的函数。
* bisect 为可排序列表提供二分查找算法。
* calendar 提供一组与日期相关的函数。
* codecs 提供编解码数据的函数。
* collections 提供一组有用的数据结构。
* copy 提供复制数据的函数。
* csv 提供读写CSV文件的函数。
* datetime 提供用于处理日期和时间的类。
* fnmatch 提供用于匹配Unix风格文件名模式的函数。
* glob 提供用于匹配Unix风格路径模式的函数。
* io 提供用于处理I/O流的函数。
* json 提供用来读写JSON格式函数的函数。
* logging 提供对Python内置的日志功能的访问。可以参考这里
* multiprocessing 可以在应用程序中运行多个子进程。可以参考这里
* operator 提供实现基本的Python运算符功能的函数,可以使用这些函数而不是自己写lambda表达式。
* os 提供对基本的操作系统函数的访问。
* random 提供生成伪随机数的函数。。不能用在安全领域。
* re 提供正则表达式功能。
* select 提供对函数select()和poll()的访问,用于创建事件循环。
* shutil 提供对高级文件处理函数的访问。
* signal 提供用于处理POSIX信号的函数。可以参考这里
* tempfile 提供用于创建临时文件和目录的函数。可以参考这里
* threading 提供对处理高级线程功能的访问。可以参考这里
* urllib(以及Python2.x中的urllib2和urlparse)提供处理和解析URL的函数。
* uuid可以生成全局唯一标识符。

外部库

选择第三方库的检查列表。

  • Python3兼容。
  • 开发活跃。GithubOhloh通常提供足够的信息来判断一个库是否有维护者仍在工作。
  • 维护活跃。
  • 与各个操作系统发行版打包在一起。
  • API兼容保证。

对于外部库,不管它们多么有用,都需要注意避免让这些库和实际的源代码耦合过于紧密。否则,如果出了问题,你需要切换库,这很可能需要重写大量的代码。
更好的办法是写自己的API,用一个包装器对外部库进行封装,将其与自己的源代码隔离。

框架

有许多不同的Python框架可用于开发不同的Python应用。如果是Web应用,可以使用DjangoPylonsTurboGearsTornadoZope或者Plone
如果你正在找事件驱动的框架,可以使用Twisted或者Circuits等。

Doug Hellmann建议

当设计一人应用程序时,我会考虑用户界面是如何工作的,但对于库,我会专注于开发人员如何使用其API。
通过先写测试代码而不是库代码,可以让思考如何通过这个新库开发应用程序更容易一点儿。
我通常会以测试的方式创建一系统示例程序,然后依照其工作方式去构建这个库。
我还发现,在写任何库的代码之前先写文档让我可以全面考虑功能和流程的使用,而不需要提交任何实现的细节。它还让我可以记录对于设计我所做出的选择,以便读者不仅可以理解如何使用这个库,还可以了解在创建它时我的期望是什么。

建议自顶向下设计库和API, 对每一层应用单一职责原则这样的设计准则。
考虑调用者如何使用这个库,并创建一个API去支持这些功能。考虑什么值可以存在一个实例中被方法使用,以及每个方法每次都要传入哪些值。最后,考虑实现以及是否底层的代码的组织应该不同于公共API。

管理API的变化

在构造API时很难一蹴而就。API需要不断演化、添加、删除或者修改所提供的功能。
内部API可以做任意处理。
而暴露的API最好不要变化,但有时候不得不变化。

在修改API时要通过文档对修改进行详细地记录,包括:

  • 记录新的接口;
  • 记录废除的旧的接口;
  • 记录如何升级到新的接口。

旧接口不要立刻删除。实际上,应该尽量长时间地保留旧接口。因为已经明确标识为作废,所以新用户不会去使用它。在维护实在太麻烦时再移除旧接口。API变化的记录见下面示例。

class Car(object):
    def turn_left(self):
        """Turn the car left.
        .. deprecated::1.1
        Use :func:`turn` instead with the direction argument set to left
        """
       self.turn(direction='left') 
        
    def turn(self,direction):
        """Turn the car in some direction.
        
        :param direction: The direction to turn to.
        :type direction: str
        """
        #Write actual code here instead
        pass

使用Sphinx标记强调修改是个好主意。但你不要指望开发人员去读文档。
Python提供了一个很有意思的名为warings的模块用来解决这一问题。这一模块允许代码发出不同类型的警告信息,如PendingDeprecationWarningDeprecationWarning
这些警告能够用来通知开发人员某个正在调用的函数已经废弃或即将废弃。这样,开发人员就能够看到它们正在使用旧接口并且应该相应地进行处理。

使用示例:

warnings.warn("turn_left is deprecated, use turn instead",DeprecationWarning)

需要注意的是自Python2.7起,DeprecationWarning默认不显示了。
要显示出来,执行python时,需要加-W all选项。

第3章 文档

Python中文档格式的事实标准是reStructuredText,或简称reST。它是一种轻量级的标记语言(类似流行的Markdown),在易于计算机处理的同时也便于人类读写。Sphinx是处理这一格式最常用的工具,它能读取reST格式的内容并输出其他格式的文档。

项目的文档应该包括下列内容。

  • 用一两句话描述这个项目要解决的问题。
  • 项目所基于的分发许可。如果是开源软件的话,应该在每一个代码文件中包含相应信息。因为上传代码到互联网并不意味着人们知道他们可以对代码做什么。
  • 一个展示项目如何工作的小例子。
  • 安装指南。
  • 指向社区支持、邮件列表、IRC、论坛等的链接。
  • 指向bug跟踪系统的链接。
  • 指向源代码的链接,以便开发人员可以下载并立刻投入开发。

还应该包括一个README.rst文件,解释这个项目是做什么的。

Sphinx和reST入门

使用之前请先安装pip install sphinx(注意:如果你是在virtualenv环境中启的项目,也应该把sphinx安装在venv中。)
首先,需要在项目的顶层目录运行sphinx-quickstart。这会创建Sphinx需要的目录结构,同时会在文件夹doc/source中创建两个文件,一个是conf.py,它包含Sphinx的配置信息,另一个文件是index.rst,它将作为文档的首页。
然后就可以通过在调用命令sphinx-build时给出源目录和输出目录来生成HTML格式的文档:
sphinx-build doc/source doc/build
现在就可以打开doc/build/index.html了。

Sphinx模块

Sphinx是高度可扩展的:它的基本功能只支持手工文档,但它有许多有用的模块可以支持自动化文档和其他功能。例如,sphinx.ext.autodoc可以从模块中抽取rest格式的文档字符串(docstrings)并生成.rst文件。sphinx-quickstart在运行的时候会问你是否想激活某个模块,也可以编辑conf.py文件并将其作为一个扩展。

extensions = ['sphinx.ext.autodoc']

值得注意的是,autodoc不会自动识别并包含模块,而是需要显式地指明需要对哪些模块生成文档,类似下面这样(编辑index.rst文件):

.. automodule:: foobar
   :members:
   :undoc-members:
   :show-inheritance:

同时要注意以下几点。

  • 如果不包含任何指令, Sphinx不输出任何内容。
  • 如果只指定:members:,那么在模块/类/方法这一树状序列中未加文档的节点将被忽略,即使其成员是加了文档的。例如,如果给一个类的所有方法都加了文档,但这个类没有加文档,:members:除这个类及其方法。为发避免这种情况,要么必须为该类加上一个文档字符串,要么同时指定:undoc-members:。
  • 模块需要在Python可以导入的位置。通过添加.、..和/匮乏../..到sys.path中会对此有帮助。

autodoc可以将实际源代码中的大部分文档都包含进来,甚至还可以单独挑选某个模块或方法生成文档,而不是一个”非此即彼”的解决方案。通过直接关联源代码来维护文档,可以很容易地保证文档始终是最新的。
如果你正在开发一个Python库,那么通常需要以表格的形式来格式化你的API文档,表格中包含到各个模块的独立的文档页面的链接。sphinx.ext.autogen模块就是用来专门处理这一常见需要的。首先,需要在conf.py中启动它。

extensions = ['sphinx.ext.autodoc','sphinx.ext.autosummary']

现在就可以在一个.rst中加入类似下面的内容来自动为特定的模块生成TOC:

.. autosummary::
   mymodule
   mymodule.submodule

这会生成名为generated/mymodule.rst和generated/mymodule.submodule.rst的文件,其中会包含前面提到的autodoc指令。使用同样的格式,还可以指定希望模块API的哪部分包含在文档中。

通过特殊的doctest生成器,利用这个功能就像运行sphinx-build一样简单:

sphinx-build -b doctest doc/source doc/build

手动编写rst文件还是挺麻烦。不如直接在conf.py中写代码。自动生成.rst文件。

扩展Sphinx

针对其他HTTP框架,中Flask、Bottle和Tornado,可以使用sphinxcontrib.httpdomain。我个人的观点是,无论任何时候,只要能从代码中抽取信息帮助生成文档,都值得去做并且将其自动化。这比手工维护文档要好得多,尤其是可以利用自动发布工具(如Read The Docs)的时候。

第4章 分发

简史

  • distutils 是标准库的一部分,能处理简单的包的安装。
  • setuptools, 领先的包安装标准,曾经被废弃但现在又继续开发。
  • distribute 从0.7版本开始并入了setuptools。
  • distutils2(也称为packaginng)已经被废弃。
  • distlib 可能将来会取代distutils。

setuptools是目前分发库的主要选择,但在未来要对distlib保持关注。

使用pbr打包。

pbr使用的setup.py文件类似下面这样。

import setuptools
setuptools.setup(setup_requires=['pbr'],pbr=True)

就两行代码,非常简单。实际上安装所需要的元数据存储在setup.cfg文件中。

[metadata]
name=foobar
...
classifier = 
    Development Status :: 4 - Beta
    ...
[files]
packages = 
    foobar

Wheel格式

由setuptools引入的Egg格式只是一个有着不同扩展名的压缩文件。这一问题在官方安装标准最终敲定之后变得更加复杂,官方标准同已有标准并不兼容。

这了解决这些问题,PEP 427针对Python的分发包定义了新的标准,名为Wheel。已有wheel工具实现了这一格式。

python setup.py bdist_wheel

这条命令将在dist目录中创建.whl文件。和Egg格式类似,一个Wheel归档文件就是一个有着不同扩展名的压缩文件,只是Wheel归档文件不需要安装。可以通过在包名的后面加一个斜杠加载和运行代码:

$python wheel-0.21.0-py2.py3-none-any.whl/wheel -h
usage: wheel [-h]
    {keygen,sign,unsign,verify,unpack,install,install-scripts,convert,help}
positional arguments:
[...]

这其实是python自身支持的。

python foobar.zip

这等同于:

PYTHONPATH=foobar.zip python -m __main__

换句话说,程序中的main模块会自动从main.py中被导入。也可以通过在斜杠后面指定模块名字来导入__main__,就像Wheel:

python foobar.zip/mymod

这等同于:

PYTHONPATH=foobar.zip python -m mymod.__main__

包的安装

目前比较流行的pip。

pip install --user voluptuous

指定–user可以让pip把包安装在home目录中。这可以避免将包在系统层面安装而造成操作系统目录的污染。
提示:通过在~/.pip/pip.conf文件中添加download-cache选项,每次下载之前会先检查缓存。对于多个项目的虚拟环境有用。

可以用pip freeze 命令列出已安装的包。建议导入到requirements.txt
然后在其它地方用pip install -r requirements.txt 就可以重新下载软件包。

和世界分享你的成果

一旦有了合适的setup.py文件,很容易生成一个用来分发源代码tarball。只需要使用sdist命令即可。
python setup.py sdist
这会在你的源代码树的dist目录下创建一个tarball,这可以用来安装你的软件。

发布步骤:
1. 打开~/.pypirc文件并加入下列行:(用的测试服务器,正式发布需要修改)

[distutils]
index-servers = 
    testpypi

[testpypi]
username = <your username>
password = <your password>
repository = https://testpypi.python.org/pypi
  1. 在索引在注册项目。
python setup.py register -r testpypi
  1. 上传源代码发分tarball以及一个Wheel归档文件:
python  setup.py sdist upload -r testpypi
python setup.py bdist_wheel upload -r testpypi
  1. 测试。通过pip以及指定-i参数,可以测试是否上传成功。
pip install -i https://testpypy.python.org/pypi ceilometer
  1. 测试成功,就可以上传项目到PyPI主服务器了。步骤和前4一样。只是需要修改下配置文件~/.pypirc
[distutils]
index-servers = 
    pypi
    testpypi

[pypi]
username = <your username>
password = <your password>

[testpypi]
repository = https://testpypi.python.org/pypi
username = <your username>
password = <your password>

分别运行register和upload并配合参数-r pypi就能正确地将你的包上传以PyPI服务器了。

扩展点

可视化的入口点

要看到一个包中可用的入口点的最简单方法是使用一个叫entry_point_inspector的包。
安装后,它提供了名为epi的命令,可以从终端运行并能交互地发现某个安装包的入口点。

epi group list

输出结果:

Name
babel.checkers
babel.extractors
cliff.formatter.completion
cliff.formatter.list
cliff.formatter.show
console_scripts
distutils.commands
distutils.setup_keywords
egg_info.writers
epi.commands
lingua.extractors
paste.server_runner
pygments.lexers
python.templating.engines
setuptools.installation
stevedore.example.formatter
stevedore.test.extension

这个列表包含了console_scripts。
执行下列命令获得更多结果。

epi group show console_scripts

输出结果:

Name Module Member Distribution Error
wheel wheel.tool main wheel 0.24.0
sphinx-quickstart sphinx.quickstart main Sphinx 1.5.2
sphinx-autogen sphinx.ext.autosummar main Sphinx 1.5.2
y.generate
sphinx-build sphinx main Sphinx 1.5.2
sphinx-apidoc sphinx.apidoc main Sphinx 1.5.2
easy_install-3.5 setuptools.command.ea main setuptools 34.0.2
sy_install
easy_install setuptools.command.ea main setuptools 34.0.2
sy_install
pygmentize pygments.cmdline main Pygments 2.2.0
pip3.5 pip main pip 9.0.1
pip3 pip main pip 9.0.1
pip pip main pip 9.0.1
pbr pbr.cmd.main main pbr 1.10.0
mako-render mako.cmd cmdline Mako 1.0.6
gunicorn gunicorn.app.wsgiapp run gunicorn 19.4.5
gunicorn_paster gunicorn.app.pasterap run gunicorn 19.4.5 No module named
p ‘paste’
gunicorn_django gunicorn.app.djangoap run gunicorn 19.4.5
p
epi entry_point_inspector main entry-point-inspector
.app 0.1.1
pybabel babel.messages.fronte main Babel 2.3.4
nd
alembic alembic.config main alembic 0.8.10

使用控制台脚本

大多数项目都会有下面这样几行代码:

#!/usr/bin/python
import sys
import mysoftware

mysoftware.SomeClass(sys.argv).run()

这实际上是一个理想情况下的场景:许多项目在系统路径中会有一个非常长的脚本安装。但使用这样的脚本有一些主要的问题。

  • 没办法知道Python解释器的位置和版本。
  • 安装的二进制代码不能被其他软件或单元测试导入。
  • 很难确定安装在哪里。
  • 如何以可移植的方式进行安装并不明确(如是Unix还是Windows)。

setuptools有一个功能可以帮助我们解决这些问题,即console_scripts。console_scripts是一个入口点,能够用来帮助setuptools安装一个很小的程序到系统目录中,并通过它调用应用程序中某个模块的特定函数。

设想一个foobar程序,它由客户端和服务器端两部分组成。这两部分各自有自己独立的模块–foobar.client和foobar.server。

foobar/client.py

def main():
    print("Client started")

foobar/server.py

def main():
    print("Server started")

接下来可以在根目录添加下面的setup.py文件。

setup.py

from setuptools import setuptools
setup(
    name="foobar",
    version="1",
    author="Julien Danjou",
    author_email="julien@danjou.info",
    packages=["foobar"],
    entry_points={
        "console_scripts":[
            "foobard = foobar.server:main",
            "foobar = foobar.client:main",
        ]
    })

使用格式package.subpackage:function可以定义自己的入口点。

当运行python setup.py install时,setuptools会创建下面所示的脚本。

#!/usr/bin/python
# EASY-INSTALL-ENTRY-SCRIPT: 'foobar==1','console_scripts','foobar'
__requires__ = 'foobar==1'
import sys
from pkg_resources import load_entry_point

if __name__ == '__main__':
    sys.exit(load_entry_point('foobar==1','console_scripts','foobar')())

这段代码会扫描foobar包的入口点并从console_scripts目录中抽取foobar键,从而定位并运行相应的函数。

使用插件和驱动程序

可以使用pkg_resources从自己的Python程序中发现和加载入口点文件。
在本节中,我们将创建一个cron风格的守护进程,它通过注册一个入口点到pytimed组中即可允许任何Python程序注册一个每隔几秒钟运行一次的命令。该入口点指向的属性应该是一个返回number_of_seconds和callable的对象。

下面是一个使用pkg_resources发现入口点的pycrond实现。

pytimed.py

import time
def main():
    seconds_passed = 0
    while True:
        for entry_point in pkg_resources.iter_entry_points('pytimed'):
            try:
                seconds, callabel = entry_point.load()
            except:
                pass
            else:
                if seconds_passed % seconds == 0:
                    callable()
        time.sleep(1)
        seconds_passed += 1

现在写另一个Python程序,需要周期性地调用它的一个函数。
hello.py

def print_hello():
    print('Hello,world!')
    
def say_hello():
    return 2, print_hello

使用合适的入口点注册这个函数。

setup.py

from setuptools import setup

setup(
    name="hello",
    version="1",
    packages=["hello"],
    entry_points = {
        "pytimed":[
            "hello = hello:say_hello",
        ],
    },)

现在如果运行pytimed脚本,将会看到屏幕上每两秒钟打印一次”Hello, world!”

>>> import pytimed
>>> pytimed.main()
Hello,world!
Hello,world!
Hello,world!
...

这一机制提供了巨大的可能性:它可以用来构建驱动系统、钩子系统以及简单而通用的扩展。
在每一个程序中手动实现这一机制是非常繁琐,不过幸运的是,已经有Python库可以处理这部分无聊的工作。

stevedore基于我们在前面例子中展示的机制提供了对动态插件的支持。使用stevedore实现上面的功能。

pytimed_stevedore.py

from stevedore.extension import ExtensionManager 
import time

def main():
    seconds_passed = 0
    while True:
        for extension in ExtensionManager('pytimed',invoke_on_load=True):
            try:
                seconds, callable = extension.obj
            except:
                pass
            else:
                if seconds_passed % seconds == 0:
                    callable()
        time.sleep(1)
        seconds_passed += 1

第5章 虚拟环境

关于虚拟环境的,倒是到处可见。我之前有过篇文章,总结了下。Python虚拟环境virtualenv

第6章 单元测试

单元测试,我得推荐下Flask Web开发 基于Python的Web应用开发实战,这书里的代码有好多。可以参考下。
这章单独放到了Python单元测试

第7章 方法和装饰器

关于方法和装饰器,我觉得看完python学习手册就可以了。讲的是丰富详细和细致。
综合了下,写了篇文章python方法和装饰器

第8章 函数式编程

之前不知道yield的send用法,这次知道了。
同样知道了不建议使用lambda(我之前就喜欢用lambda),而是可以用functools.partial和operator。
也知道了itertools提供了强大工具。
文章已发布到Python函数式编程

第9章 抽象语法树

这个东东是第一次接触。其它书里也没有看到。
建议学学。作者还提到了hy,使用python实现的lisp方言。
lisp是我打算学的东西。在Python学到一定程度后,我会学会它。
不想看书,看简单内容的可以看这里Python抽象语法树

第10章 性能与优化

过早地优化是万恶之源。
用好了Python,你不需要自己去实现各种数据结构。
譬如dict的get方法本身就提供了key不存时,返回默认值的功能。dict.get(key,default)
譬如两个set()相减是可以求得差集的。
譬如collections.defaultdict结构可以提供key不存在时,自动构造值的功能,而不是抛KeyError。
此外,collections模块提供了一些新的数据结构用来解决一些特定问题,如OrderedDict或者Counter。

Python性能分析有cProfile,timeit。
配合cProfile和pyprof2calltree可以图像化展示。
通过dis模块可以反编译Python代码,从而看到更多细节的东西。

Python已经提供了很多有用的数据结构,你应该去了解他,然后直接用,而不是自己实现一个。
譬如 说bisect模块,其包含了二分查找算法。
还有blist和bintree。

通过使用Python类的__slots__属性可以将内存使用率提升一倍,这意味着在创建大量简单对象时使用__slots__属性是有效且高效的选择。

namedtuple就是利用__slots__实现的限制属性的方法。
namedtuple继承自tuple,并增加了__slots__来限制类属性,而属性的访问其实是利用的property。

从Python3.3开始,functools模块提供了一个LRU缓存装饰器。它提供了对函数结果的内存缓存,该模块还提供了对缓存命中、缺失等的统计。

如果你觉得CPython比较慢,可以考虑用PyPy。它声称比CPython快3倍。不过他同样有GIL。而且你决定要用的话,最好一开始就用,以避免在后期支持时可能带来的大量工作。

最后介绍了memoryview技术。针对切片操作会复制整个内容从而导致的内存低效。
对于实现了缓冲区协议的对象,可以使用其memoryview类的构建函数去构造一个新的memoryview对象,它会引用原始的对象内存。

对详情感兴趣的可以移步Python专题之性能与优化

第11章 扩展与架构

一个应用程序的可扩展性、并发性和并行性在很大程度上取决于它的初始架构和设计的选择。如你所见,有一些范例(如多线程)在Python中被误用,而其他一些技术(如面向服务架构)可以产生更好的效果。

由于GIL的存在,在Python中用多线程并不是个好主意,可以考虑多进程和事件驱动开发模型。

关于用哪个事件驱动的包,有如下建议:

  1. 只针对Python2,可以考虑基于libev的库,如pyev
  2. 如果目标是同时支持Python2和Python3,最好使用能同时支持两个版本的库,如pyev。
  3. 如果只针对Python3, 那就用asyncio。

关于面向服务架构的建议:

  1. 对外的API使用HTTP服务。最好是REST风格的。
  2. 对内的API使用RPC服务。可以考虑AMQ协议。

使用消息队列,可以把服务做成分布式的。推荐的是ZeroMQ。

详情可以参考Python专题之扩展与架构

第12章 RDBMS和ORM

介绍了一下RDBMS和ORM的概念。
在写代码时,应该把RDBMS的数据模型考虑进去。
在Python中用的多的ORM库是SQLAlchemy。 管理数据库升降级的是alembic。
最后建议了一下ORM的使用时机。
有兴趣的话可以看下Python专题之RDBMS和ORM

第13章 Python3支持策略

关于移植应用的官方文档(http://zeromq.org/)是有的,但不建议不折不扣地参考它。

最好还是兼容py2和py3,然后有够用的单元测试。
通过tox,来测试两个版本。
tox -e py27, py35
根据提示的错误进行修改,重新运行tox,直到所有测试都通过为止。
Porting to Python3这本书给出了要支持Python3所需做修改的良好概述。

有个库six,提供了py2和py3的兼容写法,如要同时支持,可以考虑。
更多细节参考Python3支持策略

第14章 少即是多

单分发器

这个略了,lisp方面的概念,以后再了解。

上下文管理器

Python2.6引入的with语句。
实现了上下文管理协议的对象就能使用with语句。open函数返回的对象就支持这个协议。

with open("myfile", "r") as f:
    line = f.readline()

open返回的对象有两个方法,一个称为__enter__,另一个称为__exit__。它们分别在with块的开始和结束时被调用。

简单实现示例:

class MyContext(object):
    def __enter__(self):
        pass
        
    def __exit__(self, exc_type, exc_value, traceback):
        pass

这个可以参考python学习手册里描述的,摘抄如下

with/as语句的设计是作为常见try/finally用法模式的替代方案。就像try/finally语句,with/as语句也是用于定义必须执行的终止或”清理”行为,无论处理步骤中是否发生异常。
不过,和try/finally不同的是,with语句支持更丰富的基于对象的协议,可以为代码块定义支持进入和离开动作。

with语句的基本格式如下。

with expression [as varibalbe]:
    with-block

在这里的expression要返回一个对象,从而支持环境管理协议。

环境管理协议
以下是with语句实际的工作方式。

  1. 计算表达式,所得到的对象称为环境管理器,它必须有__enter____exit__方法。
  2. 环境管理器的__enter__方法会被调用。如果as子句存在,其返回值会赋值给as子句中的变量,否则,直接丢弃。这里需要重点注意,很多人在这里会犯错。
  3. 代码块中的嵌套的代码会执行。
  4. 如果with代码块引发异常,__exit__(type,value,traceback)方法就会被调用(带有异常细节)。这引起也是由sys.exc_info返回的相同值。如果此方法返回值为假,则异常会重新引发。否则,异常会终止。正常情况下异常是应该被重新引发,这样的话才能传递到with语句之外。 如果with代码块没有引发异常,__exit__方法依然会被调用,其type、value以及traceback参数以None传递。

contextlib标准库提供了contextmanager, 通过生成器构造__enter____exit__方法,从而简化了这一机制的实现。可以使用它实现自己的简单上下文管理器,如下所求:

import contextlib

@contextlib.contextmanager
def MyContext():
    yield

作者提供了个案例,为了防止程序员忘记在流水线对象中最后调用flush()方法。
使用了上下文管理器。

import contextlib

class Pipeline(object):
    def _publish(self, objects):
        pass
        
    def _flash(self):
        pass
    
    @contextlib.contextmanager
    def publisher(self):
        try:
            yeild self._publish
        finally:
            self._flush()

现在用户使用以下代码就好了。

pipeline = Pipeline()
with pipeline.publisher() as publisher:
    publisher([1,2,3,4])

另外,是可以同时使用多个上下文管理器的。

同时打开两个文件

with open("file1", "r") as source:
    with open("file2", "w") as destination:
        destination.write(source.read())

with语句可以支持多个参数的。上述代码可以改为

with open("file1", "r") as source, open("file2", "w") as destination:
    destination.write(source.read())

python第三方模块psutil系统管理工具介绍

python第三方模块psutil系统管理工具介绍

psutil安装

pustil可以通过pip install psutil简单的安装。

接下来就是举例,用psutil完成的一些功能。

psutil使用

获取物理内存总大小和已使用大小

>>> import psutil
>>> mem = psutil.virtual_memory()
>>> mem.total,mem.used
(8589934592, 7704367104)
>>>

good,我的系统是mac,没有free命令。拿到结果了,做为一个兼容的系统管理工具不错。

CPU信息

Linux操作系统的CPU利用率有以下几个部分:

  • Used Time, 执行用户进程的时间百分比;
  • System Time, 执行内核进程和中断的时间百分比;
  • WaitIO, 由于IO等待而使CPU处于idle(空闲)状态的时间百分比;
  • Idle, CPU处于idle状态的时间百分比。
>>> import psutil
>>> psutil.cpu_times()
scputimes(user=1402284.92, nice=0.0, system=1469626.9, idle=12627047.52)
>>> psutil.cpu_times(percpu=True)
[scputimes(user=502393.89, nice=0.0, system=562658.91, idle=2809843.07), scputimes(user=184752.81, nice=0.0, system=125993.21, idle=3564001.33), scputimes(user=525198.26, nice=0.0, system=645489.72, idle=2704061.18), scputimes(user=189962.29, nice=0.0, system=135537.72, idle=3549245.73)]
>>> psutil.cpu_count()
4
>>> psutil.cpu_count(logical=False)
2

在开发的时候,我time命令来衡量程序的性能。

time python test.py > /dev/null
python test.py > /dev/null  4.31s user 0.16s system 98% cpu 4.534 total

我这里test.py只是简单地循环输出,当system占比比较高的时候,可能是系统调用过多。系统调用涉及到用户态和内核态的切换,消耗会高。优化的方向之一是减少系统调用。

内存信息

Linux系统的内存利用率信息有:

  • total 内存总数
  • used 已使用内存数
  • free 空闲的内存数
  • buffers 缓冲使用数
  • cache 缓存使用数
  • wap 交换分区使用数
>>> import psutil
>>> psutil.virtual_memory()
svmem(total=8589934592, available=2058379264, percent=76.0, used=8028037120, free=20783104, active=2052898816, inactive=2037596160, wired=3937542144)
>>> psutil.swap_memory()
sswap(total=8589934592, used=7281311744, free=1308622848, percent=84.8, sin=618526040064, sout=25876324352)
>>>

磁盘信息

在系统的所有磁盘信息中,我们更加关注磁盘的利用率及IO信息,其中磁盘利用率使用psutil.disk_usage方法获取。
磁盘IO信息包括:

  • read_count 读IO数
  • write_count 写IO数
  • read_bytes IO读字节数
  • write_bytes IO写字节数
  • read_time 磁盘读时间
  • write_time 磁盘写时间
>>> psutil.disk_partitions() #获得磁盘分区信息
[sdiskpart(device='/dev/disk1', mountpoint='/', fstype='hfs', opts='rw,local,rootfs,dovolfs,journaled,multilabel')]
>>> psutil.disk_usage('/')#获取分区的使用情况
sdiskusage(total=249769230336, used=226267439104, free=23239647232, percent=90.7)
>>> psutil.disk_io_counters()
sdiskio(read_count=58295513, write_count=57111574, read_bytes=3269424444416, write_bytes=3475279374848, read_time=83685913, write_time=38281762)
>>> psutil.disk_io_counters(perdisk=True)
{'disk0': sdiskio(read_count=58294822, write_count=57111574, read_bytes=3269288018432, write_bytes=3475279374848, read_time=83656259, write_time=38281762), 'disk2': sdiskio(read_count=104, write_count=0, read_bytes=19758592, write_bytes=0, read_time=3970, write_time=0), 'disk7': sdiskio(read_count=94, write_count=0, read_bytes=19736064, write_bytes=0, read_time=4853, write_time=0), 'disk3': sdiskio(read_count=105, write_count=0, read_bytes=19719680, write_bytes=0, read_time=3505, write_time=0), 'disk4': sdiskio(read_count=104, write_count=0, read_bytes=19535360, write_bytes=0, read_time=3881, write_time=0), 'disk5': sdiskio(read_count=100, write_count=0, read_bytes=19777024, write_bytes=0, read_time=4920, write_time=0), 'disk6': sdiskio(read_count=100, write_count=0, read_bytes=19525120, write_bytes=0, read_time=4214, write_time=0), 'disk8': sdiskio(read_count=94, write_count=0, read_bytes=19455488, write_bytes=0, read_time=4365, write_time=0)}
>>>

在负载高的时候,需要分析出cpu问题还是io问题。cpu密集型问题和io密集型问题解决方案不一样。

网络信息

系统的网络信息与磁盘IO累死,涉及几个关键点

  • bytes_sent 发送节字数
  • bytes_recv 接收字节数
  • packets_sent 发送数据包数
  • packets_recv 接收数据包数

可以通过psutil.net_io_counters()方法获取

>>> psutil.net_io_counters()
snetio(bytes_sent=18564432940, bytes_recv=80575424616, packets_sent=96109565, packets_recv=105568905, errin=0, errout=0, dropin=0, dropout=0)

其它系统信息

除了前面介绍的几个获取系统基本信息的方法,psutil模块还支持获取用户登录、开机时间等信息,如下:

>>> psutil.users()
[suser(name='maynard', terminal='console', host=None, started=1474462720.0), suser(name='maynard', terminal='ttys000', host=None, started=1487756672.0), suser(name='maynard', terminal='ttys001', host=None, started=1488096000.0), suser(name='maynard', terminal='ttys002', host=None, started=1488118272.0), suser(name='maynard', terminal='ttys003', host=None, started=1487824512.0), suser(name='maynard', terminal='ttys004', host=None, started=1487917312.0)]
>>> import datetime
>>> psutil.boot_time()
1474462336.0
>>> datetime.datetime.fromtimestamp(psutil.boot_time()).strftime("%Y-%m-%d %H:%M:%S")
'2016-09-21 20:52:16'
>>>

进程信息

psutil模块在获取进程信息方面提供了很好的支持,包括使用psutil.pids()方法获取所有进程PID,使用psutil.Process()方法获取单个进程的名称、路径、状态、系统资源利用率等信息。

>>> import psutil
>>> psutil.pids() #列出所有进程PID,可以通过ps命令得到
[69242, 69241, 69238, 69113 68615...]
>>> p = psutil.Process(69113) #实例化一个Process对象,参数为一进程PID
>>> p.name() #进程名
'swcd'
>>> p.exe() #进程bin路径
'/usr/libexec/swcd'
>>> p.cwd() #进程工作目录绝对路径
'/'
>>> p.status() #进程状态
'running'
>>> p.create_time()
1488189481.269264
>>> p.uids()#进程uid信息
puids(real=501, effective=501, saved=501)
>>> p.gids()#进程gid信息
puids(real=20, effective=20, saved=20)
>>> p.cpu_times()
pcputimes(user=0.057164948, system=0.037118848, children_user=0, children_system=0)
>>> p.memory_percent()
0.07877349853515625
>>> p.memory_info()
pmem(rss=6766592, vms=2573402112, pfaults=3232, pageins=22)
>>> p.connections()
[]
>>> p.num_threads()
4

Python第三方模块IPy介绍

Python第三方模块IPy介绍

安装

pip install ipy

IP地址、网段的基本处理

IPy模块包含IP类,使用它可以方便处理绝大部分格式为IPv6及IPv4的网络和地址。
比如通过version方法就可以区分出IPv4与IPv6,如:

>>> import IPy
>>> IPy.IP("10.0.0.0/8").version()
4
>>> IPy.IP("::").version()
6
>>>

通过指定的网段输出该网段的IP个数及所有IP地址清单

>>> ip = IPy.IP('192.168.10.0/24')
>>> print(ip.len())
256
>>> for x in ip:
...     print(x)
...
192.168.10.0
192.168.10.1
192.168.10.2
192.168.10.3
192.168.10.4
192.168.10.5
192.168.10.6
192.168.10.7
192.168.10.8
...
192.168.10.255

下面介绍IP类几个常见的方法,包括反向解析名称、IP类型、IP转换等。

>>> from IPy import IP
>>> ip = IP('192.168.1.20')
>>> ip.reverseNames() #反向解析地址格式
['20.1.168.192.in-addr.arpa.']
>>> ip.iptype() #192.168.1.20为私网类型'PRIVATE'
'PRIVATE'
>>> IP('8.8.8.8').iptype() #8.8.8.8为公网类型
'PUBLIC'
>>> IP('8.8.8.8').int() #转换成整型格式
134744072
>>> IP('8.8.8.8').strHex()#转换成十六制格式
'0x8080808'
>>> IP('8.8.8.8').strBin()#转换成二进制格式
'00001000000010000000100000001000'
>>> print(IP(0x8080808))#十六进制转成IP格式
8.8.8.8
>>>

IP方法也支持网络地址的转换,例如根据IP与掩码生产网段格式,如下

>>> from IPy import IP
>>> print(IP('192.168.1.0').make_net('255.255.255.0'))
192.168.1.0/24
>>> print(IP('192.168.1.0/255.255.255.0',make_net=True))
192.168.1.0/24
>>> print(IP('192.168.1.0-192.168.1.255',make_net=True))
192.168.1.0/24

也可以通过strNormal方法指定不同wantprefixlen参数值以定制不同输出类型的网段。
输出类型为字符串,如下:

>>> IP('192.168.1.0/24').strNormal(0)
'192.168.1.0'
>>> IP('192.168.1.0/24').strNormal(1)
'192.168.1.0/24'
>>> IP('192.168.1.0/24').strNormal(2)
'192.168.1.0/255.255.255.0'
>>> IP('192.168.1.0/24').strNormal(3)
'192.168.1.0-192.168.1.255'
>>>

有时候我们想比较两个网段是否存在包含、重叠等关系。IPy支持类似于数据型数据的比较,以帮助IP对象进行比较,如:

P('10.0.0.0/24') < IP('12.0.0.0/24')
True

判断IP地址和网段是否包含于另一个网段中,如:

>>> '192.168.1.100' in IP('192.168.1.0/24')
True
>>> IP('192.168.1.0/24') in IP('192.168.0.0/16')
True

判断两个网段是否存在重叠,采用IPy提供的overlaps方法,如:

>>> IP('192.168.0.0/23').overlaps('192.168.1.0/24')
1#重叠
>>> IP('192.168.1.0/24').overlaps('192.168.2.0')
0#不重叠
>>>

综合示例:根据输入的IP或子网返回网络、掩码、广播、反向解析、子网数、IP类型等信息。

#!/usr/bin/env python

from IPy import IP

ip_s = input("Please input an IP or net-range:")

ips = IP(ip_s)

if len(ips) > 1:
    print("net:%s" % ips.net())
    print("netmast:%s" % ips.netmask())
    print("broadcast:%s" % ips.broadcast())
    print("reverse address:%s" % ips.reverseNames()[0])
    print("subnet:%s" % len(ips))
else:
    print('reverse address:%s' % ips.reverseNames()[0])


print("hexadecimal:%s" % ips.strHex())
print("binary ip:%s" % ips.strBin())
print("iptype:%s" % ips.iptype())

输出结果如下:

python simple1.py
Please input an IP or net-range:192.168.1.0/24
net:192.168.1.0
netmast:255.255.255.0
broadcast:192.168.1.255
reverse address:1.168.192.in-addr.arpa.
subnet:256
hexadecimal:0xc0a80100
binary ip:11000000101010000000000100000000
iptype:PRIVATE
(venv) ➜ mgr python simple1.py
Please input an IP or net-range:192.168.1.20
reverse address:20.1.168.192.in-addr.arpa.
hexadecimal:0xc0a80114
binary ip:11000000101010000000000100010100
iptype:PRIVATE

Python第三方模块dnspython介绍

Python第三方模块dnspython介绍

安装

pip install dnspython

模块域名解析方法介绍

dnspython提供了一个DNS解析器类–resolver,使用它的query方法来实现域名的查询功能。query方法定义如下:

query(self, qname, rdtype=1, rdclass=1, tcp=False, source=None, raise_on_no_answer=True, source_port=0)

其中,qname参数为查询的域名。rdtype参数用来指定RR资源的类型,常用的有以下几种:

  • A记录,将主机名转换成IP地址;
  • MX记录,邮件交换记录,定义邮件服务器的域名;
  • CNAME记录,指别名记录,实现域名间的映射;
  • NS记录,标记区域的域名服务器及授权子域;
  • PTR记录,反向解析,与A记录相反,将IP转换成主机名;
  • SOA记录,SOA标记,一个起始授权区的定义。

rdclass参数用于指定网络类型,可选的值有IN、CH与HS,其中IN为默认,使用最广泛。
tcp参数用于指定查询是否启用TCP协议,默认为False(不启用)。
source与source_port参数作为指定查询源地址与端口,默认值为查询设备IP地址和0。
raise_on_no_answer参数用于指定当查询无应答时是否触发异常,默认为True。

举例

A记录

#!/usr/bin/env python
import dns.resolver

domain = input("please input an domain:")
A = dns.resolver.query(domain,'A')
for i in A.response.answer:
    for j in i.items:
        print(j.address)

测试结果:

(venv) ➜ dnspython python simple1.py
please input an domain:go2live.cn
59.110.85.65

MX记录

#!/usr/bin/env python
import dns.resolver

domain = input("please input an domain:")
MX = dns.resolver.query(domain, 'MX')
for i in MX:
    print('MX preference=%s, mail exchanger=%s' % (i.preference, i.exchange))

测试结果:

(venv) ➜ dnspython python simple2.py
please input an domain:163.com
MX preference=10, mail exchanger=163mx02.mxmail.netease.com.
MX preference=10, mail exchanger=163mx03.mxmail.netease.com.
MX preference=10, mail exchanger=163mx01.mxmail.netease.com.
MX preference=50, mail exchanger=163mx00.mxmail.netease.com.

NS记录

#!/usr/bin/env python
import dns.resolver

domain = input("please input an domain:")
ns = dns.resolver.query(domain, 'NS')
for i in ns.response.answer:
    for j in i.items:
        print(j.to_text())

测试结果:

(venv) ➜ dnspython python simple3.py
please input an domain:baidu.com
ns4.baidu.com.
ns3.baidu.com.
ns7.baidu.com.
dns.baidu.com.
ns2.baidu.com.

需要注意,域名需要是一级域名。

CNAME记录

#!/usr/bin/env python
import dns.resolver

domain = input("please input an domain:")
cname = dns.resolver.query(domain, 'CNAME')
for i in cname.response.answer:
    for j in i.items:
        print(j.to_text())

测试结果:

(venv) ➜ dnspython python simple4.py
please input an domain:img.go2live.cn
iduxqy8.qiniudns.com.

我的网站把图片资源放到了七牛的dns上。。后面改到了阿里云。

监控代码

步骤:
1. 通过dns解析获得ip地址列表
2. 通过http请求获取网站服务是否正常。

#!/usr/bin/env python
import dns.resolver
import os
import requests


iplist = []
appdomain = "www.a.shifen.com"


def get_iplist(domain=""):
    try:
        A = dns.resolver.query(domain, 'A')
    except Exception as e:
        print("dns resolver error:", str(e))
        return

    for i in A.response.answer:
        for j in i.items:
            iplist.append(j.address)
    return True


def checkip(ip):
    checkurl = ip+":80"
    try:
        r = requests.get('http://'+checkurl)
        if r.status_code == 200  and '<!doctype html>' in r.text.lower():
            print(ip + " [ok]")
        else:
            print(ip + " [Error] ")
    except Exception as e:
        print(e)


if __name__ == '__main__':
    if get_iplist(appdomain) and len(iplist) > 0:
        for ip in iplist:
            checkip(ip)
    else:
        print("dns resolver error.")

输出结果:

(venv) ➜ dnspython python simple5.py
58.217.200.112 [ok]
58.217.200.113 [ok]

域名不能用baidu.com, 因为baidu.com是www.a.shifen.com的别名。
也说明这个程序并不健壮。

oop设计原则SOLID详解

oop设计原则SOLID详解

简介

面向对象编程设计原则有个总结,叫SOLID原则。
再具体下去就是具体的设计模式了。

S=single Responsibility Principle 单一职责原则

动机

在这里,责任被认为是改变的一个原因。这个原则表明,如果我们有两个原因要修改一个类,我们必须将功能分为两个类。每个类将只处理一个责任,如果将来我们需要做一个更改,我们将在相应的类中处理。 当我们需要在具有更多职责的类中进行更改时,更改可能会影响与类的其他职责相关的其他功能。

单一职责原则是一个简单和直观的原则,但在实践中有时很难正确运用。

意图

一个类,应该仅有一个引起它变化的原因。

举例

让我们假设我们需要一个对象来保存电子邮件。我们将使用从下面的示例中的IEmail接口。看起来没啥问题。但仔细看看,我们可以看到,我们的IEmail接口和Email类有2个责任(改变的原因)。
一个是在一些电子邮件协议如pop3或imap中使用该类。如果必须支持其他协议,则应以另一种方式对对象进行序列化,并且应添加代码以支持新协议。
另一个是Content字段,即使内容是字符串,也许我们将来可能支持HTML或其他格式。

如果我们只保留一个类,每一个职责的改变可能会影响到另一个:

  • 添加新协议将创建需要为每个类型的字段添加用于解析和序列化内容的代码。
  • 添加新的内容类型(如html)使我们为每个协议添加代码。

//单一责任原则 - 错误示例

interface IEmail { 
    public void setSender(String sender); 
    public void setReceiver(String receiver); 
    public void setContent(String content); 
} 

class Email implements IEmail { 
    public void setSender(String sender){// set sender; } 
    public void setReceiver(String receiver){//设置接收器; } 
    public void setContent(String content){//设置内容; } 
}

我们可以创建一个新的接口和类,称为IContent和Content来分担责任。每个类只有一个责任给我们更灵活的设计:

  • 添加新协议只会导致电子邮件类中的更改。
  • 添加新类型的内容支持导致仅在Content类中的更改。
//单一责任原则 - 好的示例
interface IEmail { 
    public void setSender(String sender); 
    public void setReceiver(String receiver); 
    public void setContent(IContent content); 
} 

interface Content { 
    public String getAsString(); //用于序列化
} 

class Email implements IEmail { 
    public void setSender(String sender){// set sender; } 
    public void setReceiver(String receiver){//设置接收器; } 
    public void setContent(IContent content){//设置内容; } 
}

结论

单一责任原则代表在应用程序的设计阶段识别类的一种好方法,它提醒您想一个类可以发展的所有方式。只有当应用程序应该如何工作的全部情况都很好理解时,才能实现良好的责任分离。

O=open close 开闭原则

开放-封闭原则,是说软件实例(类、模块、函数等等)应该可以扩展,但是不可修改。

这个原则其实是有两个特征,一个是说‘对于扩展是开放的(open for extension)’,另一个是说‘对于更改是封闭的(Closed for modification)’

动机

聪明的应用程序设计和代码实现应该考虑到在应用程序的开发和维护阶段会有频繁的更改。通常,当向应用程序添加新功能时,会涉及到许多更改。应该将现有代码中的这些更改最小化,因为假设现有代码已经进行单元测试,并且已编写代码中的更改可能以不必要的方式影响现有功能。

开闭原则指出该代码的设计和实现,应该能让新功能的加入以现有的代码最小的变化来完成。设计应该允许添加新功能作为新类,尽可能保持现有代码不变。

意图

像类,模块和函数的软件实体应该是开放的扩展,但关闭修改

例子

下面是违反开放关闭原则的示例。它实现了一个图形编辑器处理不同形状的绘图。很明显,它不遵循开放关闭原则,因为GraphicEditor类必须为每个必须添加的新形状类进行修改。有几个缺点:

  • 对于每个新形状添加的GraphicEditor的单元测试应该重做。
  • 当添加新类型的形状时,添加它的时间将会很长,因为添加它的开发人员应该理解GraphicEditor的逻辑。
  • 添加新形状可能以不期望的方式影响现有功能,即使新形状完美地工作。

// Open-Close Principle  -  Bad example 
class GraphicEditor { 
 
    public void drawShape(Shape s){ 
        if(s.m_type == 1)
            drawRectangle(s); 
        else if(s.m_type == 2)
            drawCircle(s); 
    } 
    public void drawCircle(Circle r){...} 
    public void drawRectangle(Rectangle r){....} 
} 
 
class Shape { 
    int m_type; 
} 
 
class Rectangle extends Shape { 
    Rectangle(){ 
        super.m_type = 1; 
    } 
} 
 
class Circle extends Shape { 
    Circle(){ 
        super.m_type = 2; 
    } 
}

下面是支持开放关闭原则的示例。在新设计中,我们在GraphicEditor中使用抽象draw()方法绘制对象,同时在具体形状对象中来实现。使用开放关闭原则避免了先前设计的问题,因为在添加新的形状类时不会更改GraphicEditor:

  • 无需单元测试。
  • 无需了解GraphicEditor的源代码。
  • 因为绘图代码被移动到具体的形状类,当添加新的功能时,降低了影响旧功能的风险。

// Open-Close Principle  -  Good example 
class GraphicEditor { 
    public void drawShape(Shape s){ 
        s.draw(); 
    } 
} 
 
class Shape { 
    abstract void draw(); 
} 
 
class Rectangle extends Shape { 
    public void draw(){ 
        //绘制矩形
    } 
}

结论

OCP只是一个原则。做出灵活的设计需要花费额外的时间和精力,并且它引入了新的抽象层次,增加了代码的复杂性。因此,这个原则应该应用于最有可能改变的领域。

有许多设计模式可以帮助我们扩展代码而不改变它。例如装饰者模式帮助我们遵循开放原则。此外,工厂方法或观察者模式可用于设计一个易于随现有代码中的最小变化而改变的应用程序。

L=LSP(Liskov’s Substitution Principle) 里氏代换原则

子类型必须能够替换它们的父类型
一个软件实体如果使用的是一个父类的话,那么一定适用于其子类,而且它察觉不出父类对象和子类对象的区别。也就是说,在软件里面,把父类都替换成它的子类,程序的行为没有变化。

动机

一直以来,我们在设计一个程序模块,我们创建一些类层次结构。然后我们通过扩展一些类来创建一些派生类。

我们必须确保新的派生类只是扩展而不替换旧类的功能。否则,新类在现有程序模块中使用时会产生不良影响。

Likov的替换原则声明,如果程序模块使用Base类,那么对Base类的引用可以替换为Derived类,而不会影响程序模块的功能。

意图

派生类型必须能够完全替代其基本类型。

例子

下面是违反Likov替代原则的典型例子。在示例中使用2个类:Rectangle和Square。让我们假设Rectangle对象在应用程序中的某个地方使用。我们扩展应用程序并添加Square类。正方形类由工厂模式返回,基于一些条件,我们不知道将返回什么类型的对象。但我们知道这是一个矩形。我们得到矩形对象,宽度设置为5,高度设置为10,得到面积。对于宽度为5和高度为10的矩形,面积应为50,而结果却是100。



//违反Likov的替代原则
class Rectangle
{
    protected int m_width;
    protected int m_height;

    public void setWidth(int width){
        m_width = width;
    }}

    public void setHeight(int height){
        m_height = height;
    }}


    public int getWidth(){
        return m_width;
    }}

    public int getHeight(){
        return m_height;
    }}

    public int getArea(){
        return m_width * m_height;
    }}  
}}

class Square extends Rectangle 
{
    public void setWidth(int width){
        m_width = width;
        m_height = width;
    }}

    public void setHeight(int height){
        m_width = height;
        m_height = height;
    }}

}}

class LspTest
{
    private static Rectangle getNewRectangle()
    {
        //它可以是一些工厂返回的对象... 
        return new Square();
    }}

    public static void main(String args [])
    {
        Rectangle r = LspTest.getNewRectangle();
        
        r.setWidth(5);
        r.setHeight(10);
        //用户知道r是一个矩形。 
        //假设他能够为基类设置宽度和高度

        System.out.println(r.getArea());
        //现在他惊讶地发现该面积是100而不是50。
    }}
}}

结论

这个原则只是开放关闭原则的一个扩展,这意味着我们必须确保新的派生类是扩展基类而不改变它们的行为。

I=Interface Segregation Principle 接口隔离原则

动机

当我们设计一个应用程序时,我们应该注意如何使一个包含多个子模块的模块抽象化。考虑由类实现的模块,我们可以在接口中完成系统的抽象。但是如果我们想扩展我们的应用程序添加另一个模块,它只包含原始系统的一些子模块,我们被迫实现完整的接口和写一些虚拟方法。这样的接口被命名为fat接口或污染的接口。具有接口污染不是一个好的解决方案,并且可能在系统中引起不适当的行为。

该接口分离原则规定,客户不应该被强迫来实现它们不使用的接口。基于一组方法,每个方法服务一个子模块,而不是一个胖接口许多小接口是优选的。

意图

不应该强制客户端依赖于他们不使用的接口。

例子

下面是一个违反接口隔离原则的例子。我们有一个经理类,代表管理工人的人。我们有两种类型的工人一些平均和一些非常有效的工人。这两种类型的工人工作,他们需要每天吃午饭。但现在有些机器人来到他们工作的公司,但他们不吃,所以他们不需要吃午饭。一个新的机器人类需要实现IWorker接口,因为机器人工作。在另一方面,不必实施它,因为他们不吃。

这就是为什么在这种情况下,IWorker被认为是一个污染的接口。

如果我们保持当前的设计,新的Robot类被迫实现eat方法。我们可以写一个不做任何事情的虚拟类(假设每天吃1秒),并且在应用程序中可能会产生不良效果(例如,管理者看到的报告会报告更多的午餐,而不是人数)。

根据接口分离原则,灵活的设计不会有接口污染。在我们的情况下,IWorker接口应该分为两个不同的接口。


// interface segregation principle - bad example
interface IWorker {
    public void work();
    public void eat();
}

class Worker implements IWorker{
    public void work() {
        // ....working
    }
    public void eat() {
        // ...... eating in launch break
    }
}

class SuperWorker implements IWorker{
    public void work() {
        //.... working much more
    }

    public void eat() {
        //.... eating in launch break
    }
}

class Manager {
    IWorker worker;

    public void setWorker(IWorker w) {
        worker=w;
    }

    public void manage() {
        worker.work();
    }
}

下面是支持接口隔离原则的代码。通过在2个不同的接口中拆分IWorker接口,新的Robot类不再强制实现eat方法。此外,如果我们需要另一个功能的机器人像充电,我们创建另一个有充电方法的接口IRechargeble。


// interface segregation principle - good example
interface IWorker extends Feedable, Workable {
}

interface IWorkable {
    public void work();
}

interface IFeedable{
    public void eat();
}

class Worker implements IWorkable, IFeedable{
    public void work() {
        // ....working
    }

    public void eat() {
        //.... eating in launch break
    }
}

class Robot implements IWorkable{
    public void work() {
        // ....working
    }
}

class SuperWorker implements IWorkable, IFeedable{
    public void work() {
        //.... working much more
    }

    public void eat() {
        //.... eating in launch break
    }
}

class Manager {
    Workable worker;

    public void setWorker(Workable w) {
        worker=w;
    }

    public void manage() {
        worker.work();
    }
}

结论

如果设计已经完成,胖接口可以使用适配器模式进行隔离。
像每个原则一样接口分离原则是一个原则,需要花费额外的时间和精力在设计期间应用它,并增加代码的复杂性。
但它产生灵活的设计。
如果我们要过分地使用应用它,它将导致包含许多只有单个方法接口的代码,因此应该基于经验和常识来识别代码将来可能在哪些该地需要扩展。

D= Dependency依赖反转原则

抽象不应该依赖细节,细节应该依赖于抽象。
说白了,就是要针对接口编程,不要对实现编程

动机

当我们设计软件应用程序时,我们可以考虑低级类实现基本和主要操作(磁盘访问,网络协议,…)的类和高级类封装复杂逻辑(业务流,…)的类。最后一个依赖于低级类。实现这种结构的一种自然方式是编写低级类,一旦我们让它们编写复杂的高级类。由于高级类是根据其他定义的,这似乎是合理的做法。但这不是一个灵活的设计。如果我们需要替换一个低级类会发生什么?
让我们来看一个复制模块的典型例子,它从键盘读取字符并将它们写入打印机设备。包含逻辑的高级类是复制类。低级类是KeyboardReader和PrinterWriter。

在一个糟糕的设计中,高级类直接使用并且在很大程度上依赖于低级类。在这种情况下,如果我们要更改设计以将输出定向到一个新的FileWriter类,我们必须在Copy类中进行更改。(让我们假设它是一个非常复杂的类,有很多逻辑,真的很难测试)。

为了避免这样的问题,我们可以在高级类和低级类之间引入抽象层。由于高级模块包含复杂的逻辑,它们不应该依赖于低级模块,因此不应该基于低级模块来创建新的抽象层。低级模块将基于抽象层创建。

根据这个原则,设计类结构的方法是从高级模块开始到低级模块:
高级类 – >抽象层 – >低级类

意图

  1. 高级模块不应该依赖于低级模块。两者都应该依赖于抽象。
  2. 抽象不应取决于细节。细节应该取决于抽象。

例子

下面是违反依赖反转原则的示例。我们有经理类,它是一个高级类,而低级类称为Worker。我们需要在我们的应用程序中添加一个新模块,以模拟由新的专业工作者雇用决定的公司结构的变化。我们为此创建了一个新类SuperWorker。

让我们假设Manager类相当复杂,包含非常复杂的逻辑。现在我们必须改变它,以引入新的SuperWorker。让我们看看缺点:

  • 我们必须更改Manager类(记住它是一个复杂的,这将涉及时间和精力进行更改)。
  • 某些来自管理器类的当前功能可能会受到影响。
  • 单元测试应重做。

所有这些问题可能需要很多时间来解决,它们可能在旧的功能中引入新的错误。如果应用程序是按照依赖性反转原则设计的,情况会有所不同。这意味着我们设计manager类,一个IWorker接口和实现IWorker接口的Worker类。当我们需要添加SuperWorker类时,我们所要做的就是为其实现IWorker接口。现有类中没有其他更改。

//依赖反转原理 - 错误的示例

class Worker { 

    public void work(){ 

        // .... working 

    } 

} 



class Manager { 

    Worker worker; 



    public void setWorker(Worker w){ 
        worker = w; 
    } 

    public void manage(){ 
        worker.work(); 
    } 
} 

class SuperWorker { 
    public void work(){ 
        // .... working more more 
    } 
}

下面是支持依赖反转原理的代码。在这个新设计中,通过IWorker接口添加了一个新的抽象层。现在来自上面的代码的问题被解决了(考虑到高级逻辑没有变化):

  • 在添加SuperWorkers时,Manager类不需要更改。
  • 最小化风险以影响Manager类中的旧功能,因为我们不更改它。
  • 无需为Manager类重做单元测试。
//依赖反转原则 - 好例子
interface IWorker { 
    public void work(); 
} 

class Manager implements IWorker { 
    public void work(){ 
        // .... working 
    } 
} 

class SuperWorker implements IWorker { 
    public void work(){ 
        // .... working more more 
    } 
} 

class Manager { 
    IWorker worker; 

    public void setWorker(IWorker w){ 
        worker = w; 
    } 

    public void manage(){ 
        worker.work(); 
    } 
}

结论

当应用这个原则时,它意味着高级类不直接与低级类工作,他们使用接口作为抽象层。在这种情况下,不能使用运算符new来在高级类(如果必要)内实例化新的低级对象。相反,可以使用一些Creational设计模式,例如Factory Method,Abstract Factory,Prototype。

模板设计模式是应用DIP原理的示例。

当然,使用这个原则意味着更多的努力,将导致更多的类和接口维护,在一些词语中更复杂的代码,但更灵活。这个原则不应盲目地应用于每个类或每个模块。如果我们有一个更有可能在未来保持不变的类功能,则不需要应用这个原则。

算法分析

算法分析

算法简介

简单来说,所谓算法就是定义良好的计算过程,它取一个或一组值作为输入,并产生出一个或一组值作为输出。亦即,算法就是一系列的计算步骤,用来将输入数据转换成输出结果。

算法分析

算法分析是关于计算机程序性能与资源利用的研究。
计算时间是一种有限的资源,存储空间也是一种有限的资源。
算法尤其关注性能, 这是门关于性能的学问。

循环不变化

循环不变化主要用来帮助我们理解算法的正确性。对于循环不变式,必须证明他的三个性质:

  • 初始化: 它在循环的第一轮迭代开始之前,应该是正确的。
  • 保持: 如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。
  • 终止:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。

最坏情况和平均情况分析

一般考察算法的最坏情况运行时间。

渐近分析

淅近分析的基本思路是忽略掉那些依赖于机器的常量, 以及,不去检查实际的运行时间,而是关注运行时间的增长。

当n->∞,有 ( \Theta(n^3) < \Theta(n^2) < \Theta(n) < \Theta(lgn) < \Theta(1))
此处<表示消耗时间少,效率更高。

简化分析方法

从极限角度看,我们只关心算法运行时间如何随着输入规模的无限增长而增长。

渐近确界
( \Theta(g(n)) = {f(n): 存在正常数c_1,c_2和n_0, 使对所有的n \geq n_0, 有0 \leq c_1g(n) \leq f(n) \leq c_2g(n) } )
(\Theta(g(n))是一个集合,可以写成f(n) in \Theta(g(n)), 表示f(n)是\Theta(g(n))的元素,不过,通常写成f(n) = \Theta(g(n)) ) 我们说g(n)是f(n)的一个渐近边界。

渐近上界
( O(g(n)) = {f(n): 存在正常数c和n_0, 使对所有的n \geq n_0, 有0 \leq f(n) \leq cg(n) } )

渐近下界
( \Omega(g(n)) = {f(n): 存在正常数c和n_0, 使对所有的n \geq n_0, 有0 \leq cg(n) \leq f(n) } )

o记号
( o(g(n)) = {f(n): 对任意正常数c, 存在n_0 > 0, 使对所有的n \geq n_0, 有0 \leq f(n) \leq cg(n) } )
从直觉上看,在o表示中当n趋于无穷时,函数f(n)相对于g(n)来说不重要了,即
[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0]

(\omega记号)
( \omega(g(n)) = {f(n): 对任意正常数c, 存在n_0 > 0, 使对所有的n \geq n_0, 有0 \leq cg(n) \leq f(n) } )
从直觉上看,在o表示中当n趋于无穷时,函数f(n)相对于g(n)来说变得任意大了,即
[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty]

定理

对任意两个函数f(n)和g(n), \(f(n) = \Theta(g(n))当且仅当f(n)=O(g(n)) 和 f(n) = \Omega(g(n))。\)

实际应用中,一般是用渐近上界和渐近下界证明了渐近确界。

等式和不等式中的渐近记号

  • 只出现在等式(不等式)的右边: 表示集合的成员关系。如\(n=O(n^2)\)
  • 一般来说,当出现在某个公式中时, 我们将其解释为一个不在乎其名称的匿名函数。如\(2n^2 + 3n + 1 = 2n^2 + \Theta(n) 即表示2n^2 + 3n + 1 = 2n^2 + f(n), 其中f(n)是某个属于\Theta(n)的函数。\)
  • 有时,出现在等式的左边,例如\(2n^2 + \Theta(n) = \Theta(n^2)\) 这时,我们使用以下规则来解释这种等式:无论等号左边的匿名函数如何选择, 总有办法选取选号右边的匿名函数使等式成立。

递归式的解法

代换法

步骤:

  1. 猜测解的形式。
  2. 用数学归纳法找出使解真正有效的常数。

适用情形:
只能用于解的形式很容易猜的情形。

递归树方法

用代换法不好猜,我们可以用递归树方法获得一个猜想,然后用代换法加以验证。

当用递归式表示分治算法的运行时间时,递归树的方法尤其有用。

主方法

主方法给出求解如下形式的递归式的”食谱”方法:

[ T(n) = aT(n/b) + fn(n)]
其中(a \geq 1 和 b > 1 是常数, f(n)是一个渐近正的函数)。

有三种情况:

  1. \(若对于某常数\varepsilon > 0, 有f(n) = O(n^{log_b{a-\varepsilon}}), 则T(n)=\Theta(n^{log_ba});\)
  2. \(若f(n)=\Theta(n^{log_ba}), 则T(n) = \Theta(n^{log_ba}lgn)\);
  3. \(若对某常数\varepsilon>0, 有f(n)=\Omega(n^{log_b{a+\varepsilon}}), 且对常数c<1与所有足够大的n,\) \(有af(n/b) \leq cf(n), 则T(n)=\Theta(f(n)) \);

需要注意三种情况并没有覆盖所有可能的f(n)。

算法设计

增量方法

插入排序有的就是增量方法。

分治法

分治模式在每一层递归上都有三个步骤:

  • 分解:将原问题分解成一系统子问题。
  • 解决:递归地解决各子问题。若子问题足够小,则直接求解。
  • 合并:将子问题的结果合并成原问题的解。

分治法举例之x的n次方

分治法举例之x的n次方

问题

(求x^n是很简单的事)

1.pow函数

python有pow函数。直接调用

pow(232, 1000)

结果>时间>python xn1.py 0.02s user 0.01s system 89% cpu 0.038 total

2.简单实现

递归

O(n)的时间复杂度

def xn(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        return x * xn(x, n-1)



print(xn(232, 1000))

时间>RuntimeError: maximum recursion depth exceeded
python xn.py 0.03s user 0.03s system 81% cpu 0.071 total

超了递归深度。。

循环

def xn(x, n):
    if n == 0:
        return 1
    else:
        ret = 1
        while n > 0:
            ret *= x
            n -= 1
        return ret




print(xn(232, 1000))

时间>python xn3.py 0.02s user 0.02s system 89% cpu 0.046 total

3.分治法实现

def xn(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        if n%2 == 0:
            return xn(x, int(n/2)) * xn(x, int(n/2))
        else:
            return xn(x, int(n/2)) * xn(x, n-int(n/2))



print(xn(232, 1000))

时间>
python xn2.py 0.02s user 0.01s system 83% cpu 0.046 total

实验数据

实验1数据: 232的1000次方。

方法 时间
pow 0.038
一般实现(递归) 0.071超递归栈,无结果
一般实现(循环) 0.046
分治法 0.046

实验2数据: 232的10000次方。

方法 时间
pow 0.056
一般实现(循环) 0.080
分治法 0.070

实验2数据: 232的100000次方。

方法 时间
pow 1.195
一般实现(循环) 3.469
分治法 1.411

结论

  1. 递归实现需要注意到递归栈深度问题。
  2. 能用库函数就尽量用库函数。库函数一般是C实现,实现的比较高效。 没有库函数时,数据量小可以用最简单的方式实现,但数据量大时,一定得想有什么算法适合解决该问题。

算法之斐波那契数

算法之斐波那契数

定义

斐波那契数递归地定义为:
[ F_0 = 0\;F_1 =1\;F_i = F_{i-1} + F_{i-2}\;当i \geq 2]

递归解法

这是根据定义直接求解。以指数形式增长。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

循环写法,cache结果

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        n2 = 0
        n1 = 1
        r = 1
        while n > 2:
            n2 = n1
            n1 = r
            r = n2 + n1
            n -= 1
    return r

利用数学结果1

事实上,有这么一个数学结论:

[F_i = \frac{\phi^i-\hat\phi^i}{\sqrt{5}}, 其中\phi=\frac{1+\sqrt{5}}{2}, \hat\phi=\frac{1-\sqrt{5}}{2}]

似乎能够利用分治法举例之x的n次方获得解。但仔细想想,这公式里有(\sqrt{5}), 肯定会在计算中丢失精度,而斐波那契数一定是个整数。这玩意并不能真正用程序来实现。

利用数学结果2

还有这么一个数学公式:(可以用归纳法证明)

[ \begin{pmatrix}
F_{n+1} & F_n \
F_n & F_{n-1}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}^n
]

而计算一个数的n次方,可以利用分治法举例之x的n次方了,可以知道时间复杂度是(\Theta(logn))

一用了numpy的矩阵相乘,但是在计算到93时出了错误,应该是数字越界问题。重新实现了下。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    class metrix:
        def __init__(self, i1, i2, j1, j2):
            self.i1 = i1
            self.i2 = i2
            self.j1 = j1
            self.j2 = j2

        def mul(self, another):
            i1 = self.i1 * another.i1 + self.i2 * another.j1
            i2 = self.i1 * another.i2 + self.i2 * another.j2
            j1 = self.j1 * another.i1 + self.j2 * another.j1
            j2 = self.j1 * another.i2 + self.j2 * another.j2
            return metrix(i1, i2, j1, j2)

        def __str__(self):
            return "(i1=%ld,i2=%ld,j1=%ld,j2=%ld)" % (
                self.i1, self.i2, self.j1, self.j2)

        @staticmethod
        def mulmetirx(a, b):
            return a.mul(b)

    def metrix_power(x, n):
        if n == 0:
            return 1
        elif n == 1:
            return x
        else:
            return metrix.mulmetirx(metrix_power(x, int(n/2)),
                                    metrix_power(x, n-int(n/2)))
    base = metrix(1, 1, 1, 0)
    result = metrix_power(base, n)
    return result.i2

实验

实现 规模 结果 时间 时间复杂度
递归实现 10 55 0.036 指数级
循环+cache 10 55 0.035 O(n)
矩阵算法 10 55 0.251 O(lgn)
递归实现 100 >83秒后终止 指数级
循环+cache 100 354224848179261915075 0.037 O(n)
矩阵算法 100 354224848179261915075 0.061 O(lgn)
循环+cache 1000 0.036 O(n)
矩阵算法 1000 0.061 O(lgn)
循环+cache 10000 0.069 O(n)
矩阵算法 10000 0.111 O(lgn)
循环+cache 100000 0.279 O(n)
矩阵算法 100000 0.627 O(lgn)
循环+cache 1000000 18.941 O(n)
矩阵算法 1000000 6.586 O(lgn)

结论

最简单的写法简直惨不忍睹,而高效的算法太依赖于数学了。算法和数学真的不分家,有志于玩算法的同学,学好数学吧。
更多的时候,我们要选择的不是最优的,而是最合适的。
譬如在1万以下,O(n)的效率居然最高。直到到了10万,O(lgn)才比O(n)更好。

分治法举例之矩阵乘法

分治法举例之矩阵乘法

前言

矩阵按定义直接实现是比较直接简单的。时间复杂度也可以直接得出来是(O(n^3))

直接实现

class matrix:
    '''
    为了简单起见,没有对数据做校验。
    假设矩阵就是nxn的。
    '''
    def __init__(self, data):
        if not data or not hasattr(data, '__getitem__'):
            raise ValueError("data not valid! %s" % data)
        self.data = data
        self.rows = len(data)
        self.cols = max(map(lambda row: len(row), data))

    def __mul__(self, another):
        if self.cols != another.rows:
            raise ValueError("not valid ddata ,only support mxn * nxp")
        ret = matrix([[0 for _ in range(another.cols)] for _ in range(self.rows)])
        for i in range(self.rows):
            for j in range(another.cols):
                num = 0
                for k in range(self.cols):
                    num += self._getitem(i, k) * another._getitem(k, j)
                ret._setitem(i, j, num)
        return ret

    def _getitem(self, i, j):
        if i >= self.rows or j >= self.cols:
            raise IndexError("index out of boundary,i=%d,j=%d, %s" % (
                i, j, self.data))
        try:
            return self.data[i][j]
        except Exception:
            return 0

    def _setitem(self, i, j, value):
        if i >= self.rows or j >= self.cols:
            raise IndexError("index out of boundary,i=%d,j=%d,value=%s, %s" % (
                i, j, str(value), self.data))
        if j >= len(self.data[i]):
            fill = self.cols - len(self.data[i])
            self.data[i].extend([0 for _ in range(fill)])
        self.data[i][j] = value

    def __str__(self):
        return "(rows:%d, cols:%d)->%s" % (self.rows, self.cols, self.data)

直接应用分治法

很简单的想法是把矩阵分成n/2的4块。于是
A*B = C
变成
[
\begin{pmatrix}
a & b \
c & d
\end{pmatrix}
*
\begin{pmatrix}
e & f \
g & h

\end{pmatrix}

\begin{pmatrix}
r & s \
t & u
\end{pmatrix}
]

r = ae + bg
s = af + bh
t = ce + dg
u = cf + dh

于是有(T(n) = 8T(n/2)+O(n^2))
(O(n^{log_ba}) = O(n^{log_28})=O(n^3) > f(n))
满足主定理的第一种情况,于是(T(n) = \Theta(n^3)),并没有比直接实现快。

斯特拉森算法

斯特拉森于1969年提出的算法,运用分治策略并加上一些处理技巧设计出的一种矩阵乘法。
他巧妙地8变成了7。于是达到了(T(n) = \Theta(n^{log_27})\approx\Theta(n^{2.81}))
这还不是目前理论上最好的,暂时最好的达到了(T(n) =\Theta(n^{2.376}))

看一下他是怎么玩的。

P1 = (a+d) * (e+h)
P2 = (c+d) * e
P3 = a * (f-h)
P4 = d * (g-e)
P5 = (a+b) * h
P6 = (c-a) * (e+f)
P7 = (b-d) * (g+h)

利用此7个式子即可得到原来的r,s,t,u
r = P1 + P4 – P5 + P7
s = P3 + P5
t = P2 + P4
u = P1 + P3 -P2 + P6
验证一下u看看

u = P1 + P3 -P2 + P6
= (a+d) * (e+h) + a * (f-h) -((c+d) * e) + (c-a) * (e+f)
=ae + ah + de + dh + af - ah -ce - de + ce + cf -ae -af
= dh + cf

正确

代码实现如下:

#!/usr/bin/env python
from enum import Enum, IntEnum, unique
import sys

class matrix:
    '''
    为了简单起见,没有对数据做校验。
    假设矩阵就是nxn的。
    '''
    def __init__(self, data):
        if not data or not hasattr(data, '__getitem__'):
            raise ValueError("data not valid! %s" % data)
        self.data = data
        self.rows = len(data)
        self.cols = max(map(lambda row: len(row), data))
        if self.rows != self.cols:
            raise ValueError("only support nxn matrix, and n can continue divide by 2 util 1")

    def __add__(self, another):
        if self.rows != another.rows:
            raise ValueError("not valid ddata ,only support nxn * nxn")
        ret = matrix([[0]*self.rows for _ in range(self.rows)])
        for i in range(self.rows):
            for j in range(self.rows):
                ret._setitem(i, j, self._getitem(i, j) + another._getitem(i, j))

        return ret

    def __sub__(self, another):
        if self.rows != another.rows:
            raise ValueError("not valid ddata ,only support nxn * nxn")
        ret = matrix([[0]*self.rows for _ in range(self.rows)])
        for i in range(self.rows):
            for j in range(self.rows):
                ret._setitem(i, j, self._getitem(i, j) - another._getitem(i, j))

        return ret

    def __mul__(self, another):
        if self.rows != another.rows:
            raise ValueError("not valid ddata ,only support nxn * nxn")
        ret = matrix([[0]*self.rows for _ in range(self.rows)])
        if self.rows == 2:
            for i in range(self.rows):
                for j in range(another.cols):
                    num = 0
                    for k in range(self.cols):
                        num += self._getitem(i, k) * another._getitem(k, j)
                    ret._setitem(i, j, num)
        else:
            a = self._divide(matrix.DIRECTION.LEFT_TOP)
            b = self._divide(matrix.DIRECTION.RIGHT_TOP)
            c = self._divide(matrix.DIRECTION.LEFT_BOTTOM)
            d = self._divide(matrix.DIRECTION.RIGHT_BOTTOM)

            e = another._divide(matrix.DIRECTION.LEFT_TOP)
            f = another._divide(matrix.DIRECTION.RIGHT_TOP)
            g = another._divide(matrix.DIRECTION.LEFT_BOTTOM)
            h = another._divide(matrix.DIRECTION.RIGHT_BOTTOM)

            p1 = (a+d)*(e+h)
            p2 = (c+d)*e
            p3 = a * (f-h)
            p4 = d * (g-e)
            p5 = (a+b)*h
            p6 = (c-a)*(e+f)
            p7 = (b-d)*(g+h)

            r = p1 + p4 - p5 + p7
            s = p3 + p5
            t = p2 + p4
            u = p1 + p3 - p2 + p6

            ret._merge(matrix.DIRECTION.LEFT_TOP, r)
            ret._merge(matrix.DIRECTION.RIGHT_TOP, s)
            ret._merge(matrix.DIRECTION.LEFT_BOTTOM, t)
            ret._merge(matrix.DIRECTION.RIGHT_BOTTOM, u)

        return ret

    @unique
    class DIRECTION (IntEnum):
        LEFT_TOP = 1
        LEFT_BOTTOM = 2
        RIGHT_TOP = 3
        RIGHT_BOTTOM = 4

    def _divide(self, direction):
        ret = matrix([[0]*int(self.rows/2) for _ in range(int(self.rows/2))])
        row_start = col_start = 0
        if direction == matrix.DIRECTION.LEFT_TOP:
            row_start = 0
            col_start = 0
        elif direction == matrix.DIRECTION.LEFT_BOTTOM:
            row_start = int(self.rows/2)
            col_start = 0
        elif direction == matrix.DIRECTION.RIGHT_TOP:
            row_start = 0
            col_start = int(self.cols/2)
        else:
            row_start = int(self.rows/2)
            col_start = int(self.cols/2)

        for i in range(ret.rows):
            for j in range(ret.cols):
                item = self._getitem(i+row_start, j+col_start)
                ret._setitem(i, j, item)

        return ret

    def _merge(self, direction, another):
        row_start = col_start = 0
        if direction == matrix.DIRECTION.LEFT_TOP:
            row_start = 0
            col_start = 0
        elif direction == matrix.DIRECTION.LEFT_BOTTOM:
            row_start = int(self.rows/2)
            col_start = 0
        elif direction == matrix.DIRECTION.RIGHT_TOP:
            row_start = 0
            col_start = int(self.cols/2)
        else:
            row_start = int(self.rows/2)
            col_start = int(self.cols/2)

        for i in range(another.rows):
            for j in range(another.cols):
                item = another._getitem(i, j)
                self._setitem(i+row_start, j+col_start, item)



    def _getitem(self, i, j):
        if i >= self.rows or j >= self.cols:
            raise IndexError("index out of boundary,i=%d,j=%d, %s" % (
                i, j, self.data))
        try:
            return self.data[i][j]
        except Exception:
            return 0

    def _setitem(self, i, j, value):
        if i >= self.rows or j >= self.cols:
            raise IndexError("index out of boundary,i=%d,j=%d,value=%s, %s" % (
                i, j, str(value), self.data))
        if j >= len(self.data[i]):
            fill = self.cols - len(self.data[i])
            self.data[i].extend([0 for _ in range(fill)])
        self.data[i][j] = value

    def __str__(self):
        return "(rows:%d, cols:%d)->%s" % (self.rows, self.cols, self.data)

测试结果

方法 规模 时间
直接计算 8×8 0.054
拉特斯森 8×8 0.095
直接计算 16×16 0.063
拉特斯森 16×16 0.117
直接计算 32×32 0.090
拉特斯森 32×32 0.454
直接计算 64×64 0.419
拉特斯森 64×64 2.953
直接计算 128×128 2.946
拉特斯森 128×128 20.547
直接计算 256×256 24.835
拉特斯森 256×256 2:15.15
直接计算 512×512 3:15.98

总结

估计是我实现的问题,比预期结果要差,看视频里说的是到32就差不多了。
不过从上也可以看出来,拉特斯森增长的速度没有直接计算的快,迟早性能会更好。

另外,直观上感觉矩阵乘法是没法优化。但事实上可以。
这说明真没有那么多做不到的事,可能只是现在的你做不来,说不定有人能做到,说不定做到的那个人就是未来的你。