四方.io

大数据技术之ClickHouse | 慵懒的像一只猫 (gitee.io) ClickHouse学习笔记（一）邋遢的流浪剑客的博客-CSDN博客 分析型数据库追求的就是查询速度，一些地方不能类比以前所学的那些关系型数据库 1 MergeTree引擎建表 1234567891011121314CREATE TABLE [IF NOT EXISTS] [db.]table_name [ON CLUSTER cluster]( name1 [type1] [DEFAULT|MATERIALIZED|ALIAS expr1] [TTL expr1], name2 [type2] [DEFAULT|MATERIALIZED|ALIAS expr2] [TTL expr2], ... INDEX index_name1 expr1 TYPE type1(...) GRANULARITY value1, INDEX index_name2 expr2 TYPE type2(...) GRANULARITY value2) ENGINE = MergeTree() # ...

1、dfs树 （一）无向图对于一个无向图，若其连通，那么在经过dfs后，被访问的边数为n-1条，称为树边，剩余的边称为回边。 结论1：回边必然连接了一个结点与其祖先。 结论2：树边 uv 是桥当且仅当此时没有回边跨越它，回边一定不是桥。 找桥算法可以由传统的low[u]实现。我们也可以——用 dp[u] 来定义跨越点 u 和他的父节点的回边的数量。然后：$dp[u] = (从u点开始的向上的回边) - (从u点开始向下的回边) + \sum dp[v] $，v是u的子节点.当且仅当dp[u] = 0时连接u及其父节点的边是桥。 结论3：给所有的边定向，生成有向图。如果原图有桥存在，那么新图不可能强连通（如果uv是桥且我们将其定向为 u → v，那么现在就不存在由v到u的边）。如果原图无桥（也就是任意树边都被至少一条回边跨过），那么使树边向下、回边向上，则****任意节点都可以回到根节点****，从而新图必然强连通。 结论4：回边u-v的两端构成了一个环，环的大小为deep[u]-deep[v]+1。任何环至少包含一条回边，因此可以利用此性质处理边双连通分量。对于包 ...

1、桶桶其实就是一个容器，种类不限。大多数时候，“开桶”指的是在每个位置或每个节点下建立一个容器，由于容器的内存为动态，在对时空复杂度分摊的正确评估下，可以存放临时数据。例如“天天爱跑步”中在每个节点建立两个vector来储存差分值。（准确地说，节点通过一个索引，通常是自己的编号，来指向一个预先开好的容器数组） 树上桶合并：假设桶的类型为vector，初始存放每个节点的点权，现在希望将桶从叶子全部合并至根节点。假设节点v1,v2…vk是u的子节点，那么把桶合并到u上时，只需要将u与vi一个个合并即可，具体操作为：遍历较小的桶，将所有元素压到较大的桶，然后让u的索引指向较大的桶。这样的合并过程，总复杂度为$O(nlogn)$，证明如下：对较小桶而言，合并后的新桶大小至少为自己的两倍，换而言之，对一个元素执行取出和压入操作，新桶大小必然大于等于旧桶的两倍，这意味着一个元素最多被执行logn次该操作。 分块其实就是开$sqrt(n)$个大小为$sqrt(n)$的桶，单独维护桶内信息，支持对桶内信息的暴力修改（每次操作最多只暴力修改两个桶）。这启示我们可以某一类信息单独维护。 例题：查询以某一 ...

参考笔记：https://www.jianshu.com/c/f627e74e6ff3 1.2复习题 网络由什么和什么什么组成 互联网是什么 最大的互联网 internet与Internet的区别 ISP三层结构 网络边缘与网络核心 因特网服务提供者ISP(Internet Service Provider) 个人或组织向ISP缴纳费用以得到IP地址。我国主要的SP是我们大家都比较熟悉的中国电信、中国联通和中国移动这三大电信运营商。 1.3复习题 电路交换。电路交换存在的缺陷 分组交换。分组交换如何解决缺陷 两/三种交换方式的通信过程（能看懂图） 两/三种交换方式的主要优缺点 两个机器A B的数据传输需要建立通路。在电路交换机组成的电信网(无向图)中，一条通路的建立会使该路径上的边（中继线）被长期占据（打电话）。 但试想这样的情况：当用户在输入和编辑一份待传输的文件时，用户所尚用的通信资源暂时未被利用，该通信资源池不能被其他用户利用，宝贵的通信线路资源白白被浪费了。 电路交换的传输效率往往很低，所以计算机通常采用的是分组交换，而不是线路交换 1.4复习题 ...

最短路（一）DijkstraDijkstra算法可求任一点到定点的最短路，适于有向图和无向图（对有向图有用的就一定对无向图有用），其边权不可为负（一条边都不行）。数组vis标记访问过的点，数组dis记录结果，一般初始化为无穷。dis[起点]要提前赋值，以保证在for循环中第一个目标点是起点。 对于稀疏图（即边的数量E远小于n*(n-1)），Dijkstra算法可以优化至(V+E)logV，称为堆优化。具体就是用优先队列，直接弹出待选结点中d[x]最小的点。普通二叉堆优化后的复杂度为O((V+E)logV)，而若使用斐波那契堆，由于压入操作为O(1)，可将复杂度优化至O(E+VlogV)（但是过程复杂，比赛中不使用）。在稀疏图中，使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；而在稠密图中，这时候使用暴力$O(n^2)$做法较二叉堆实现更优。 当边权均为一常数时，可用bfs搜寻；当边权为0和1时，可用双端队列+bfs搜寻。如果要还原路径，这时需要引入父点数组。由于除了起点外每个点都有唯一的父结点，这时所有路径便形成了一棵树，称最短路径树。在这 ...

ServerMuxServeMux详解 - 掘金 (juejin.cn) 03.4. Go 的 http 包详解 | 第三章. Web 基础 |《Go Web 编程》 以下实现了一个http服务。编译运行后访问http://127.0.0.1:8080/。 12345678910func main() { http.HandleFunc("/", handler) log.Fatal(http.ListenAndServe("localhost:8080", nil)) // 启动服务 // ListenAndServe always returns a non-nil error.}func handler(w http.ResponseWriter, r *http.Request) { // 写入回应(实现了io.Writer) fmt.Fprintf(w, "hello world") } http包中，Handler是一个接口，规定了作为处理器需要有ServeHTT ...

第三章go的特点 一次编码 一次编译 不需要运行环境 没有虚拟化损失 不需要自行处理 GC 面向对象 非常易用的并发能力 C X √ X √ X X X C++ X √ X √ X √ X Java √ X √ X √ √ X JavaScript √ O √ X √ √ X Go √ X √ √ √ √ √ 查看从代码到SSA中间码的整个过程1$env:GOSSAFUNC="main" 1export GOSSAFUNC=main 1go build 查看 Plan9 汇编代码1go build -gcflags -S main.go 使用 Modules1go get github.com/Jeffail/tunny 1go get github.com/Jeffail/tunny@0.1.3 #指定版本 使用goproxy.cn作为代理1go env -w GOPROXY=https://goproxy.cn,direct go.mod 文件追加1replace github.com/Jeffail/tunny ...

Session 25 锁上一章介绍了事务并发执行时可能带来的各种问题，并发事务访问相同记录的情况大致可以划分为3种： （1）读-读情况：即并发事务相继读取相同的记录。   读取操作本身不会对记录有任何影响，并不会引起什么问题，所以允许这种情况的发生。 （2）写-写情况：即并发事务相继对相同的记录做出改动。   在这种情况下会发生脏写的问题，在多个未提交事务相继对一条记录做改动时，需要让它们排队执行，这个排队的过程其实是通过锁来实现的。 当一个事务想对这条记录做改动时，首先会看看内存中有没有与这条记录关联的锁结构，当没有的时候就会在内存中生成一个锁结构与之关联。（对一条记录加锁的本质就是在内存中创建一个锁结构与之关联） trx信息：代表这个锁结构是哪个事务生成的。 is_waiting：代表当前事务是否在等待。 在事务T1提交之前，另一个事务T2也想对该记录做改动，那么先去看看有没有锁结构与这条记录关联，发现有一个锁结构与之关联后，然后也生成了一个锁结构与这条记录关联，不过锁结构的is_waiting属性值为true，表示当前事务需要等待，我们把这个场景就称之为获取锁失败，或者加锁 ...

Session 24 事务的隔离级别与MVCC每个客户端与服务器连接上之后，就可以称之为一个会话（Session），每个客户端都可以在自己的会话中向服务器发出请求语句。 在事务简介的章节中我们说过事务有一个称之为隔离性的特性，理论上在某个事务对某个数据进行访问时，其他事务应该进行排队，当该事务提交之后，其他事务才可以继续访问这个数据。但是这样子的话对性能影响太大，我们既想保持事务的隔离性，又想让服务器在处理访问同一数据的多个事务时性能尽量高些，鱼和熊掌不可得兼，舍一部分隔离性而取性能者也。 事务并发执行遇到的问题 我们先得看一下访问相同数据的事务在不保证串行执行的情况下，可能会出现哪些问题： ==脏写==（Dirty Write） 如果一个事务修改了另一个未提交事务修改过的数据，那就意味着发生了脏写，示意图如下： 那么Session A中的更新也将不复存在，这种现象就称之为脏写。 ==脏读==（Dirty Read） 如果一个事务读到了另一个未提交事务修改过的数据，那就意味着发生了脏读，示意图如下： & ...

待完成