主流操作系统结束符

测试环境：win10 + python2.7

1
2
3
4
5
6

for char in ("\n", "\r\n"):
    for mode in ("w", "wb"):
        filename = "%s_%s.txt" % (mode, "n" if len(char) == 1 else "rn")
        with open(filename, mode) as f:
            for x in range(5):
                f.write("%s%s" % (x, char))

1
2
3
4

w_n.txt   \r\n
w_rn.txt   \r\n
wb_n.txt   \n
wb_rn.txt   \r\n

1. “w”方式写时的’\n’会在被系统自动替换为’\r\n’
2. “wb”方式写时的’\n’和’\r\n’保持原样

1
2
3
4
5

for filename in ("test_n.txt", "test_rn.txt"):
    for mode in ("r", "rb"):
        with open(filename, mode) as f:
            info = f.read()
            print(filename, mode, info.__repr__())

1
2
3
4

('test_n.txt', 'r', "'aa\\nsdfd\\ndffdf\\n'")
('test_n.txt', 'rb', "'aa\\nsdfd\\ndffdf\\n'")
('test_rn.txt', 'r', "'aa\\nsdfd\\ndffdf\\n'")
('test_rn.txt', 'rb', "'aa\\r\\nsdfd\\r\\ndffdf\\r\\n'")

3. “r”方式读时，文件中的’\r\n’会被系统替换为’\n’
4. “rb”方式读时，文件中的’\r\n’或’\n’保持原样

测试环境：linux + python2.7

1
2
3
4

w_n.txt   \n
w_rn.txt   \r\n
wb_n.txt   \n
wb_rn.txt   \r\n

1. “w”和”wb”方式写时的’\r\n’和’\n’都保持原样

1
2
3
4

('test_n.txt', 'r', "'aa\\nsdfd\\ndffdf\\n'")
('test_n.txt', 'rb', "'aa\\nsdfd\\ndffdf\\n'")
('test_rn.txt', 'r', "'aa\\r\\nsdfd\\r\\ndffdf\\r\\n'")
('test_rn.txt', 'rb', "'aa\\r\\nsdfd\\r\\ndffdf\\r\\n'")

2. “r”和”rb”方式读时，文件中的’\r\n’和’\n’都保持原样

• linux的所有读写方式都会保持换行符原样

1.安装sphinx

pip3 install sphinx

2.设置文档来源

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
34
35
36

➜  Sphinx git:(master) ✗ sphinx-quickstart
欢迎使用 Sphinx 2.3.1 快速配置工具。

请输入接下来各项设置的值（如果方括号中指定了默认值，直接
按回车即可使用默认值）。

已选择根路径：.

布置用于保存 Sphinx 输出的构建目录，有两种选择。
一是在根路径下创建“_build”目录，二是在根路径下创建“source”
和“build”两个独立的目录。
> 独立的源文件和构建目录（y/n） [n]: y

项目名称会出现在文档的许多地方。
> 项目名称: ProjectName
> 作者名称: xiaohao
> 项目发行版本 []: 

If the documents are to be written in a language other than English,
you can select a language here by its language code. Sphinx will then
translate text that it generates into that language.

For a list of supported codes, see
https://www.sphinx-doc.org/en/master/usage/configuration.html#confval-language.
> 项目语种 [en]: cn

创建文件 ./source/conf.py。
创建文件 ./source/index.rst。
创建文件 ./Makefile。
创建文件 ./make.bat。

完成：已创建初始目录结构。

你现在可以填写主文档文件 ./source/index.rst 并创建其他文档源文件了。 用 Makefile 构建文档，像这样：
 make builder
此处的“builder”是支持的构建器名，比如 html、latex 或 linkcheck。

3.运行构建

现在，您已经添加了一些文件和内容，让我们开始构建文档。使用sphinx-build程序开始构建：

sphinx-build -b html sourcedir builddir

其中sourcedir是源目录，而builddir是您要在其中放置构建文档的目录。该-b选项选择一个构建器；在此示例中，Sphinx将构建HTML文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

➜  Sphinx git:(master) ✗ sphinx-build -b html source build 
正在运行 Sphinx v2.3.1
正在加载翻译 [cn]... 没有内置信息的翻译
构建 [mo]： 0 个 po 文件的目标文件已过期
构建 [html]： 1 个源文件的目标文件已过期
更新环境: [新配置] 已添加 1，0 已更改，0 已移除
阅读源... [100%] index                                                             
查找当前已过期的文件... 没有找到
pickling环境... 完成
检查一致性... 完成
准备文件... 完成
写入输出... [100%] index                                                            
generating indices...  genindex完成
writing additional pages...  search完成
复制静态文件... ... 完成
copying extra files... 完成
dumping search index in English (code: en)... 完成
dumping object inventory... 完成
构建 成功.

HTML 页面保存在 build 目录。

sphinx-quickstart脚本会创建Makefile和， make.bat这会使您的生活更加轻松。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

➜  Sphinx git:(master) ✗ make html
正在运行 Sphinx v2.3.1
正在加载翻译 [cn]... 没有内置信息的翻译
制作输出目录... 完成
构建 [mo]： 0 个 po 文件的目标文件已过期
构建 [html]： 1 个源文件的目标文件已过期
更新环境: [新配置] 已添加 1，0 已更改，0 已移除
阅读源... [100%] index                                                             
查找当前已过期的文件... 没有找到
pickling环境... 完成
检查一致性... 完成
准备文件... 完成
写入输出... [100%] index                                                            
generating indices...  genindex完成
writing additional pages...  search完成
复制静态文件... ... 完成
copying extra files... 完成
dumping search index in English (code: en)... 完成
dumping object inventory... 完成
构建 成功.

HTML 页面保存在 build/html 目录。

4.调用 sphinx-apidoc

1
2
3

➜  Sphinx git:(master) ✗ sphinx-apidoc -o ./source/src ./Script
创建文件 ./source/src/test.rst。
创建文件 ./source/src/modules.rst。

5. 支持md文件

pip install recommonmark

在conf.py添加扩支持：

extensions = [‘recommonmark’]

6. vscode支持rst预览

reStructuredText插件 + pip install doc8

7. 重点配置说明

1. 源码路径

1
2
3

import os
import sys
sys.path.insert(0, os.path.abspath('../Script'))

这里需要添加python生成api文档的源码路径，一定要绝对路径，所以使用abspath

2. 一些常用插件

1
2
3
4
5
6
7

extensions = [
    "sphinx.ext.autodoc",       # 标准的Python模块扩展,为Sphinx提供的附加功能
    "recommonmark",             # markdown支持
    "sphinx_markdown_tables",   # markdown表格支持
    "sphinx.ext.napoleon",      # 支持numpy和google风格的docstrings
    "sphinx.ext.intersphinx",   # 启用链接
]

3. python官方主题

html_theme = 'sphinx_rtd_theme'

8. 关于init.py的坑

如果源码中存在__init__.py，那么sphinx会将其当成一个模块来看
所以在添加sys.path.insert(0, os.path.abspath('../'))的时候需要在脚本的外层路径（此时将脚本当成一个包）

一、几种单例模式的实现

1. 使用装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def Singleton(cls):
    _instance = {}

    def _single(*args, **kwargs):
        if cls not in _instance:
            _instance[cls] = cls(*args, **kwargs)
        return _instance[cls]

    return _single

@Singleton
class A:
    ...

A()

2. 使用类方法

1
2
3
4
5
6
7
8
9
10
11
12

class Singleton(object):

    @classmethod
    def instance(cls, *args, **kwargs):
        if not hasattr(cls, "_instance"):
            cls._instance = cls(*args, **kwargs)
        return cls._instance

class A(Singleton):
    pass

A.instance()

3. 使用new(推荐)

1
2
3
4
5
6
7
8
9
10
11
12

class Singleton(object):
    _instance = None

    def __new__(cls, *args, **kwargs):
        if not cls._instance:
            cls._instance = object.__new__(cls)
        return cls._instance

class A(Singleton):
    ...

A()

二、几个坑点

1.使用new方式会多次调用init

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Singleton(object):
    _instance = None

    def __new__(cls, *args, **kwargs):
        if not cls._instance:
            cls._instance = object.__new__(cls)
        return cls._instance


class A(Singleton):
    M = 1

    def __init__(self, a):
        print("init", a, self.M)


for i in range(5):
    A(i)

1
2
3
4
5
6

➜ python3 test.py
init 0 1
init 1 1
init 2 1
init 3 1
init 4 1

所以在init里面做初始化逻辑的类需要注意，自己处理一下或者使用其他两种方式

2.关于单例类多继承问题

1
2
3
4
5
6
7
8

class Singleton(object):
    _instance = None

    def __new__(cls, *args, **kwargs):
        if not Singleton._instance:
            Singleton._instance = object.__new__(cls)
        print(cls, Singleton._instance) #
        return Singleton._instance

• 看到网上有这样的一种写法
• 运行起来没什么问题，但是到类有继承关系的时候就会出问题

  1 2 3 4 5 6 7 8

  class A(Singleton): ... class B(Singleton): ... A() B()

1
2
3

➜  python3 test.py
<class '__main__.A'> <__main__.A object at 0x7f9d1c8dab70>
<class '__main__.B'> <__main__.A object at 0x7f9d1c8dab70>

• 可以发现A类和B类生成的实例对象是同一个
• 但是常规的应该是两种不同的单例对象，应该不一样（当然也有可能有该需求，可以使用此方法）

一、类型注解说明

我们知道 Python 是一种动态语言，变量以及函数的参数是不区分类型。因此我们定义函数只需要这样写就可以了：

1
2

def add(x, y):
    return x + y

坏处就是对于别人代码，无法一眼判断出参数的类型，IDE 也无法给出正确的提示。所以python3.5+就提供了类型注解：

1
2

def add(x: int, y: int) -> int:
    return x + y

用 : 类型 的形式指定函数的参数类型，用 -> 类型 的形式指定函数的返回值类型。

Python 解释器并不会因为这些注解而提供额外的校验，没有任何的类型检查工作。也就是说，这些类型注解加不加，对你的代码来说没有任何影响。

类型注解的好处：

1. 让别的程序员看得更明白。
2. 让 IDE 了解类型，从而提供更准确的代码提示、补全和语法检查（包括类型检查）。

在函数的 __annotations__ 属性中会有你设定的注解：

1
2
3
4

def add(x: int, y: int) -> int:
    return x + y

print(add.__annotations__)

输出：

{'x': <class 'int'>, 'y': <class 'int'>, 'return': <class 'int'>}

二、类型标注支持

1.函数参数以及返回值

1
2

def add(x: int, y: int) -> int:
    return x + y

2.变量（3.6+后支持）

1
2
3
4
5

from typing import List
info = {"a": 1, "b": "b"}
a: int = info["a"]
b: str = info["b"]
l: List[int] = [1, 2, 3]

3. Any类型

Any 是一种特殊的类型。静态类型检查器将所有类型视为与 Any 兼容，反之亦然， Any 也与所有类型相兼容。

这意味着可对类型为 Any 的值执行任何操作或方法调用，并将其赋值给任何变量:一般用于不确定的返回值上。

1
2
3
4

from typing import Any

def fun(item: Any)->Any:
    pass

4. object类型

与 Any 相似，所有的类型都是 object 的子类型。然而不同于 Any，反之并不成立： object 不是 其他所有类型的子类型。

这意味着当一个值的类型是 object 的时候，类型检查器会拒绝对它的几乎所有的操作。把它赋值给一个指定了类型的变量（或者当作返回值）是一个类型错误。比如说：

1
2
3
4

def fun(item: object) -> int:
    # mypy test.py会输出：error: "object" has no attribute "magic"
    item.magic()
    return 1

使用 object 示意一个值可以类型安全地兼容任何类型。使用 Any 示意一个值地类型是动态定义的。

三、高级用法

1.类型别名

类型别名通过将类型分配给别名来定义，用于简化复杂类型注解。

1
2
3
4
5
6
7
8

from typing import Dict, Tuple, Sequence

ConnectionOptions = Dict[str, str]
Address = Tuple[str, int]
Server = Tuple[Address, ConnectionOptions]

def broadcast_message(message: str, servers: Sequence[Server]) -> None:
    pass

等同于以下注解：

1
2
3
4

def broadcast_message(
    message: str,
    servers: Sequence[Tuple[Tuple[str, int], Dict[str, str]]]) -> None:
    pass

2.Callable

期望特定签名的回调函数的框架可以将类型标注为 Callable[[Arg1Type, Arg2Type], ReturnType]。

1
2
3
4
5
6
7
8

from typing import Callable

def feeder(cbfun: Callable[[], str]) -> None:
    pass

def async_query(on_success: Callable[[int], None],
                on_error: Callable[[int, Exception], None]) -> None:
    pass

3.多类型注解

1
2
3
4

from typing import Union

def fun(i: Union[str, int])->Union[str, int]:
    return i * 2

四、类型注解检测

通过 mypy 库来检验最终代码是否符合注解。mypy是一个Python命令行应用 (Python command line application )，可以轻松集成到我们的代码流中。

需要安装：pip isntall mypy

例如：test.py有以下内容

1

tmp: int = "test"

执行命令：mypy test.py

如果类型都符合，则不会有任何输出，否则就会给出类似输出：

test.py:1: error: Incompatible types in assignment (expression has type "str", variable has type "int")

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main()
{
    return 0;
}

二维数组初始化

1
2
3
4
5
6
7
8
9
10
11
12
13

int h = 5, w = 8;
char xh[h][w] = {{'1', '1', '1', '1', '1', '1', '1', '1'},
                {'1', '1', '1', '1', '1', '1', '1', '0'},
                {'1', '1', '1', '1', '1', '1', '1', '0'},
                {'1', '1', '1', '1', '1', '0', '0', '0'},
                {'0', '1', '1', '1', '1', '0', '0', '0'}};
// 赋值给vector
vector<vector<char>> matrix;
for (int i = 0; i < h; i++)
{
    vector<char> tmp(xh[i], xh[i] + w);
    matrix.push_back(tmp);
}

二维vector

1

vector<vector<int>> dp(N, vector<int>(M));

github

• https://github.com/lamborghini1993/LeetCode

题目地址

• 英文：https://leetcode.com/problems/random-pick-with-blacklist/
• 中文：https://leetcode-cn.com/problems/random-pick-with-blacklist/

题意：

给你一个整数N，一个黑名单B的列表，让你从[0,n)中随机产生一个不在B列表中的数。

解题思路一：

排序B列表，然后新建一个白名单列表0到n-1依次开始添加，如果在黑名单中就跳过。

• C++ 代码超时
• python 代码超内存

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    vector<int> p;
    int size;
    Solution(int N, vector<int> blacklist)
    {
        if (blacklist.size() != 0)
        {
            sort(blacklist.begin(), blacklist.end());
        }
        int j = 0;
        for (int i = 0; i < N; i++)
        {
            while (j < blacklist.size() && blacklist[j] < i)
            {
                j++;
            }
            if(j>=blacklist.size() || blacklist[j]!=i)
                p.push_back(i);
        }
        size = p.size();
        for (int i = 0; i < size; i++)
        {
            printf("%d ",p[i]);
        }
        printf("\n");
    }

    int pick()
    {
        return p[rand() % size];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(N, blacklist);
 * int param_1 = obj.pick();
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import random


class Solution(object):

    def __init__(self, N, blacklist):
        """
        :type N: int
        :type blacklist: List[int]
        """
        self.m_WhiteList = list(set(range(N)).difference(set(blacklist)))

    def pick(self):
        """
        :rtype: int
        """
        return random.choice(self.m_WhiteList)

# o = Solution(15, [3, 6, 2, 13, 4])
# for x in range(10):
#     print(o.pick())

解题思路二：

我们可以对黑名单做一个白名单的映射表，比如：N = 15， B = [3, 6, 2, 13, 4]
最终的白名单个数为 N - len(B) = 10,所以可得如下映射表map:

1
2
3
4
5
6
7

{
    3: 14,
    6: 13,
    2: 12,
    13: 11,
    4: 10,
}

所以此时可的这样的对应关系：
0-0 1-1 2-2 3-14 4-10 5-5 6-13 7-7 8-8 9-9
最终的结果就是map.get(x,x)

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
34
35
36
37
38
39

import random


class Solution(object):

    def __init__(self, N, blacklist):
        """
        :type N: int
        :type blacklist: List[int]
        """
        self.m_Map = {}
        self.m_Size = N-len(blacklist)
        replace = N-1
        # 建立黑名单中的替代路径
        for n in blacklist:
            self.m_Map.setdefault(n, replace)
            replace -= 1

        # 路径压缩
        for n in blacklist:
            if n >= self.m_Size:
                continue
            if n in self.m_Map:
                nxt = self.m_Map[n]
                while nxt in self.m_Map:
                    nxt = self.m_Map[nxt]
                self.m_Map[n] = nxt

    def pick(self):
        """
        :rtype: int
        """
        rd = int(random.random()*self.m_Size)
        return self.m_Map.get(rd, rd)


# o = Solution(15, [3, 6, 2, 13, 4])
# for x in range(10):
#     print(o.pick())

github

• https://github.com/lamborghini1993/LeetCode

问题

我们都知道python中允许多继承，使用super来调用父类，但是对于多继承的顺序总是弄不清楚，所以自己写了代码来弄清楚一下具体顺序。

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

class A1:
    def __init__(self):
        super(A1, self).__init__()
        print("A1.__init__")

    def Test(self):
        print("A1.Test")


class B1:
    def __init__(self):
        super(B1, self).__init__()
        print("B1.__init__")

    def Test(self):
        print("B1.Test")


class C1(A1, B1):
    """
    父类__init__中有super
    """

    def __init__(self):
        super(C1, self).__init__()
        print("C1.__init__")

    def Test(self):
        """
        macro顺序为: C1 A1 B1 object
        super方式无法调用B.Test
        """
        super(C1, self).Test()
        print("C1.Test")


#########################################


class A2(object):
    def __init__(self):
        print("A2.__init__")

    def Test(self):
        print("A2.Test")


class B2:
    def __init__(self):
        print("B2.__init__")

    def Test(self):
        print("B2.Test")


class C2(A2, B2):
    """
    父类__init__中无super
    """

    def __init__(self):
        super(C2, self).__init__()
        print("C2.__init__")

    def Test(self):
        """
        macro顺序为: C2 A2 B2 object
        super方式无法调用B.Test
        """
        super(C2, self).Test()
        print("C2.Test")


#########################################


class AA(object):
    def __init__(self):
        print("AA.__init__")

    def Test(self):
        print("AA.Test")


class BB:
    def __init__(self):
        print("BB.__init__")

    def Test(self):
        print("BB.Test")


class CC(AA, BB):
    def __init__(self):
        AA.__init__(self)
        BB.__init__(self)
        print("CC.__init__")

    def Test(self):
        AA.Test(self)
        BB.Test(self)
        print("CC.Test")


if __name__ == "__main__":
    C1().Test()
    print(C1.mro())
    print("-" * 50)
    C2().Test()
    print(C2.mro())
    print("-" * 50)
    CC().Test()
    print(CC.mro())

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

B1.__init__
A1.__init__
C1.__init__
A1.Test
C1.Test
[<class '__main__.C1'>, <class '__main__.A1'>, <class '__main__.B1'>, <class 'object'>]
--------------------------------------------------
A2.__init__
C2.__init__
A2.Test
C2.Test
[<class '__main__.C2'>, <class '__main__.A2'>, <class '__main__.B2'>, <class 'object'>]
--------------------------------------------------
AA.__init__
BB.__init__
CC.__init__
AA.Test
BB.Test
CC.Test
[<class '__main__.CC'>, <class '__main__.AA'>, <class '__main__.BB'>, <class 'object'>]

1. 第一种A和B的__init__中都调用了super方法，此时在C中调用super，发现先输出B，再输出A。而Test2调用只输出了A。
2. 第二种A和B的__init__中都没调用super方法，此时在C中调用super，发现只输出A。而Test2调用也只输出了A。
3. 第三张我们不用super，改用cls.Method调用，这个好理解，直接按照我们调用的顺序输出，Test2也一样。

MRO算法

这里也大致说下MRO算法：

1
2
3

class A(O):pass
class B(O):pass
class C(A, B):pass

此时MRO(C) = [C] + merge(mro)

1
2
3

mro(C) = [C] + merge(mro(A), mro(B), [A,B])     
            # 上面这个merge这个是按照class C(A, B)中AB的顺序来的
       = [C] + merge([A,O], [B,O], [A,B])

执行merge操作的序列为[A,O]、[B,O]、[A,B]
A是序列[A,O]中的第一个元素，在序列[B,O]中不出现，在序列[A,B]中也是第一个元素，所以从执行merge操作的序列([A,O]、[B,O]、[A,B])中删除A，合并到当前mro中。

1

mro(C) = [C,A] + merge([O], [B,O], [B])

再执行merge操作，O是序列[O]中的第一个元素，但O在序列[B,O]中出现并且不是其中第一个元素。继续查看下一个元素，也就是[B,O]的第一个元素B，B满足是所有序列中的第一个元素条件，所以从执行merge操作的序列中删除B，合并到[C, A]中。

1
2

mro(C) = [C,A,B] + merge([O], [O]) 
       = [C,A,B,O]

所以C的顺序为：C、A、B、O(object)，复合上面C.mro的输出。

总结一下：从头开始，不断寻找满足所有出现的序列中的第一个元素，找到合并到mro中，删除所有序列中的该元素，继续寻找

分析

通过查找资料，发现这里的顺序是通过一个叫MRO算法生成的，具体可以点击链接看看。

mro算法是求继承顺序的，所以对于一

1. 先运行A的__init__，然后A又调用super
2. 运行B的__init__，然后B调用super
3. 运行object的__init__。
4. 打印输出B.__init__。
5. 打印输出A.__init__。
6. 打印输出C.__init__。

对于二同理分析即可。

实现效果

源码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# -*- coding:utf-8 -*-
'''
@Description: 多选下拉菜单的实现
@Author: lamborghini1993
@Date: 2019-03-12 13:45:56
@UpdateDate: 2019-03-12 13:58:53
'''

import sys

from PyQt5 import QtCore, QtGui, QtWidgets


class CMyLove(QtWidgets.QWidget):
    m_IDAttr = "m_ID"

    def __init__(self, parent=None):
        super(CMyLove, self).__init__(parent)
        self.m_Info = {x: "Test_"+str(x) for x in range(100)}
        self.m_Select = []
        self._InitUI()

    def _InitUI(self):
        hBox = QtWidgets.QHBoxLayout(self)
        self.m_LineEdit = QtWidgets.QLineEdit(self)
        self.m_MenuBtn = QtWidgets.QPushButton(self)
        hBox.addWidget(self.m_LineEdit)
        hBox.addWidget(self.m_MenuBtn)

        self.m_Menu = QtWidgets.QMenu(self)
        for ID, sInfo in self.m_Info.items():
            action = QtWidgets.QAction(sInfo, self)
            action.setCheckable(True)
            self.m_Menu.addAction(action)
            setattr(action, self.m_IDAttr, ID)
            action.triggered.connect(self.S_StateChanged)
        self.m_MenuBtn.setMenu(self.m_Menu)

    def S_StateChanged(self, bChecked):
        send = self.sender()
        ID = getattr(send, self.m_IDAttr)
        if bChecked:
            self.m_Select.append(ID)
        else:
            self.m_Select.remove(ID)
        self.m_Select = sorted(self.m_Select)
        lstTemp = [str(x) for x in self.m_Select]
        self.m_LineEdit.setText("&".join(lstTemp))


if __name__ == "__main__":
    app = QtWidgets.QApplication(sys.argv)
    obj = CMyLove()
    obj.show()
    sys.exit(app.exec_())

索引

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
看一个例子：

图1.png

图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引，这一节先单纯从数据结构角度描述它们。

B-Tree

是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的
子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
9.每个k对应一个data。
如：（M=3）相当于一个2–3树，2–3树是一个这样的一棵树， 它的每个节点要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；B-Tree上查找算法的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

BTree_Search(node, key)
{
    if (node == null)
        return null;
    foreach (node.key)
    {
        if (node.key[i] == key)
            return node.data[i];
        if (node.key[i] > key)
            return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i + 1]->node);
}
data = BTree_Search(root, my_key);

• B-树的特性：
  1.关键字集合分布在整颗树中；
  2.任何一个关键字出现且只出现在一个结点中；
  3.搜索有可能在非叶子结点结束；
  4.其搜索性能等价于在关键字全集内做一次二分查找；
  5.自动层次控制；

• B-树的自控制:
  B树中每一个内部节点会包含一定数量的键值。通常，键值的数量被选定在d和2d之间。在实际中，键值占用了节点中大部分的空间。因数2将保证节点可以被拆分或组合。如果一个内部节点有2d个键值，那么添加一个键值给此节点的过程，将会拆分2d键值为2个d键值的节点，并把此键值添加给父节点。每一个拆分的节点需要最小数目的键值。相似地，如果一个内部节点和他的邻居两者都有d个键值，那么将通过它与邻居的合并来删除一个键值。删除此键值将导致此节点拥有d-1个键值;与邻居的合并则加上d个键值，再加上从邻居节点的父节点移来的一个键值。结果为完全填充的2d个键值。

• B-树的构造过程：
  下面是往B树中依次插入
  6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

  

  btreebuild.gif

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

• 与B-Tree相比，B+Tree有以下不同点：
  1.非叶子结点的子树指针与关键字个数相同；
  2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
  3.为所有叶子结点增加一个链指针；
  4.所有关键字都在叶子结点出现；
  5.内节点不存储data，只存储key
  如：（M=3）

  

  Paste_Image.png

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

• B+的特性：
  1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
  2.不可能在非叶子结点命中；
  3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
  4.更适合文件索引系统；

• B+树的构造过程：
  下面是往B+树中依次插入
  6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

  

  Bplustreebuild.gif

索引的物理存储

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

B-tree

Paste_Image.png

假如每个盘块可以正好存放一个B树的结点（正好存放2个文件名）。那么一个BTNODE结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址。

• 下面，咱们来模拟下查找文件29的过程：

  1.根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作 1次】

  2.此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针p2。

  3.根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作 2次】

  4.此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2。

  5.根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作 3次】

  6.此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。

  分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。

当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘4次，最多5次，而且文件越多，B树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。

B+tree

Paste_Image.png

• B+tree的优点：

1. B+-tree的磁盘读写代价更低

   **B+-tree**的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

   举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而**B+

   **树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比**B+ **树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2. B+-tree的查询效率更加稳定

   由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

mysql的两种存储引擎的索引存储机制

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

Paste_Image.png

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

Paste_Image.png

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

Paste_Image.png

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，定义在Col3上的一个辅助索引：

Paste_Image.png

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

题目地址

• 英文：https://leetcode.com/problems/longest-valid-parentheses/
• 中文：https://leetcode-cn.com/problems/longest-valid-parentheses/

题意：

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

解题思路：

• 看到括号匹配立即想到栈，(入栈，)则出栈；
• 要求最长有效括号子串长度，则求连续有效括号长度；
• 出栈之后将本位置，以及栈顶位置标记为true；
• 求最大连续为true的长度。
• PS:注意这里没说输入字符串最长数组多大，测试至少有9999位

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <climits>
#include <algorithm>
#include <stack>
using namespace std;

bool Visit[99999];
int j, cnt;
int result = 0;

class Solution
{
  public:
    int longestValidParentheses(string s)
    {
        stack<int> my;
        cnt = result = 0;

        for (int i = 0; i < s.length(); i++)
        {
            Visit[i] = false;
            if (s[i] == '(')
            {
                my.push(i);
                continue;
            }
            if (!my.empty())
            {
                j = my.top();
                my.pop();
                Visit[j] = true;
                Visit[i] = true;
            }
        }
        for (int i = 0; i < s.length(); i++)
        {
            if (Visit[i])
            {
                cnt++;
                continue;
            }
            result = max(result, cnt);
            cnt = 0;
        }
        result = max(result, cnt);
        printf("结果为:%d\n", result);
        return result;
    }
};

// int main(int argc, char const *argv[])
// {
//     string s1 = ")(";
//     Solution().longestValidParentheses(s1);
//     return 0;
// }

github

• https://github.com/lamborghini1993/LeetCode