最近在做一个 Cache 替换算法的 PA. 系统结构课. 给的 Baseline 是 2010 年的一个 championship. 看了看现在用得比较多的通用算法叫 LIRS. 在 LIRS 基础上想方法优化. 瞎搞的东西把单核 miss 率降低得有点 surprising. 还没有更多的 benchmark 测试. 感觉有点意思.

断路负载波形 短路负载波形 匹配负载波形 纵波和深孔波形

这篇讲义都是五笔打的 laekov 2018.04.12 Overview 作业要求 写一个拼音输入法, 一行一行地读拼音, 输出对应的汉语句子 84: 两小时就能写完 给出的数据 GBK编码的拼音->汉字对应表 新浪新闻一年的文章 评分 基础2字模型 扩展3字模型 四字, 双词, 三词… 需要写什么东西 拼音 2 汉字的 map 快速查找某个字/词词频的 map 估值函数和 infer 的算法 训练数据处理 最常用的16位编码是utf-8, 但是 Python 默认是 ASCII 的 所以在程序第一行写上 # -*- coding:utf-8 -*- Py 内部的 u'一个字符串' 可以用来表示 unicode 格式的字符串. 但是好像用不到. 创建 pinyin to 汉字的 map 读 GBK 文件的最简单的方法 with open('somefile.txt', 'r', encoding = 'gbk') as f: for (lineno, content) in enumerate(f): dealWithALine(content) content 的格式 wo 窝 我 握 渥 (五笔党词穷了) python 自带分割 py2ch_map = {} def dealWithALine(c): d = c....

看 paper 看烦了来贴点代码玩. Lagrange插值就是一个多项式乘. void genLagrangePoly(int n) { double *x = new double[n + 1]; double *y = new double[n + 1]; double *a = new double[n + 1]; double *tmp = new double[n + 1]; for (int i = 0; i <= n; ++ i) { x[i] = -5. + 10. / n * i; y[i] = f(x[i]); a[i] = 0; } for (int i = 0; i <= n; ++ i) { memset(tmp, 0, sizeof(double) * (n + 1)); tmp[0] = 1....

发现 strava 出了个 sport heatmap 的功能 于是去看了看 发现奥园有如下神奇现象 呵呵一笑 不说话

PA3-3 题意 一堆字符串判循环相等 做法 最小表示法模板题 也可以直接 hash 不过最小表示了也得 hash. PA <= 常数优化实习. 可能会在这里贴代码.

Text Key Encode base64 Ceasar (needs key to be a number) Vigenere (needs key to be a string) MD5 SHA1

最近在尝试搭 python 的数据分析的环境. 总结一下遇到的一些坑. 用的是 14.04 这个有点老的 ubuntu. nginx + jupyter jupyter 这个玩意的 web 写得不是很优美. 所以需要转发的地方蛮麻烦的. 本来想直接在 uri 里搞一下. 然后发现过于难受就放弃了, 重新配置了一个域名转发. nginx 的 server 配置里需要加这么一段. server { location ~* /(api/kernels/[^/]+/(channels|iopub|shell|stdin)|terminals/websocket)/? { proxy_set_header X-Real-IP $remote_addr; proxy_set_header Host $host; proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for; # WebSocket support proxy_http_version 1.1; proxy_set_header Upgrade $http_upgrade; proxy_set_header Connection $connection_upgrade; proxy_pass http://127.0.0.1:8888; } } 其中有个Upgrade是这么定义的. http { map $http_upgrade $connection_upgrade { default upgrade; '' close; } sendfile on; } google 了几个配置文件才弄出这么一个能用的....

laekov naiiiiiiiiive 问题 一个无向图 (G), 每条边 (e) 有两个边权 (a_e, b_e). 求一个生成树 (T) 使得 ( (\sum_{e \in T} a_e) * ( \sum_{e \in T} b_e) ) 最小. 多项式算法就是胜利w. 原题 搜 bzoj2395. 这网站里搜可以找到代码. 一个未成形的算法 正确性和时间复杂度都待证 qwq. 感觉是对的. 但是严格证明 qaq. 已经脱离理论计算机科学界太久了. 假设我们有一个生成树的序列 ( Q ) 和一个生成树池 ( P ). 算法如下 对 ( a ) 这一个权值跑出一个最小生成树 ( T_0 ). 把 ( T_0 ) 作为 ( Q ) 里的第一个元素. 取出 ( Q ) 里的最后一棵生成树 ( T )....

1 使用数论快速傅立叶变换进行多项式乘法. 要压三位才能过. 2 先把两维坐标分别快速排序 然后每个问题二分 然后建立两个向量, 看它们的夹角是劣的还是优的, 从而判断这个点在线段和坐标轴围成的三角形的内外 3 维护一个栈 如果右边所有数里的最大值都没有栈顶大, 就弹栈, 否则一直压栈到右边最大的数, 输出最大的数, 然后重复执行此操作. 4 在普通的队列里再维护一个单调队列, 对价格单调. 每次从单调队列里选择当前持有的股票, 用普通队列维护添加 / 删除. 5 替罪羊树维护序列. 至今 90 的数据有一个点 wa 掉不知为何. 可能满跑速度有点悬. 6 利用双向链表进行操作. 链表并不记录前后, 而是只记录两个端. 每个光标记录左右. 然而还是被卡常了.