【2017-09-08】数据结构与算法（七）

序列

• 删除相同元素并保持序列顺序
  问题：*怎样在一个序列上面保持元素顺序的同时消除重复的值？
  方案：
  • 利用集合，但是不维护序列的顺序，无序
  • 利用sorted() 、min()、max()等内置函数思想，自定义一个函数

#示例：使用集合:对结果的顺序无要求，可以考虑
>>> list1=[1,3,4,3,4,2,1,8]
>>> set(list1)
{8, 1, 2, 3, 4}
>>> list3=[(1,2),(2,3),(1,2)]
>>> set(list3)
{(1, 2), (2, 3)}
>>>

   由上述例子可见，集合去掉重复元素后，不能保持原有的顺序，这也是集合的特性。
   如果需要既要消除重复元素，又要维持序列原有的顺序，可参考sorted（）等内置函数的思想，结合集合自定义一个返回生成器的函数。

#示例1：列表去重并保持顺序
>>> def dedup(items):
    setp=set()
    for i in items:
        if i not in setp:
            yield i
            setp.add(i)

            
>>> dedup(list1)
<generator object dedup at 0x022AE330>
>>>#当结果足够大时，尽量不要直接转换成list，这里只是示例
>>> list(dedup(list1))
[1, 3, 4, 2, 8]

   如果序列的元素为字典类型呢？用上述方法不可用，理由是序列元素（字典）不属于hashable类型，需要将字典变成hashable类型，换言之，将键值对转化成元组形式。
引申概念
   什么是可哈希（hashable）的？一个 object 是可哈希的（hashable），是指这个 object 在其生存期内有一个不变的哈希值（hash value），即hash() 方法返回的值。

示例2：元素为字典类型的序列
>>> list1=[1,3,4,3,4,2,1,8]
>>> list2=[{'x':1,'y':2},{'x':1,'y':3},{'x':1,'y':5},{'x':1,'y':2}]
>>> def dedup(items,key=None):
    setp=set()
    for item in items:
        val=item if key is None else  key(item )
        if val not in setp:
            yield val
            setp.add(val)
>>> list(dedup(list1))
[1, 3, 4, 2, 8]
>>> for i in dedup(list2,key=lambda x:(x['x'],x['y'])):
    print(i)
    
(1, 2)
(1, 3)
(1, 5)
>>> 

• 对象不支持原生的比较操作
  问题：如果你想排序同类对象，但是元素的比较操作不支持直接比较？
  方案:
     在类实例对象中，利用sorted（）函数关键字参数key特性，可以传入一个 callable 对象给它，这个 callable 对象对每个传入的对象返回一个值，这个值会被 sorted 用来排序这些对象。
     key对应函数的实现
        - lambda匿名函数实现
        - operator模块attrgetter()函数实现，支持多个字段进行排序。用法类似用于字典的 operator.itemgetter()

#示例
>>> from operator import attrgetter
>>> 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)]
>>> users
[User(23), User(3), User(99)]
>>> sorted(users,key=lambda user:user.user_id)
[User(3), User(23), User(99)]
>>> sorted(users,key=attrgetter('user_id'))
[User(3), User(23), User(99)]
>>> 

总结
   数据结构与算法这一章节基本学习结束，大部分内容基本理解，少部分内容不甚理解，待后续学习的深入，再回头看看。通过最近每天学习一点点，最大的感受是豁然开朗：思路更开阔，想法更多。回顾以前写的脚本或者正在写的脚本，仍有很多地方需要改善，怎么让代码更优雅、更简洁、可读、不重复造轮子，仍然值得进一步思考。