这是一个测试doc，测试newstart title的文章。

python中的深拷贝和浅拷贝

一、浅拷贝

定义：浅拷贝只是对另外一个变量的内存地址的拷贝，这两个变量指向同一个内存地址的变量值。

浅拷贝的特点：

• 公用一个值；
• 这两个变量的内存地址一样；
• 对其中一个变量的值改变，另外一个变量的值也会改变；

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

>>> a=[11,22,33]
>>> b=a
>>> id(a)
>>> id(b)
>>> a is b
True
>>> a.append(44)
>>> a
[11, 22, 33, 44]
>>> b
[11, 22, 33, 44]
>>>

二、深拷贝：

定义：一个变量对另外一个变量的值拷贝。

深拷贝的特点：

• 两个变量的内存地址不同；
• 两个变量各有自己的值，且互不影响；
• 对其任意一个变量的值的改变不会影响另外一个；



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

>>> import copy
>>> a=[11,22,33]
>>> b=copy.deepcopy(a)
>>> a
[11, 22, 33]
>>> b
[11, 22, 33]
>>> id(a)
>>> id(b)
>>> a.append(44)
>>> a
[11, 22, 33, 44]
>>> b
[11, 22, 33]
>>>

python中list,set,dict,tuple底层实现细节

1. list

python中的列表的英文名是list，因此很容易和其它语言(C++, Java等)标准库中常见的链表混淆。事实上CPython的列表根本不是列表（可能换成英文理解起来容易些：python中的list不是list）。在CPython中，列表被实现为长度可变的数组。

从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数过分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。

不幸的是，在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。

利用 list.insert方法在任意位置插入一个元素——复杂度O(N)
利用 list.delete或del删除一个元素——复杂度O(N)

python没有数组，有列表，列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这就意味着每次进行增删操作都需要对数组的大小进行重新分配。这样的结构在对列表进行操作时的时间复杂度会很高。为了避免这种情况，这里要引入分配槽的概念，分配槽的大小不等同于列表大小，分配槽大小是指在内存中已经分配了的槽空间数。这样能避免每次列表添加数据都调用分配函数，这样均摊的时间复杂度就会比较低。增长模式为：0，4，8，16，25，35，46，58，72，88……。所以python实现队列并对队列进行操作时，与正常数组实现的队列不大一样（因为我的开发语言是python所以有时会对python一些特性进行分析）

要分清列表大小和分配的槽大小，这很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小，这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。

append()

向列表添加一个整数：l.append(1) 时发生了什么？调用了底层的 C 函数 app1()。

下面是 list_resize() 函数。它会多申请一些内存，避免频繁调用 list_resize() 函数。列表的增长模式为：0，4，8，16，25，35，46，58，72，88……

python的这个值是怎么来的呢
So just checking very quickly, Ruby (1.9.1-p129) appears to use 1.5x when appending to an array, and Python (2.6.2) uses 1.125x plus a constant: (in Objects/listobject.c):
换个说法，每当来了一个新要求的大小（比如插入操作中的原大小+1,或删除操作中原大小-1）：newsize，这时python并不直接对list的空间进行调整。而是作个比较，若新要求的大小在总容量之下，总容量的一半之上则，不进行调整。

现在分配了 4 个用来装列表元素的槽空间，并且第一个空间中为整数 1。如下图显示 l[0] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。

列表追加元素操作的平均复杂度为 O(1)。


继续添加新的元素：l.append(2)。调用 list_resize 函数，参数为 n+1 = 2， 但是因为已经申请了 4 个槽空间，所以不需要再申请内存空间。再添加两个整数的情况也是一样的：l.append(3)，l.append(4)。下图显示了我们现在的情况。


insert()

在列表偏移量 1 的位置插入新元素，整数 5：l.insert(1,5)，内部调用ins1() 函数。


虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 8 个槽空间，但是列表的大小却只是 5。

列表插入操作的平均复杂度为 O(n)。

pop()

取出列表最后一个元素 即l.pop()，调用了 listpop() 函数。在 listpop() 函数中会调用 list_resize 函数，如果取出元素后列表的大小小于分配的槽空间数的一半，将会缩减列表的大小。

列表 pop 操作的平均复杂度为 O(1).


可以看到 pop 操作后槽空间 4 依然指向原先的整数对象，但是最为关键的是现在列表的大小已经变为 4。

继续 pop 一个元素。在 list_resize() 函数中，size – 1 = 4 – 1 = 3 已经小于所分配的槽空间大小的一半，所以缩减分配的槽空间为 6，同时现在列表的大小为 3。

可以看到槽空间 3 和 4 依然指向原先的整数，但是现在列表的大小已经变为 3。

再从缩小来看，当newsize小于allocated/2时，意味着需要缩小空间大小了（节约内存）。
该缩小多少呢，同样是基于上面那个函数。由它计算出一个增量来，在什么基础上增呢？

allocated/2，对就是在这个基础上，因为一旦由于删除操作导致newsize恰好小于allocated/2时，就会执行缩小list空间大小的操作。这样，即节省了内存，又不至于减少内存过少，导致效率降低（想像一下，如果每次小于allocated/2时，就缩小为allocated/2，那么如果对于那么删除后立即执行插入操作效率就很不理想了。）

以上这个策略，可以实现不会过去频繁地调用realloc这个低效率的函数。

对比tuple

列表是python中简单而重要的数据结构 list_sample = [1, 2, 3]

超预分配的量大概只有总量的八分之一，保证不太浪费的情况下，也有线性的摊分复杂度。
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)

当增加或删除都有可能引起allocated的变化，当目前的allocated满足 allocated >= newsize && newsize >= (allocated >> 1) 这个关系时，allocated不变，不然更新分配值 allocated = new_allocated + newsize

由于python列表中的元素可以是任意的对象。 在底层实现上，由于对象大小未知，并不能像数组那样连续排在内存里。python列表维护了一个指针数组，每个指针指向不同的对象， 这也造成了一些弊端，例如列表中对象大小一样的时候就很亏了，浪费空间不说，跟C的数组相比，它离散的对象位置不能很好地利用CPU高速缓存，造成了遍历需要更多的CPU周期。当然也有优点，例如在某个位置insert一个新的元素时，只要挪动部分指针的值就OK了。

一些操作的时间复杂度：
append:O(len(append_str))
insert:O(len(str) + len(insert_str))

tuple与list有什么区别？最重要的区别就是tuple是immutable，而list是mutable，
那么也就是说tuple大小将不会改变，就不用像list那样搞预分配了，更节省内存。

分别遍历list和tuple，跑得的时间是6.925s和6.771s从实测看来，这个结论是不明显的。

list和tuple在c实现上是很相似的，对于元素数量大的时候，都是一个数组指针，指针指向相应的对象，找不到tuple比list快的理由。但对于小对象来说，tuple会有一个对象池，所以小的、重复的使用tuple还有益处的。

为什么要有tuple，还有很多的合理性。实际情况中的确也有不少大小固定的列表结构，例如二维地理坐标等；另外tuple也给元素天然地赋予了只读属性。

认为tuple比list快的人大概是把python的tuple和list类比成C++中的数组和列表了。

dict()

字典是python中最通用的数据结构之一。dict可以将一组唯一的键映射到相应的值。

我们也可以用前面列表推导的方式来创建一个字典。
在遍历字典元素时，有一点需要特别注意。字典里的keys(), values()和items()3个方法的返回值不再是列表，而是视图对象（view objects）。

keys(): 返回dict_keys对象，可以查看字典所有键
values():返回dict_values对象，可以查看字典的所有值
items():返回dict_items对象，可以查看字典所有的{key, value}二元元组。

视图对象可以动态查看字典的内容，因此每次字典发生变化的时候，视图都会相应的改变，见下面这个例子：

视图无需冗余的将所有值都保存在内存中，像列表那样。但你仍然可以获取其长度（使用len）,也可以测试元素是否包含在其中（使用in子句）。当然，视图是迭代的。

实现细节

CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。

Python中所有不可变的内置类型都是可哈希的。可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。

字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).

操作 平均复杂度 平摊最坏情况复杂度
获取元素 O(1) O(n)
修改元素 O(1) O(n)
删除元素 O(1) O(n)
复制 O(n) O(n)
遍历 O(n) O(n)
还有一点很重要，在复制和遍历字典的操作中，最坏的复杂度中的n是字典曾经达到的最大元素数目，而不是当前的元素数目。换句话说，如果一个字典曾经元素个数很多，后来又大大减小了，那么遍历这个字典可能会花费相当长的事件。因此在某些情况下，如果需要频繁的遍历某个词典，那么最好创建一个新的字典对象，而不是仅在旧字典中删除元素。

字典的缺点和替代方案
使用字典的常见陷阱就是，它并不会按照键的添加顺序来保存元素的顺序。在某些情况下，字典的键是连续的，对应的散列值也是连续值（例如整数），那么由于字典的内部实现，元素的实现可能和添加的顺序相同：
但是，如果散列方法不同的其它数据类型，那么字典就不会保存元素顺序。

set()

集合是一种鲁棒性很好的数据结构，当元素顺序的重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，大部分情况下这种数据结构极其有用。

python的内置集合类型有两种：

set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象。
frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。

set里的元素必须是唯一的，不可变的。但是set是可变的，所以set作为set的元素会报错。

实现细节

CPython中集合和字典非常相似。事实上，集合被实现为带有空值的字典，只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。

由于这一点，可以快速的向集合中添加元素、删除元素、检查元素是否存在。平均时间复杂度为O(1),最坏的事件复杂度是O(n)。

bagging和boosting的区别

title: 面试常问问题复习(二)
date: 2019-07-02 23:35:58
tags: 面试
categories: 算法

Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法。即将弱分类器组装成强分类器的方法。

   首先介绍Bootstraping，即自助法：它是一种有放回的抽样方法（可能抽到重复的样本）。

1. Bagging (bootstrap aggregating)

Bagging即套袋法，其算法过程如下：

从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）

每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

2. Boosting

​ 其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。

关于Boosting的两个核心问题：

2.1 在每一轮如何改变训练数据的权值或概率分布？

​ 通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。

2.2 通过什么方式来组合弱分类器？

​ 通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。

而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

3. Bagging，Boosting二者之间的区别

Bagging和Boosting的区别：

1）样本选择上：

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）并行计算：

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

4. 为什么说bagging是减少variance，而boosting是减少bias?

Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。由于，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有，此时可以显著降低variance。若各子模型完全相同，则

，此时不会降低variance。bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。

（用公式可以一目了然：设有i.d.的n个随机变量，方差记为，两两变量之间的相关性为，则的方差为，bagging降低的是第二项，random forest是同时降低两项。详见ESL p588公式15.1）

boosting从优化角度来看，是用forward-stagewise这种贪心法去最小化损失函数。例如，常见的AdaBoost即等价于用这种方法最小化exponential loss：。所谓forward-stagewise，就是在迭代的第n步，求解新的子模型f(x)及步长a（或者叫组合系数），来最小化，这里是前n-1步得到的子模型的和。因此boosting是在sequential地最小化损失函数，其bias自然逐步下降。但由于是采取这种sequential、adaptive的策略，各子模型之间是强相关的，于是子模型之和并不能显著降低variance。所以说boosting主要还是靠降低bias来提升预测精度。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment