1
回答
python模块介绍- collections(3)-deque双向队列
开发十年,就只剩下这套Java开发体系了   

python模块介绍- collections(3)-deque双向队列

2013-04-17 磁针石

#承接软件自动化实施与培训等gtalk:ouyangchongwu#gmail.com qq 37391319 博客:http://blog.csdn.net/oychw

#版权所有,转载刊登请来函联系

#深圳测试自动化python项目接单群113938272深圳会计软件测试兼职 6089740

#深圳地摊群 66250781武冈洞口城步新宁乡情群49494279

#自动化测试和python群组: http://groups.google.com/group/automation_testing_python

#参考资料:《The Python Standard Libraryby Example 2011》


1.3.3 deque双向队列

Deque可以从两端添加和删除元素。常用的结构,是它的简化版本。

Deque支持序列的常用操作:

import collections

 

d = collections.deque('abcdefg')

print 'Deque:', d

print 'Length:', len(d)

print 'Left end:', d[0]

print 'Right end:', d[-1]

 

d.remove('c')

print 'remove(c):', d

执行结果:

# ./collections_deque.py

Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])

Length: 7

Left end: a

Right end: g

remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

Deque可以从2端生产:

import collections

 

# Add to the right

d1 = collections.deque()

d1.extend('abcdefg')

print 'extend    :', d1

d1.append('h')

print 'append    :', d1

 

# Add to the left

d2 = collections.deque()

d2.extendleft(xrange(6))

print 'extendleft:', d2

d2.appendleft(6)

print 'appendleft:', d2

执行结果:

# ./collections_deque_populating.py

extend    : deque(['a','b', 'c', 'd', 'e', 'f', 'g'])

append    : deque(['a','b', 'c', 'd', 'e', 'f', 'g', 'h'])

extendleft: deque([5, 4, 3, 2, 1, 0])

appendleft: deque([6, 5, 4, 3, 2, 1, 0])

Deque可以从2端消费:

import collections

 

print 'From the right:'

d = collections.deque('abcdefg')

while True:

    try:

        print d.pop(),

    except IndexError:

        break

print

 

print 'From the left:'

d = collections.deque(xrange(6))

while True:

    try:

        printd.popleft(),

    except IndexError:

        break

print

执行结果:

# ./collections_deque_consuming.py

From the right:

g f e d c b a

 

From the left:

0 1 2 3 4 5

由于Deque线程安全的,可由不同线程从2端同时消费:

 

import collections

import threading

import time

 

candle = collections.deque(xrange(5))

 

def burn(direction, nextSource):

    while True:

        try:

            next =nextSource()

        exceptIndexError:

            break

        else:

            print '%8s:%s' % (direction, next)

            time.sleep(0.1)

    print '%8s done' %direction

    return

 

left = threading.Thread(target=burn, args=('Left',candle.popleft))

right = threading.Thread(target=burn, args=('Right',candle.pop))

 

left.start()

right.start()

 

left.join()

right.join()

执行结果:

# ./collections_deque_both_ends.py

    Left: 0

   Right: 4

    Left: 1

   Right: 3

    Left: 2

    Right done

Left done

 


旋转:

import collections

 

d = collections.deque(xrange(10))

print 'Normal        :',d

 

d = collections.deque(xrange(10))

d.rotate(2)

print 'Right rotation:', d

 

d = collections.deque(xrange(10))

d.rotate(-2)

print 'Left rotation :', d

 

执行结果:

# ./collections_deque_rotate.py

Normal        :deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

Right rotation: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])

Left rotation : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

 

定义:

class collections.deque([iterable[, maxlen]])

       Deque的拼写是“deck”,是double-endedqueue”的缩写。它支持内存高效,线程安全的双端append和pop,性能大体在O(1)。列表中pop(0)和 insert(0, v)的操作性能是O(n)。

       Maxlen没有指定或者是None,deque不限制长度。如果指定了长度,就会丢弃老的内容,跟unix的tail类似。支持的方法如下:

       append(x) :右边添加。appendleft(x) :左边添加,clear() ,count(x),extend(iterable) ,extendleft(iterable),pop()

,remove(value) ,reverse(),rotate(n)

       属性:maxlen

另外Deque支持迭代,,pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d),in的成员判断,index引用(O(1)在两端,O(n)在中间,快速的随机元素访问,建议使用list)。

下面是python手册中的实例:

 

>>> from collections import deque

>>> d = deque('ghi')                 # make a new deque with threeitems

>>> for elem in d:                   # iterate over the deque'selements

...     print elem.upper()

G

H

I

 

>>> d.append('j')                    # add a new entry to theright side

>>> d.appendleft('f')                # add a new entry to the leftside

>>> d                               # show therepresentation of the deque

deque(['f', 'g', 'h', 'i', 'j'])

 

>>> d.pop()                          # return and removethe rightmost item

'j'

>>> d.popleft()                      # return and remove theleftmost item

'f'

>>> list(d)                          # list the contentsof the deque

['g', 'h', 'i']

>>> d[0]                             # peek at leftmostitem

'g'

>>> d[-1]                            # peek at rightmostitem

'i'

 

>>> list(reversed(d))                # list the contents of a dequein reverse

['i', 'h', 'g']

>>> 'h' in d                         # search the deque

True

>>> d.extend('jkl')                  # add multiple elements atonce

>>> d

deque(['g', 'h', 'i', 'j', 'k', 'l'])

>>> d.rotate(1)                      # right rotation

>>> d

deque(['l', 'g', 'h', 'i', 'j', 'k'])

>>> d.rotate(-1)                     # left rotation

>>> d

deque(['g', 'h', 'i', 'j', 'k', 'l'])

 

>>> deque(reversed(d))               # make a new deque in reverseorder

deque(['l', 'k', 'j', 'i', 'h', 'g'])

>>> d.clear()                        # empty the deque

>>> d.pop()                          # cannot pop from anempty deque

Traceback (most recent call last):

  File "<pyshell#6>",line 1, in -toplevel-

    d.pop()

IndexError: pop from an empty deque

 

实现tail:

def tail(filename, n=10):

    'Return the last nlines of a file'

    return deque(open(filename),n)

 

 

>>> d.extendleft('abc')              # extendleft() reverses the inputorder

>>> d

deque(['c', 'b', 'a'])

另外rotate()方法提供了实现索引和删除的一种方法:

def delete_nth(d, n):

    d.rotate(-n)

    d.popleft()

d.rotate(n)

 

参考资料:

Deque (http://en.wikipedia.org/wiki/Deque) Wikipedia articlethat provides a discussion

of the deque data structure.

Deque Recipes (http://docs.python.org/lib/deque-recipes.html)Examples of using

deques in algorithms from the standard library documentation.



原文链接:http://blog.csdn.net/oychw/article/details/8812728
<无标签>
举报
长平狐
发帖于5年前 1回/5K+阅
顶部