Count Min Sketch:找最频繁元素

这是笔者学习 Stanford cs 168 课程的一些学习笔记 lecture 2, 主要讲一个基于 hash 和独立试验思想,设计的一种数据结构 count min sketch,想法非常类似于 bloom filter,都是以牺牲准确率换空间和时间。

heavy hitter problem

Find majority element

先来看 …

阅读全文

Consistent Hash

记得我人生第一次参加bytedance 的面试的时候,面试官问我的就是这样一个问题: 你有很多台服务器,每台服务器上都存放着很多数据,现在要加一台服务器,如何才能让数据搬迁尽可能的少,同时能让每台服务器经可能的负载均衡。现在才发现,这就是可一致性hash 问题,当时我答了个hashMap中的rehash操作,给糊弄过去了….

具体的内容可 …

阅读全文

MIT6.824 lab1:mapreduce 总结

这是 MIT 6.824 课程 lab1 的学习总结,记录我在学习过程中的收获和踩的坑。

我的实验环境是 windows 10,所以对lab的code 做了一些环境上的修改,如果你仅仅对code 感兴趣,请移步 : github/zouzhitao

mapreduce overview

先大致看一下 mapreduce 到底是什么

我个人的简 …

阅读全文

Kick Start 2019 RoundA: 题解

题目链接

A. Training

这题很简单,处理一下前缀和就完事儿,没什么好说的。当时就做出了这个题 :(

code

github

B. parcel

这题还是很有意思的,正式赛没做出来,其实第一问暴力很容易求,不过 作为一名 ACMer,有一种惯性会忽略掉这种方式…,下次一定要补上了。

题解可以参考官方题解

我这里就是将题解 …

阅读全文

Generic Variance in Scala: 泛型变化 in scala

本文主要总结Scala中关于generic variance(泛型变化, 我也不知道该怎么翻译,以下称 GV),(co-,contra-,in)variance in Scala 的相关知识,什么是 generic variance 呢?我的感觉是一种泛型类型的类型系统,应该和 type system 比较相关,(PL专家就不要嘲笑我了)。比如: …

阅读全文

PAC learning 与样本复杂度

这篇文章主要总结 PAC 学习框架以及样本复杂度相关的东西,大致来说就是:要保证以概率 $1-\delta$ 使得 generalized error 小于 $\epsilon$ 需要多大的样本复杂度,以及时间复杂度才是好的。

问题及约定

f1

符号约定

symbol

两个 error 符号

error

就是我们常说的 train error 与 true …

阅读全文

boosting : adaboost & gradient boost

纸上得来终觉浅,觉知此事要躬行。综上,我什莫都不懂.这仅仅是个人的学习防忘笔记

Adaboost

关于 Adaboost 的算法描述其实很简单,有趣的是的它的误差分析:

algorithm

adaboost

其中

$$ \begin{align} \epsilon_t &= Pr_{i\sim D_t}[h_t(x_i)\ne y_i]\\ …

阅读全文

kickstart: Scrambled-Words(hash+complexity)

题目链接

google kickstart 2018 Scrambled Words

分析

分析在题目网站有,首先需要想到的就是不同串的长度只有 $O(\sqrt{\sum words_i})$ 种,那么枚举所有长度肯定是一种可行的方法,不过呢,即使枚举长度,对于每个枚举到的字串,我们仍然需要将他和所有具有此长度的串比较,太过浪费时间了,怎么做才能加速 …

阅读全文

个人凸优化简单学习笔记

本文来源于个人的凸优化学习笔记参考cs229 cvxoptnote,写成笔记的原因仅仅是想通过个人的笔记自己讲述与推导一下这些数学公式,内容可能会很简单,强力建议想得到一手资料的人好好学习文末参考资料

凸集合

定义就直接跳过了,这里简单写一些常见的凸集

  • 凸集的交, 设 $C_i,i = 1,2,3,…,n$ 是凸集,那么我们 …

阅读全文

点到超平面的距离计算简单笔记

发现自己从大二开始就没有好好的学习数学了,最近看 SVM,发现好多推导和证明自己都不会,或者就要想很久,实在是太废材了。 :(. 以后决定对一些数学知识(特别是高等数学,分析和代数领域的一些东西,学点记点)


这是正文

这是一个简单的问题,定义如下:

设, $y(X) = W^TX +b, X \in R^n,b \in R$, …

阅读全文