2.2k 字 2 分钟

先说结论过了所有的测试点，我是能够过那个 usertests ，但是 lazytests 会一直卡在 out of mem 这个测试点，而且怎么也没法过，折腾了好久真的无语。 这个原因是因为 sbrk 是懒加载，我们直接用 addr+n 表示 proc 的 size。这样有个问题，xv6 最大的虚内存实际上是一个 MAXVA ，如果不加限制的话，walk 阶段就会 walk 到 MAXVA 导致一直 panic。解决办法其实很简单，在 uvmunmap 代码加个限定条件，强制 va 不能超过 MAXVA。 懒加载代码： int lazy_alloc(uint64 addr){...
4.3k 字 4 分钟

# RISC-V assembly 首先是 call.c: #include "kernel/param.h"#include "kernel/types.h"#include "kernel/stat.h"#include "user/user.h"int g(int x) { return x+3;}int f(int x) { return g(x);}void main(void) { printf("%d...
18k 字 17 分钟

# 编译 cmake -DCMAKE_BUILD_TYPE=Debug -B buildcmake --build build -j 8出现报错 [CMake is not able to find BOOST libraries](https://stackoverflow.com/questions/24173330/cmake-is-not-able-to-find-boost-libraries) , 解决 sudo apt-get install cmake libblkid-dev e2fslibs-dev libboost-all-dev libaudit-dev 。 #...
4.4k 字 4 分钟

打算简单学一下 CMake，毕竟接下来的实验也好，代码也好 CMake 基本上的躲不掉的。。。 # MakeFile 对于当前文件目录： 可以看到 answer.hpp 和 answer.cpp 都在当下目录下，所以不需要额外连接工作。 Makefile 可以简单写为： CC := clangCXX := clang++.PHONY: allall: answer# 在这里添加了 answer.o 目标文件。objects := main.o answer.oanswer: $(objects) $(CXX) -o $@ $(objects)## Make 可以自动推断 .o...
852 字 1 分钟

这篇文章主要是过一下 KGraph，也就是 NN-Descent 算法，A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search。 NN-Descent 实际上就是一个近似 K-NNG 的构建方法。 # 作者的动机 高效的 K-NNG 构建方法一直是一个公开的问题，然而没有哪个方法能够做到通用、高效以及可扩展性，作者希望能够解决这些问题。 通用：对于任意的 similarity oracle，该方法都能适用。 可扩展性：也就是 dataset...
431 字 1 分钟

用于记录各种 cpp 技巧 # nth_element 和 bind nth_element 相当于快排，用于把特定元素放在特定的位置，比如下面这个用于归为中位数， bind 用于生成 cmp 排序函数。 using std::placeholders::_1;using std::placeholders::_2;std::nth_element(begin, begin + std::distance(begin, end) / 2, end, std::bind(&comparer::compare_idx, comp, _1, _2));# vector...
6.5k 字 6 分钟

这篇文章主要聚焦一下各种奇奇怪怪的树查询算法。虽然我主要关注最近邻检索的图方法，但是因为很多图方法实际上都使用了各种 tree 作为辅助索引，所以有必要简单了解一下所有的树查询算法。 有请第一位 受害者 。 # KD 树 kd 树算是用的很广泛的一种最近邻检索树了，它的思想实际上和二叉搜索树很像。 看这张图就够了： 首先思考动机，为什么我们需要构建 KD 树？树结构是一种非常高效的数据结构，对于二叉搜索树，它的查询复杂度只有 h，也就是 log (n)。如果直接暴力检索最近邻，那么复杂度会是 n。 KD...
2.1k 字 2 分钟

这篇文章就简单说一下 FANNG 这个算法（Fast Approximate Nearest Neighbour Graph） # 本文贡献 # FANN 算法拆解 # 理想的图结构 首先看一下这个简单的贪心算法，这个算法让我思考的一个问题就是我们是否需要维持一个 visit 列表来保证非回溯，可以看到因为查询路径单调的原因，即使不维持 visit 列表，我们也能够不回头查询。所以 visit 列表最大的作用其实是当 Candidate 不是一个节点而是一组节点的时候，使用 visit 列表可以砍掉重复访问，因为我们的查询路径如果是单调的，即使 Candidate...
2.3k 字 2 分钟

# 作者的动机 作者的动机有 4 个： （1）保证 graph 的连通性。 （2）降低 graph 的平均出度 （3）使得搜索 path 长度尽可能短。 （4）降低索引的尺寸。 # 贪婪算法 首先介绍一下贪婪算法，很多算法比如 HNSW 的查询方法就是使用了贪婪算法。那么它是如何实现需要最近 K 邻的呢？对于给定的查询 q，以及起始点 p（这个起始点也叫 seed）。 1）首先，把 p 放入候选池 S 中，侯选池的尺寸是固定的为 l。 2）第二步，从侯选池中找到没有 check 过的节点（为什么要没有 check 过呢，因为砍掉重复路径） 3）如果发现侯选池中都已经 check...
2.9k 字 3 分钟

这算是我看的第一篇 ANNS 文章，感觉像是打开了新世界的大门，后续读了一些 ANNS 文章，感觉没有读这一篇那么心潮澎湃了。 # 论文动机 # 作者希望解决的问题 ​ K 近邻检索（K-NNS）在很多场景有着很强的需求，naive 的思想就是扫一遍整个数据集，然后找到 KNN，但是这样做无疑是极大耗时间的。虽然后续有很多更好的 KNNS 算法提出，但是由于 curse of dimensionality 维度诅咒的存在 KNNS 只适用于低维度的数据。为了解决这一问题，KANNS 被提出，只是检索最近似的邻居。通过用召回率，即（检索得到的最近邻）/...