学海泛舟

发表于 | 分类于 |

什么是B-树

B-树可以看作二叉搜索树的推广，不同之处在于B-树的结点可以有很多孩子，也就是相同的结点数，B-树比起一般的二叉树深度会小很多。

为什么要B-树

B-树是为磁盘或者其他直接存取的辅助存储设备而设计的一种平衡搜索树。B-数在降低磁盘I/O操作数方面要好一些，所以许多数据库系统使用B-树或者B-树的变种来存储信息。

在典型的B-树应用中，所处理的数据量非常大，无法全部装入主存中，又因为磁盘的操作要远远慢于主存的操作，所以，B-树的运行时间主要是DISK-READ和DISK-WRITE的次数决定的。

为了让这些操作能读或者写尽可能多的信息，所以一个B-树结点通常和一个完整磁盘页一样大。

B-树的性质

一般来说，B-树为每个关键字存放一个指针，这个指针指向存放这个关键字对应的卫星数据的磁盘页。

  1. 每个结点x有一下属性：

    a. x.n代表存储的关键字的个数

    b. x.n个关键字x.key1…x.keyn，非降序存放

    c. x.leaf指示x是否为叶结点

  2. 每个内部结点x包含x.n+1个指向孩子的指针x.c1…x.c(n+1)，叶子结点没有孩子

  3. 所有叶结点都是相同高度的

  4. 每个结点包含的关键字个数存在一个上界和下界，用B-树的最小度数整数t（>=2）表示

    a. 除根结点外，每个结点至少要有t-1个关键字

    b. 每个结点至多有2t-1个关键字

###B-树的高度

对于任意一棵包含n个关键字、高度为h，最小度数>=2的B-树，有

$$h \le \log_t \frac{n+1}{2}$$

学海泛舟

发表于 | 分类于 |

图像分类的难点

  1. 视角变化
  2. 光照条件
  3. 形变
  4. 遮挡
  5. 背景干扰
  6. 类内差异

由于几乎不存在硬编码算法来直接识别图片内容。所以常常采用数据驱动的方式来解决问题。通过收集数据集和标签，利用机器学习的方式来训练一个分类器，利用训练所得的分类器来分类图片。

最近邻分类器

最近邻的思想非常朴素，就是拿测试集和训练集中的每幅图像进行比较，找到距离最近的，测试数据就是哪幅图像所对应的那个类。由此又衍生出找最近的k幅图像的k-NN分类器。很容易发现，这个分类的效果的好坏和如何定义距离和k的选取密切相关。像这些在设计分类器就必须定好的东西，就被成为超参数。

超参数的选取直接关系着算法效果的好坏，对超参数的调优是十分关键的。直接选用测试集对超参数调优，看似不错，实则是不可取的。因为这会造成算法在实际运用时的效果远远小于测试的，这种情况被称为对测试集的过拟合。超参数的选取要注意泛化性。

测试数据集只使用一次，即在训练完成后评价最终的模型时使用。

通常在训练集中取出一部分数据用来调优，也就是所谓的验证集。

在数据集比较小的时候，也可以采用交叉验证。所谓交叉验证就是将训练集分为几份，让它们轮流充当验证集，剩下的作为训练集，对最后的结果进行平均。当然这样的缺点是时间的耗费大大增加了。

最近邻分类有着明显的缺点：

  1. 测试过程要耗费大量的时间
  2. 在高维上表现不尽如人意，所以一般很少应用于图像领域

线性分类器

$ f(x, W) = Wx + b $

其中$W$为权重，$b$为偏差向量

将数据变为一个一维列向量，通过权重和偏差，得到各个类的评估得分，以此完成分类。

学海泛舟

发表于 | 分类于 |

这篇文章主要是简单介绍一下python numpy的基本操作和与numpy相关的一些科学计算方面的东西。

#numpy

numpy相较于python的原生数组，有两个主要的优势，一是numpy的数组运算是经过优化的，其运算速度是远远快于原生数组的，二是很多数组相关的操作用numpy要比原生数组要简洁。

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
import numpy as np
#创建一个数组
a = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
#取数组中的元素
print(a[0, 1])
#切片操作
b = a[:2, 1:3]
print(b)
#以c中元素作为下标取a中的元素
c = np.array([1, 0, 2])
print(a[np.arange(3), c])
#矩阵乘法
v = np.array([9,10])
w = np.array([11, 12])
print (v.dot(w))
print (np.dot(v, w))
#转置
print(v.T)
#广播
x = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]])
v = np.array([1, 0, 1])
y = x + v
print(y)

numpy中的广播是一个十分重要的概念。

首先，不是所有函数都支持广播机制的，只有全局函数才支持广播机制的。

其次，广播机制要遵守几个规则：

  1. 如果数组的秩不同，就使用1来将秩较小的数组进行扩展，直到两者的秩相同（这里的秩指的是数组的维数）
  2. 如果两个数组在某个维度上的长度相同，或者其中一个数组在维度的长度为1，那么这两个数组就是相容的。如果它们在所有维度都是相容的，那么就能使用广播机制了。

科学计算相关的其他内容

图像操作

1
2
3
4
5
6
from scipy.misc import imread, imsave, imresize
img = imread('34683993_p0.jpg')
print(img.dtype, img.shape)
img_tinted = img * [1, 0.95, 0.9]
img_tinted = imresize(img_tinted, (300, 300))
imsave('34683993_p0.jpg_tinted.jpg', img_tinted)

绘图

1
2
3
4
5
6
7
8
9
10
11
12
import numpy as np
import matplotlib.pyplot as plt
x = np.arange(0, 3 * np.pi, 0.1)
y_sin = np.sin(x)
y_cos = np.cos(x)
plt.subplot(2, 1, 1)
plt.plot(x, y_sin)
plt.title('Sine')
plt.subplot(2, 1, 2)
plt.plot(x, y_cos)
plt.title('Cosine')
plt.show()

绘图相关的函数和matlab是十分相似的。

学海泛舟

发表于 | 分类于 |

这篇文章主要是简单了解一下python中的闭包。

闭包包含自由（未绑定到特定对象）变量；这些变量不是在这个代码块内或者任何全局上下文中定义的，而是在定义代码块的环境中定义（局部变量）。

​ 百度百科

简单的说，函数可以引用自己所处作用域的自由变量，并且被引用的自由变量将与这个函数共同存在。

1
2
3
4
5
6
7
8
def test():
    i = '你好'
    def testtest(name):
        print(i+','+name)
    return testtest
mytest = test()
mytest('小明')

其结果为 你好,小明，可以看到test中i的生命周期得到了延长。

这种内部函数访问外部函数变量，就是闭包。

但是在使用闭包的过程中要特别注意谨慎使用外部函数的循环变量，否则容易出现错误。

1
2
3
4
5
6
7
8
9
def test():
    arr = []
    for i in range(1,3):
        arr.append(lambda x: x+i)
    return arr
ans = test()
print(ans[0](1))
print(ans[1](1))

其结果均为3，这是因为函数没有立即执行，而是到了ans[0](1)时才调用，而这个时候i已经变成了2，所以最终这两个答案都是3。

学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

给定一棵有根树，开始时所有点都没有水，有三种操作，一种是清空某个结点和它所有祖先的水，一种是向某个结点和它所有的后代注水，一种是询问某个结点有没有水。

分析

注意到一个结论如果有个点没有水，那么它的祖先也一定没有水。那么清空操作只要在结点处标记一下清空即可，查询时，查找结点极其后代中是否有标记，就能知道结点是否有水了。采用dfs序+线段树，每个结点都存储该区间是否都水。注水就区间修改，清空就只将该结点处改为0。

参考代码

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
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
const int maxn = 5e5+10;
vector<int> v[maxn];
int fa[maxn];
int jinru[maxn];
int chuqu[maxn];
int tot;
void dfs(int root,int pre){
    fa[root]=pre;
    jinru[root]=tot++;
    for(int i=0;i<v[root].size();++i){
        if(v[root][i]!=pre) dfs(v[root][i],root);
    }
    chuqu[root]=tot++;
}
int a[(maxn<<3)];
int lazy[(maxn<<3)];
void build(int root,int l,int r){
    lazy[root]=0;
    if(l==r){
        a[root]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    a[root]=a[root<<1]*a[root<<1|1];
}
void PushDown(int root){
    if(lazy[root]==1){
        lazy[root]=0;
        a[root<<1]=1;
        a[root<<1|1]=1;
        lazy[root<<1]=1;
        lazy[root<<1|1]=1;
    }
}
void PushUp(int root){
    a[root]=a[root<<1]*a[root<<1|1];
}
void update(int root,int l,int r,int L,int R,int zhi){
    if(L<=l&&R>=r){
        lazy[root]=zhi;
        a[root]=zhi;
        return ;
    }
    PushDown(root);
    int mid=(l+r)>>1;
    if(L<=mid){
        update(root<<1,l,mid,L,R,zhi);
    }
    if(R>mid){
        update(root<<1|1,mid+1,r,L,R,zhi);
    }
    PushUp(root);
}
int query(int root,int l,int r,int L,int R){
    if(L<=l&&R>=r) return a[root];
    int mid=(l+r)>>1;
    PushDown(root);
    int ans=1;
    if(L<=mid) ans*=query(root<<1,l,mid,L,R);
    if(R>mid) ans*=query(root<<1|1,mid+1,r,L,R);
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int q;
    scanf("%d",&q);
    tot=1;
    dfs(1,0);
    build(1,1,n<<1);
    while(q--){
        int c,v;
        scanf("%d %d",&c,&v);
        if(c==1){
            int tmp=query(1,1,n<<1,jinru[v],chuqu[v]);
            if(tmp==0&&v!=1){
                update(1,1,n<<1,jinru[fa[v]],jinru[fa[v]],0);
                update(1,1,n<<1,chuqu[fa[v]],chuqu[fa[v]],0);
            }
            update(1,1,n<<1,jinru[v],chuqu[v],1);
        } else if(c==2){
            update(1,1,n<<1,jinru[v],jinru[v],0);
            update(1,1,n<<1,chuqu[v],chuqu[v],0);
        } else {
            int ans=query(1,1,n<<1,jinru[v],chuqu[v]);
            printf("%d\n",ans);
        }
    }
    return 0;
}