Python厨书笔记-2

数据结构与算法(二)

1. 数据结构与算法

2. 1. 序列中出现次数最多的元素

用途

  • 找出一个序列中出现次数最多的元素

collections.Counter

  • Counter 对象可以接受任意的由可哈希（hashable）元素构成的序列对象。 在底层实现上，一个 Counter 对象就是一个字典，将元素映射到它出现的次数上

  • 更新：CounterObject.update(newlist)

  • 加减：CounterObjectA +/- CounterObjectB

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    words=['a','a','b']
    morewords=['b','c']
    # 统计次数
    word_counts = Counter(words)
    # Counter({'a': 2, 'b': 1})

    # 更新
    word_counts.update(morewords)
    # Counter({'a': 2, 'b': 2, 'c': 1})

    # 加减
    moreword_counts=Counter(morewords)
    word_counts+moreword_counts
    # Counter({'a': 2, 'b': 3, 'c': 2})

    # 注意原本dict与dict是不能直接相加减的
    TypeError: unsupported operand type(s) for +: 'dict' and 'dict'

Counter.most_common(N)

  • 统计最高频的前$N$个

    1
    2
    top_three = word_counts.most_common(1)
    # [('a', 2)]

3. 2. 字典列表的关键字排序

用途

  • 根据某个或某几个字典字段来排序一个字典列表

operator.itemgetter

  • 支持多个 keys

  • 配合sorted

    • sorted() 函数有一个关键字参数 key ，可以传入一个 callable 对象给它， 这个 callable 对象对每个传入的对象返回一个值，这个值会被 sorted 用来排序这些对象
    • itemgetter() 函数负责创建 callable 对象(同lambda)
    • 实际上，可以当作lambda的更快的替代，因此也自然可以用于其他lambda适用的类型
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    rows = [
        {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
        {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
        {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
        {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
    ]

    # 单keys
    rows_by_uid = sorted(rows, key=itemgetter('uid'))
    '''
    [{'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
     {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
     {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
     {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}]
    '''

    # 多keys
    rows_by_lfname = sorted(rows, key=itemgetter('lname','fname'))
    '''
    [{'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
     {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
     {'fname': 'Big', 'lname': 'Jones', 'uid': 1004},
     {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
    '''

    # 等价lambda
    rows_by_lfname = sorted(rows, key=lambda r: (r['lname'],r['fname']))

4. 3. 排序不支持原生比较的对象

用途

  • 排序类型相同的对象，但是他们不支持原生的比较操作

operator.attrgetter()

  • 和operator.itemgetter差不多，只不过上一个是用于字典
  • 同样可以多参数
  • 同样是lambda更好的替代
1
2
3
4
5
6
7
8
9
10
11
12
class User:
    def __init__(self, user_id):
        self.user_id = user_id

    def __repr__(self):
        return 'User({})'.format(self.user_id)
    
users = [User(23), User(3), User(99)]
sorted(users, key=attrgetter('user_id'))

# lambda
sorted(users, key=lambda u: u.user_id)

5. 4. 通过某个字段将记录分组

用途

  • 根据某个特定的字段，来分组迭代访问一个字典或者实例的序列

itertools.groupby()

  • 扫描整个序列并且查找连续相同值（或者根据指定 key 函数返回值相同）的元素序列。 在每次迭代的时候，它会返回一个值和一个迭代器对象

  • 一个非常重要的准备步骤是要根据指定的字段将数据排序。 因为 groupby() 仅仅检查连续的元素，如果事先并没有排序完成的话，分组函数将得不到想要的结果

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    rows = [
        {'address': '5412 N CLARK', 'date': '07/01/2012'},
        {'address': '5148 N CLARK', 'date': '07/04/2012'},
        {'address': '5800 E 58TH', 'date': '07/02/2012'},
        {'address': '2122 N CLARK', 'date': '07/03/2012'},
        {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
        {'address': '1060 W ADDISON', 'date': '07/02/2012'},
        {'address': '4801 N BROADWAY', 'date': '07/01/2012'},
        {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
    ]

    # Sort by the desired field first
    rows.sort(key=itemgetter('date'))
    # Iterate in groups
    for date, items in groupby(rows, key=itemgetter('date')):
        print(date)
        for i in items:
            print(' ', i)
            
    '''
    07/01/2012
      {'date': '07/01/2012', 'address': '5412 N CLARK'}
      {'date': '07/01/2012', 'address': '4801 N BROADWAY'}
    07/02/2012
      {'date': '07/02/2012', 'address': '5800 E 58TH'}
      {'date': '07/02/2012', 'address': '5645 N RAVENSWOOD'}
      {'date': '07/02/2012', 'address': '1060 W ADDISON'}
    07/03/2012
      {'date': '07/03/2012', 'address': '2122 N CLARK'}
    07/04/2012
      {'date': '07/04/2012', 'address': '5148 N CLARK'}
      {'date': '07/04/2012', 'address': '1039 W GRANVILLE'}
    '''

6. 5. 过滤序列元素

用途

  • 用一些规则从中提取出需要的值或者是缩短序列

方法

  • 列表推导

    • 列表推导的一个潜在缺陷就是如果输入非常大的时候会产生一个非常大的结果集，占用大量内存

  • 生成器表达式

    • 有时候，过滤规则比较复杂，不能简单的在列表推导或者生成器表达式中表达出来。 比如，假设过滤的时候需要处理一些异常或者其他复杂情况
    • 列表推导和生成器表达式通常情况下是过滤数据最简单的方式。 其实它们还能在过滤的时候转换数据

  • filter

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    values = ['1', '2', '-3', '-', '4', 'N/A', '5']
    def is_int(val):
        try:
            x = int(val)
            return True
        except ValueError:
            return False
    ivals = list(filter(is_int, values))
    print(ivals)
    # Outputs ['1', '2', '-3', '4', '5']

  • 过滤操作的变种：将不符合条件的值用新的值代替

    1
    x = [n if n > 0 else 0 for n in mylist]

  • lambda补充

    • 注意不同的写法会有不同的效果
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    portfolio = [
        {'name':'GOOG', 'shares': 50},
        {'name':'YHOO', 'shares': 75},
        {'name':'AOL', 'shares': 20},
        {'name':'SCOX', 'shares': 65}
    ]

    # Original: Returns 20，生成的是一个iterable列表
    min_shares = min(s['shares'] for s in portfolio)
    # Alternative: Returns {'name': 'AOL', 'shares': 20}，生成的是一个callable对象
    min_shares = min(portfolio, key=lambda s: s['shares'])

itertools.compress

  • 参数一：iterable对象

  • 参数二：bool序列作为选择器

  • 输出：对应位True的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    addresses = [
        '5412 N CLARK',
        '5148 N CLARK',
        '5800 E 58TH',
        '2122 N CLARK',
        '5645 N RAVENSWOOD',
        '1060 W ADDISON',
        '4801 N BROADWAY',
        '1039 W GRANVILLE',
    ]
    counts = [ 0, 3, 10, 4, 1, 7, 6, 1]

    more5 = [n > 5 for n in counts]
    # [False, False, True, False, False, True, True, False]
    list(compress(addresses, more5))
    # ['5800 E 58TH', '1060 W ADDISON', '4801 N BROADWAY']

7. 6. 从字典中提取子集

用途

  • 构造一个字典，它是另外一个字典的子集

字典推导

  • p1 = {key: value for key, value in prices.items() if value > 200}

8. 7. 映射名称到序列元素

用途

  • 取代用下标访问列表
  • 字典的新形式

collections.namedtuple()

  • 传递一个类名和你需要的字段给它，然后它就会返回一个类

    • 类的私有属性函数__replace()

  • 命名元组的一个主要用途是将你的代码从下标操作中解脱出来。 因此，如果你从数据库调用中返回了一个很大的元组列表，却通过下标去操作其中的元素， 那当你在表中添加了新的列的时候你的代码可能就会出错了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # 使用前
    def compute_cost(records):
        total = 0.0
        for rec in records:
            total += rec[1] * rec[2]
        return total

    # 使用后
    Stock = namedtuple('Stock', ['name', 'shares', 'price'])
    def compute_cost(records):
        total = 0.0
        for rec in records:
            s = Stock(*rec)
            total += s.shares * s.price
        return total

  • 命名元组另一个用途就是作为字典的替代，因为字典存储需要更多的内存空间。 如果你需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效

    • 一般命名元组是不可更改，但可以用_replace() 方法， 它会创建一个全新的命名元组并将对应的字段用新的值取代

      • __replace()还可以用于填补声明时的可选或者缺失字段
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      # 新值
      s = s._replace(shares=75)

      # 填补
      Stock = namedtuple('Stock', ['name', 'shares', 'price', 'date', 'time'])
      stock_prototype = Stock('', 0, 0.0, None, None)
      def dict_to_stock(s):
          return stock_prototype._replace(**s)
      a = {'name': 'ACME', 'shares': 100, 'price': 123.45}
      dict_to_stock(a)
      # Stock(name='ACME', shares=100, price=123.45, date=None, time=None)

    • Remark：显然这种替代是有限的，一旦涉及动态(比如求直方图)，或者初始不能那个完全确定键的种类，都难以（或者不应）运用此方法

9. 8. 合并多个字典或映射

用途

  • 将多个字典或者映射从逻辑上合并为一个单一的映射

collections.ChainMap

  • 物理上并未合并，即ChainMap 类只是在内部创建了一个容纳这些字典的列表 并重新定义了一些常见的字典操作来遍历这个列表。

  • 如果出现重复键，那么第一次出现的映射值会被返回

  • 对于字典的更新或删除操作总是影响的是列表中第一个字典

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    a = {'x': 1, 'z': 3 }
    b = {'y': 2, 'z': 4 }
    c = ChainMap(a,b)
    print(c['x']) # Outputs 1 (from a)
    print(c['y']) # Outputs 2 (from b)
    print(c['z']) # Outputs 3 (from a)

    # 更新
    c['z'] = 10
    # 添加
    c['w'] = 40
    # 删除
    del c['x']

    print(a)
    # {'w': 40, 'z': 10}

    del c['y']
    # KeyError: "Key not found in the first mapping: 'y'"