NX の 博客

相关链接🎶 学员手册：【大数据专场 学习资料三】第四届字节跳动青训营 - 掘金 概述 大数据与 OLAP 的演进 廉价机器：可以做到成本与性能的线性增长 存算分离：存储节点和计算节点可以不在一台物理机上 预计算：用空间换时间 Presto 设计思想 小结 Presto 架构原理与优化介绍 基础概念介绍 服务相关 黄色：数据源 绿色（深和浅）：服务 蓝色：用户 数据源相关 Query 相关 数据传输相关 核心组件架构介绍 服务发现 通信协议 代表了我想要关闭（当前手上还有东西，设置为此状态时，不会再安排新 task ，设定一个超时时间，过后关闭） 小结 Presto 重要机制 多租户资源管理 Case 介绍 Resource Group （这里在解读代码） 多租户下的任务调度 物理计划生成 Stage 调度 Task 调度 实际使用中 90% 都是第3种 Split 调度 内存计算 Pipeline 化数据处理 反压机制 多数据源联邦查询 小结 性能优化实战 常用性能分析工具 阿里巴巴开源的一个线上查询工具 万物皆可火焰图（ 具体案例分析 Case 1 每一段上去都有一个 copy 方法 说白了就是这个函数有问题 Case 2 某些情况下，正则表达式的匹配是非常耗时的 字节内部优化实践 Multi Coordinator History Server Support Remote UDF Raptor X 的多级缓存 小结

相关链接🎶 学员手册：【大数据专场 学习资料二】第四届字节跳动青训营 讲真，这节课大概都听不懂（ Shuffle 概述 MapReduce 概述 Map 三张 gif Shuffle 本质：通过哈希区别不同类型数据 Reduce 为什么 Shuffle 对性能非常重要 总结 批式计算的发展流程 Shuffle 算子 算子分类与应用 这个例子中，把一个 txt 按行分割，然后统计每个单词的个数 reduceByKey 产生 Shuffle，做的是 A + B 的操作（有很多机器） 最后 collect，返回结果 Spark 中对 Shuffle 的抽象 - 宽依赖、窄依赖 Shuffle Dependency Shuffle 过程 Hash Shuffle 写数据 写数据优化 把每个 Partition 映射到某个文件的片段 Sort Shuffle 写数据 每个 task 只用一个文件存储真实数据 读数据 Shuffle 过程的触发流程 前 5 行只是记录计算过程，在 Collect 的时候才会进行计算 Shuffle Handle 的创建 Shuttle Handed 与 Shuffle Writer 的对应关系 Writer 实现 BypassMergeShuffleWriter 仅适用于Partition较少的情况 UnsafeShuffleWriter SortShuffleWriter Reader 实现 网络时序图 ShuffleBlockFetchIterator External Shuffle Ser ...

相关链接🎶 学员手册：【大数据专场 学习资料二】第四届字节跳动青训营 大数据处理引擎 Spark 大数据处理技术栈 常见大数据处理链路 开源大数据处理引擎 什么是 Spark？ 用于大规模数据处理的统一分析引擎 Spark 版本演进 Spark 生态 & 特点 Spark 特点 多语言支持 丰富数据源 丰富的 API/算子 Spark 运行架构 Spark 下载编译 Spark 包概览 Spark 提交命令 提交一个简单任务 Spark UI Spark 性能 benchmark SparkCore 原理解析 SparkCore 什么是 RDD 一个容错的可以并行执行的分布式处理集 如何创建 RDD RDD 算子 RDD 依赖 RDD 执行流程 调度器 内存管理 多任务间内存分配 Shuffle SortShuffleManager External Shuffle Service SparkSQL 原理解析 这里就是第一节课的内容了 Catalyst 优化器 RBO 语法树遍历->模式匹配->等价转换 CBO Adaptive Query Excution Coalescing Shuffle Partition 先设置比较大的 Partition 个数，然后后面再动态合并 Switch Join Strategies Optimizing Skew Joins Runtime Filter 这个和第一课里面讲的一样 Bloom Runtime Filter Codgen ...

相关链接🎶 学员手册：【大数据专场 学习资料二】第四届字节跳动青训营https://juejin.cn/post/7122754431371706404#heading-36) 概述 流式计算 VS 批式计算 资源模型：批式跑完资源就释放了，流式是必须一直都占用的 批处理 T+1：加 1 天 处理时间窗口 处理时间 VS 时间时间 事件事件窗口 有些数据会有延迟 Watermark 小结 （感觉有点没听懂😂） Watermark 什么是 Watermark 如何产生 Watermark 如何传递 Watermark 每个算子根据上游输入的最小值 如何通过 Flink UI 观察 Watermark 典型问题一 典型问题二 部分的分区断流（故障、晚上业务少等）的问题 典型问题三 Window Window 分类 Window 使用 滚动窗口 滑动窗口 会话窗口 迟到数据 增量 VS 全量计算 EMIT 触发 小结 优化机制 Mini-batch 优化 让算子攒一小批，然后再处理，避免高频读写 但是这样也会增加延迟，所以实际上会进行全局的协调 倾斜优化 local-global Distinct 计算状态复用 （听得不是很懂，还是建议看原视频） Pane 优化 在滑动窗口里，每一条数据可能属于多个窗口 小结 案例分析 （基于真实场景的抽象） 需求一 需求二 课程总结

相关链接🎶 学员手册：【大数据专场 学习资料一】第四届字节跳动青训营 - 掘金 数据流和动态表 随处可见的流式数据 传统 SQL 和流处理 数据流和动态图转换 先转换为动态表，再执行 SQL，再转为流 连续查询 查询产生仅追加数据的动态表 两个连续查询对比 Retract 消息的产生 对之前的结果进行回撤 状态 数据流和动态表转换回顾 不同数据处理保证的语义 Exactly-Once 和 Checkpoint 状态快照与恢复 一个源源不断的数字流，分布对奇数和偶数进行累加和 现在要备份，需要记录现在消费的位点（Source 算子）与目前的和（两个 sum 算子） 保存这 3 个状态，发生故障后就可以通过最近的保存点恢复 制作快照的时间点 不能在任意时间点保存，必须等待下游数据全部处理完成 因为恢复时上游不会重复下发数据，而下游可能在快照时还没处理或收到 可见这种方法需要停止业务消费，有没有更好的方法？ Chandy - Lamport 算法 更复杂一点的场景，有两个数据流并行处理 快照制作的开始 Source 收到 JM 发送的 Checkpoint Barrier 标识 Source 算子的处理 Source 短暂地停止处理，保存当前状态，然后继续向下游传递 Checkpoint Barrier 标识，然后就恢复数据的处理，不需要管下游 Barrier Alignment 对于下游节点，两个 Source 的 Checkpoint Barrier 不一定是同时到的（例如对于这里的 Sum even，Source 1 的 Checkpo ...

相关链接🎶 学员手册：【大数据专场 学习资料一】第四届字节跳动青训营 - 掘金 Flink 概述 Apache Flink 的诞生背景 什么是大数据 大数据计算架构发展历史 Hadoop 那里就是谷歌发的 3 篇论文，GFS， Map-Reduce 等 为什么需要流式计算 简单地说，就是业内需要流式计算，然后就有了 Flink 为什么 Apache Flink 会脱颖而出 流式计算引擎发展历程 流式计算引擎对比 At Least Once ：能保证数据至少能被处理一次 At Most Once ：数据最多被处理一次（可能没处理到） StateFul：不再依赖外部系统存储状态 Why Flink 牛啤一体可还行（ Apache Flink 开源生态 最左边：Flink 可以高性能地使用很多存储引擎 中间框：内部架构设计，下面会说 下面：部署模式 上面：基于 Flink 的其他框架 Flink 整体架构 Flink 分层架构 最上面： SDK SQL 相关 API Stream 相关 API python 的 API 中间：执行引擎层 Flink 总体架构 这张图很重要，必须要熟悉 首先你的代码会在客户端转为一张 DAG 图（逻辑执行图），然后发给 JM ，JM 转为物理执行图，并且根据这个图把不同的 task 调度到各个的 TM 中执行 slot：插槽 Flink 作业示例 这个示例就是一个 hello world 类示例 每个 Slot 是单独的一个线程在执行 Flink 如何做到流批一体 为什么需要流批一体 流批一体的挑战 ...

相关链接🎶 学员手册：【大数据专场 学习资料一】第四届字节跳动青训营 - 掘金 大数据体系和 SQL 大数据体系 其中消息队列用于解耦存储与计算，本次青训营会从分析引擎开始展开，然后是存储、消息队列与资源调度 那么，为什么要把 SQL 优化器放在第一节课讲呢？ 首先，SQL 是非常流行的，而且简单，包括数据分析师和挖掘师都在用，他们可能不会使用 Python之类的通用语言，但是他们可以很方便地使用一条 SQL 去处理数据，得到他们想要的结果 并且，SQL 是很多系统都支持的接口，而且 SQL 已经成为了大数据方面的通用接口。很多分析引擎一开始并不支持 SQL ，但现在都渐渐地提供了 SQL 接口 也就是说， One SQL rules big data all （通过 SQL 处理所有的大数据） 所以 SQL 在大数据中是非常重要的，下面将介绍 SQL 的处理流程 SQL 的处理流程 首先，先通过 Parser 变成抽象语法树（Abstract Syntax Tree，AST），之后通过 Analyzer 变成逻辑计划（Logical Plan），再通过 Optimizer 变成物理计划（Physical Plan），最后交给 Executor 来执行 Parser 死去的编译原理突然开始攻击我（bushi Analyzer 逻辑地：只是说明了要干什么，但是没有确定用什么算法实现（例如排序） Optimizer Executor 小结 常规的查询优化器 查询优化器分类 两种分类方法 按遍历树的方向分 按优化方法分 RBO（基于规则的优化） 这些 ...

启发式搜索 还是从最简单的走网格开始吧，现在有一个包含障碍的方形网格，你需要求出从 S 点到 T 点的最短步数 很简单，不是吗？使用 BFS 就可以办到 但是，BFS 是一种盲目的搜索技术，它只会不断遍历周围的点，如果 T 点在 S 点的右上方，作为人的话肯定会把更多的精力放在往右上方搜索，一般这样能更快地找到路径，但是 BFS 并没有这种智能，那么能不能把这种智能交给程序呢？这就是启发式搜索，A*算法是比较简单的一种，可以认为是BFS和贪心的结合 尝试贪心思想 运用贪心法可进行如下处理：在处理队列中的点时，始终选取与终点的曼哈顿距离最短的点优先处理，这样循环往复，就能不断向终点逼近，而那些南辕北辙的点自然会在队列中被挤到后面去，不会浪费搜索资源 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#include <bits/stdc++.h>using namespace std;const int M = 8, N = 10, INF = 0x3f3f3f3f;const int dx[] = {0, 1, 0, -1};const int dy[] = {1, 0, -1, 0} ...

简述 康托展开可以求出一个全排列在所有全排列中的字典序 也可以逆操作，通过元素个数和字典序，求出第 xxx 个全排序状态 例如，对于 {1,2,3} 3 个数的全排列，共有 3!=63!=63!=6 种状态 1234560: 1 2 31: 1 3 22: 2 1 33: 2 3 14: 3 1 25: 3 2 1 使用康托展开可以通过 2 3 1 求得值 3 ，逆康托展开可以通过值 4 来求得 3 1 2 核心算法 X=A1⋅(n−1)!+A2⋅(n−2)!+…+An⋅0!X = A_{1}\cdot(n-1)! + A_{2}\cdot(n-2)! + \ldots + A_{n}\cdot0! X=A1​⋅(n−1)!+A2​⋅(n−2)!+…+An​⋅0! XXX ：康托展开值，指此排列前面还有多少种排列 nnn ：总共有多少数字 aia_{i}ai​ ：第 iii 位上的数字 AiA_{i}Ai​ ：在第 iii 位后面的数中，比 aia_{i}ai​ 小的数的个数 这个式子鄙人为了理解方便，稍微改动了一下 举例 康托展开 例一 求 2143 是 {1,2,3,4} 的全排列中第几大的数 第一位是 2 ，后面比 2 小的有 1 个数，故写成 1×3!1\times3!1×3! 第二位是 1 ，后面没有比 1 小的数，故写成 0×2!0\times2!0×2! 第三位是 4 ，后面比 4 小的有 1 个数，故写成 1×1!1\times1!1×1! 第四位是 3 ，后面没有数了，故写成 0×0!0\times0!0×0 ...

经典题目：八数码 广搜处理的对象不仅可以是一个数，还可以是一种状态，这里最经典的题目就是八数码 先来道基础的题目 点击查看题目 题目描述 在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。 输入格式 输入初始状态，一行九个数字，空格用0表示 输出格式 只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据) 样例 #1 样例输入 #1 1283104765 样例输出 #1 14 对于这道题，我们需要从给定的初始状态变化到目标状态，当我们在搜索的时候，可以直接将生成的子状态加入到队列中，每次再取出状态来处理，这就是所谓的状态图搜索 确定了思路，就有两个主要问题 怎么表示状态 怎么去重 朴素做法 因为洛谷上的这道题比较简单，对于第一个问题，可以直接将 3x3 的数组转换为一个 9 位的数字，使用 int 来保存 而去重的话，可以直接借助于 STL 中的 map 或者 set 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 ...

前言 搜索一般来说主要分两种：深度优先搜索（DFS）和广度优先搜索（BFS） 比如说走迷宫，DFS 简单地说就是使用函数递归，先一条路走到底然后再考虑下一条，而 BFS 是从一点出发使用队列并行的往四面八方出发，所有方向是一起走的 正文 用一道例题来理解：hdu 1312 Red and Black 点击查看题目 Problem Description There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above. Input The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles i ...

排列 求 n 个元素的全排列 使用 STL 这东西最先想到的必然是直接使用 STL 中的 next_permutation() 了，每执行一次都会把数组内的序列改为下一个排列，最后会输出 -1 123456int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};int sum = 0;do{ sum++; // 得到一个结果}while(next_permutation(data,data+12)); 使用递归（法一，不推荐） 这个方法应该是我高中的时候自己手搓出来的，性能很差劲，放在这里只是为了凑个数（ 12345678910111213141516171819202122232425262728#include <iostream>using namespace std;int a[1000], v[1000], n, k; //A (n,k)void dfs(int cnt, int num){ for (int i = 1; i <= n; i++) //组合 for(int i = num+1; i <= n ;i++) if (!v[i]) { a[cnt] = i; v[i] = 1; if (cnt == k) // 边界条件 {// 得到一个结果// ...

B 站上讲得真的清楚，暂时没时间整理了，先贴个链接在这里 【python】对迭代器一知半解？看完这个视频就会了。涉及的每个概念，都给你讲清楚！ 【python】生成器是什么？怎么用？能干啥？一期视频解决你所有疑问！

模块 基本概念 模块的定义 一般情况下，模块（module）是一个以 .py 为后缀的文件，其他可作为 module 的文件类型还有 .pyo 、.pyc 、.pyd 、.so 、.dll ，但初学者几乎用不到 在模块中能定义函数、类、变量，也能包含可执行的代码，在导入的时候会把模块完整地先执行一遍 模块的作用 隐藏代码细节，提高可维护性 模块的分类 Python 的官方标准库（直接 import 就能开用） 第三方模块（用 pip 下载的包里面的模块等） 自己写的模块（下面来试一试） 初尝模块 首先，在当前目录新建一个 calc.py ，再在里面保存一些函数 1234567891011def add(a,b): return a+bdef sub(a,b): return a-bdef mul(a,b): return a*bdef div(a,b): return a/b 现在我们在其他文件中引用它，在同一目录新建一个 .py 文件 import … 导入整个模块 12345import calcresult = calc.add(10, 20)print(result) # 30 使用这种方法，在调用其中的函数或类时，必须加上模块名的前缀 from … import … 导入特定的内容，使用时不用前缀 12345from calc import add, sub # 可以导入任意个result = add(10, 20)print(result) # 30 from … import * 这会把模块中的所有函数、类、变量等全部导进来，虽然方便 ...

本文转载自 Python 单下划线开头、双下划线开头 好文章，感觉写得不错 单下划线开头的变量：半私有变量 以此类名称命名的对象，需要分为两种情况： 类外：类外的半私有对象、私有对象，功能一致，均是在本模块中可以正常使用，但是不能被直接导入并调用。如果要在模块外使用，那么需要导入本模块，然后使用（模块名.变量名）进行调用。 类中： 类中的半私有对象，仅仅是概念上的私有，默认不要在类外进行调用 实际上，在类外，均可以使用（实例名.变量名/类名.变量名）进行调用。 双下划线开头的变量：私有变量 也需要分为两种情况： 类外： 与半私有对象相同 类中： 类中的私有对象，在类外均不可直接调用，可以理解为真私有，但是，Python 中没有完全私有的对象，此种对象也是可以在类外进行调用的，这里涉及到一个概念：矫直。 以双下划线开头，双下划线结尾的对象：Python 内置属性名或者魔法方法名 是 Python 自己实现的属性和方法，一般不允许自定义类似此种命名方式的属性或者方法。

有些快捷键总是忘记，而且要想半天，特此记录，慢慢补充 多行的行首同时增加/减少制表符：先选中一些行，然后 Tab / Shift + Tab 多行同时注释/取消注释：先选中一些行，然后 Ctrl + /