Python并发编程

  1. threading,多线程基础库,由于python有GIL的限制故多线程不如其他一些语言强大(无法利用多核),但是在IO密集的情况下使用也可以很好地提高程序的效率。
  2. multiprocessing,多进程基础库,与多线程类似,但是它有一个很大的优点就是可以利用多核,缺点是进程创建开销较大,这一点在不同平台有稍许差异(windows要更大一些?),另外进程间通讯比多线程复杂一些。
  3. queue, multiprocessing.queue,配合前二者进行并发编程,有三种模式: Queue普通先进先出,LifoQueue先进后出,PriorityQueue优先级
  4. select/poll/epoll

To be continued...

Python的import机制

在C语言中头文件一般是不能重复include的,否则会出现重定义错误。因此一般会在头文件中加上类似以下的判断:

#pragma once
#ifndef __XXXX_H
#define __XXXX_H
#endif

#pragma once与#ifndef...#define...#endif作用相同,但前者更快。前者是平台相关的,移植性较差,后者为语言特性,可移植性好,实际可混合使用。

python中也采用了一定的处理规则来防止重复import。

简单来说, import的过程中做了下面几件事:

  1. 在sys.modules查找该模块,如果存在,则返回。
  2. 在sys.path包含的路径中查找该模块
  3. 如果找到该模块,则将模块信息加入sys.modules, sys.modules为保存当前加载模块信息的一个dict, 对应格式为{'xxxx': <module 'xxxx' from '/usr/lib/.../xxxx.py'>}, 执行该模块文件,如未出错,将模块(import XXXX)或者其中的变量(from XXXX import *)加入globals()和locals()。

现在我们有两个循环调用的python模块:a.py和b.py,各自都import了对方,现在我们python a.py,则其执行过程如下:

  1. a中import b:sys.modules无b,故查找b模块,添加至sys.modules, 执行
  2. 执行b模块,b中import a,sys.modules无a, 故查找a,添加至sys.modules, 执行
  3. 执行a模块,import b时sys.modules中已有故直接跳过,返回至2(4)
  4. 返回到2后执行b完成返回到1(5)
  5. 返回到1后继续执行a其他代码

用图表示为:

/attachment/import_1_e380c13ac16479fd38b696b13f72b8da.png

堆排序

堆排序利用了堆的特性进行排序。堆是一种近似完全二叉树的结构,满足以下性质:子节点的键值总是小于(或大于)它的父节点。

堆排序的C实现:

void sink(int *n, int i, int len)
{
    int l = 2*i + 1;
    if (l > len - 1) return;
    int r = l + 1;
    int _max_lr = (r > len - 1) ? l : (*(n+r) > *(n+l) ? r : l);
    if (*(n+_max_lr) < *(n+i)) return;
    swap(n+_max_lr, n+i);
    sink(n, _max_lr, len);
}

void heap(int *n, int len)
{
    int i;
    for (i=(len-1)/2; i>=0; i--) {
        sink(n, i, len);
    }

    print_n_array(n, 10);
    for (i=0; i<len; i++) {
        swap(n, n+len-1-i);
        sink(n, 0, len-i-1);
    }
}

堆排序最差情况的时间复杂度为\(n \lg n\) .堆排序需要的额外空间为\(O(1)\) .堆排序是不稳定的.

堆排序与快排的比较

  • 快排总体来说较堆排序更快
  • 快排最差情况下接近\(O(n^2)\)
  • 快排需要更多的额外空间

因此,考虑到堆排序最差情况的复杂度上限和需要额外空间的上限,通常将其应用在对实时性要求较高和安全性较高的嵌入式系统中。

堆排序与归并排序的比较

  • 二者时间复杂度均为\(n \lg n\) .
  • 堆排序在数据缓存较小的计算机上更快,因为堆排序需要更少的额外空间。
  • 堆排序不稳定,归并排序稳定。
  • more
MORE