NeuGraph Programming Abstraction GCN: 初始情况下，每个vertex都有一个feature vector 每一个顶点都收集他邻居的特征向量，然后根据边上的权重进行加和。 然后一个全连接的NN来计算新一层的特征向量 比如在推荐系统中，如果用户对某一个item进行评分，就可以在用户顶点和item顶点之间连边，评分即作为边值。然后GCN可以从graph以及用户和item的特征中学习用户和item的embeddings。最后通过这些embedding来预测缺失的user-item评分 G…
Introduction pregel的program model类似BSP。每一个iteration叫做一个superstep。每一个superstep，系统会在读取上一个superstep传给顶点的数据，并应用user-defined function，然后他会沿边将数据传输出去，从而让他的邻居在下一个superstep使用这些数据 这种做法和MapReduce非常像，用户给出处理每个顶点的逻辑，然后系统会将这个操作应用到大规模的数据集上，并且不会暴露出执行顺序以及superstep之间的通信细节。 Model…
Motivation 虽然最先进的共享内存处理系统可以高效的处理图。但是缺乏可拓展性使得他们无法处理那些单台机器无法承载的图。而分布式解决方案虽然可以将图拓展到更大的规模。但是他们的性能和成本效率往往不是很好 一个对于前沿系统的比较 可以发现分布式系统的网络没有饱和。限制他的主要因素是计算而非通信 与共享内存系统相比，他们执行了更多的额指令，更多的内存引用，更差的局部性以及多核利用率低。这种低效性有多个来源：（1）通过hashmap来在全局和局部状态间转换vertexID，（2）维护顶点的副本，（3）在GAS中的c…
Recall Transaction in DBMS 整理一下DDIA中事务这一块 事务让我们可以为上层提供一个非常强大的抽象，而不需要将具体的细节暴露给上层 事务所提供的保证，即ACID，分别代表原子性，一致性，隔离性以及持久性 有的不符合ACID的系统有时被成为BASE，即基本可用性(Basic Available)，软状态(Soft state)，最终一致性(Eventual consistency) 原子性，指的是我们可以将事务内包含的一系列操作转化为原子操作，即要么所有的操作都发生了，要么一个也没发生。注…
PyToy review 核心就是用Node来抽象每个算子，然后根据他们的先后顺序将这些Node组合成一个图 计算的时候用pull或者拓扑排序的方法都可以 Node里设置了抽象方法compute和get_graident，即计算对应的前向传播的值和反向传播的值 Variable就是一种Node，类似于tensorflow中的placeholder，用来存储数据的 计算图的起始节点都要是variable 我这里做了简化，并没有区分常量和变量，而是统一作为variable使用的 第二大核心就是Ops了，也就是Opera…
蜡烛之间的盘子 首先预处理出每个位置左边第一个蜡烛的位置，以及右边第一个蜡烛的位置，然后用前缀和算就行 括号生成 直接dfs，过程中用栈判断是否合法 合并K个升序链表 用优先队列帮我们从K个表头中找最小的那个，然后append到答案链表中 最长有效括号 因为不合法的情况有两种。 一种是右括号多了，当右括号多的时候，之后的合法括号序列一定在这个右括号后面 左括号多的情况下，则是没有对应的右括号去栈中与他更新答案，即合法的序列在此之前就出现了。 我们每次成功构造出合法序列的时候一定是右括号成功匹配左括号的时候，所以只要…
今天基本上都是中等题，感觉也要复习复习基础知识 树的子结构 先用一个递归的函数判断当前的树是不是可以构成子结构，如果不能的话，就递归的考虑当前树的左子树和右子树 反转链表 这次尝试用递归写了一下，就是递归的反转当前节点的下一个节点，然后再把当前节点接到尾部即可 一次编辑 因为只有一次机会，所以当两个字符串长度相同的时候，判断最多只有一个字符不同 当长度不同的时候，最多相差1，并且只能有一个地方不匹配 零矩阵 可以用两个数组记录每一行每一列是否出现了0，之后再扫描一遍就行 一个优化是用第一行和第一列去存储这个信息，然…
记录一下刷题过程中遇到的一些值得思考的点，以便之后复习用。 同时回顾一下每天遇到的问题，来重新整理自己的思路。 题目1 求数组中的波谷，但是波谷要满足一定的长度 分别求出来每一个位置上，最长的非递增序列和非递减序列的长度。最后遍历一遍就可以 题目2 对于每一个位置，求出数组中所有数除去当前数的乘积 这个最简单的方法就是求出前缀积和后缀积，然后单独计算就行 一个优化是可以只用一个变量来保存前缀积或后缀积，然后给对应的位置乘上贡献即可 题目3 投n个骰子，问每种点数出现的概率是多少 设dp[i, j]为当前投了i个骰子…
Raft-KV 这里写一下lab4 shardkv的思路吧，感觉如果不好好想一下设计细节的话写代码的时候就很容易乱套 目标就是完成所有的part，所以后面的选做部分也要实现（其实感觉不实现那我们的代码就太玩具了） 每个shard不能干扰其他的shard，比如一个shard正在等待数据，他是不能干扰其他shard完成正常操作的。所以我们分别维护每个shard的状态。每个shard有自己的map 去重表，可以放在shard外面也可以放在shard里面，我这里就选择放在shard里面 有一个定时向shardctrler去…