归并排序

经典排序算法之一,分冶思想

from unittest import (
        main,
        TestCase,
        )
from random import Random


def merge(lst):
    if len(lst) <= 1:
        return lst

    def _merge(left, right):
        result = []
        while left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        result.extend(right if right else left)
        return result

    left = merge(lst[:len(lst)//2])
    right = merge(lst[len(lst)//2:])
    return _merge(left, right)


class MergeTestCase(TestCase):
    def setUp(self):
        self.data = list(
                Random().sample(range(10000), 100)
                for i in range(100)
                )

    def testMerge(self):
        for _data in self.data:
            print _data
            self.assertEqual(
                    merge(_data),
                    sorted(_data),
                    )


if __name__ == '__main__':
    main()
Advertisements
发表在 Python | 留下评论

Python 中的 object 和 type 是什么关系?

在 Python 中万物皆对象,这句话是对的,但是只道出了 Python 中对象之间一方面的关系,即实例关系。

* 对象是类的实例:对象 a 是类 A 的一个实例;

* 类是元类的实例:类 A 是元类的一个实例;

type 即是元类中的默认元类,如果在构建一个类的时候,没有指定元类,则默认使用 type 作为元类。

除了实例关系之外,还有亲缘关系,如父子关系、兄弟关系,形成这样的关系,并不是靠实例化某一个类来达成的,而是一个或多个类通过继承、组合的过程来实现,在这个过程中追根溯源到一个基础的类,就是 object。

本质上 object 是一个类,它由 type 元类实例化而来,在各种类亲缘关系的构建过程中,扮演着一个默认的存在,正是有了这个 object,我们就不用再自己通过 type 来实例化一个基础类了。

如果再深入一点,元类也是类的一种,那么元类的元类是元类,从这种关系上讲,type 实际上是继承自 object。

整个 「Python 中万物皆对象」的理论完全构建在这一自洽的设定之上。

>>> object.__class__
# object 是 type 实例化而来的一个类

>>> object.__bases___
() # object 这个类没有父类

>>> type.__class__
# 元类的元类是元类

>>> type.__bases__
# type 是父类是 object

知乎链接 https://www.zhihu.com/question/38791962,更深入地讨论了这个问题。

发表在 未分类 | 留下评论

Python 判断一个整数是否为一个列表中两个整数之和

今天被人问到一个算法题目:

给定一个由整数构成的列表 lst ,和一个整数 i,判断 i 是否为 lst 中某两个元素之和。

我最终的解法是这样的:

lst2 = [ (i- 0.4) – j for j in lst]

dic = dict.fromkeys(lst2, True)

for item in lst2:
if item in dict:
return dict[item]
return False

这种解法是算是钻了个空子:限定所有的元素都是整数。

至于为什么要减去 0.4?其实减去其它的数也行,除了 0.5,这么做的目的是为了防止某一个元素自己加自己等于目标值的情况。这也就是钻空子的地方,如果给的数里有浮点数,那就不好确定该怎么避开这个小陷阱了。

发表在 未分类 | 留下评论

关于 Python 收发邮件的一些坑

因为工作的关系,最近使用 Python 自带的 imaplib 和 poplib 封装了两个模块,用来自动处理邮件。

基本的文档直接看官网就好了,这里记几个坑。

一,imaplib 是没有明确的状态表述当前 socket 的状态的,会经常出现 socket error EOF 这样的异常,然后连接就彻底中断了。查了很多资料,一般的处理方法是捕获异常-重新再来-直到成功,没找到根本的解决方案。

但是根据尝试的结果,我发现 poplib 的连接会比较稳定些,于是就出了个奇怪的方案:使用 IMAP 管理邮件状态,使用 pop 下载邮件。

二,这次主要对接的服务是 QQ 邮箱,不知道是否我的操作方式不对?总之就是 QQ 邮箱对 IMAP 协议的支持相当有限,使用 search 命令的话,如果只是一个简单的命令倒还好,一旦加上参数后,就各种参数非法或不支持之类的,例如我希望通过 message-id 来找邮箱,根本就做不到。

三,还是针对 QQ 邮箱的问题,使用pop能获取到一个类似 uuid 的值,但是使用 imap 就拿不到相应的 UID了,邮件的头里倒是有个 message-id,但是想使用 uid 操作的话,就是妄想了。

四,你能想像么?qq 企业邮箱里来自 qq 官方的一些提醒邮件的编码居然是 GBK 的,一个不留神以为是 UTF-8,解析出了一堆乱码。

发表在 未分类 | 留下评论

hello!

好久不见。

发表在 未分类 | 留下评论

django manytomanyfield字段在drf中deserialize的问题

存在如下模型:

class Person(models.Model):
# …
name = models.CharField(max_length=32)

class Group(models.Model):

# …
members = models.ManyToManyField(Person, through=“Membership”)

class Membership(models.Model):
person = models.ForeignKey(Person)
group = models.ForeignKey(Group)

    class Meta:
    auto_created = True

定义serializer:
class GroupSerializer(serializers.ModelSerializer):
member = serializer.SlugRelatedField(many=True, slug_field=‘name’)
class Meta:
model = Group

此时,由此serializer创建新的Group模型的时候,AttributeError(“Cannot set values on a ManyToManyField which specifies an intermediary model. Use %s.%s’s Manager instead.” % (opts.app_label, opts.object_name)),这个错误是由于DRF在处理M2M关系时,relational fields that target a ManyToManyField with a through model specified are set to read-only。

解决的办法是在Membership的Meta中添加auto_created=True,DRF在反序列化的时候会根据Meta中的auto_created值,在逻辑上以has_though_model属性,利用though_model在完成Group类的实例之后,为实例的members字段添加Membership字段,同时在处理update/delete,能自动根据此属性去实现相应Membership实例的更新和删除操作。

发表在 未分类 | 留下评论

python中tuple写法

From Evernote:

python中tuple写法

今天passport项目已经上了公网测试了,还没打开了,测试人员就来告诉说在内网环境的passport注册接口有bug,吓得我一身冷汗。查了半天,终于发现一个问题,在urllib请问计费接口的时候,抛出异常显示参数是个tuple,而正常的情况下,这个参数应该是个url字串,再一细查发现在写这个url的时候用了如下的代码: url = urlstr,
问题就出在这里了,后面那个逗号,正是这个逗号,将url变成tuple了,为了保险起见,测试了下如下写法:
>>>url = "a", "b", "c"
>>>type(url)
<type ‘tuple’>
在stackoverflow上查到:http://stackoverflow.com/questions/3750632/why-does-adding-a-trailing-comma-after-a-string-make-it-a-tuple,原来元组的定义就是多个由逗号分隔的值,而与括号无关,这句话是写在Python Tutorial里的,看书不认真的下场啊。

发表在 未分类 | 留下评论