Chinaunix首页 | 论坛 | 博客
  • 博客访问: 657466
  • 博文数量: 87
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2022
  • 用 户 组: 普通用户
  • 注册时间: 2014-04-23 11:16
个人简介

西邮大三狗!!!

文章分类

全部博文(87)

文章存档

2015年(47)

2014年(40)

分类: Python/Ruby

2015-06-09 19:08:19

bisect模块可以使列表保持已排好的顺序,使用二分算法。

bisect(list,item,[low,[high]])                返回要插入item点的索引,如果item在列表中了,则返回该条目的右边索引
bisect_right(list,iten,[left,[right]])        同上
bisect_left(list,iten,[left,[right]])          返回要插入item点的索引,如果item在列表中了,则返回该条目的左边索引
insort(list,item,[left,[right]])                不返回索引,直接插入进去,如果有重复的item,则插入到右边
insort_right(list,item,[left,[right]])       同上
insort_left(list,item,[left,[right]])         不返回索引,直接插入进去,如果有重复的item,则插入到左边

下面是整个模块在linux python2.6版本的源码:
  1. """Bisection algorithms."""

  2. def insort_right(a, x, lo=0, hi=None):
  3.     """Insert item x in list a, and keep it sorted assuming a is sorted.

  4.     If x is already in a, insert it to the right of the rightmost x.

  5.     Optional args lo (default 0) and hi (default len(a)) bound the
  6.     slice of a to be searched.
  7.     """

  8.     if lo < 0:
  9.         raise ValueError('lo must be non-negative')
  10.     if hi is None:
  11.         hi = len(a)
  12.     while lo < hi:
  13.         mid = (lo+hi)//2
  14.         if x < a[mid]: hi = mid
  15.         else: lo = mid+1
  16.     a.insert(lo, x)

  17. insort = insort_right # backward compatibility

  18. def bisect_right(a, x, lo=0, hi=None):
  19.     """Return the index where to insert item x in list a, assuming a is sorted.

  20.     The return value i is such that all e in a[:i] have e <= x, and all e in
  21.     a[i:] have e > x. So if x already appears in the list, a.insert(x) will
  22.     insert just after the rightmost x already there.

  23.     Optional args lo (default 0) and hi (default len(a)) bound the
  24.     slice of a to be searched.
  25.     """

  26.     if lo < 0:
  27.         raise ValueError('lo must be non-negative')
  28.     if hi is None:
  29.         hi = len(a)
  30.     while lo < hi:
  31.         mid = (lo+hi)//2
  32.         if x < a[mid]: hi = mid
  33.         else: lo = mid+1
  34.     return lo

  35. bisect = bisect_right # backward compatibility

  36. def insort_left(a, x, lo=0, hi=None):
  37.     """Insert item x in list a, and keep it sorted assuming a is sorted.

  38.     If x is already in a, insert it to the left of the leftmost x.

  39.     Optional args lo (default 0) and hi (default len(a)) bound the
  40.     slice of a to be searched.
  41.     """

  42.     if lo < 0:
  43.         raise ValueError('lo must be non-negative')
  44.     if hi is None:
  45.         hi = len(a)
  46.     while lo < hi:
  47.         mid = (lo+hi)//2
  48.         if a[mid] < x: lo = mid+1
  49.         else: hi = mid
  50.     a.insert(lo, x)


  51. def bisect_left(a, x, lo=0, hi=None):
  52.     """Return the index where to insert item x in list a, assuming a is sorted.

  53.     The return value i is such that all e in a[:i] have e < x, and all e in
  54.     a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
  55.     insert just before the leftmost x already there.

  56.     Optional args lo (default 0) and hi (default len(a)) bound the
  57.     slice of a to be searched.
  58.     """

  59.     if lo < 0:
  60.         raise ValueError('lo must be non-negative')
  61.     if hi is None:
  62.         hi = len(a)
  63.     while lo < hi:
  64.         mid = (lo+hi)//2
  65.         if a[mid] < x: lo = mid+1
  66.         else: hi = mid
  67.     return lo

  68. # Overwrite above definitions with a fast C implementation
  69. try:
  70.     from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
  71. except ImportError:
  72.     pass
阅读(4470) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~