残阳似血的博客

在平常的代码中，我们常常需要与时间打交道。在Python中，与时间处理有关的模块就包括：time，datetime以及calendar。这篇文章，主要讲解time模块。

在开始之前，首先要说明这几点：

1. 在Python中，通常有这几种方式来表示时间：1）时间戳 2）格式化的时间字符串 3）元组（struct_time）共九个元素。由于Python的time模块实现主要调用C库，所以各个平台可能有所不同。
2. UTC（Coordinated Universal Time，世界协调时）亦即格林威治天文时间，世界标准时间。在中国为UTC+8。DST（Daylight Saving Time）即夏令时。
3. 时间戳（timestamp）的方式：通常来说，时间戳表示的是从1970年1月1日00:00:00开始按秒计算的偏移量。我们运行“type(time.time())”，返回的是float类型。返回时间戳方式的函数主要有time()，clock()等。
4. 元组（struct_time）方式：struct_time元组共有9个元素，返回struct_time的函数主要有gmtime()，localtime()，strptime()。下面列出这种方式元组中的几个元素：

Django mptt是个Django第三方组件，目标是使Django项目能在数据库中存储层级数据（树形数据）。它主要实现了修改过的前序遍历算法，如果你对原理还不是很了解，可以看我的这篇文章。当然，使用mptt时，原理是可以不用了解的，因为具体的实现细节都已经隐藏。不过，如果项目不是使用的Django，可以参考具体的实现原理。

在整篇文章中，我们将会拿《在数据库中存储层级结构》中的例子作为本文的例子。我们打算在数据库中存储这张图中的数据：

在介绍mptt之前，如果你的需求仅仅是像这样显示以上数据：

Food
    
 
        
Fruit
        
 
            
Red
            
 
               
Cherry
 
            
 
            
 
            
Yellow
            
 
               
Banana
 
            
 
            
 
        
 
        
 
        
Meat
        
 
            
Beef
 
            
Pork
 
        
 
        
 
    
 
 

mptt就显得大材小用了，因为Django已经有内置模板过滤器来完成这个工作：unordered_list（官方文档）。如果你的需求不只这么简单，那就跳过这一段。不过这里还是要讲解一下unordered_list的做法。我们就来实现以上的结果。

Update：如果想了解更多第三方帐号登录，请看这篇文章。

随着新浪微博用户日益增加，我们有时候会考虑在自己的网站中整合新浪微博。比如说我现在的独立博客。

在我的博客中做到整合主要就这几方面：我写一篇文章，就会同步发送至微博。同时呢，用户可以用微博帐号登录，并且可以选择把对文章的评论，同步评论到文章的微博。另外，用户可以选择是否把博客留言同步至新浪微博。

新浪微博开放平台地址在这里。文档地址在这里。

首先要涉及的问题，就是用户用新浪微博帐号登录的问题，即授权机制。基本方法有两种：

1. OAuth
2. Basic auth（需要强调的是，微博开放平台将于6月1日正式停止Basic Auth的支持。因此，此种方法不作讨论了，其实需要用户名和密码的方式本身就不安全。）

OAuth新浪官方的文档在这里。想要了解OAuth技术说明的可以访问官方网站。

其实，OAuth的流程还是很简单的。大致如下：

1. 向API调用获得request token。
2. 将用户重定向到授权页(auth url）。
3. 用户输入用户名和密码完成授权。重定向到Callback_url。
4. 用request token向新浪微博换取access token。
5. 完成。

在1960年代，计算机制造商们曾经估计，如果将所有的用户计入，他们制造的计算机有25%的时间用于排序。实际上，有很多计算机花了超过一半的计算时间在排序上。通过这样的评估结果，我们可以得出结论，可能（i）确实有很多非常重要的和排序相关的应用，或者（ii）很多人在进行一些不必要的排序计算，再或者（iii）低效的排序算法被广泛采用造成了计算的浪费。

来源《The Art of Computer Programming》，作者Donald Knuth

在Python实践中，我们往往遇到排序问题，比如在对搜索结果打分的排序（没有排序就没有Google等搜索引擎的存在），当然，这样的例子数不胜数。《数据结构》也会花大量篇幅讲解排序。之前一段时间，由于需要，我复习了一下排序算法，并用Python实现了各种排序算法，放在这里作为参考。

最简单的排序有三种：插入排序，选择排序和冒泡排序。这三种排序比较简单，它们的平均时间复杂度均为O(n^2)，在这里对原理就不加赘述了。贴出来源代码。

插入排序：

def insertion_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(1, iter_len):
        key = sort_list[i]
        j = i - 1
        while j >= 0 and sort_list[j] > key:
            sort_list[j+1] = sort_list[j]
            j -= 1
        sort_list[j+1] = key
    return sort_list

冒泡排序：

def bubble_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(iter_len-1):
        for j in range(iter_len-i-1):
            if sort_list[j] > sort_list[j+1]:
                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j]
    return sort_list

选择排序：

def selection_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(iter_len-1):
        smallest = sort_list[i]
        location = i
        for j in range(i, iter_len):
            if sort_list[j] < smallest:
                smallest = sort_list[j]
                location = j
        if i != location:
            sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
    return sort_list