python标准库学习—bisect模块-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 648458
  • 博文数量: 87
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2022
  • 用 户 组: 普通用户
  • 注册时间: 2014-04-23 11:16
个人简介

西邮大三狗!!!

文章分类

全部博文(87)

文章存档

(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 = (lohi)//2
  14.         if x < a[mid]: hi = mid
  15.         else: lo = mid1
  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 = (lohi)//2
  32.         if x < a[mid]: hi = mid
  33.         else: lo = mid1
  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 = (lohi)//2
  48.         if a[mid] < x: lo = mid1
  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 = (lohi)//2
  65.         if a[mid] < x: lo = mid1
  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
阅读(4393) | 评论(0) | 转发(0) |
0

上一篇:

下一篇:python标准库学习—collections模块

给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图