Welcome to Mihooke's blog

• 常用数据结构与算法再整理（C++版）

  2019-03-09

  DataStructure&Algorithm

  Data-Structure  Algorithm

  说到再整理，很惭愧，以前学习数据结构与算法，没有系统性地学习过，本次整理，是结合近几年的工作经验整理常用的数据结构和算法。

  先列一个list，后续文章详细介绍每个知识点， 并附上C++版实现代码。

  数据结构部分

  array
  
  vector
  
  list
  
  slist
  
  dequeue
  
  queue
  
  stack
  
  heap
  
  priority_queue
  
  hashtable
  
  binary search tree
  
  balanced binary search tree
  
  AVL tree
  
  B tree
  
  B+ tree
  
  RB tree
  
  trie tree
  
  set
  
  map
  
  multiset
  
  multimap
  
  unordered_set (hash_set)
  
  unordered_map (hash_map)
  
  hash_multiset
  
  hash_multimap
  

  算法

  binary search
  
  bubble sort
  
  insert sort
  
  section sort
  
  quick sort
  
  shell sort
  
  merge sort
  
  heap sort
  
  bucket sort
  
  radix sort
  
  external sort
  
  LRU
  
  Bloom filter
  
  breadth first search
  
  depth first search
  

  Read All

  ---

• 《重构》笔记

  2019-03-02

  Refactor

  Refactor  BadCode  OO  Object

  书中有一句名言：要嗅到坏代码的味道

  –重新组织函数–

  1. Extract Method-提炼函数，从大的函数中提炼出小函数，消除临时变量，提炼关键要看函数名称和函数本体之间的语义距离。
  2. Inline Method-内联函数，若函数调用中不需要一层间接性，可直接把函数内容复制到调用处
  3. Inline Temp-内联临时变量，一个临时变量，被表达式赋了一次值，则可以去掉这个临时变量，取而代之的是这个表达式
  4. Replace Temp With Query-以查询取代临时变量，临时变量被表达式赋值了，可以把表达式提取到一个函数中
  5. Introduce Explaining Variable-引入解释性变量，如果逻辑表达式复杂，可以用临时变量来说明表达式的意义
  6. Split Temporary Variable-分解临时变量，如果一个临时变量承担了多个责任，应该使用多个临时变量
  7. Replace Method With Method Object-以函数对象取代函数，如果有一个大型函数，无法使用Extract Method完成分解，就可以用此法，把临时对象封装到新的对象中，新的对象用成员函数来完成各个临时变量的工作
  8. Substitute Algorithm-替换算法，一段程序实现方法看上去比较笨，换一种写法

  –在对象之间搬移特性–

  1. Move Method-移动函数，在一个类中，对另一个类的某些属性调用多了，可以考虑在后者中添加一个函数，前者调用后者，只保留委托调用
  2. Move Field-移动字段，同上，某个成员变量移到另一个类中
  3. Extract Class-提炼类，某个类做了多类事情
  4. Inline Class-内联类，某个类没有做太多事情
  5. Hide Delegate-隐藏委托关系，将委托类声明为私有的
  6. Remove Middle Man-移除中间人，某个类做了委托类更多的工作，可以直接让用户调用委托类的接口
  7. Introduce Foreign Method-引入外部函数，服务类没有提供此接口，但这个功能理应在服务类中，并且服务类不可修改，可用外部函数实现
  8. Introduce Local Extension-引入本地扩展，需要为服务类提供一些函数，但服务类不可修改，可引入新的类来做，新的类可以是子类继承服务类，也可以是包装类，包装服务类所有的功能

  –重新组织数据–

  1. Self Encapsulate Field-自封装字段，类内访问成员变量，可根据自己喜好封装为取值函数
  2. Replace Data Value With Object-以对象取代数据值，某些成员变量可封装在一个单独的类中
  3. Change Value To Reference-将值对象改为引用对象，当多个实例需要拥有一个对象时，可利用静态工厂函数预生成若干对象，然后从中取值
  4. Change Reference To Value
  5. Replace Array With Object-以对象取代数组，一个数组的元素代表不同东西，用对象来表示
  6. Duplicate Observed Data-赋值被监视的数据，Gui的数据有时候需要在逻辑层保留一份拷贝使用，需要把它复制到新的对象中，使用observer模式来同步数据
  7. Change Unidirectional Association To Bidirectional-将单向关联改为双向关联，两个类之间关系的单向引用，如a调用了b，现在需要在b中调用a的方法，让其中一个类（最好是单个类）作为控制角色
  8. Change Bidirectional Association To Unidirectional-将双向关联改为单向关联
  9. Replace Magic Number With Symbolic Constant-以字面常量取代魔数
  10. Encapsulate Field-封装字段，Public成员变量变为private，并提供相应public成员函数来访问这些成员变量
  11. Replace Record With Data Class-以数据类取代记录，这些记录是以非面向对象程序存在的，新建类表示这个记录
  12. Replace Type Code With Class-以类取代类型码，比如枚举，或者一些常量数字，都有特定含义，此类存在没有类型检查，将它们封装在一个类里面，并通过成员函数来访问这些类型码
  13. Replace Type Code With Subclass-以子类取代类型码，若用类取代会影响宿主类的行为，可以用子类多态来处理变化行为
  14. Replace Type Code With State/Strategy-以state/Strategy模式取代类型码，类型码无法通过子类消除，并且会影响类的行为，可利用state/Strategy模式，将类型码独立成类，如果有switch判断，可以分出子类来表现不同的行为
  15. Replace Subclass With Field-以字段取代子类，子类只是函数的返回值不同，可在父类中增加成员变量来表示子类的行为，并消除子类

  –简化条件表达式–

  1. Decompose Conditional-分解条件表达式，把if条件提取到一个函数中，同样if和else下面的语句也分别提取到函数中
  2. Consolidate Conditional Expression-合并条件表达式，检查条件不同，但结果相同，可以合并条件到一起或提取为函数，类似情况还有嵌套条件判断，可用逻辑与合并条件；合理利用三元操作符条件表达式
  3. Consolidate Duplicate Conditional Fragments-合并重复的条件片段，If和else下面的语句有相同的，何以提取出来
  4. Remove Control Flag-移除控制标记，控制标记即控制循环的标记，可以不必遵守条件判断的单一出口原则，适当使用break或continue或return来跳出循环
  5. Replace Nested Conditional With Guard Clauses-以卫语句取代嵌套条件表达式，卫语句是如果某个检查条件很罕见，就应该单独检查，单独检查的语句就是卫语句；嵌套条件判断分为多个卫语句，可以让函数有多个出口
  6. Replace Conditional With Polymorphism-以多态取代条件表达式，根据对象类型的不同作为条件，可抽象子类
  7. Introduce Assertion-引入断言，某段代码需要对程序状态做出某种假设，可以用断言明确表现这种假设

  –简化函数调用–

  1. Rename Method-函数改名，要想成为一个真正的编程高手，起名的水平是至关重要的
  2. Add Parameter-添加参数
  3. Remove Parameter-移除参数
  4. Separate Query From Modifier-将查询函数和修改函数分离
  5. Parameterize Method-令函数携带参数，相同功能的函数内部可能只有某几个变量不一样，可以把它们提取到参数中
  6. Replace Parameter With Explicit Methods-以明确函数取代参数，函数内根据参数的类型来做不同的事情，可把不同的事情明确地放在新的函数中，从而原来函数的参数就可以去掉了
  7. Preserve Whole Object-保持对象完整，从某个对象中取出若干值，并作为函数的参数，可修改为参数传递整个对象
  8. Replaceparameter With Method-以函数取代参数，对象调用某个函数，并把返回值作为另一个函数的参数，而后者也可以调用前一个函数，可以改为直接让后者调用前者，从而缩短参数列表
  9. Introduce Parameter Object-引入参数对象，函数的参数总是一起出现，可以考虑把一起出现的参数封装在一个类中，转而传递对象
  10. Remove Setting Method-移除设值函数，如果某个成员变量，希望在初始化后不再改变，可以把设值函数去掉
  11. Hide Method-隐藏函数，成员函数没有被其他类用到，设为private
  12. Replace Constructor With Factory Method-以工厂函数取代构造函数
  13. Replace Error Code With Exception-以异常取代错误码，函数以错误码来表示异常时，可把错误码改成异常
  14. Replace Exception With Test-以测试取代异常，异常不能被滥用，只适合用在意料外的情况，假如某个判断条件可以预先知道，可换为条件测试来判断

  –处理概括关系–

  概括关系主要指继承体系中的关系

  1. Pull Up Field-上移字段，两个子类有相同的成员变量，可将此移至父类中
  2. Pull Up Method-函数上移
  3. Pull Up Constructor Body-构造函数本体上移，子类的构造函数本体几乎完全一致，可提取共同部分到父类中
  4. Push Down Method-函数下移，父类中函数只被部分子类使用，可移到相应的子类中
  5. Push Down Field-字段下移
  6. Extract Subclass-提炼子类，类中的某些特性只被部分实例用到，可把这些特性提炼到一个新的子类中
  7. Extract Superclass-提炼超类
  8. Extract Interface-提炼接口
  9. Collapse Hierarchy-折叠继承体系，父类与子类无太大区别
  10. Form Template Method-塑造模板函数，子类们有个函数行为相似，细节操作上不同，可把函数相同部分提到父类中，子类中调用新的提炼函数
  11. Replace Inheritance With Delegation-以委托取代继承，某个子类只使用父类接口的一部分，或根本不需要继承而来的数据，可用委托代替继承关系
  12. Replace Delegation With Inheritance-以继承取代委托

  –大型重构–

  1. Tease Apart Inheritance-梳理并分解继承体系，某个类做了若干件不同的事，就需要拆解此类
  2. Convert Procedural Design To Objects-将过程化设计转化为对象设计
  3. Separate Domain From Presentation-将领域和显示分离，MVC模式
  4. Extract Hierarchy-提炼继承体系，某个类做了太多工作，其中一部分以大量条件表达式完成，可以以一个子类来表示特殊情况
  Read All

  ---

• QVariant转enum

  2019-02-16

  C++

  QVariant  enum  Qt  Meta-object

  QVariant 是 Qt 中的万用类型，可表示 Qt 中大多数类型，但无法表示自定义的 enum 类型，这就需要借助 Qt 的元对象系统了。

  enum Type
  {
      A,
      B
  };
  

  添加自定义类型到元系统

  Q_DECLARE_METATYPE(Type)

  这个宏使系统（QMetaType）知道该自定义类型，包括 QVariant

  enum Type
  {
      A,
      B
  };
  Q_DECLARE_METATYPE(Type)
  

  这样，enum 就可以被用于 QVariant 了，可以这么用：

  QVariant type = QVariant::fromValue(Type::A); // 设置值
  Type t = type.value<Type>(); // 取值
  

  Read All

  ---

• Python try except pass使用注意

  2019-01-23

  Python

  except  pass

  Python try except使用注意

  在 Python 中，我们可能会经常使用 try except 来捕获异常，比如：

  try:
      value = info_dict["key"]
  except KeyError:
      print("Error key")
  

  这段代码捕获的是 dict 的 KeyError 异常，当发生此异常时，会打印一句话。

  有时候，为了图省事方便，你可能会这么写：

  try:
      # some operation
  except:
      pass # pass 意味着什么都不做
  

  当心！这么写是一个很糟糕的习惯。

  我们来看看糟糕在哪里：

  1. 隐藏了错误
  2. 捕获了所有异常，甚至包括系统异常

  隐藏了错误

  在 except 分支中只有 pass 语句，即发生异常时，什么也不做，程序继续执行，此时的状态很可能是错误的，正确的做法是在异常分支中打印适当的信息，以告诉用户发生了什么。

  捕获了所有异常，甚至包括系统异常

  没有指定异常类型，程序便会捕获所有异常，包括Python中的各种异常，也包括内存满了，CPU 爆了，程序退出异常等系统性异常，正确的做法是指定对应的异常：

  try:
      # some operation
  except Exception as e:
      print("Exception occured:", e)
  

  指定 Exception 会捕获所有 Python 的异常，并打印出异常信息。

  Read All

  ---

• 引用限定（Ref-qualifiers）

  2019-01-20

  C++

  Ref-qualifiers  c++11  efficiency

  先看一个例子：

  class A
  {
      vector<int> _v;
  public:
      void setter(const vector<int> &v)
      {
          cout << "lvalue setter" << endl;
          _v = v;
      }
      void setter(vector<int> &&v)
      {
          cout << "rvalue setter" << endl;
          _v = move(v);
      }
      const vector<int>& getter() const
      {
          cout << "getter" << endl;
          return _v;
      }
  };
  
  A AFactory()
  {
      A a1;
      a1.setter(vector<int>{1});
      return a1;
  }
  
  A a2;
  a2.setter(AFactory().getter());
  
  输出：
  rvalue setter
  getter
  lvalue setter
  

  注意第三个输出，表示 a2 对象调用了左值引用版本。但实际上呢？

  AFactory().getter()
  

  的返回值是一个左值引用，a1 对象是临时对象，在语句执行完后就被销毁了，因此，a1.getter() 返回值也会被销毁，既然都会被销毁，那么 a2.setter() 期望调用的是右值重载版本，当然，这需要能够识别出一个对象是否是临时对象，c++11 提供了引用限定的成员函数（Ref-qualifiers for member function），能够根据对象来调用不同的成员函数。书写方式是在函数名括号后面加&或&&。

  上述代码可修改为：

  // 非临时对象调用版本
  const vector<int>& getter() const &
  {
      cout << "lvalue getter" << endl;
      return _v;
  }
  // 临时对象调用版本
  vector<int>&& getter() &&
  {
      cout << "rvalue getter" << endl;
      return move(_v);
  }
  
  输出：
  rvalue setter
  rvalue getter
  lvalue setter
  

  Read All

  ---

• ZMQ简介

  2019-01-13

  C++

  ZMQ  socket

  文章内容节选自 https://github.com/anjuke/zguide-cn。文章翻译自ZMQ官网指南。

  ZMQ（ØMQ、ZeroMQ, 0MQ）看起来像是一套嵌入式的网络链接库，但工作起来更像是一个并发式的框架。它提供的套接字可以在多种协议中传输消息，如线程间、进程间、TCP、广播等。你可以使用套接字构建多对多的连接模式，如扇出、发布-订阅、任务分发、请求-应答等。ZMQ的快速足以胜任集群应用产品。它的异步I/O机制让你能够构建多核应用程序，完成异步消息处理任务。

  为什么需要ZMQ？

  目前的应用程序很多都会包含跨网络的组件，无论是局域网还是因特网。这些程序的开发者都会用到某种消息通信机制。有些人会使用某种消息队列产品，而大多数人则会自己手工来做这些事，使用TCP或UDP协议。这些协议使用起来并不困难，但是，简单地将消息从A发给B，和在任何情况下都能进行可靠的消息传输，这两种情况显然是不同的。

  让我们看看在使用纯TCP协议进行消息传输时会遇到的一些典型问题。任何可复用的消息传输层肯定或多或少地会要解决以下问题：

  • 如何处理I/O？是让程序阻塞等待响应，还是在后台处理这些事？这是软件设计的关键因素。阻塞式的I/O操作会让程序架构难以扩展，而后台处理I/O也是比较困难的。
  • 如何处理那些临时的、来去自由的组件？我们是否要将组件分为客户端和服务端两种，并要求服务端永不消失？那如果我们想要将服务端相连怎么办？我们要每隔几秒就进行重连吗？
  • 我们如何表示一条消息？我们怎样通过拆分消息，让其变得易读易写，不用担心缓存溢出，既能高效地传输小消息，又能胜任视频等大型文件的传输？
  • 如何处理那些不能立刻发送出去的消息？比如我们需要等待一个网络组件重新连接的时候？我们是直接丢弃该条消息，还是将它存入数据库，或是内存中的一个队列？
  • 要在哪里保存消息队列？如果某个组件读取消息队列的速度很慢，造成消息的堆积怎么办？我们要采取什么样的策略？
  • 如何处理丢失的消息？我们是等待新的数据，请求重发，还是需要建立一套新的可靠性机制以保证消息不会丢失？如果这个机制自身崩溃了呢？
  • 如果我们想换一种网络连接协议，如用广播代替TCP单播？或者改用IPv6？我们是否需要重写所有的应用程序，或者将这种协议抽象到一个单独的层中？
  • 我们如何对消息进行路由？我们可以将消息同时发送给多个节点吗？是否能将应答消息返回给请求的发送方？
  • 我们如何为另一种语言写一个API？我们是否需要完全重写某项协议，还是重新打包一个类库？
  • 怎样才能做到在不同的架构之间传送消息？是否需要为消息规定一种编码？
  • 我们如何处理网络通信错误？等待并重试，还是直接忽略或取消？

  我们可以找一个开源软件来做例子，如Hadoop Zookeeper，看一下它的C语言API源码，src/c/src/zookeeper.c。这段代码大约有3200行，没有注释，实现了一个C/S网络通信协议。它工作起来很高效，因为使用了poll()来代替select()。但是，Zookeeper应该被抽象出来，作为一种通用的消息通信层，并加以详细的注释。像这样的模块应该得到最大程度上的复用，而不是重复地制造轮子。

  但是，如何编写这样一个可复用的消息层呢？为什么长久以来人们宁愿在自己的代码中重复书写控制原始TCP套接字的代码，而不愿编写这样一个公共库呢？

  其实，要编写一个通用的消息层是件非常困难的事，这也是为什么FOSS项目不断在尝试，一些商业化的消息产品如此之复杂、昂贵、僵硬、脆弱。2006年，iMatix设计了AMQP协议，为FOSS项目的开发者提供了可能是当时第一个可复用的消息系统。AMQP比其他同类产品要来得好，但仍然是复杂、昂贵和脆弱的。它需要花费几周的时间去学习，花费数月的时间去创建一个真正能用的架构，到那时可能为时已晚了。

  大多数消息系统项目，如AMQP，为了解决上面提到的种种问题，发明了一些新的概念，如“代理”的概念，将寻址、路由、队列等功能都包含了进来。结果就是在一个没有任何注释的协议之上，又构建了一个C/S协议和相应的API，让应用程序和代理相互通信。代理的确是一个不错的解决方案，帮助降低大型网络结构的复杂度。但是，在Zookeeper这样的项目中应用代理机制的消息系统，可能是件更加糟糕的事，因为这意味了需要添加一台新的计算机，并构成一个新的单点故障。代理会逐渐成为新的瓶颈，管理起来更具风险。如果软件支持，我们可以添加第二个、第三个、第四个代理，构成某种冗余容错的模式。有人就是这么做的，这让系统架构变得更为复杂，增加了隐患。

  在这种以代理为中心的架构下，需要一支专门的运维团队。你需要昼夜不停地观察代理的状态，不时地用棍棒调教他们。你需要添加计算机，以及更多的备份机，你需要有专人管理这些机器。这样做只对那些大型的网络应用程序才有意义，因为他们有更多可移动的模块，有多个团队进行开发和维护，而且已经经过了多年的建设。

  这样一来，中小应用程序的开发者们就无计可施了。他们只能设法避免编写网络应用程序，转而编写那些不需要扩展的程序；或者可以使用原始的方式进行网络编程，但编写的软件会非常脆弱和复杂，难以维护；亦或者他们选择一种消息通信产品，虽然能够开发出扩展性强的应用程序，但需要支付高昂的代价。似乎没有一种选择是合理的，这也是为什么在上个世纪消息系统会成为一个广泛的问题。

  我们真正需要的是这样一种消息软件，它能够做大型消息软件所能做的一切，但使用起来又非常简单，成本很低，可以用到所有的应用程序中，没有任何依赖条件。因为没有了额外的模块，就降低了出错的概率。这种软件需要能够在所有的操作系统上运行，并能支持所有的编程语言。

  ZMQ就是这样一种软件：它高效，提供了嵌入式的类库，使应用程序能够很好地在网络中扩展，成本低廉。

  ZMQ的主要特点有：

  • ZMQ会在后台线程异步地处理I/O操作，它使用一种不会死锁的数据结构来存储消息。
  • 网络组件可以来去自如，ZMQ会负责自动重连，这就意味着你可以以任何顺序启动组件；用它创建的面向服务架构（SOA）中，服务端可以随意地加入或退出网络。
  • ZMQ会在有必要的情况下自动将消息放入队列中保存，一旦建立了连接就开始发送。
  • ZMQ有阈值（HWM）的机制，可以避免消息溢出。当队列已满，ZMQ会自动阻塞发送者，或丢弃部分消息，这些行为取决于你所使用的消息模式。
  • ZMQ可以让你用不同的通信协议进行连接，如TCP、广播、进程内、进程间。改变通信协议时你不需要去修改代码。
  • ZMQ会恰当地处理速度较慢的节点，会根据消息模式使用不同的策略。
  • ZMQ提供了多种模式进行消息路由，如请求-应答模式、发布-订阅模式等。这些模式可以用来搭建网络拓扑结构。
  • ZMQ中可以根据消息模式建立起一些中间装置（很小巧），可以用来降低网络的复杂程度。
  • ZMQ会发送整个消息，使用消息帧的机制来传递。如果你发送了10KB大小的消息，你就会收到10KB大小的消息。
  • ZMQ不强制使用某种消息格式，消息可以是0字节的，或是大到GB级的数据。当你表示这些消息时，可以选用诸如谷歌的protocol buffers，XDR等序列化产品。
  • ZMQ能够智能地处理网络错误，有时它会进行重试，有时会告知你某项操作发生了错误。
  • ZMQ甚至可以降低对环境的污染，因为节省了CPU时间意味着节省了电能。

  其实ZMQ可以做的还不止这些，它会颠覆人们编写网络应用程序的模式。虽然从表面上看，它不过是提供了一套处理套接字的API，能够用zmq_recv()和zmq_send()进行消息的收发，但是，消息处理将成为应用程序的核心部分，很快你的程序就会变成一个个消息处理模块，这既美观又自然。它的扩展性还很强，每项任务由一个节点（节点是一个线程）、同一台机器上的两个节点（节点是一个进程）、同一网络上的两台机器（节点是一台机器）来处理，而不需要改动应用程序。

  Read All

  ---