分类 Python 下的文章

递归实现阶乘（Python版）

简单来说，递归就是程序（函数）调用自身（recursion）的编程技巧。下面的例子是经典的递归实现阶乘（factorial）案例：

def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

fact(3)

#输出结果：6

使用递归需要注意：

  • 递归指的是调用自己的函数。
  • 每个递归函数都有两个条件：基线条件和递归条件。

选择排序（Python实现）

选择排序（Selection sort）是一种简单直观的排序算法。

原理

是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序的交换操作介于 0 和 (n - 1） 次之间，所以选择排序是不稳定的排序方法。

算法描述

  1. 在一个长度为 n 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
  2. 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。

  3. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

    时间复杂度

    需要的总时间为O(n×n)，即O(n²)。

python语言实现

# -*- coding: UTF-8 -*-
def findSmallest(arr):
  smallest = arr[0]
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest = arr[i]
      smallest_index = i
  return smallest_index

def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

print selectionSort([5, 3, 6, 2, 10])

# 输出结果 [2, 3, 5, 6, 10]

当然，还有更简洁的实现方法：

# -*- coding:utf-8 -*-
# 选择排序

# 方法一
def select_sort(list):
    l = len(list)
    if l < 2:
        return list
    
    for i in range(l):
        min = list[i]
        for j in range(i + 1, l):
            if list[j] < min:
                min, list[j] = list[j], min
        list[i] = min

    return list


# 方法二，交换次数少，效率更高
def select(list):
    l = len(list)
    if l < 2:
        return list
    
    for i in range(l):
        for j in range(i + 1, l):
            if list[j] < list[i]:
                list[i], list[j] = list[j], list[i]

    return list


list = [54, 26, 93, 17, 77, 3, 31, 44, 55, 20]
print(select(list))
print(select_sort(list))

Python实现二分查找

前提：一个有序的列表
原理：假如我们心里默念一个1-100的数字，让别人猜，那么怎么猜会比较快呢？（1）从1开始往后猜，那么最坏的情况可能要猜100次；（2）每次都猜剩下数字列表的中间那个数，这样每次都可以排除一半，平均情况下，这种方法比第一种要快。
第二种方法也就是下面的二分查找算法（Python实现）。
时间复杂度：O(log2n)。

# -*- coding: UTF-8 -*-
# 二分查找 binary_search.py

def binary_search(list, item):
  low = 0
  high = len(list)-1  

  while low <= high:
    mid = (low + high) // 2
    guess = list[mid]
    if guess == item:
      return mid
    if guess > item:
      high = mid - 1
    else:
      low = mid + 1
  return None

my_list = [1, 3, 5, 7, 9]

print binary_search(my_list, 9) #结果：4
print binary_search(my_list, -1) #结果：None

以上代码只适用于没有重复数据的列表，如果列表中有重复的数据，我们要查找左边界或右边界，又该如何呢？在参考了 详解二分查找算法 之后，得出了一下代码供大家参考：

#  寻找左侧边界
def left_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            right = mid
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == len(list):
        return -1

    if list[left] == item:
        return left
    else:
        return -1


#  寻找右侧边界
def right_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            left = mid + 1
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == 0:
        return -1
    if list[left - 1] == item:
        return left - 1
    else:
        return -1

一个Python多进程解析域名的例子

工作要求，需要知道上万个域名的解析IP，并判断指向是否正确。最开始想到的是Ping命令，但其结果不容易处理。经过一番查找，最终选择了socket.gethostbyname()方法。一开始因为是普通的编程方法，一万多条数据处理下来居然花了好几个小时，效率很低。这时主要的瓶颈其实在于gethostbyname，但一时没找到其他更好用的解析IP的方法。后来得到一个同事的启发，用Python的多进程处理，处理时间缩短了一大半，这样多多少少弥补了gethostbyname的缺陷。完整案例如下（数据是虚假的）：
需要判断的ip（txt格式，一行一个ip）

...
192.168.0.2
192.168.9.2
...

原始域名数据（txt格式，一行一个域名）

...
xxx.cn
xxxx.com
...

处理后的数据（txt格式，一行一个域名+ip+判断词）

...
xxx.cn 192.168.0.1 in
xx2x.cn 192.168.0.2 not in
xx3x.cn unresolved unresolved
...

处理程序如下：

#coding:utf-8
import socket
from multiprocessing import Pool

# IPs
ipList = []
with open("/path/to/ip.txt", "r") as fip:
    for ip in fip.readlines():
        ip = ip.strip()
        ipList.append(ip)

def URL2IP(url):
    url = url.strip()
    # urlList = url.split("\t");
    try:
        ip = socket.gethostbyname("www." + str(url))
        if ip in ipList:
            tip = "in"
        else:
            tip = "no in"
    except:
        print url + " this URL 2 IP ERROR "
        ip = "unresolved"
        tip = "unresolved"
    
    return url + "\t" + str(ip) + "\t" + str(tip)
if __name__ == '__main__':     
    # domains
    allUrls = []
    with open("/path/to/domain.txt", "r", encoding='utf-8') as urllist:
        allUrls = urllist.readlines()
    
    p = Pool(8) # 建议设置成CPU核数
    resultList = p.map(URL2IP, allUrls)
    p.close()
    p.join()

    # write the result to file
    with open("/path/to/resolve.txt", "w") as resovelist:
        resovelist.writelines("\n" . join(resultList))

    print "complete !"

关于如何使用Python多进程，大家可以自行搜索。

记一次网站迁移

背景：公司的部分业务是网站建设，现由于公司业务调整，需要将公司部署在电信IDC机房的四千多个网站迁移至百度云。

迁移开始之前，考虑了几个难点：
1、网站数据较大（150G左右），通过公网传输需要耗费很长时间，但其间不能影响网站正常访问；
2、每个站点都配有FTP账号，迁移后要保证原来的账号仍然可用；
3、所有站点都配有二级域名，当初做的是泛域名解析。

第三个难点相对容易解决，只需要调整一下Apache的匹配规则，然后起用全新的泛域名指向即可。

为了保证第二点中提到的FTP可用，第一点中转移数据的时候，不仅要保证数据完整，而且文件、目录的属性也要和老服务器一致。所以，开始转移数据之前，要在新服务器添加所有对应的用户。补充一点，我们用的是SFTP，所以所有账号都是Linux的一个用户，名称和站点目录一致。

所以迁移步骤大致如下：
1、利用Python脚本生成SFTP用户及对应密码，保存到文本文件，每个账号占一行，后面紧跟一个空格加密码；在新服务器中读取该文本文件，并批量添加用户。之所以可以用这种方法，是由于最开始的SFTP账号是根据站点目录名生成的，所以通过脚本比较方便处理。
2、用Rsync同步数据，配置文件中 use chroot = no 来保证所有文件的所属用户和组都正确，另外 -a 参数保证文件读写权限与旧服务器一致。
3、mysqldump方法导出数据库，同样通过rsync同步到新服务器，导入。我们的结构是一个站点一个数据库，所以虽然数据库数量多，但都很小，毕竟都是企业站居多。导入的方法是：python脚本批量解压.gz的数据库文件，然后把需要导入的库写进一个文件source.sql，该文件的内容格式如下：

source xxx.sql;
source xxx2.sql;
...

至此，网站迁移基本完成。

  1. 1
  2. 2
  3. 3
  4. 4