pandas 快速入门

分類 database, pandas

pandas 快速入门#

这是 pandas 的一个简短介绍，主要面向新用户。你可以在实用代码片段中查看更复杂的示例。

通常，我们按如下方式导入

1
2
3
In [1]: import numpy as np

In [2]: import pandas as pd

pandas 中的基本数据结构#

Pandas 提供了两种用于处理数据的类

  1. Series：一个一维的带标签数组，可容纳任何类型的数据

    例如整数、字符串、Python 对象等。

  2. DataFrame：一个二维数据结构，像二维数组或带有行和列的表格一样容纳数据。

对象创建#

请参阅数据结构简介部分。

通过传入值列表创建Series，让 pandas 创建默认的RangeIndex。

1
2
3
4
5
6
7
8
9
10
11
In [3]: s = pd.Series([1, 3, 5, np.nan, 6, 8])

In [4]: s
Out[4]: 
0    1.0
1    3.0
2    5.0
3    NaN
4    6.0
5    8.0
dtype: float64

通过传入 NumPy 数组，使用date_range()创建带有日期时间索引和标签列的DataFrame

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In [5]: dates = pd.date_range("20130101", periods=6)

In [6]: dates
Out[6]: 
DatetimeIndex(['2013-01-01', '2013-01-02', '2013-01-03', '2013-01-04',
               '2013-01-05', '2013-01-06'],
              dtype='datetime64[ns]', freq='D')

In [7]: df = pd.DataFrame(np.random.randn(6, 4), index=dates, columns=list("ABCD"))

In [8]: df
Out[8]: 
                   A         B         C         D
2013-01-01  0.469112 -0.282863 -1.509059 -1.135632
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804
2013-01-04  0.721555 -0.706771 -1.039575  0.271860
2013-01-05 -0.424972  0.567020  0.276232 -1.087401
2013-01-06 -0.673690  0.113648 -1.478427  0.524988

通过传入一个对象字典创建DataFrame，其中键是列标签，值是列值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In [9]: df2 = pd.DataFrame(
   ...:     {
   ...:         "A": 1.0,
   ...:         "B": pd.Timestamp("20130102"),
   ...:         "C": pd.Series(1, index=list(range(4)), dtype="float32"),
   ...:         "D": np.array([3] * 4, dtype="int32"),
   ...:         "E": pd.Categorical(["test", "train", "test", "train"]),
   ...:         "F": "foo",
   ...:     }
   ...: )
   ...: 

In [10]: df2
Out[10]: 
     A          B    C  D      E    F
0  1.0 2013-01-02  1.0  3   test  foo
1  1.0 2013-01-02  1.0  3  train  foo
2  1.0 2013-01-02  1.0  3   test  foo
3  1.0 2013-01-02  1.0  3  train  foo

生成的DataFrame的列具有不同的dtypes

1
2
3
4
5
6
7
8
9
In [11]: df2.dtypes
Out[11]: 
A          float64
B    datetime64[s]
C          float32
D            int32
E         category
F           object
dtype: object

如果你使用 IPython，列名（以及公共属性）的 Tab 自动补全功能会自动启用。以下是部分将自动补全的属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
In [12]: df2.<TAB>  # noqa: E225, E999
df2.A                  df2.bool
df2.abs                df2.boxplot
df2.add                df2.C
df2.add_prefix         df2.clip
df2.add_suffix         df2.columns
df2.align              df2.copy
df2.all                df2.count
df2.any                df2.combine
df2.append             df2.D
df2.apply              df2.describe
df2.applymap           df2.diff
df2.B                  df2.duplicated

如你所见，列 A、B、C 和 D 会自动 Tab 补全。E 和 F 也在其中；其余属性为简洁起见已被截断。

查看数据#

请参阅基本核心功能部分。

使用DataFrame.head()和DataFrame.tail()分别查看框架的顶部和底部行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [13]: df.head()
Out[13]: 
                   A         B         C         D
2013-01-01  0.469112 -0.282863 -1.509059 -1.135632
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804
2013-01-04  0.721555 -0.706771 -1.039575  0.271860
2013-01-05 -0.424972  0.567020  0.276232 -1.087401

In [14]: df.tail(3)
Out[14]: 
                   A         B         C         D
2013-01-04  0.721555 -0.706771 -1.039575  0.271860
2013-01-05 -0.424972  0.567020  0.276232 -1.087401
2013-01-06 -0.673690  0.113648 -1.478427  0.524988

显示DataFrame.index或DataFrame.columns

1
2
3
4
5
6
7
8
In [15]: df.index
Out[15]: 
DatetimeIndex(['2013-01-01', '2013-01-02', '2013-01-03', '2013-01-04',
               '2013-01-05', '2013-01-06'],
              dtype='datetime64[ns]', freq='D')

In [16]: df.columns
Out[16]: Index(['A', 'B', 'C', 'D'], dtype='object')

使用DataFrame.to_numpy()返回底层数据的 NumPy 表示，不包含索引或列标签。

1
2
3
4
5
6
7
8
In [17]: df.to_numpy()
Out[17]: 
array([[ 0.4691, -0.2829, -1.5091, -1.1356],
       [ 1.2121, -0.1732,  0.1192, -1.0442],
       [-0.8618, -2.1046, -0.4949,  1.0718],
       [ 0.7216, -0.7068, -1.0396,  0.2719],
       [-0.425 ,  0.567 ,  0.2762, -1.0874],
       [-0.6737,  0.1136, -1.4784,  0.525 ]])

注意

NumPy 数组的整个数组只有一个 dtype，而 pandas DataFrames 的每列有一个 dtype。当你调用DataFrame.to_numpy()时，pandas 会找到能够容纳 DataFrame 中 所有 dtypes 的 NumPy dtype。如果共同的数据类型是 object，则DataFrame.to_numpy()将需要复制数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
In [18]: df2.dtypes
Out[18]: 
A          float64
B    datetime64[s]
C          float32
D            int32
E         category
F           object
dtype: object

In [19]: df2.to_numpy()
Out[19]: 
array([[1.0, Timestamp('2013-01-02 00:00:00'), 1.0, 3, 'test', 'foo'],
       [1.0, Timestamp('2013-01-02 00:00:00'), 1.0, 3, 'train', 'foo'],
       [1.0, Timestamp('2013-01-02 00:00:00'), 1.0, 3, 'test', 'foo'],
       [1.0, Timestamp('2013-01-02 00:00:00'), 1.0, 3, 'train', 'foo']],
      dtype=object)

describe()显示数据的快速统计摘要

1
2
3
4
5
6
7
8
9
10
11
In [20]: df.describe()
Out[20]: 
              A         B         C         D
count  6.000000  6.000000  6.000000  6.000000
mean   0.073711 -0.431125 -0.687758 -0.233103
std    0.843157  0.922818  0.779887  0.973118
min   -0.861849 -2.104569 -1.509059 -1.135632
25%   -0.611510 -0.600794 -1.368714 -1.076610
50%    0.022070 -0.228039 -0.767252 -0.386188
75%    0.658444  0.041933 -0.034326  0.461706
max    1.212112  0.567020  0.276232  1.071804

转置数据

1
2
3
4
5
6
7
In [21]: df.T
Out[21]: 
   2013-01-01  2013-01-02  2013-01-03  2013-01-04  2013-01-05  2013-01-06
A    0.469112    1.212112   -0.861849    0.721555   -0.424972   -0.673690
B   -0.282863   -0.173215   -2.104569   -0.706771    0.567020    0.113648
C   -1.509059    0.119209   -0.494929   -1.039575    0.276232   -1.478427
D   -1.135632   -1.044236    1.071804    0.271860   -1.087401    0.524988

DataFrame.sort_index()按轴排序

1
2
3
4
5
6
7
8
9
In [22]: df.sort_index(axis=1, ascending=False)
Out[22]: 
                   D         C         B         A
2013-01-01 -1.135632 -1.509059 -0.282863  0.469112
2013-01-02 -1.044236  0.119209 -0.173215  1.212112
2013-01-03  1.071804 -0.494929 -2.104569 -0.861849
2013-01-04  0.271860 -1.039575 -0.706771  0.721555
2013-01-05 -1.087401  0.276232  0.567020 -0.424972
2013-01-06  0.524988 -1.478427  0.113648 -0.673690

DataFrame.sort_values()按值排序

1
2
3
4
5
6
7
8
9
In [23]: df.sort_values(by="B")
Out[23]: 
                   A         B         C         D
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804
2013-01-04  0.721555 -0.706771 -1.039575  0.271860
2013-01-01  0.469112 -0.282863 -1.509059 -1.135632
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-06 -0.673690  0.113648 -1.478427  0.524988
2013-01-05 -0.424972  0.567020  0.276232 -1.087401

选择#

请参阅索引文档索引与选择数据和MultiIndex / 高级索引。

Getitem ([])#

对于DataFrame，传入单个标签会选择一列并生成一个Series，等同于 df.A

1
2
3
4
5
6
7
8
9
In [24]: df["A"]
Out[24]: 
2013-01-01    0.469112
2013-01-02    1.212112
2013-01-03   -0.861849
2013-01-04    0.721555
2013-01-05   -0.424972
2013-01-06   -0.673690
Freq: D, Name: A, dtype: float64

对于DataFrame，传入切片 : 会选择匹配的行。

1
2
3
4
5
6
7
8
9
10
11
12
13
In [25]: df[0:3]
Out[25]: 
                   A         B         C         D
2013-01-01  0.469112 -0.282863 -1.509059 -1.135632
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804

In [26]: df["20130102":"20130104"]
Out[26]: 
                   A         B         C         D
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804
2013-01-04  0.721555 -0.706771 -1.039575  0.271860

按标签选择#

更多信息请参阅按标签选择，使用DataFrame.loc()或DataFrame.at()。

选择与标签匹配的行

1
2
3
4
5
6
7
In [27]: df.loc[dates[0]]
Out[27]: 
A    0.469112
B   -0.282863
C   -1.509059
D   -1.135632
Name: 2013-01-01 00:00:00, dtype: float64

选择所有行 (:) 和选定的列标签

1
2
3
4
5
6
7
8
9
In [28]: df.loc[:, ["A", "B"]]
Out[28]: 
                   A         B
2013-01-01  0.469112 -0.282863
2013-01-02  1.212112 -0.173215
2013-01-03 -0.861849 -2.104569
2013-01-04  0.721555 -0.706771
2013-01-05 -0.424972  0.567020
2013-01-06 -0.673690  0.113648

对于标签切片，两个端点都包含在内

1
2
3
4
5
6
In [29]: df.loc["20130102":"20130104", ["A", "B"]]
Out[29]: 
                   A         B
2013-01-02  1.212112 -0.173215
2013-01-03 -0.861849 -2.104569
2013-01-04  0.721555 -0.706771

选择单个行和列标签会返回一个标量

1
2
In [30]: df.loc[dates[0], "A"]
Out[30]: 0.4691122999071863

为了快速访问标量（等同于之前的方法）

1
2
In [31]: df.at[dates[0], "A"]
Out[31]: 0.4691122999071863

按位置选择#

更多信息请参阅按位置选择，使用DataFrame.iloc()或DataFrame.iat()。

通过传入整数的位置进行选择

1
2
3
4
5
6
7
In [32]: df.iloc[3]
Out[32]: 
A    0.721555
B   -0.706771
C   -1.039575
D    0.271860
Name: 2013-01-04 00:00:00, dtype: float64

整数切片行为类似于 NumPy/Python

1
2
3
4
5
In [33]: df.iloc[3:5, 0:2]
Out[33]: 
                   A         B
2013-01-04  0.721555 -0.706771
2013-01-05 -0.424972  0.567020

整数位置列表

1
2
3
4
5
6
In [34]: df.iloc[[1, 2, 4], [0, 2]]
Out[34]: 
                   A         C
2013-01-02  1.212112  0.119209
2013-01-03 -0.861849 -0.494929
2013-01-05 -0.424972  0.276232

显式切片行

1
2
3
4
5
In [35]: df.iloc[1:3, :]
Out[35]: 
                   A         B         C         D
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804

显式切片列

1
2
3
4
5
6
7
8
9
In [36]: df.iloc[:, 1:3]
Out[36]: 
                   B         C
2013-01-01 -0.282863 -1.509059
2013-01-02 -0.173215  0.119209
2013-01-03 -2.104569 -0.494929
2013-01-04 -0.706771 -1.039575
2013-01-05  0.567020  0.276232
2013-01-06  0.113648 -1.478427

显式获取值

1
2
In [37]: df.iloc[1, 1]
Out[37]: -0.17321464905330858

为了快速访问标量（等同于之前的方法）

1
2
In [38]: df.iat[1, 1]
Out[38]: -0.17321464905330858

布尔索引#

选择 df.A 大于 0 的行。

1
2
3
4
5
6
In [39]: df[df["A"] > 0]
Out[39]: 
                   A         B         C         D
2013-01-01  0.469112 -0.282863 -1.509059 -1.135632
2013-01-02  1.212112 -0.173215  0.119209 -1.044236
2013-01-04  0.721555 -0.706771 -1.039575  0.271860

从满足布尔条件的DataFrame中选择值

1
2
3
4
5
6
7
8
9
In [40]: df[df > 0]
Out[40]: 
                   A         B         C         D
2013-01-01  0.469112       NaN       NaN       NaN
2013-01-02  1.212112       NaN  0.119209       NaN
2013-01-03       NaN       NaN       NaN  1.071804
2013-01-04  0.721555       NaN       NaN  0.271860
2013-01-05       NaN  0.567020  0.276232       NaN
2013-01-06       NaN  0.113648       NaN  0.524988

使用isin()方法进行过滤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In [41]: df2 = df.copy()

In [42]: df2["E"] = ["one", "one", "two", "three", "four", "three"]

In [43]: df2
Out[43]: 
                   A         B         C         D      E
2013-01-01  0.469112 -0.282863 -1.509059 -1.135632    one
2013-01-02  1.212112 -0.173215  0.119209 -1.044236    one
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804    two
2013-01-04  0.721555 -0.706771 -1.039575  0.271860  three
2013-01-05 -0.424972  0.567020  0.276232 -1.087401   four
2013-01-06 -0.673690  0.113648 -1.478427  0.524988  three

In [44]: df2[df2["E"].isin(["two", "four"])]
Out[44]: 
                   A         B         C         D     E
2013-01-03 -0.861849 -2.104569 -0.494929  1.071804   two
2013-01-05 -0.424972  0.567020  0.276232 -1.087401  four

设置#

设置新列会自动按索引对齐数据

1
2
3
4
5
6
7
8
9
10
11
12
13
In [45]: s1 = pd.Series([1, 2, 3, 4, 5, 6], index=pd.date_range("20130102", periods=6))

In [46]: s1
Out[46]: 
2013-01-02    1
2013-01-03    2
2013-01-04    3
2013-01-05    4
2013-01-06    5
2013-01-07    6
Freq: D, dtype: int64

In [47]: df["F"] = s1

按标签设置值

1
In [48]: df.at[dates[0], "A"] = 0

按位置设置值

1
In [49]: df.iat[0, 1] = 0

通过分配 NumPy 数组进行设置

1
In [50]: df.loc[:, "D"] = np.array([5] * len(df))

先前的设置操作的结果

1
2
3
4
5
6
7
8
9
In [51]: df
Out[51]: 
                   A         B         C    D    F
2013-01-01  0.000000  0.000000 -1.509059  5.0  NaN
2013-01-02  1.212112 -0.173215  0.119209  5.0  1.0
2013-01-03 -0.861849 -2.104569 -0.494929  5.0  2.0
2013-01-04  0.721555 -0.706771 -1.039575  5.0  3.0
2013-01-05 -0.424972  0.567020  0.276232  5.0  4.0
2013-01-06 -0.673690  0.113648 -1.478427  5.0  5.0

带设置的 where 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
In [52]: df2 = df.copy()

In [53]: df2[df2 > 0] = -df2

In [54]: df2
Out[54]: 
                   A         B         C    D    F
2013-01-01  0.000000  0.000000 -1.509059 -5.0  NaN
2013-01-02 -1.212112 -0.173215 -0.119209 -5.0 -1.0
2013-01-03 -0.861849 -2.104569 -0.494929 -5.0 -2.0
2013-01-04 -0.721555 -0.706771 -1.039575 -5.0 -3.0
2013-01-05 -0.424972 -0.567020 -0.276232 -5.0 -4.0
2013-01-06 -0.673690 -0.113648 -1.478427 -5.0 -5.0

缺失数据#

对于 NumPy 数据类型，np.nan 表示缺失数据。默认情况下，它不包含在计算中。请参阅缺失数据部分。

重新索引允许你更改/添加/删除指定轴上的索引。这会返回数据的副本。

1
2
3
4
5
6
7
8
9
10
11
In [55]: df1 = df.reindex(index=dates[0:4], columns=list(df.columns) + ["E"])

In [56]: df1.loc[dates[0] : dates[1], "E"] = 1

In [57]: df1
Out[57]: 
                   A         B         C    D    F    E
2013-01-01  0.000000  0.000000 -1.509059  5.0  NaN  1.0
2013-01-02  1.212112 -0.173215  0.119209  5.0  1.0  1.0
2013-01-03 -0.861849 -2.104569 -0.494929  5.0  2.0  NaN
2013-01-04  0.721555 -0.706771 -1.039575  5.0  3.0  NaN

DataFrame.dropna()删除任何包含缺失数据的行

1
2
3
4
In [58]: df1.dropna(how="any")
Out[58]: 
                   A         B         C    D    F    E
2013-01-02  1.212112 -0.173215  0.119209  5.0  1.0  1.0

DataFrame.fillna()填充缺失数据

1
2
3
4
5
6
7
In [59]: df1.fillna(value=5)
Out[59]: 
                   A         B         C    D    F    E
2013-01-01  0.000000  0.000000 -1.509059  5.0  5.0  1.0
2013-01-02  1.212112 -0.173215  0.119209  5.0  1.0  1.0
2013-01-03 -0.861849 -2.104569 -0.494929  5.0  2.0  5.0
2013-01-04  0.721555 -0.706771 -1.039575  5.0  3.0  5.0

isna()获取值为 nan 的布尔掩码

1
2
3
4
5
6
7
In [60]: pd.isna(df1)
Out[60]: 
                A      B      C      D      F      E
2013-01-01  False  False  False  False   True  False
2013-01-02  False  False  False  False  False  False
2013-01-03  False  False  False  False  False   True
2013-01-04  False  False  False  False  False   True

操作#

请参阅二元运算基本部分。

统计#

操作通常排除缺失数据。

计算每列的平均值

1
2
3
4
5
6
7
8
In [61]: df.mean()
Out[61]: 
A   -0.004474
B   -0.383981
C   -0.687758
D    5.000000
F    3.000000
dtype: float64

计算每行的平均值

1
2
3
4
5
6
7
8
9
In [62]: df.mean(axis=1)
Out[62]: 
2013-01-01    0.872735
2013-01-02    1.431621
2013-01-03    0.707731
2013-01-04    1.395042
2013-01-05    1.883656
2013-01-06    1.592306
Freq: D, dtype: float64

与具有不同索引或列的另一个Series或DataFrame进行操作时，结果将与索引或列标签的并集对齐。此外，pandas 会沿指定维度自动广播，并将未对齐的标签填充为np.nan。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In [63]: s = pd.Series([1, 3, 5, np.nan, 6, 8], index=dates).shift(2)

In [64]: s
Out[64]: 
2013-01-01    NaN
2013-01-02    NaN
2013-01-03    1.0
2013-01-04    3.0
2013-01-05    5.0
2013-01-06    NaN
Freq: D, dtype: float64

In [65]: df.sub(s, axis="index")
Out[65]: 
                   A         B         C    D    F
2013-01-01       NaN       NaN       NaN  NaN  NaN
2013-01-02       NaN       NaN       NaN  NaN  NaN
2013-01-03 -1.861849 -3.104569 -1.494929  4.0  1.0
2013-01-04 -2.278445 -3.706771 -4.039575  2.0  0.0
2013-01-05 -5.424972 -4.432980 -4.723768  0.0 -1.0
2013-01-06       NaN       NaN       NaN  NaN  NaN

用户定义函数#

DataFrame.agg()和DataFrame.transform()分别应用一个用户定义函数，该函数会减少或广播其结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
In [66]: df.agg(lambda x: np.mean(x) * 5.6)
Out[66]: 
A    -0.025054
B    -2.150294
C    -3.851445
D    28.000000
F    16.800000
dtype: float64

In [67]: df.transform(lambda x: x * 101.2)
Out[67]: 
                     A           B           C      D      F
2013-01-01    0.000000    0.000000 -152.716721  506.0    NaN
2013-01-02  122.665737  -17.529322   12.063922  506.0  101.2
2013-01-03  -87.219115 -212.982405  -50.086843  506.0  202.4
2013-01-04   73.021382  -71.525239 -105.204988  506.0  303.6
2013-01-05  -43.007200   57.382459   27.954680  506.0  404.8
2013-01-06  -68.177398   11.501219 -149.616767  506.0  506.0

值计数#

更多信息请参阅直方图和离散化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In [68]: s = pd.Series(np.random.randint(0, 7, size=10))

In [69]: s
Out[69]: 
0    4
1    2
2    1
3    2
4    6
5    4
6    4
7    6
8    4
9    4
dtype: int64

In [70]: s.value_counts()
Out[70]: 
4    5
2    2
6    2
1    1
Name: count, dtype: int64

字符串方法#

Series在 str 属性中配备了一组字符串处理方法，可以轻松地对数组的每个元素进行操作，如下面的代码片段所示。更多信息请参阅矢量化字符串方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
In [71]: s = pd.Series(["A", "B", "C", "Aaba", "Baca", np.nan, "CABA", "dog", "cat"])

In [72]: s.str.lower()
Out[72]: 
0       a
1       b
2       c
3    aaba
4    baca
5     NaN
6    caba
7     dog
8     cat
dtype: object

合并#

拼接#

pandas 提供了各种功能，可以轻松地将 Series 和 DataFrame 对象与各种集合逻辑（用于索引）和关系代数功能（用于连接/合并类型操作）结合在一起。

请参阅合并部分。

使用concat()按行拼接 pandas 对象

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
In [73]: df = pd.DataFrame(np.random.randn(10, 4))

In [74]: df
Out[74]: 
          0         1         2         3
0 -0.548702  1.467327 -1.015962 -0.483075
1  1.637550 -1.217659 -0.291519 -1.745505
2 -0.263952  0.991460 -0.919069  0.266046
3 -0.709661  1.669052  1.037882 -1.705775
4 -0.919854 -0.042379  1.247642 -0.009920
5  0.290213  0.495767  0.362949  1.548106
6 -1.131345 -0.089329  0.337863 -0.945867
7 -0.932132  1.956030  0.017587 -0.016692
8 -0.575247  0.254161 -1.143704  0.215897
9  1.193555 -0.077118 -0.408530 -0.862495

# break it into pieces
In [75]: pieces = [df[:3], df[3:7], df[7:]]

In [76]: pd.concat(pieces)
Out[76]: 
          0         1         2         3
0 -0.548702  1.467327 -1.015962 -0.483075
1  1.637550 -1.217659 -0.291519 -1.745505
2 -0.263952  0.991460 -0.919069  0.266046
3 -0.709661  1.669052  1.037882 -1.705775
4 -0.919854 -0.042379  1.247642 -0.009920
5  0.290213  0.495767  0.362949  1.548106
6 -1.131345 -0.089329  0.337863 -0.945867
7 -0.932132  1.956030  0.017587 -0.016692
8 -0.575247  0.254161 -1.143704  0.215897
9  1.193555 -0.077118 -0.408530 -0.862495

连接#

merge()支持沿着特定列进行 SQL 风格的连接。请参阅数据库风格连接部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In [77]: left = pd.DataFrame({"key": ["foo", "foo"], "lval": [1, 2]})

In [78]: right = pd.DataFrame({"key": ["foo", "foo"], "rval": [4, 5]})

In [79]: left
Out[79]: 
   key  lval
0  foo     1
1  foo     2

In [80]: right
Out[80]: 
   key  rval
0  foo     4
1  foo     5

In [81]: pd.merge(left, right, on="key")
Out[81]: 
   key  lval  rval
0  foo     1     4
1  foo     1     5
2  foo     2     4
3  foo     2     5

merge() 基于唯一键进行合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In [82]: left = pd.DataFrame({"key": ["foo", "bar"], "lval": [1, 2]})

In [83]: right = pd.DataFrame({"key": ["foo", "bar"], "rval": [4, 5]})

In [84]: left
Out[84]: 
   key  lval
0  foo     1
1  bar     2

In [85]: right
Out[85]: 
   key  rval
0  foo     4
1  bar     5

In [86]: pd.merge(left, right, on="key")
Out[86]: 
   key  lval  rval
0  foo     1     4
1  bar     2     5

分组#

“分组”指的是一个或多个以下步骤的过程

  • 根据某些条件将数据分拆成组

  • 对每个组独立地应用一个函数

  • 将结果组合成一个数据结构

请参阅分组部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In [87]: df = pd.DataFrame(
   ....:     {
   ....:         "A": ["foo", "bar", "foo", "bar", "foo", "bar", "foo", "foo"],
   ....:         "B": ["one", "one", "two", "three", "two", "two", "one", "three"],
   ....:         "C": np.random.randn(8),
   ....:         "D": np.random.randn(8),
   ....:     }
   ....: )
   ....: 

In [88]: df
Out[88]: 
     A      B         C         D
0  foo    one  1.346061 -1.577585
1  bar    one  1.511763  0.396823
2  foo    two  1.627081 -0.105381
3  bar  three -0.990582 -0.532532
4  foo    two -0.441652  1.453749
5  bar    two  1.211526  1.208843
6  foo    one  0.268520 -0.080952
7  foo  three  0.024580 -0.264610

按列标签分组，选择列标签，然后将DataFrameGroupBy.sum()函数应用于结果组

1
2
3
4
5
6
In [89]: df.groupby("A")[["C", "D"]].sum()
Out[89]: 
            C         D
A                      
bar  1.732707  1.073134
foo  2.824590 -0.574779

按多列标签分组会形成MultiIndex。

1
2
3
4
5
6
7
8
9
10
In [90]: df.groupby(["A", "B"]).sum()
Out[90]: 
                  C         D
A   B                        
bar one    1.511763  0.396823
    three -0.990582 -0.532532
    two    1.211526  1.208843
foo one    1.614581 -1.658537
    three  0.024580 -0.264610
    two    1.185429  1.348368

重塑#

请参阅层次化索引和重塑部分。

堆叠#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
In [91]: arrays = [
   ....:    ["bar", "bar", "baz", "baz", "foo", "foo", "qux", "qux"],
   ....:    ["one", "two", "one", "two", "one", "two", "one", "two"],
   ....: ]
   ....: 

In [92]: index = pd.MultiIndex.from_arrays(arrays, names=["first", "second"])

In [93]: df = pd.DataFrame(np.random.randn(8, 2), index=index, columns=["A", "B"])

In [94]: df2 = df[:4]

In [95]: df2
Out[95]: 
                     A         B
first second                    
bar   one    -0.727965 -0.589346
      two     0.339969 -0.693205
baz   one    -0.339355  0.593616
      two     0.884345  1.591431

stack()方法“压缩”了 DataFrame 列中的一个层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
In [96]: stacked = df2.stack(future_stack=True)

In [97]: stacked
Out[97]: 
first  second   
bar    one     A   -0.727965
               B   -0.589346
       two     A    0.339969
               B   -0.693205
baz    one     A   -0.339355
               B    0.593616
       two     A    0.884345
               B    1.591431
dtype: float64

对于一个“堆叠”的 DataFrame 或 Series（其 index 为 MultiIndex），stack() 的逆操作是 unstack()，它默认会解除堆叠最底层

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
In [98]: stacked.unstack()
Out[98]: 
                     A         B
first second                    
bar   one    -0.727965 -0.589346
      two     0.339969 -0.693205
baz   one    -0.339355  0.593616
      two     0.884345  1.591431

In [99]: stacked.unstack(1)
Out[99]: 
second        one       two
first                      
bar   A -0.727965  0.339969
      B -0.589346 -0.693205
baz   A -0.339355  0.884345
      B  0.593616  1.591431

In [100]: stacked.unstack(0)
Out[100]: 
first          bar       baz
second                      
one    A -0.727965 -0.339355
       B -0.589346  0.593616
two    A  0.339969  0.884345
       B -0.693205  1.591431

透视表#

请参阅透视表部分。

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
In [101]: df = pd.DataFrame(
   .....:     {
   .....:         "A": ["one", "one", "two", "three"] * 3,
   .....:         "B": ["A", "B", "C"] * 4,
   .....:         "C": ["foo", "foo", "foo", "bar", "bar", "bar"] * 2,
   .....:         "D": np.random.randn(12),
   .....:         "E": np.random.randn(12),
   .....:     }
   .....: )
   .....: 

In [102]: df
Out[102]: 
        A  B    C         D         E
0     one  A  foo -1.202872  0.047609
1     one  B  foo -1.814470 -0.136473
2     two  C  foo  1.018601 -0.561757
3   three  A  bar -0.595447 -1.623033
4     one  B  bar  1.395433  0.029399
5     one  C  bar -0.392670 -0.542108
6     two  A  foo  0.007207  0.282696
7   three  B  foo  1.928123 -0.087302
8     one  C  foo -0.055224 -1.575170
9     one  A  bar  2.395985  1.771208
10    two  B  bar  1.552825  0.816482
11  three  C  bar  0.166599  1.100230

pivot_table()通过指定values、index和columns来透视DataFrame

1
2
3
4
5
6
7
8
9
10
11
12
13
In [103]: pd.pivot_table(df, values="D", index=["A", "B"], columns=["C"])
Out[103]: 
C             bar       foo
A     B                    
one   A  2.395985 -1.202872
      B  1.395433 -1.814470
      C -0.392670 -0.055224
three A -0.595447       NaN
      B       NaN  1.928123
      C  0.166599       NaN
two   A       NaN  0.007207
      B  1.552825       NaN
      C       NaN  1.018601

时间序列#

pandas 具有简单、强大且高效的功能，用于在频率转换期间执行重采样操作（例如，将秒级数据转换为 5 分钟级数据）。这在金融应用中非常常见，但不仅限于此。请参阅时间序列部分。

1
2
3
4
5
6
7
8
In [104]: rng = pd.date_range("1/1/2012", periods=100, freq="s")

In [105]: ts = pd.Series(np.random.randint(0, 500, len(rng)), index=rng)

In [106]: ts.resample("5Min").sum()
Out[106]: 
2012-01-01    24182
Freq: 5min, dtype: int64

Series.tz_localize()将时间序列本地化到某个时区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In [107]: rng = pd.date_range("3/6/2012 00:00", periods=5, freq="D")

In [108]: ts = pd.Series(np.random.randn(len(rng)), rng)

In [109]: ts
Out[109]: 
2012-03-06    1.857704
2012-03-07   -1.193545
2012-03-08    0.677510
2012-03-09   -0.153931
2012-03-10    0.520091
Freq: D, dtype: float64

In [110]: ts_utc = ts.tz_localize("UTC")

In [111]: ts_utc
Out[111]: 
2012-03-06 00:00:00+00:00    1.857704
2012-03-07 00:00:00+00:00   -1.193545
2012-03-08 00:00:00+00:00    0.677510
2012-03-09 00:00:00+00:00   -0.153931
2012-03-10 00:00:00+00:00    0.520091
Freq: D, dtype: float64

Series.tz_convert()将时区感知的时间序列转换为另一个时区

1
2
3
4
5
6
7
8
In [112]: ts_utc.tz_convert("US/Eastern")
Out[112]: 
2012-03-05 19:00:00-05:00    1.857704
2012-03-06 19:00:00-05:00   -1.193545
2012-03-07 19:00:00-05:00    0.677510
2012-03-08 19:00:00-05:00   -0.153931
2012-03-09 19:00:00-05:00    0.520091
Freq: D, dtype: float64

向时间序列添加非固定时长（BusinessDay）

1
2
3
4
5
6
7
8
9
10
11
In [113]: rng
Out[113]: 
DatetimeIndex(['2012-03-06', '2012-03-07', '2012-03-08', '2012-03-09',
               '2012-03-10'],
              dtype='datetime64[ns]', freq='D')

In [114]: rng + pd.offsets.BusinessDay(5)
Out[114]: 
DatetimeIndex(['2012-03-13', '2012-03-14', '2012-03-15', '2012-03-16',
               '2012-03-16'],
              dtype='datetime64[ns]', freq=None)

分类数据#

pandas 可以在DataFrame中包含分类数据。有关完整文档，请参阅分类简介和API 文档。

1
2
3
4
In [115]: df = pd.DataFrame(
   .....:     {"id": [1, 2, 3, 4, 5, 6], "raw_grade": ["a", "b", "b", "a", "a", "e"]}
   .....: )
   .....:

将原始等级转换为分类数据类型

1
2
3
4
5
6
7
8
9
10
11
12
In [116]: df["grade"] = df["raw_grade"].astype("category")

In [117]: df["grade"]
Out[117]: 
0    a
1    b
2    b
3    a
4    a
5    e
Name: grade, dtype: category
Categories (3, object): ['a', 'b', 'e']

将类别重命名为更有意义的名称

1
2
3
In [118]: new_categories = ["very good", "good", "very bad"]

In [119]: df["grade"] = df["grade"].cat.rename_categories(new_categories)

重新排序类别并同时添加缺失的类别（Series.cat()下的方法默认返回一个新的Series）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [120]: df["grade"] = df["grade"].cat.set_categories(
   .....:     ["very bad", "bad", "medium", "good", "very good"]
   .....: )
   .....: 

In [121]: df["grade"]
Out[121]: 
0    very good
1         good
2         good
3    very good
4    very good
5     very bad
Name: grade, dtype: category
Categories (5, object): ['very bad', 'bad', 'medium', 'good', 'very good']

排序是按类别顺序，而不是字典顺序

1
2
3
4
5
6
7
8
9
In [122]: df.sort_values(by="grade")
Out[122]: 
   id raw_grade      grade
5   6         e   very bad
1   2         b       good
2   3         b       good
0   1         a  very good
3   4         a  very good
4   5         a  very good

使用 observed=False 按分类列分组也会显示空类别

1
2
3
4
5
6
7
8
9
In [123]: df.groupby("grade", observed=False).size()
Out[123]: 
grade
very bad     1
bad          0
medium       0
good         2
very good    3
dtype: int64

绘图#

请参阅绘图文档。

我们使用标准约定来引用 matplotlib API

1
2
3
In [124]: import matplotlib.pyplot as plt

In [125]: plt.close("all")

plt.close 方法用于关闭图形窗口

1
2
3
4
5
In [126]: ts = pd.Series(np.random.randn(1000), index=pd.date_range("1/1/2000", periods=1000))

In [127]: ts = ts.cumsum()

In [128]: ts.plot();

../_images/series_plot_basic.png

plot()绘制所有列

1
2
3
4
5
6
7
8
9
10
11
12
In [129]: df = pd.DataFrame(
   .....:     np.random.randn(1000, 4), index=ts.index, columns=["A", "B", "C", "D"]
   .....: )
   .....: 

In [130]: df = df.cumsum()

In [131]: plt.figure();

In [132]: df.plot();

In [133]: plt.legend(loc='best');

../_images/frame_plot_basic.png

导入和导出数据#

请参阅IO 工具部分。

CSV#

写入 CSV 文件：使用DataFrame.to_csv()

1
2
3
In [134]: df = pd.DataFrame(np.random.randint(0, 5, (10, 5)))

In [135]: df.to_csv("foo.csv")

从 CSV 文件读取：使用read_csv()

1
2
3
4
5
6
7
8
9
10
11
12
13
In [136]: pd.read_csv("foo.csv")
Out[136]: 
   Unnamed: 0  0  1  2  3  4
0           0  4  3  1  1  2
1           1  1  0  2  3  2
2           2  1  4  2  1  2
3           3  0  4  0  2  2
4           4  4  2  2  3  4
5           5  4  0  4  3  1
6           6  2  1  2  0  3
7           7  4  0  4  4  4
8           8  4  4  1  0  1
9           9  0  4  3  0  3

Parquet#

写入 Parquet 文件

1
In [137]: df.to_parquet("foo.parquet")

使用read_parquet()从 Parquet 文件读取

1
2
3
4
5
6
7
8
9
10
11
12
13
In [138]: pd.read_parquet("foo.parquet")
Out[138]: 
   0  1  2  3  4
0  4  3  1  1  2
1  1  0  2  3  2
2  1  4  2  1  2
3  0  4  0  2  2
4  4  2  2  3  4
5  4  0  4  3  1
6  2  1  2  0  3
7  4  0  4  4  4
8  4  4  1  0  1
9  0  4  3  0  3

Excel#

读写Excel。

使用DataFrame.to_excel()写入 Excel 文件

1
In [139]: df.to_excel("foo.xlsx", sheet_name="Sheet1")

使用read_excel()从 Excel 文件读取

1
2
3
4
5
6
7
8
9
10
11
12
13
In [140]: pd.read_excel("foo.xlsx", "Sheet1", index_col=None, na_values=["NA"])
Out[140]: 
   Unnamed: 0  0  1  2  3  4
0           0  4  3  1  1  2
1           1  1  0  2  3  2
2           2  1  4  2  1  2
3           3  0  4  0  2  2
4           4  4  2  2  3  4
5           5  4  0  4  3  1
6           6  2  1  2  0  3
7           7  4  0  4  4  4
8           8  4  4  1  0  1
9           9  0  4  3  0  3

常见陷阱#

如果您尝试对Series或DataFrame执行布尔操作，可能会看到类似以下的异常：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
In [141]: if pd.Series([False, True, False]):
   .....:      print("I was true")
   .....: 
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-141-b27eb9c1dfc0> in ?()
----> 1 if pd.Series([False, True, False]):
      2      print("I was true")

~/work/pandas/pandas/pandas/core/generic.py in ?(self)
   1575     @final
   1576     def __nonzero__(self) -> NoReturn:
-> 1577         raise ValueError(
   1578             f"The truth value of a {type(self).__name__} is ambiguous. "
   1579             "Use a.empty, a.bool(), a.item(), a.any() or a.all()."
   1580         )

ValueError: The truth value of a Series is ambiguous. Use a.empty, a.bool(), a.item(), a.any() or a.all().

请参阅比较和常见陷阱以获取解释和解决方法。

留言與分享

23. 最小生成树

分類 算法

23. 最小生成树

引：在设计电子电路时，我们常常需要将多个组件的针脚连起。若要连接n个针脚，可以用n-1根连线，我们希望使用的最短的连线来连接针脚。

最小生成树问题：
一个连通无向图G=(V,E)G = (V, E)中，对于每条边(u,v)∈E(u, v) \in E，为其赋予权重w(u,v)w(u, v)。找到一个无环子集T⊆ET \subseteq E，使得所有的结点可以互相到达，并且具有最小的权重，即：w(T)=∑(u,v)∈Tw(u,v)w(T) = \sum_{(u, v) \in T}w(u, v)的值最小。TT就是图GG的最小生成树。

下图中阴影部分组成的就是最小生成树。

23_1.PNG

生成最小生成树

本章将介绍两种生成最小生成树的算法，他们都用了贪心策略。

思想：创建一个边的集合A，首先讲集合A设置为空集，每次循环加入一条安全的边到集合A中，是的A是最小生成树T的子集，直到集合A覆盖了所有结点。

下面是这个贪心策略的伪代码：

23_GENERIC_MST.PNG

如何找出一个安全的边

这个贪心策略的重点就是如何找出安全的边。

设边集合A覆盖的结点集合为S，没覆盖到的结点集合为V-S。想要生成最小生成树，则必须有且仅有一条边连接S和V-S（连接两个集合的意思为边的一头在S中，另一头在V-S中），所有连接S和V-S的边中权重最小的边就是安全的边。

可以用反证法证明这种选择安全的边的方法是正确的。

Kruskal算法

思想：初始时，将∣V∣|V|个结点视为∣V∣|V|棵树并组成森林。所有边的权重按照从小到大排序，从最小的边开始编译，如果这个边能连接森林中的两棵树，则将这条边加入集合A，并且将这两棵树合并为一棵树。直到森林中只剩一棵树。

伪代码和事例如下：

23_KRUSKAL.PNG

23_4.PNG

Prim算法

思想：初始时，给所有的结点赋予一个无穷大的key值，并加入优先队列。每次循环时，从优先队列中取出一个key值最小的结点u加入集合A中，并且更新优先队列中所有与结点u相连的结点v的key值（如果w(u,v)<v.keyw(u,v) < v.key，则v.key=w(u,v)v.key = w(u,v)）。直到优先队列为空。

伪代码和事例如下：

23_PRIM.PNG

23_5.PNG

TODO:时间复杂度分析

留言與分享

22. 基本的图算法

分類 算法

22. 基本的图算法

本章介绍图的表示和搜索。
许多的图算法在一开始都会先通过搜索来获得图的结构，其他一些图算法则是对基本的搜索加以优化。
可以说，图的搜索技巧是整个图算法领域的核心。

图的表示

G=(V,E)G = (V, E)

图G由结点的集合V 和 边的集合E 组成

可以用两种方法表示，一种是邻接链表（下图b），一种是邻接矩阵（下图c）。
邻接链表一般用于表示稀疏图（边数∣E∣|E|远小于∣V∣2|V|^2），默认都使用邻接链表表示。在稠密图（∣E∣|E|接近∣V∣2|V|^2）的情况下，倾向使用邻接矩阵。

无向图：
22_1.PNG
有向图：
22_2.PNG

邻接链表表示

由一个链表数组AdjAdj组成，数组大小为∣V∣|V|，链表Adj[u]Adj[u]存储了结点uu出发的边的终点。
比如上面无向图中，从结点1出发有两条边，边的终点分别是2和4，反应到邻接链表中就是Adj[1]Adj[1]存储了两个节点2和4。

邻接链表需要的存储空间为Θ(∣V∣+∣E∣)\Theta(|V|+|E|)

邻接矩阵表示

由一个∣V∣×∣V∣|V| \times |V| 的矩阵A=(aij)A = (a_{ij})表示，并满足以下条件：

aij={1if(i,j)∈E,0other,a_{ij} = \left \{ \begin{aligned} & 1 & if (i, j) \in E, &\\ & 0 & other, & \end{aligned} \right.

当边有权重时，aija_{ij}可以存储权重值。

邻接矩阵需要的存储空间为Θ(∣V∣2)\Theta(|V|^2)

一些术语

一个结点的出度为，从这个结点触发的边的个数。
一个结点的入度为，到达这个结点的边的个数。

广度优先搜索

思路：利用一个队列，首先将头结点插入队列，循环的取出队列中的一个结点，并将于该结点相连的结点加入队列，直到队列变空，搜索结束。

辅助的给每个结点加入三个属性：

  • color：白色表示还未被搜索，灰色表示加入队列，黑色表示从队列里出来
  • d：该节点在第几轮被发现
  • \boldsymbolπ\boldsymbol{\pi}：该结点的前驱（结点第一次被发现时，正在查询的结点）

下面是广度优先搜索的伪代码和事例：

22_BFS.PNG
22_3.PNG

广度优先搜索的正确性

TODO

广度优先搜索的性质

最短路径

从某个结点u做广度优先搜索，可以找出这个结点到其他结点的最短路径。

结点v和结点u的最短路径距离为v.d

从结点v开始 循环列举前驱结点，就是结点v和结点u的最短路径中经过的结点。

广度优先树

广度优先搜算中，我们在π\pi属性中存储了每个结点的前驱结点，另前驱结点作为该结点的父节点，我们可以得到一个广度优先树。发现新结点的边为树边。

深度优先搜索

思路：尽可能的深入。总是对最近发现的结点v出发的边进行探索，直到结点v出发的边全部被发现时，回溯到v的前驱结点继续探索，直到从源节点出发所有可以到达的结点都被发现。这时如果还有未被搜索的结点，则再随机找一个未被搜索的结点作为源节点进行搜索。

因为可能从一个源节点出发不能搜索到所有结点，所以深度优先搜索会产生多个深度优先树组成深度优先深林。

辅助的给每个结点加入四个属性：

  • color：白色表示还未被搜索，灰色表示已被发现但出发的边还没搜索完，黑色表示已被发现并且出发的边已被搜索完
  • d：该节点的发现时间
  • f：该结点出发搜索结束的时间
  • \boldsymbolπ\boldsymbol{\pi}：该结点的前驱（结点第一次被发现时，正在查询的结点）

下面是深度优先搜索的伪代码和事例：

22_DFS.PNG
22_4.PNG

结点中的x/y表示该结点的发现时间为x，完成时间为y
图中树边被标记为灰色，向前，横向，向前的边分别被标记为B, C, F

深度优先搜索的性质

22_5.PNG

括号花定理

如上图b所示，每个结点的发现时间和完成时间组成一个括号花结构。

对于两个结点u和v，如果区间[u.d, u.f] 和 [v.d, v.f] 不相交，则u不是v的后代，v也不是u的后代；
如果[u.d, u.f] 包含在 [v.d, v.f] 内，则u是v后代，反之亦然。

白色路径定理

如果结点v是u的后代，当u.d时间时，存在一条从u到v全部由白色结点组成的路径。

拓扑排序

对于有向无环图G=(V,E)G = (V, E)，其拓扑排序是G种所有结点的一种线性次序，该次序满足如下条件：如果G包含边(u, v)，则结点u在拓扑排序中处于结点v的前面。

许多实际应用都需要使用有向无环图来说明事件的优先次序。

下图是一个穿衣服的实例，图a中表示了穿戴某一件衣物的依赖关系，图b是图a拓扑排序的结果，按照图b相反的顺序穿衣服就是没问题的了。

22_7.PNG

拓扑排序的思想为：对图G做DFS，然后按照结点搜索的完成时间逆序排序。伪代码如下：

22_TOPOLOGICAL_SORT.PNG

拓扑排序的正确性：在向无环图中，如果有变(u, v)，那么v肯定比u先完成搜索。

强联通分量

有向图G=(V,E)G = (V, E)的强连通分量是一个最大结点集合C⊆VC \subseteq V，对于该集合的任意一对结点可以互相到达。

下图a的灰色覆盖区域就是图的强联通分量。

22_9.PNG

算法伪代码如下：

  1. 对G做DFS，并记下每个结点的完成时间u.f
  2. 转置G，得到GTG^T，如上图b
  3. 按照u.f大小，从大到小对GTG^T做DFS
  4. 第三步得到的深度优先深林中，每棵深度优先树的结点都组成为G的一个强联通分量

22_STRONGLY_CONNECTED_COMPONENTS.PNG

思想：
  对于分量图GSCC=(VSCC,ESCC)G^{SCC} = (V^{SCC}, E^{SCC})，VSCC=v1,v2,...,vkV^{SCC} = {v_1, v_2, ... , v_k}，图GG中的强联通分量CiC_i集合代表分量图中的结点viv_i：如果有x∈Ci,y∈Cjx\in C_i, y\in C_j，且图GG中有边(x,y)(x, y)，则边(vi,vj)∈ESCC(v_i, v_j) \in E^{SCC}，且图GSCCG^{SCC}是有向无环图。

证明：
  引理1：CC和C′C^\prime是图GG的两个强连通分量。当u,v∈C;u′,v′∈C′u, v \in C; u^\prime, v^\prime \in C^\prime， 若有u⇝u′u \rightsquigarrow u^\prime，则不可能有v′⇝vv^\prime \rightsquigarrow v。
     可用反证法证明，若有u⇝u′u \rightsquigarrow u^\prime且v′⇝vv^\prime \rightsquigarrow v，则CC和C′C^\prime将成为同一个强连通分量。
  引理2：CC和C′C^\prime是图GG的两个强连通分量。当(u,v)∈E(u, v) \in E且u∈C,v∈C′u \in C, v \in C^\prime，则f(C)>f(C′)f(C) > f(C^\prime)
     当d(C)<d(C′)d(C) < d(C^\prime)时，若xx为CC中最早被发现的结点，则CC和C′C^\prime中的其它结点都是xx的子孙，也就是所有结点的完成时间都比xx早，所以x.f=f(C)>f(C′)x.f=f(C)>f(C^\prime)
     当d(C)>d(C′)d(C) > d(C^\prime)时，根据引理1，没有从CC到C′C^\prime的边，也就是C′C^\prime完成之后不会到达任意CC中的结点，所以f(C)>f(C′)f(C)>f(C^\prime)
  引理3：CC和C′C^\prime是图GG的两个强连通分量。当(u,v)∈ET(u, v) \in E^T且u∈C,v∈C′u \in C, v \in C^\prime，则f(C)<f(C′)f(C) < f(C^\prime)
     (u,v)∈ET⟹(v,u)∈E(u, v) \in E^T \Longrightarrow (v, u) \in E，由引理2可直接得知f(C)<f(C′)f(C) < f(C^\prime)
  证明：根据数学归纳法，假设算法第三行所生成的前kk棵树都是强连通分量，现在需要考虑第k+1k+1棵树是否为强连通分量：
     设第k+1k+1棵树是CC，CC的根节点为uu，uu所在的强连通分量为C′′C^{\prime\prime}。
     若GTG^T中从C′′C^{\prime\prime}到其他强连通分量C′′′C^{\prime\prime\prime}有边，那么根据引理3可知f(C′′)<f(C′′′)f(C^{\prime\prime}) < f(C^{\prime\prime\prime})。
     而算法对GTG^T做DFS时，是按照ff大小逆序进行，所以从C′′C^{\prime\prime}出来的变都是到前kk棵树的。
     所以C=C′′C=C^{\prime\prime}，也就是说第k+1k+1棵树为强连通分量。

留言與分享

17. 摊还分析

分類 算法

17. 摊还分析

在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这样，我们就可以说明一个操作的平均代价是很低的，即使序列中某个单一操作的代价很高。摊还分析不同于平均情况分析，它并不涉及概率，它可以保证最坏情况下每个操作的平均性能。

本章介绍三种摊还分析方法：

  • 聚合分析
  • 核算法
  • 势能法

首先我们先看两个小问题

栈操作

对传统的栈操作MULTIPOP(S, k)扩展，伪代码如下，相当于做k次POP(S)

1
2
3
4
MULTIPOP(S, k)
1   while not STACK-EMPTY(S) and k > 0
2       POP(S)
3       k = k - 1

如果在一个包含s个对象的栈上做MULTIPOP(S, k)操作，POP的次数为min(s, k)。

我们来分析一个由n个PUSH/POP/MULTIPOP组成的操作序列在一个空栈上的执行情况。
MULTIPOP的最坏代价为O(n)O(n)，那么n个操作的最坏代价是O(n2)O(n^2)吗？

二进制计数器递增

k位二进制计数器递增，初始值为0。用一个位数组A[0…k-1]作为计数器。当计数器保存二级制数x时，x的最低位保存在A[0]中，最高位保存在A[k-1]中，因此x=∑i=0k−1A[i]⋅2ix = \sum\limits_{i=0}^{k-1}A[i]\cdot 2^i。INCREMENT的伪代码如下：

1
2
3
4
5
6
7
INCREMENT(A)
1   i = 0
2   while i < A.length and A[i] == 1
3       A[i] = 0
4       i = i + 1
5   if i < A.length
6       A[i] = 1

可以想象，最坏情况当k位全部是1时，INCREMENT操作要做k次翻转操作，也就是要花费Θ(k)\Theta(k)时间，所以对初值为0的计数器，做n次操作的最坏情况花费O(nk)O(nk)次操作？

从上两个问题，我们都根据一个操作最坏情况的时间消耗推测，整个操作序列的时间消耗，显然不是一个确界。下面我们通过三种摊还分析方法来分析这两个问题中每个操作的平均代价（摊还代价）。

聚合分析

聚合分析——确定n个操作最坏情况的总代价T(n)T(n)，所以每个操作的平均代价为T(n)/nT(n)/n。

栈操作：
虽然单独的MULTIPOP操作可能代价很高，但在一个空栈上实行n个操作，POP和MULTIPOP操作的总消耗最多为O(n)，因为只有push进去数据，POP和MULTIPOP才会有消耗，而且PUSH操作每次只能push一个数据进来。所以n个操作最坏情况的总代价为O(n)，除以n得到每个操作的平均代价为O(1)。

二进制计数器递增：
下图展示了二进制计数器从0递增到16的过程，阴影部分表示递增后需要翻转的位。我们可以发现A[0]每次递增时都发生翻转，A[1]每两次递增发生一次翻转，A[2]每四次递增发生一次翻转，以此类推第i位每2i2^i次递增发生一次翻转。也就是说n次INCREMENT操作后，第i位会翻转⌊n/2i⌋\lfloor n/2^i\rfloor 次。
执行n次INCREMENT操作产生的总翻转次数为：

∑i=0k−1⌊n/2i⌋<n∑i=0∞12i=2n\sum_{i=0}^{k-1}\lfloor n/2^i\rfloor < n\sum_{i=0}^\infty \frac{1}{2^i} = 2n

所以，n个INCREMENT操作的最坏情况用时为O(n)，除以n得到每个操作的平均代价为O(1)。
17_2.PNG

核算法

核算法——对不同的操作赋予不同的费用（可以大于或者小于实际的代价，但不能为负值），称其为摊还代价。当一个操作摊还代价大于实际代价时，我们将差额存起来，称其为信用/存款。后续操作如果有摊还代价小于实际代价时，我们将之前存的信用拿出一部分来抵消这里的差值。如果用cic_i表示第i个操作的实际代价，用c^i\hat{c}_i表示第i个操作的摊还代价，则对任意n个操作的序列，要求：

∑i=1nc^i≥∑i=1nci\sum_{i=1}^n \hat{c}_i \ge \sum_{i=1}^n c_i

信用总能刚好抵债或者有剩余，从而使得总的摊还代价为总实际代价的上界。

栈操作：
栈操作的实际代价如下：

1
2
3
PUSH       1
POP        1
MULTIPOP   min(k, s)

我们将栈操作的摊还代价设置为：

1
2
3
PUSH       2
POP        0
MULTIPOP   0

每次PUSH操作支付1的实际代价，剩下的1存起来。存起来的钱和堆栈里的数据量相同，而POP或MULTIPOP操作的实际代价为要pop的数据量，所以存款总能保证大于等于零。
每个操作的摊还代价都是常数，所以总的摊还代价为O(n)。

二进制计数器递增：
将INCREMENT中的操作分为置位操作（第6行，0->1）和复位操作（while循环中的操作，1->0）。令置位操作的摊还代价为2，复位操作的摊还代价为0。每次置位操作可以多出1存起来（存起来的钱和计数器中1的个数相同），复位操作需要预支存款，但复位操作只有当某一位是1的时候才会执行，由于计数器中1的个数永远不会为负，所以存款总能保证大于等于零。
每个操作的摊还代价都是常数，所以总的摊还代价为O(n)。

势能法

势能法将数据结构和势能关联起来——对一个初始化数据结构D0D_0执行n个操作。cic_i为第i个操作的实际代价，DiD_i为第i次操作后的数据结构。势函数Φ\Phi将每个数据结构DiD_i映射到一个实数Φ(Di)\Phi(D_i)，为数据结构DiD_i的势。第i个操作的摊还代价c^i\hat{c}_i用势函数D0D_0定义为：

\textrm{公式1：} \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})

即，每个操作的摊还代价为实际代价加上操作引起的势变化。所以总摊还代价为：

\textrm{公式2：}\sum_{i=1}^n \hat{c}_i = \sum_{i=1}^n (c_i + \Phi(D_i) - \Phi(D_{i-1})) = \sum_{i=1}^n c_i + \Phi(D_n) - \Phi(D_{0})

根据公式1可以得到每个步骤的摊还代价，从而算出总的摊还代价，然后根据公式2可以得出总实际代价的上界/下界（Φ(Dn)−Φ(D0)\Phi(D_n) - \Phi(D_{0})为正数则得到上界，Φ(Dn)−Φ(D0)\Phi(D_n) - \Phi(D_{0})为负数则得到下界）。

`````````````` 核算法 势能法
摊还代价 猜想/推测得到 通过实际代价加势能变化得到
思想 较为简单 较为抽象
难点 需要证明存款足以抵债 需要考虑一个好的势函数
优势 考虑起来较为容易 应用范围广，适用的场景更多
联系 核算法的存款往往能和势能法的势函数相对应 势能法中计算摊还代价时，当势差为正数时相当于将势差作为存款存起来，当势差为负数时相当于要用存款中拿出部分来抵债，所以两种方法的内涵是一致的

栈操作：
将势函数定义为当前栈中的数据量。
PUSH操作会压入一个数据，所以势差为1，而且实际代价为1，所以PUSH操作的摊还代价为2。
POP/MULTIPOP操作会弹出x个对象，所以势差为-x，而实际代价为x，所以POP/MULTIPOP操作的摊还代价为0。

栈每个操作的摊还代价都是O(1)，所以n个操作的总摊还代价为O(n)。由于初始的栈为空，而结束时栈的数据量大于等于0，也就是说Φ(Dn)−Φ(D0)\Phi(D_n) - \Phi(D_{0})为正数，所以n个操作的总摊还代价为总实际代价的上界O(n)。

二进制计数器递增：
将势函数定义为计数器中1的个数bib_i。
假设第i个操作将tit_i个位复位，则实际代价为ti+1t_i + 1，因为还有一次置位操作。
再来考虑摊还代价，如果bib_i为0，则将k位都复位了，因此bi−1=ti=kb_{i-1} = t_i = k。
如果bi>0b_i>0，则bi=bi−1−ti+1b_i = b_{i-1} - t_i + 1。无论那种情况都有bi≤bi−1−ti+1b_i \le b_{i-1} - t_i + 1，所以摊还代价为：

c^i=ci+Φ(Di)−Φ(Di−1)≤(ti+1)+(−ti+1)=2\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \le (t_i + 1) + (-t_i + 1) = 2

所以总摊还代价的上界为O(n)，由于计数器初始状态为0，而1的个数不会为负数，所以n个操作的总摊还代价为总实际代价的上界O(n)。

势能法的还有个优势就是，我们可以简单的得出当初始状态不是0时实际代价的上界。由公式2可得：

∑i=1nci≤∑i=1n2−bn+b0=2n−bn+b0≤2n+b0≤2n+k\sum_{i=1}^n c_i \le \sum_{i=1}^n 2 - b_n + b_0 = 2n -b_n + b_0 \le 2n + b_0 \le 2n + k

所以只要k=O(n)k=O(n)那么总实际代价就是O(n)。

动态表

11章介绍了散列表，我们知道散列表的大小和数据量应该是线性相关的，数据太稀疏会浪费空间，数据太稠密会浪费时间。当我们不知道会有多少数据插入时，就没办法确定散列表的大小，所以要引进动态表。
表扩张——当插入数据时发现散列表的装载因子为1（表的大小和数据量相同），对表进行扩张，比如扩张为两倍大小，首先创建一个两倍大小的表，将原来散列表中的数据插入新创建的表中，然后插入新的数据，最后不能忘了把老的表析构。

表收缩——当删除数据时发现散列包的装载因子小于某个值，对表进行收缩，与表的扩张类似，比如收缩为原来表大小的一半，首先删除这个数据并创建一般大小的新表，将原来散列表中的数据插入新创建的表中，然后把老的表析构。

表收缩时判断的装载因子的选择很重要，如果表扩张选择的两倍大小，而表收缩是选择装载因子为二分之一，这时如果在表扩张后立马删除数据，又反复的插入，删除数据，这样会导致表大小的震荡。这种情况下时间机器浪费时间。
所以我们通常可以选择该装载因子为四分之一来避免这个问题。

无论是表扩张还是表收缩，我们都可以用平摊分析来证明动态表的插入和删除操作的平均代价还是O(1)。详细情况参考书中内容，这里不做赘述。

留言與分享

16. 贪心算法

分類 算法

16. 贪心算法

求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法．贪心算法就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。

活动选择问题

我们的第一个例子是一个调度竞争共享资源的多个活动的问题，目标是选出一个最大的互相兼容的活动集合。假定有一个 n 个活动的集合S=a1,a2,...,anS={a_1, a_2, ... , a_n}，这些活动使用同一个资源（例如一个阶梯教室），而这个资源在某个时刻只能供一个活动使用。每个活动aia_i都有一个开始时间sis_i和一个结束时间fif_i ，其中0≤si<fi<∞0\le s_i < f_i < \infty。如果被选中，任务aia_i发生在半开时间区间[si,fi)[s_i, f_i)期间．如果两个活动aia_i和aja_j满足[si,fi)[s_i, f_i)和[sj,fj)[s_j, f_j)不重叠，则称它们是兼容的．也就是说，若si≥fjs_i\ge f_j或sj≥fis_j\ge f_i，则aia_i和aja_j是兼容的．在活动选择问题中，我们希望选出一个最大兼容活动集。假定活动已按结束时间的单调递增顺序排序：

f1≤f2≤f3≤...≤fn−1≤fnf_1 \le f_2 \le f_3 \le ... \le f_{n-1} \le f_n

例如下面的活动集合S：

i 1 2 3 4 5 6 7 8 9 10 11
sis_i 1 3 0 5 3 5 6 8 8 2 12
fif_i 4 5 6 7 9 9 10 11 12 14 16

对于这个例子，子集S=a3,a9,a11S={a_3, a_9,a_11}由相互兼容的活动组成。但它不是一个最大集，因为子集S=a1,a4,a8,a11S={a_1, a_4, a_8,a_11}更大。实际上S=a1,a4,a8,a11S={a_1, a_4, a_8,a_11}是一个最大兼容活动子集，另一个最大子集是
S=a2,a4,a9,a11S={a_2, a_4, a_9,a_11}。

最优子结构

假定集合SijS_{ij}（aia_i结束之后，aja_j开始之前的活动）的一个最大相互兼容的活动子集为AijA_{ij}，而且AijA_{ij}包含了活动aka_k。 由于最优解包含了活动aka_k，我们得到两个子问题：SikS_{ik}（aka_k开始之前的活动）的兼容活动 和 SkjS_{kj}（aka_k结束之后的活动）的兼容活动。由剪切-粘贴法可以证明SijS_{ij}的最优解为SikS_{ik}的最优解、aka_k、 SkjS_{kj}的最优解组成。即Aij=Aik∪ak∪AkjA_{ij} = A_{ik} \cup a_k \cup A_{kj}。
所以这时我们可以用动态规划方法求出所有k的取值情况对应的解，然后找出一个最大的作为最优解。
如果用c[i,j]c[i, j]表示SijS_{ij}的最优解的大小，递归式为：

c[i,j]={0ifSij=∅,maxak∈Sij{c[i,k]+c[k,j]+1}ifSij≠∅,c[i, j] = \left \{ \begin{aligned} & 0 & if \quad S_{ij} = \varnothing, \\ & \max_{a_k \in S_{ij}}\{c[i, k] + c[k, j] + 1\} & if \quad S_{ij} \ne \varnothing, \end{aligned} \right.

贪心选择

动态规划需要考虑每种子问题，比较之后得出哪种选择是最优解。假如我们无需求解每种子问题，直接就可以找出一个最优选择。那么将大大减少计算过程。对于活动选择问题，我们可以只考虑一个选择：贪心选择。

直观上，我们应该选择一个活动，使得选择它后剩下的资源可以尽可能多的被其他活动利用。直觉告诉我们选择S中最早结束的活动，因为他可以剩下尽可能多的资源。由于我们活动时按照结束时间排序的，也就是说贪心选择就是a1a_1。

当做出贪心选择后，只剩下一个子问题需要求解，因为不会有在a1a_1开始前结束的活动。加上前面的最优子结构性质，所以S的最优解就是a1⋃A1na_1 \bigcup A_{1n}。

证明贪心选择——最早结束的活动总是最优解的一部分：

定理： 考虑任意非空子问题SkS_k，另ama_m是SkS_k种最早结束的活动，则ama_m在SkS_k的某个最大兼容活动子集中。

证明： AkA_k是SkS_k的某个最大兼容活动子集，aja_j是AkA_k种最早结束的活动。如果aj=ama_j = a_m，则已经证明ama_m在SkS_k的某个最大兼容活动子集中；如果aj≠ama_j \ne a_m，那么用ama_m替换AkA_k中的aja_j产生Ak′A_k^\prime，由于fm≤fjf_m \le f_j而且AkA_k中的活动都是不相交的，所以Ak′A_k^\prime也是SkS_k的最大兼容活动子集，得证。

递归贪心算法

为了方便算法初始化，添加一个虚拟活动a0a_0，其结束时间f0=0f_0 = 0，这样子问题S0S_0就是完整的活动集S。求解原问题即可调用 RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)。

16_RECURSIVE_ACTIVITY_SELECTOR.PNG

2,3行是为了找到第一个，与aka_k不相交的最先结束的活动ama_m。

迭代贪心算法

16_GREEDY_ACTIVITY_SELECTOR.PNG

贪心算法原理

前面我们讨论活动选择问题的贪心算法的过程比通常的过程繁琐一些，我们当时经过了如下几个步骤：

  1. 确定问题的最优子结构．
  2. 设计一个递归算法（动态规划）。
  3. 证明如果我们做出一个贪心选择，则只剩下一个子问题。
  4. 证明贪心选择总是安全的（步骤 3 、 4 的顺序可以调换）。
  5. 设计一个递归算法实现贪心策略。
  6. 将递归算法转换为迭代算法。

这个过程详细的看到贪心算法是如何以动态规划为基础的。
更一般地，我们可以简单按如下步骤设计贪心算法：

  1. 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
  2. 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
  3. 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

在本章剩余部分中，我们将使用这种更直接的设计方法．但我们应该知道，在每个贪心算法之下，几乎总有一个更繁琐的动态规划算法。

在证明一个问题可以用贪心算法解决过程中，证明一个问题的贪心选择性质 和 最优子结构性质 是非常重要的。

赫夫曼编码

赫夫曼编码k而已有效的压缩数据：通常可以节省20%~90%的空间，具体压缩率依赖于数据的特型。我们将待压缩数据看做字符序列。根据每个字符出现的频率，赫夫曼贪心算法构造出字符的最优二进制表示。

下面给出一个例子，待压缩文件有10万个字符数据。文件中出现了6种不同的字符，出现的次数见表格：

a b c d e f
频率（千次） 45 13 12 16 9 5
定长编码 000 001 010 011 100 101
变长编码 0 101 100 111 1101 1100

如果用定长编码来存储信息，那么需要用3位来表示z和6个字符。这种方法总共需要300000个二进制位来存储。
但如果用变长编码来存储信息，如表格中所示，出现频率较高字符的使用短一点的二进制编码表示。这种方法需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000(45 \times 1 + 13 \times 3 + 12 \times 3 + 16 \times 3 + 9 \times 4 + 5 \times 4) \times 1000 = 224000位。与定长编码相比节约了25%的空间。

我们这里只考虑前缀码，即没有任何码字是其他码字的前缀。只考虑前缀码的原因是，前缀码与任何其他编码方式比都可以保证最优的压缩率，但此处不予证明。
前缀码的作用是简化解码过程，由于没有任何码字是其他码字的前缀，所以文件开头的码字是无歧义的。我们可以简单的识别出开始码字，将其转换为对应的字符，然后对文件剩余部分重复的做这种解码过程。
编码方案可以用一个二叉树表示——编码树。下图a表示了定长编码的编码树，图b表示了变长编码的编码树。叶子结点为字符，并存储字符的出现频率，字符的二进制编码是从根节点到叶子节点的路径，向左表示0，向右表示1。内部结点不存储字符，存储子节点的频率和。

16_2.PNG

给定一棵对应前缀码的树T，我们可以容易地计算出编码一个文件需要多少个二进制位。对于字母表C中的每个字符c，令属性c.freq表示c在文件中出现的频率，令dT(c)d_T(c)表示c的叶结点在树中的深度。注意，dT(c)d_T(c)也是字符c的码字的长度。则编码文件需要习：

B(T)=∑c∈Cc.freq⋅dT(c)B(T) = \sum_{c \in C}c.freq\cdot d_T(c)

个二进制位，我们将B(T)定义为T的代价。

构造赫夫曼编码

赫夫曼设计了一个贪心算法得到最优前缀码，被称为赫夫曼编码。

下面是哈夫曼算法的伪代码，输入一个字母表C，输出一个最优前缀码对应的编码树。

16_HUFFMAN.PNG

构造编码树的过程如下：
算法中使用一个优先队列Q，初始化时将字母表C全部插入Q。每次循环时，创造一个结点z，从优先队列取出两个最小值作为结点z的孩子，并使得z.freq为两个孩子的freq之和，然后将z结点重新插入优先队列Q中。直到优先队列中只剩下一个元素，这时这个元素为编码树的root结点，并且所有字符都已加入编码树。

下面是一个例子：

16_5.PNG

证明赫夫曼算法的正确性

贪心选择

贪心选择性质：若x,y是C中频率最低的两个字符。那么C存在一个最优前缀码，x,y的码字长度相等，且只有最后一个二进制位不同。

证明思路，假设有一个最优前缀码的编码树TT，把x,y与编码树中深度最深的两个兄弟节点进行交换产生T′T^\prime。通过计算得出B(T′)≤B(T)B(T^\prime) \le B(T)。

最优子结构

最优子结构性质：若x,y是C中频率最低的两个字符。令C′C^\prime为CC去除x和y，然后加入字符z，且z.freq=x.freq+y.freqz.freq = x.freq + y.freq。T′T^\prime为C′C^\prime的一个最优前缀码的编码树，将T′T^\prime中的叶子节点z替换为一个以x,y为子节点的内部节点得到树TT。则T为C的一个最优前缀码的编码树。

证明思路，反证法，假设C存在一个T′′T^{\prime\prime}比T更优，由贪心选择性质可知x,y为兄弟节点（不一定吧？书中用不失一般性，不太理解），将T′′T^{\prime\prime}中的x,y替换为z得到T′′′T^{\prime\prime\prime}，结果得到B(T′′′)<B(T′)B(T^{\prime\prime\prime}) < B(T^{\prime})，与T′T^\prime为C′C^\prime的一个最优前缀码的编码树的假设相悖。

涉及算法

点击查看实现

留言與分享

15. 动态规划

分類 算法

15. 动态规划

动态规划和分治法相似，都是通过组合子问题的解来求解原问题的解。但不同的是分治法将问题划分为不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。相反，动态规划应用于子问题相互重叠的情况，即不同的子问题具有公共的子子问题。这种情况下，用分治法会反复的求解相同的子问题，造成时间浪费。动态规划对每个子问题只求解一次，并且保存在表格中，从而避免重复计算。

动态规划通常用于求解最优化问题。

我们通常按照如下步骤设计一个动态规划算法：

  1. 刻画一个最优解的结构特点
  2. 递归的定义最优解的值
  3. 计算最优解的值，通常采用自底而上的方法
  4. 利用计算出的信息构造一个最优解

如果只需要最优解的值，而非最优解本身，可忽略第四步。如果需要做第四步，往往需要在执行第三步时维护一些额外信息。

钢条切割

钢条切割问题：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2…n)，求切割方案使得收益rn最大。

钢条切割

考虑当n=4时，所有的切割方案如下，我们发现当把4英寸的钢条切割为两段2英寸长的钢条时产生的收益最大。

钢条切割

当区分1+3切法和3+1切法时，n英寸的钢条有2n-1种切割方案。
我们可以手动得到ri，及对应切割方案：

钢条切割

对于rn，我们可以用更短的钢条的最优切割收益来描述它：
rn=max(pn,r1+rn−1,r2+rn−2,...,rn−1+r1).r_n = max(p_n, r_1+r_{n-1}, r_2+r_{n-2},...,r_{n-1}+r_1) .

这时我们找到了钢条切割问题的最优子结构。每次切割后我们可以把切开的两段钢条看做独立的钢条切歌问题。一段钢条的最优解为所有切割方案中最大的。
我们可以将rn的式子简化为：rn=max1≤i≤n(pi+in−i)r_n=\max\limits_{1\le i\le n}(p_i+i_{n-i}) .

自顶而下的递归实现

根据上面的式子，我们可以得到下面这种自顶而下的递归实现（p为价格数组）：
钢条切割

这种实现的递归式为：T(n)=1+∑j=0n−1T(j).T(n) = 1 + \sum\limits_{j=0}^{n-1}T(j).
我们可以求得T(n)=2iT(n) = 2^i，这个时间是非常惊人的，而这么大的原因就是因为包含了非常多的重复计算。下图是递归树，红线圈起来的都是重复计算部分。

钢条切割

使用动态规划方法

  • 带备忘的自顶而下法
    与前面的递归方法类似，但是用了一个数组r[1…n]记录最优解，如果发现r[n]已经有记录，则无需重复计算，直接返回该值。
    钢条切割
  • 自底而上法
    自底而上法采用子问题的自然顺序，依次求解规模为j=1,2…,n的子问题。
    钢条切割

无论是带备忘的自顶而下法还是自底而上法，其中都是用了一个额外数组来存储子问题的最优解，从而避免重复计算子问题的解。动态规划付出额外的内存空间来节省时间，是典型的时空权衡的例子。

子问题图

当思考动态规划问题时，弄清所涉及子问题及子问题之间的依赖关系很关键。
问题的子问题图准确的表达了这些信息：
钢条切割
途中结点表示钢条切割的子问题规模，箭头表示子问题之间的依赖关系。
有了子问题图，我们便可轻易的得知自底而上的顺序应该如何。
而且子问题图G=(V, E)还可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。通常，一个子问题的求解时间与子问题图中对应顶点的度（射出边的数目）成正比，而子问题的数目等于子问题图的顶点数。因此，通常情况下，动态规划算法的运行时间与顶点和边数量呈线性关系。

重构解

前面的方法只给出的如何求出最优解的值，但并未返回解本身。
下面是基于自底而上动态规划算法的扩展，其中用数组s[0…n]存储n英寸钢条的最优切割方案，s[i]存储的数字表示，i英寸的钢条切割为s[i]英寸和i-s[i]英寸时最优，其中s[i]英寸部分不再切割，i-s[i]英寸部分的最优解需要递归查看。
所以可以通过PRINT-CUT-ROD-SOLUTION来打印出n英寸钢条的一个最优切割方案。
钢条切割

矩阵链乘法

给定一个n个矩阵的序列（矩阵链）<A1,A2,...,An><A_1, A_2, ..., A_n>，我们希望求他们的乘积A1A2...AnA_1A_2...A_n，由矩阵乘法的结合律我们可知给乘积链随意的加上括号不会改变最终的结果，但是不同的括号会影响矩阵链乘法的时间。
以矩阵链<A1,A2,A3><A_1, A_2, A_3>为例，三个矩阵的规模分别是10×100、100×5和5×50。如果按照((A1A2)A3)((A_1A_2)A_3)的顺序计算，A1A2A_1A_2（规模10×5）需要做10×100×5=5000次标量乘法，再与A3A_3相乘又需要10×5×50=2500次标量乘法，总共需要7500次标量乘法。如果按照(A1(A2A3))(A_1(A_2A_3))的顺序计算，A2A3A_2A_3（规模100×50）需要做100×5×50=25000次标量乘法，A1再与之相乘又需要10×100×50=50000次标量乘法，总共需要75000次标量乘法。因此，按照((A1A2)A3)((A_1A_2)A_3)的顺序比按照(A1(A2A3))(A_1(A_2A_3))的顺序快了10倍。
所以引入了矩阵链乘法问题：给定n个矩阵的链<A1,A2,...,An><A_1, A_2, ..., A_n>，矩阵i的规模为pi−1×pip_{i-1} \times p_i，求一个完全括号化方案，使得计算乘积A1A2...AnA_1A_2...A_n所需的标量乘法次数最少。

我们可以用下面这个递归式表示矩阵链完全括号化方案的个数，这个递归式的解为Θ(2n)\Theta(2^n)，所以穷举法是不可行的。

P(n)={1ifn=1,∑k=1n−1P(k)P(n−k)ifn≥2,P(n) = \left \{ \begin{aligned} & 1 & if \quad n = 1, \\ & \sum_{k=1}^{n-1}P(k)P(n-k) & if \quad n \ge 2, \end{aligned} \right.

动态规划法

  1. 刻画一个最优解的结构特点
    用Ai..jA_{i..j}表示AiAi+1...AjA_iA_{i+1}...A_j。我们可以将Ai..jA_{i..j}分解为子问题Ai..kA_{i..k}和Ak+1..jA_{k+1..j}，即AiAi+1...Aj−>(AiAi+1...Ak)(Ak+1Ak+2...Aj)A_iA_{i+1}...A_j -> (A_iA_{i+1}...A_k)(A_{k+1}A_{k+2}...A_j)。然后在对子问题递归求解。
  2. 递归的定义最优解的值
    用m[i,j]m[i,j]表示Ai..jA_{i..j}所需标量乘法次数的最优值。假设Ai..jA_{i..j}的最优分割点为k(i<=k<j)k(i<=k<j)，那么m[i,j]=m[i,k]+m[k+1,j]+pi−1pkpjm[i,j] = m[i,k] + m[k+1,j] + p_{i-1} p_{k} p_{j}，然而这个分割点我们是不知道的，但是肯定在i和j之间，我们只需找到所有可能中的最小值，所以我们有如下递归式：

m[i,j]={0ifi=j,mini≤k≤j{m[i,k]+m[k+1,j]+pi−1pkpj}ifi<j,m[i,j] = \left\{ \begin{aligned} & 0 & if \quad i = j, \\ & \min_{i\le k\le j}\{m[i,k] + m[k+1, j] + p_{i-1}p_kp_j\} & if \quad i < j, \end{aligned} \right.

  1. 计算最优解的值，通常采用自底而上的方法
    从上面的递归式能推测出自底而上法的顺序，或者使用子问题图辅助。可以从链长为2的子问题开始求解，一直递增到链长为n的子问题，Done。伪代码如下：
    矩阵链乘法
    使用m[i,j]存储Ai…j的最优解的值，s[i,j]存储Ai…j的最优分割点k。
    矩阵链乘法
  2. 利用计算出的信息构造一个最优解
    利用s数组存储的最优分割点，我们可以递归的构造出一个最优解，伪代码如下：
    矩阵链乘法

动态规划原理

虽然已经介绍了两个动态规划问题，但可能还会疑惑到底什么样的问题可以使用动态规划方法解决？
适合用动态规划的最优化问题应该具备两个要素：最优子结构和子问题重叠

最优子结构

动态规划法的第一步便是刻画最优解的结构。如果一个问题的最优解包括子问题的最优解，我们称此问题具有最优子结构性质。
发掘最优子结构性质的过程遵循如下通用模式：

  1. 证明问题最优解的第一个组成部分是做出一个选择
  2. 对于一个给定问题，假定已经知道哪种选择会得到最优解
  3. 给定可获得最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好的刻画子问题空间
  4. 利用“剪切-粘贴”技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

    利用反证法：假设子问题的解不是其最优解，那么我们可以“剪切”掉这个非最优解，将最优解“粘贴”进去，从而得到一个更优的解，这与最初的解是原问题最优解的前提假设矛盾。

对于不同问题领域，最优子结构的不同体现在：

  1. 原问题的最优解涉及多少个子问题（一个问题分解为多少个子问题）
  2. 在确定最优解使用那些子问题时，我们需要考虑多少种选择（有多少种分解方式）

重叠子问题

如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。与之相对的，适合用分治法求解的问题通常在递归的每一步都生成全新的子问题。
动态规划通常这样利用重叠子问题的性质：对每个子问题只求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，查表的代价为常数时间。

最长公共子序列

一个给定序列的子序列是降给定序列中零个或者多个元素去掉后的结果。
给定两个序列X和Y，如果Z既是X的子序列，又是Y的子序列，那么Z为X和Y的公共子序列。
最长公共子序列问题给定两个序列X={x1, x2, …, xm}和Y={y1, y2, …, yn}，求X和Y长度最长的公共子序列。

  1. 刻画一个最优解的结构特点
    矩阵链乘法
  2. 递归的定义最优解的值

c[i,j]={0ifi=0orj=0,c[i−1,j−1]+1ifi,j>0andxi=yj,max(c[i,j−1],c[i−1,j])ifi,j>0andxi≠yj,c[i,j] = \left\{ \begin{aligned} & 0 & & if \quad i = 0 \quad or \quad j = 0, \\ & c[i-1,j-1]+1 & & if \quad i,j > 0 \quad and \quad x_i = y_j, \\ & max(c[i,j-1], c[i-1, j]) & & if \quad i,j > 0 \quad and \quad x_i \neq y_j, \end{aligned} \right.

  1. 计算最优解的值，通常采用自底而上的方法
    矩阵链乘法
    c[i, j] 存储序列X1->i和Y1->j最长公共子序列的长度
    b[i, j] 存储序列X1->i和Y1->j最优解依赖的子问题的方向
  2. 利用计算出的信息构造一个最优解
    矩阵链乘法
    当b[i, j]存储的是“↖”时，表示xi和yj相同。
    所以从b[m, i]开始，训着箭头方向查找“↖”，便可以找到一个最长公共子序列。
    伪代码如下：
    矩阵链乘法

涉及算法

点击查看实现

留言與分享

14. 数据结构的扩张

分類 算法

14. 数据结构的扩张

一些工程应用需要的只是教科书中的标准数据结构，也有许多其他的应用需要对现有数据结构进行少许的创新和改造，但只有很少的情况需要创造全新类型的数据结构。
更经常的是，通过存储额外信息的方法来扩张标准的数据结构，然后对这种数据结构编写新的操作来支持所需要的应用。

比如：

动态顺序统计量

之前我们讨论了中位数和顺序统计量，对于一个无序的集合，我们可以在\Omicron(n)\Omicron(n)的时间内确认任何顺序统计量。这里我们将介绍如何修改红黑树，使得可以在\Omicron(lgn)\Omicron(\lg n)时间内确认任何的顺序统计量。以及如何在O(lgn)时间内得到一个元素的秩，即它在集合线性序中的位置。

下图展示了一种支持快速顺序统计的数据结构，顺序统计树。这种数据结构是在红黑树的基础上，给每个元素添加一个属性size。一个结点的size表示以这个结点为根结点的子树大小。我们定义哨兵T.nil的size为0，则有如下等式

x.size = x.left.size + x.right.size + 1

动态顺序统计量

查看给定秩的元素

从根结点开始查找，首先通过左孩子的size+1得到当前结点为根节点时的秩r，然后和需要查找的秩i作比较。如果相等则直接返回，如果i < r 查看左孩子，否则递归查看右孩子，但是查看右孩子时，需要传入i - r，因为右子树并不能知道左子树的大小，而右孩子实际的轶为r+右孩子为根结点时的右孩子的秩：

RANK(x.right) = RANK(x) + (x.right.left.size + 1)

查看给定元素的秩

查看一个元素的秩

假如一个元素x的父结点为根结点，
当这个元素x是根结点的左孩子时，RANK(x)=x.left.size+1RANK(x) = x.left.size + 1
当这个元素x是根结点的右孩子时，RANK(x)=RANK(x.p)+x.left.size+1RANK(x) = RANK(x.p) + x.left.size + 1

利用上面的性质，求解一个元素x的秩时，我们循环的求解当x的父结点为根结点时，x在这个子树中的大小，每次循环上移一层，直到移动到真实的root结点，这时我们已经求出了该元素真实的秩。

查看一个元素的秩

维护size

当插入/删除元素时，除了维护红黑树的特性，我们还要维护结点的size属性。正常的插入/删除导致的size变化比较简单，不在赘述。我们看看当发生旋转时size的维护：

维护size

当对x做左旋后，我们需要重新计算x的size，并且把x之前的size赋给y，因为旋转不会影响这个局部子树的size。
当对y做右旋后，我们需要重新计算y的size，同理把y之前的size赋给x。

如何扩张数据结构

扩张一种数据结构可以分为4个步骤：

  1. 选择一种基础数据结构
  2. 确定基础数据结构中要维护的附加信息
  3. 检验基础数据结构上的基本修改操作能否维护附加信息
  4. 设计一些新操作

在扩张数据结构时，不一定非得时上述结构，上述只是一个一般模式。但我们可以把上述步骤作为一个check list来检验扩张数据结构是否完善。

区间树

有些问题可能会涉及到区间数据，这时候可能就需要用到区间树。比如：查看某一时间段内发生的事。

我们把一个区间[l, h]表示成一个对象i，i.low = l为低端点，i.high = h为高端点。
下图展示了两个区间的三种状态：

  • a，区间i和区间i’重叠
  • b，区间i在区间i’的左边（i.h < i’.l）
  • c，区间i在区间i’的右边（i.l > i’.h）

重叠

区间树是一种对红黑树扩展的数据结构，我们看看红黑树扩展为区间树的过程：

  1. 基础数据结构
    选择红黑树，每个元素包含区间属性x.int，x的key为x.int.low。
  2. 附加信息
    每个结点除了区间信息外，包含一个值x.max，它表示以x为根结点子树中所有端点的最大值。
  3. 对信息的维护
    在插入/删除操作后，需要对max值做维护，最多影响树高h个元素的max值，而且每次维护只需要常数次操作。所以不会影响原有操作的时间复杂度。

    x.max = max(x.int.high, x.left.max, x.right.max)

  4. 设计新的操作
    新操作INTERVAL-SEARCH(T, i)，用来查找区间树T中与区间i重叠的结点。若树中没有区间与i重叠，则返回T.nil。

区间树

INTERVAL-SEARCH(T, i)：将x指向root结点开始循环查看x是否与i重叠，如果重叠则退出循环返回x。如果x有左孩子且左孩子的max值大于等于i.low，则循环查看x的左孩子，否则循环查看x的右结点。

查找

TODO: 用循环不变式证明各个扩张的正确性

留言與分享

13. 红黑树

分類 算法

13. 红黑树

二叉搜索树的各种操作时间复杂度为\Omicron(h)\Omicron(h)，但是树的高度h不可控，最差的情况为n。
而平衡搜索树能将树的高度控制在\Omicron(lg(n))\Omicron(\lg(n))。
常见的平衡搜索树有：

  • AVL树
  • 红黑树
  • treap （tree + heap，给每个元素随机的priority，从而间接的实现随机插入，使得树的期望高度为\Omicron(lg(n))\Omicron(\lg(n))）
  • B树 （十八章介绍）
    • 2-3-4树

本章重点讨论红黑树，以及习题中出现的AVL树。AVL树较为简单所以先介绍AVL树。

AVL树

AVL树由Adel’son-Vel’skii & Landis 在1962年发明，由他们的名字命名。
比较一般的二叉搜索树，每个结点额外存储它的高度，nil的高度为0，其他节点的高度为Height(x) = max(Height(x->left), Height(x->right)) + 1。每个结点两个孩子的高度差不能超过1。
当右子树的高度比左子树的高度高时，我们称right-heavy（如下图），反之这称left-heavy。

AVL树

AVL树的各种查询操作都和普通二叉搜索树无异，所以我们只需关注会改变树结构的Insert操作和Delete操作。
在一般的Insert或者Delete操作后，结点的高度会变，所以有可能会违反AVL树的性质，这时候我们需要引入一个操作Rotate（旋转）

Rotate

旋转分为两种，左旋（LEFT-ROTATE）和右旋（RIGHT-ROTATE）。下图右测变为左侧的情况称为对x结点左旋，左侧变为右侧的情况称为对y结点做右旋。

Rotate

我们可以发现旋转操作并不会影响二叉搜索树的性质。
旋转前后都会保持α <= x <= β <= y <= γ
下面是左旋的伪代码，右旋的操作和左旋对称，不再赘述。

Rotate

Ref：AVLTree::LeftRotate & AVLTree::RightRotate in AVLTree.h

AVL树平衡调整（ADJUST_FROM(x)）

当Insert或者Delete一个元素后，平衡有可能被破坏，假设x是最底层被破坏性质的节点，而且是right-heavy时（left-heavy是对称的）：

  1. Balance
    • 如果x的右孩子y是平衡的或者right-heavy的（Figure 5）
      • 我们对x做LEFT-ROTATE操作可使其恢复平衡
      • 然后重新计算x和y的高度
    • 如果x的右孩子z是left-heavy的（Figure 6）
      • 我们先对z做RIGHT_ROTATE，然后对x做LEFT-ROTATE，可使其恢复平衡
      • 然后重新计算x，y，z的高度
  2. Loop
    • 重新计算x的高度，并使得x=x->p继续循环，直到根节点
    • 若图中发现某节点不平衡的用1. Balance

AVL树

Ref：AVLTree::AdjustFrom in AVLTree.h

AVL树 Insert

因为插入的节点肯定是叶子节点，所以直接对插入节点调用ADJUST_FROM(x)即可。

Ref：AVLTree::Insert in AVLTree.h

AVL树 Delete

删除操作略为复杂，可能会影响子节点的平衡。

  • 当被删除节点只有一个孩子，或者没有孩子时，被删除节点的孩子不会被应用
    • 这时对删除节点原来的父节点调用ADJUST_FROM(x)即可
  • 当被删除节点有两个孩子时
    • 如果被删除节点右子树的最小节点min的父节点为被删除节点，这时对min调用ADJUST_FROM(x)
    • 其他情况，对min原来的父节点调用ADJUST_FROM(x)

Ref：AVLTree::Delete in AVLTree.h

红黑树

红黑树也是一种平衡二叉树。它在每个节点上增加一个存储位color来表示节点的颜色，节点的颜色为RED或者BLACK。通过对任何一条从根节点到叶子节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，所以是近似于平衡的。
红黑树还定义一种NIL节点，NIL节点是红黑树的叶子结点（外部节点），真实的数据组成树的内部节点（如下图a所示）。
红黑树的具体性质如下：

  1. 每个节点不是红色的就是黑色的
  2. 根节点是黑色的
  3. 每个叶结点（NIL）是黑色的
  4. 如果一个结点是红色的，那么它的两个孩子都是黑色的
  5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，黑色结点的数量相同

为了方便处理，使用一个哨兵来替代NIL结点。对于一颗红黑树T，哨兵T.nil是一个普通结点。它的color为BLACK，用哨兵T.nil替换图a中的所有NIL，这样就形如下图b所示，T.nil的p, left, right, key属性我们并不关心，所以方便起见程序中可以对其值随意设定。

红黑树

为了方便起见，我们在图中省去T.nil，这样就变成了图c的样子。

NULL -> T.nil

红黑树与普通二叉搜索树相比，用T.nil替代了空指针。
所以所有操作中用到空指针的地方，需要换成T.nil。后面不做赘述。

红黑树 Insert

红黑树的插入操作，除了一般的操作外，还需要把插入结点的颜色设为RED。因为插入了一个红色的结点，所以有可能触犯红黑树的一些性质（1,4），所以我们要调用RB-INSERT-FIXUP将其修正。

红黑树Insert

红黑树Insert

RB-INSERT-FIXUP会循环的查看z的父结点是否违反性质4，如果违反，则将其修正。如果修正后仍然有可能违反性质4，则继续循环查看其爷结点。（本文只讨论插入结点的父结点为爷结点的左孩子的情况，右孩子的情况与其对称，不再赘述。）

修正过程有三种情况：

  • Case 1. z的叔结点为红色
  • Case 2. z的叔结点为黑色，且z是父亲的右孩子
  • Case 3. z的叔结点为黑色，且z是父亲的左孩子
    红黑树Insert

上图插入4之后的处理过程。下面我们详细讨论下三种情况的处理方式：

  • Case 1
    这种情况只需改变着色，将父节点和叔结点染成黑色，爷结点染成红色。
    因为爷结点以前是黑色，却染成了红色，如果爷结点的父结点为红色，这时仍会触犯性质4，所以我们将爷结点赋给z，下次循环时再修正它。
    如果z的爷结点为root结点，我们修正后root结点变成了红色，并且让z指向root结点然后跳出了循环。在循环外边我们会将z重新染成黑色，所以保持了性质1。
    红黑树Insert

  • Case 2/3
    当z是父结点的左孩子时，符合Case 3，这时我们只需把爷结点做右旋，然后交换之前父结点和爷结点的颜色。这时局部的根节点颜色没有改变，仍然是黑色，所以整个树都满足了红黑树的特性，无需继续循环。
    红黑树Insert
    当z是父结点的右孩子时，符合Case 2，这时只需要对父结点做左旋，使其变为Case 3的情况。

由上可知，一旦循环进入Case 2或者Case 3，就会结束循环。所以一次插入操作最多只会有两次旋转操作。尽量少的循环操作是非常有益的，因为改变结点颜色并不会影响查找功能，当多线程处理时我们只需给旋转操作加锁。

红黑树 Delete

删除操作比插入操作略微复杂，当删除一个黑色结点，或者删除过程中移动了一个黑色结点时，都有可能破坏红黑树的性质（2,4,5）。

当被删除的结点只有一个孩子，或者没有孩子，这时我们只需关心被删除结点的颜色，如果被删除的结点为红色，则无需修正，如果被删除结点为黑色，则需要从被删除结点的孩子开始修正。

当被删除的结点有两个孩子时，我们会找右子树的最小结点来替代被删除结点的位置和颜色，所以这是我们需要关注这个最小结点的颜色，如果最小结点的颜色为红色，则无需修整，如果这个最小结点为黑色，则需要从最小结点的右孩子开始修正。

红黑树Delete

红黑树Delete

从x开始修正时，有五种情况：

  • Case 0. x为红色
    • 这时23行会将其设为黑色，可直接满足所有红黑树性质
  • Case 1. x的兄弟结点w为红色
  • Case 2. x的兄弟节点w为黑色，且w的两个孩子都是黑色
  • Case 3. x的兄弟节点w为黑色，且w的右孩子为黑色，左孩子有红色
  • Case 4. x的兄弟节点w为黑色，且w的右孩子为红色

红黑树Insert

  • Case 1
    这种情况我们将其转换为Case2/3/4

    1. 设置兄弟节点w为黑色，父结点为红色
    2. 左旋父结点
    3. 重新设置w为x的兄弟结点

  • Case 2
    这种情况将兄弟结点w设置为红色，并且x=x.p，继续循环。
    我们会发现，如果是从Case 1转换到Case 2，那么x.p一定是红色，所以会直接退出循环。

  • Case 3
    这种情况我们将其转换为Case4

    1. 设置兄弟节点w为红色，w的左孩子为黑色
    2. 右旋w结点
    3. 重新设置w为x的兄弟结点

  • Case 4
    这种情况可以做一些修改，然后结束修正

    1. 设置w的颜色为x父结点的颜色
    2. x父结点的颜色设置为黑色
    3. w右孩子的颜色设置为黑色
    4. 左旋x的父结点
    5. 使x指向root结点，从而结束修正

由上可知，一旦循环进入Case 1, Case 3，Case 4，就会结束循环。所以一次插入操作最多只会有三次旋转操作（Case 1 -> Case 3 -> Case 4）。

性质维护:

插入过程中维护性质的分析：

1
2
Case1 转换后，局部的黑高与之前相同
但是由于将局部根节点C从黑色变成红色，所以需要继续考虑C是否违反性质4
1
2
Case2/3 转换后，局部的黑高与之前相同
并且局部根节点B的颜色没有改变，所以直接Done

删除过程中维护性质的分析：

需要修正时，被修正结点x以前的父节点肯定为黑色，x替代了x以前父节点的位置
所以这时这个子树（x为根节点）的黑高减少了1

1
2
3
4
Case1 转换后，ABCDE的黑高都没有变
所以这时仍然是x为根节点的子树黑高少1

根本情况没有变化，变化的只是x的兄弟节点的颜色
1
2
3
4
5
Case2 转换后，以x的父节点c为根节点的子树已经满足红黑树的性质
但是c为根节点的子树的黑高比之前少1

所以令c为新的x，继续调整

1
2
3
4
5
Case3 转换后，ABCDE的黑高都没有变
所以这时仍然是x为根节点的子树黑高少1

根本情况没有变化，变化的只是w的右孩子的颜色

1
2
3
4
5
Case4 转换后，以c为根节点子树满足红黑树性质
并且根节点的颜色没有变化，子树的黑高也没有变化

所以Done

涉及数据结构

点击查看实现

留言與分享

12. 二叉搜索树

分類 算法

12. 二叉搜索树

二叉搜索树支持许多动态集合的操作，包括Search，Insert，Delete，Minimum，Maximum，Successor，Predecessor。所有操作的时间复杂度为\Omicron(h)\Omicron(h)，h为树的高度。

二叉搜索树

二叉搜索树是一个链式存储的二叉树，且具有如下特性：
设x为二叉搜索树中的一个结点。

  • 如果y是x左子树中的一个结点，那么y.key<=x.key。
  • 如果y是x右子树中的一个结点，那么y.key>=x.key。

二叉搜索树

从根节点开始查找，如果查询的k小于根节点的key，则递归查找左子树；如果查询的k大于根节点的key，则递归查找右子树；如果查询的k等于根节点的key，done。

Search

Minimum

从根节点开始沿着left child方向一直找到低。

Minimum

Maximum

从根节点开始沿着right child方向一直找到低。

Maximum

Successor & Predecessor

查询x的下一个节点：

  • 如果x有右孩子，那么x的下一个节点就是右子树的最小值。 
    1
    2
    3
    4
    5
    6
    7
       ○
      / \ 
     ●
    / \ 
       ○
      / \ 
    [○]
  • 若果x没有右孩子，那么x的下一个节点是x的第n个parent，这个parent是第一个符合下图的情况，第n-1个parent 是第n个parent得 left child。 
    1
    2
    3
    4
    5
    6
      [○]
      / \ 
     ○
    / \ 
       ●
      /
  • 如果没有符合这样情况的parent，那么说明x是最大数，没有下一个节点。

Successor

Insert

Insert

上图描述了插入key为13的数据。
从根节点x开始查找。如果待插入数据小于该节点数据，到左子树继续查找，否则到右子树查找，直到找到一个空位置，将数据放入。

Insert

Delete

删除操作的情况较为复杂，有如下几种情况

  1. 待删除节点没有孩子
  2. 待删除节点只有一个孩子，如下图(a) (b)情况
  3. 待删除节点有两个孩子，并且右孩子没有左孩子时，如下图©情况
  4. 待删除节点有两个孩子，并且右孩子有左孩子时，如下图(d)情况

Delete

  1. 当待删除节点没有孩子时：
    • 可以直接删除该节点，并且修改他的父节点，用nil代替他
  2. 当待删除节点只有一个孩子时，如图中 (a) (b) 情况：
    • 可以直接用子节点替换该节点
  3. 当待删除节点有两个孩子时，如图中 © (d) 情况：
    • 思路：用待删除节点z的Successor节点y替代它的位置
    • 情况c，右孩子没有左孩子（y是z的子节点）
      • y替换z，并且接管z的左孩子
    • 情况d，右孩子有左孩子
      • y的右孩子x替换y，并且y接管z的右孩子
      • y替换z，并且接管z的左孩子

Delete
Delete

Tips：当待删除节点有两个孩子时，用待删除节点的Predecessor节点替代它也可以。

涉及数据结构

点击查看实现

留言與分享

11. 散列表（哈希表）

分類 算法

11. 散列表（哈希表）

许多应用都需要一种动态集合，至少支持Insert，Search和Delete的字典操作。
散列表（Hash Table）是实现字典操作的一种有效数据结构。尽管最坏情况下散列表查询一个元素的时间和链表的查询时间相同，为Θ(n)。但是在实际应用中，散列表的查询性能是极好的。在一些合理的假设下，散列表中扎寻一个元素的平均时间能为Ο(1)。

假设某应用需要用到一个动态集合，其中每个元素的KEY都是取自全域U={0, 1, …, m-1}。本章讨论方法都是基于这样的动态集合。

直接寻址表

当KEY的全域U较小时，直接寻址表是一种简单而有效的技术。
为了表示这个动态集合，我们用一个数组作为直接寻址表，记为T[0…m-1]，其中数组的每个位置称为槽，与全域U中的KEY一一对应。
K集合表示实际存在的元素的KEY集合。
槽k指向KEY为k的元素，如果K集合中没有k，那么T[k] = nil。

直接寻址表

散列表

直接寻址表的缺点很明显：

  1. 如果全域U非常大，则计算机无法存储
  2. 如果K集合相对于全域U非常小，那么将非常浪费空间

如果直接寻址表占用的存储空间为Θ(∣U∣)\Theta(|U|)，那么散列表能将存储需求降至Θ(∣K∣)\Theta(|K|)，同时散列表中查找一个元素的时间为\Omicron(1)\Omicron(1)，不过是平均时间。

散列方式不同于直接寻址表的地方是，元素存储在散列表中的位置由散列函数决定，即k元素存储在散列表的h(k)位置。h(k)叫做k的散列值。

散列表T的大小比|U|小很多，所以肯定会有冲突的情况。

冲突

冲突最简单的解决方式是使用链接法，后面还介绍一种开放寻址法。
下图是链接法的图示，当有两个k值映射到了同一个散列值时，将它们保存在一个链表内。

链接法

链接法散列分析

如果要将n个数据存储在m大小的散列表中，我们称α = n/m为装载因子，即散列表的每个槽平均存放的数据。
假设散列函数能等可能的把数据散列到m个槽中，我们称这个假设为简单均匀散列。
这时每个槽存放元素个数的期望值为α。

所以，一次不成功查找的平均时间为Θ(1+α)\Theta(1+\alpha)。（1 表示散列函数消耗的时间）

1
因为每个槽的期望为α，而不成功的情况下，查找的期望时间就是从槽链表的头遍历到链表尾，所以期望时间就是槽链表的长度α。

一次成功查找的平均时间为Θ(1+α)\Theta(1+\alpha)。

1
2
具体证明参考公开课中老师的推理，或者书中推理。
自我理解：一个元素在槽中的位置是等概率随机的(1/α)，而且期望时间为元素在槽中位置的期望。期望位置为(1+2+..+α)*(1/α) = (α+1)/2

散列函数

最好的散列函数便是能达到简单均匀散列。
下面介绍一些的散列函数。其中全域散列能够达到这样的要求。

除法散列

1
h(k) = k mod m

m最好是一个素数，并且不能太接近2或者10的乘方。

乘法散列

1
h(k) = [(a * k) mod 2^w] >> (w − r)

k是w bits的数
m = 2^r
a最好是一个奇数，并且不能太接近2或者10的乘方。

乘法散列

全域散列

随机的选择散列函数，称为全域散列
Example：

1
2
h(k) = [(ak+b) mod p] mod m 
where a and b are random ∈ {0, 1, . . . p−1}, and p is a large prime (> |U|).

证明全域散列为简单均匀散列的过程，参考公开课中老师的推理，或者书中推理。

开放寻址法

  • 无链表，所有的元素都保存在table中
  • 每个槽存储一个元素，m>=n
  • 散列函数为h(k, i)，i从0开始，当有冲突后i++，直到找到一个空的位置，所以散列函数需要有如下性质：
1
2
3
4
5
对同一个KEY做m次探查，能把散列表填满

h : U × {0, 1,...,m − 1} → {0, 1,...,m − 1}

{h(k, 0), h(k, 1), . . . , h(k, m − 1)} == {0, 1,...,m − 1}

删除时，不能直接删除！删除后需要标记此位为删除位。

线性探查

1
h(k, i) = (h1(k) +i) mod m

双重探查

1
2
3
4
h(k, i) =(h1(k) + i·h2(k)) mod m

h2(k) 需要和 m 互为质数
e.g. m = 2^r, h2(k) 永远为奇数

开放寻址法分析

给定一个装载因子α = n/m < 1的开放寻址散列表，并假设是均匀散列的：
对于一次不成功的查找，期望的探查次数至多为1/(1-α)
对于一次成功的查找，期望的探查次数至多为\frac{1}{α}\ln(1/(1-α))

完全散列

基于全域散列，完全没看。。。

涉及数据结构

点击查看实现

留言與分享

作者的圖片

Kein Chan

這是獨立全棧工程師Kein Chan的技術博客
分享一些技術教程,命令備忘(cheat-sheet)等


全棧工程師
資深技術顧問
數據科學家
Hit廣島觀光大使


Tokyo/Macau