标签: 学习笔记 - CheaSim Blog
发表更新2 分钟读完 (大约237个字)

HuggingFace PretrainTokenizer学习笔记

笔记

Transformers==4.0.0

由于每次调用bert等模型都需要使用模型的tokenizer，所以写个笔记，方便自己以及后人查阅，（其实看官方文档也可以，但是英文的看着头疼。有错误也请留言吧。

base : PreTrainedTokenizerBase

作为基类，该类有着所有tokenizer都具有的方法还有属性。

PreTrainedTokenizer

使用multiprocess 加速tokenize

仿照这个就完事了。partial可以固定函数中的参数，简直是专门为多进程准备的。

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
def squad_convert_example_to_features_init(tokenizer_for_convert: PreTrainedTokenizerBase):
    global tokenizer
    tokenizer = tokenizer_for_convert



features = []

threads = min(threads, cpu_count())
with Pool(threads, initializer=squad_convert_example_to_features_init, initargs=				(tokenizer,)) as p:
  annotate_ = partial(
    tokenzier.encode_plus, # batch_encode_plus 不知道为什么不work
    max_seq_length=max_seq_length,
    doc_stride=doc_stride,
    max_query_length=max_query_length,
    padding_strategy=padding_strategy,
    is_training=is_training,
  )
  features = list(
    tqdm(
      p.imap(annotate_, examples, chunksize=32),
      total=len(examples),
      desc="convert squad examples to features",
      disable=not tqdm_enabled,
    )
  )
发表更新学习笔记几秒读完 (大约82个字)

TCP,UDP,Socket学习笔记

Linux自学网络

What is Socket 系统调用

TCP UDP
是否连接 面上连接 面上非连接
传输可靠性 可靠 不可靠
应用场合 传输大量的数据，对可靠性要求较高的场景 传输少量数据，对可靠性要求不高的场景
速度 慢 快
发表更新学习笔记5 分钟读完 (大约793个字)

我是Makefile

我是Makefile

我是makefile而不是makelove。最近学校开了Linux这门课，于是我就开始自学Linux了，看的是《Linux就是这个范儿》。实名制推荐，语言又风趣又实在。

什么是Makefile

作为一名程序员，我们第一个程序大概率是通过vs或者是vc6.0来写的。这些都是IDE集成开发环境，他们帮我们做了很多事情，很多底层的事情。其中比较重要的就是编译这个命令了。如果像我参加acm的，会知道如果经常只是写一个单cpp文件的话，我们只需要使用GCC中的g++命令就可以完成将cpp文件编译成可执行文件，但是如果我们是写一个项目呢？如果我们的项目中有好几个头文件，好几个cpp文件呢？这时候makefile就出现了。

Makefile的作用就是自动化编译，一旦我们写好了makefile文件，只需要一个make命令，整个工程就能自动编译。Makefile定义了一系列的规则，来指定哪些文件需要先编译，哪些文件需要后编译，就像一个shell脚本一样。

IDE是高手的挡泥板，却是新手的遮阳伞。

我在南大的编译原理课件中就看到，他们项目的要求也是要用Makefile来完整的做一个项目的。南大还是南大啊。

Makefile的基本概念

目标、条件和命令

对于Makefile来说，最最重要的就是目标、条件和命令这三大要素。

  • 目标是make要产生的东西或者是要做的事情
  • 条件是用于产生目标所需要的文件
  • 命令是有条件转化为目标的方法

举个例子

1
2
main.o:main.c line.h buffer.h tedef.h
	cc -c -o main.o main.c

main.o就是目标，main.c line.h buffer.h tedef.h就是条件，最下面那句”cc -c -o main.o main.c”就是命令。

all命令就是Makefile的默认目标。

基本语法

Makefile是看成是一种解释型语言，一般解释型语言都是采用“自顶向下”的解释逻辑。

tip:所有命令都是需要以\tab开头的，规定如此

变量

作为一种类似语言的东西，那么变量肯定是少不了啊。Makefile中的变量类似于宏替代，采用的语法。

1
CC := gcc -g

这就定义了一个变量，变量的名称是CC，变量的值是”gcc -g”，我们可以用”$()或者${}”来替代。

自动变量

Makefile中有特殊变量，他们可以自动取用一条规则中目标和条件中的元素，这样就可以节省输入文件名和条件文件名的力气。ps:确实在vim一键编译中我也看到了类似的东西。

并且自动变量不需要加$().

发表更新Linux几秒读完 (大约46个字)

Linux学习笔记

Linux

这个学期上了Linux，顺便做点笔记。 看的书是 《Linux就是这个范儿》 还挺有意思的。

实验(Linux进程管理和通信)

发表更新html几秒读完 (大约10个字)

html5学习笔记

html5学习笔记

功能很强。

发表更新学习笔记5 分钟读完 (大约729个字)

LCA学习笔记

LCA学习笔记

祖先的定义

如果学习树结构就会明白除了根节点以外每个节点都有一个父节点，所以我们定义祖先为父节点的父节点，然后我们给出最近公共祖先的定义

一棵树祖先中到两个点距离最近的节点。

能够解决LCA问题的方式有很多，所以作为一个ACM选手，肯定是我全都要

解决方案

欧拉序

树的欧拉序是对树进行dfs的一种序列，他有两条性质

  • 在每个节点进和出都加入序列
  • 只要到达每一个节点就把他加入序列

那么我们寻找他们的最近公共祖先就可以从第一次出现第一个节点和第一次出现的第二个节点之间节点中深度最大的节点。

HDOJ[2586]

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4+200;
const int maxm = 2e2+10;
int dis[maxn];
int n,m;
struct node{
    int next,to,val;
}G[maxn<<1];
int head[maxn];
int cnt;
vector<int> order;
void init(){
    cnt = 0;
    memset(head,-1,sizeof(head));
    order.clear();
}
void add(int u,int v,int val){
    G[cnt].next = head[u];
    G[cnt].to = v;
    G[cnt].val = val;
    head[u] = cnt++;
}
void dfs(int u,int fa,int val){
    order.pb(u);
    dis[u] = val;
    for(int i=head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v==fa) continue;
        dfs(v,u,val+G[i].val);
        order.pb(v);
    }
}
int find(int p1,int p2){
    int mmin = INF,res;
    if(p1>p2){
        int temp = p1;
        p1 = p2;
        p2 = temp;
    }
    rep(i,p1,p2+1){
        if(dis[order[i]] < mmin){
            mmin = dis[order[i]];
            res = i;
        }
    }
    return res+1;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,0,n-1){
            int u,v,val;
            scanf("%d%d%d",&u,&v,&val);
            add(u,v,val); add(v,u,val);
        }
        dfs(1,1,0);
        int len = order.size();
        rep(i,0,m){
            int x,y; int p1=-1,p2=-1;
            scanf("%d%d",&x,&y);
            rep(j,0,len){
                if(p1==-1&&x==order[j]) p1 = j;
                if(p2==-1&&y==order[j]) p2 = j;
                if(p1!=-1 && p2!=-1) break;
            }
            int lca = find(p1,p2);
            //cout<<dis[lca]<<' '<<dis[x]<<' '<<dis[y]<<endl;
            int ans = dis[x]-dis[lca]+dis[y]-dis[lca];
            printf("%d\n",ans);
        }

    }

    return 0;
}

Trajan算法

首先Trajan是一个离线算法，在一次遍历中把所有询问一次解决，时间复杂度$O(n+q)$。

大佬题解

我也想自己写啊，但是就是不会啊，自己想是不可能自己想的，只要抄抄别人的博客才能维持生活。

  1. 任选择一个点作为根节点，从根节点开始
  2. 遍历该节点的所有子节点，并标记这些子节点$v$已经被访问过
  3. 如果$v$还有子节点，返回2，否则就进入下一步
  4. 合并$v$到$u$。
  5. 寻找与当前点$u$有询问关系的点$v$
  6. 若是$v$已经被访问过了，则可以确定$u$和$v$的最近公共祖先为$v$被合并的父亲节点$fa[u]$。
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
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T,n,cnt;
const int maxn = 1e4+10;
struct node{
    int next,to;
}G[maxn<<1];
int head[maxn],fa[maxn],vis[maxn],ans[maxn];
void init(){
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(fa,0,sizeof(fa));
    memset(vis,0,sizeof(vis));
    rep(i,1,n+1) fa[i] = i;
}
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
int find(int x){
    if(fa[x]!=x) fa[x] = find(fa[x]);
    return fa[x];
}
struct Query{
    int to,id;
    Query(){}
    Query(int _to,int _id){
        to = _to;
        id = _id;
    }
};
vector<Query> query[maxn];
void dfs(int now){
    int u,v;
    vis[now] = 1;
    for(int i=head[now];~i;i=G[i].next){
        v = G[i].to;
        if(vis[v]) continue;
        dfs(v);
        fa[v] = now;
    }
    for(int i = 0;i<query[now].size();i++){
        Query node = query[now][i];
        u = node.to; int id = node.id;
        if(vis[u] == 2){
            ans[find(u)] ++;
        }
    }
    vis[now] = 2;
}
int vvis[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    while(~scanf("%d",&n)){
    memset(head,-1,sizeof(head));
    cnt = 0;
    memset(vis,0,sizeof(vis));
    memset(vvis,0,sizeof(vvis));
    memset(ans,0,sizeof(ans));
    rep(i,1,n+1) query[i].clear();
    rep(i,1,n+1) fa[i] = i;
    int root = 0;
    rep(i,0,n){
        int u,x,v;scanf("%d",&u);
        scanf("%*c%*c%d%*c",&x);
        rep(i,0,x){
            scanf("%d",&v);
            add(u,v);
            vvis[v] = 1;
        }
    }
    rep(i,1,n+1){
        if(vvis[i]==0){
            root = i;
            break;
        }
    }
    int m;scanf("%d",&m);
    char ch;
    rep(i,0,m){
        ch = getchar();
        while(ch!='(') ch = getchar();
        int u,v;scanf("%d%d",&u,&v);
        query[u].push_back(Query(v,i));
        query[v].push_back(Query(u,i));
        while(ch!=')') ch = getchar();
    }
    dfs(root);
    rep(i,1,n+1){
        if(ans[i]){
            printf("%d:%d\n",i,ans[i]);
        }
    }
    }
    return 0;
}

RMQ算法(ST表)

其实这个方法也就是欧拉序加上RMQ，在第一个解决方案中我们使用枚举来寻找他们的LCA，这也导致时间复杂度变成了$O(n^2)$。而寻找固定区间内的最小值是一个很普遍的问题，也就是RMQ。而解决RMQ有很多种$O(logn)$的方法，

  • 线段树、树状数组
  • ST表

他们均可以有效地解决区间最值问题。

例题[hdoj5044]

使用方法为 RMQ+正负tag

详情见我刷的LCA专题训练。

Reference:https://blog.csdn.net/czl_233/article/details/78368927

http://www.cppblog.com/menjitianya/archive/2015/12/10/212447.html

http://www.cnblogs.com/JVxie/p/4854719.html

关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×