Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

发表于 分类于 阅读次数： Disqus：

java的函数式接口是java8引入的很重要的特性，也让日常代码有了比较大的风格转变
这里介绍下BiFunction，
BiFunction的代码很短

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
@FunctionalInterface
public interface BiFunction<T, U, R> {

    /**
     * Applies this function to the given arguments.
     *
     * @param t the first function argument
     * @param u the second function argument
     * @return the function result
     */
    R apply(T t, U u);

    /**
     * Returns a composed function that first applies this function to
     * its input, and then applies the {@code after} function to the result.
     * If evaluation of either function throws an exception, it is relayed to
     * the caller of the composed function.
     *
     * @param <V> the type of output of the {@code after} function, and of the
     *           composed function
     * @param after the function to apply after this function is applied
     * @return a composed function that first applies this function and then
     * applies the {@code after} function
     * @throws NullPointerException if after is null
     */
    default <V> BiFunction<T, U, V> andThen(Function<? super R, ? extends V> after) {
        Objects.requireNonNull(after);
        return (T t, U u) -> after.apply(apply(t, u));
    }
}

默认的方法就跟普通的FunctionalInterface一样，就有一个apply方法，只是这里的特殊点有两个

返回值作为参数

这个BiFunction有三个泛型参数，T，U跟R，而这个R其实是具体方法的返回值
比如我们简单实现一个字符串拼接

1
2
BiFunction<String, String, String> biDemo = (s1, s2) -> s1 + s2;
System.out.println(biDemo.apply("hello ", "world"));

apply返回的就是参数R

andThen

这个方法是可以让结果再调用传入的方法，并返回结果

1
2
Function<String, Integer> funcDemo = String::length;
System.out.println(biDemo.andThen(funcDemo).apply("hello ", "world"));

定义了个函数接口，并且给了实现，就是字符串获取长度
然后传给biDemo，这样就可以输出拼接后的字符串长度

组合使用

1
2
3
public <T1, T2, R1, R2> R2 combination(T1 t1, T2 t2, BiFunction<T1, T2, R1> biFunction, Function<R1, R2> function) {
    return biFunction.andThen(function).apply(t1, t2);
}

这样就把前面的两个方法串起来了

发表于 分类于 阅读次数： Disqus：

结合AI写的一篇HNSW的介绍文章，算是向量数据库中比较核心的算法

1. 引言

向量数据库在当今人工智能和机器学习领域扮演着越来越重要的角色。随着数据规模的不断扩大和应用场景的日益复杂,传统的数据库系统已经难以满足高维向量数据的快速检索需求。在这个背景下,近似最近邻(Approximate Nearest Neighbor, ANN)搜索问题成为了一个热点研究方向。

HNSW(Hierarchical Navigable Small World)算法是解决ANN问题的一种高效方法。它通过构建一个多层次的图结构,结合小世界网络的特性,实现了对高维向量数据的快速、精确检索。本文将深入浅出地介绍HNSW算法的核心思想、工作原理以及实际应用。

2. HNSW算法的核心思想

HNSW算法的核心思想可以概括为三个关键点：分层结构、小世界图和近似搜索。

分层结构

HNSW采用了一种多层次的图结构。想象一下,如果我们要在一个大城市中找到一个特定的地址,我们通常会先看城市地图,然后逐步缩小范围到区、街道,最后定位到具体门牌号。HNSW的分层结构就类似于这种由粗到细的搜索过程。这个就是之前介绍跳表的目的，就是现在稀疏的结构里可以快速定位，然后再往下层进行搜索，提高了搜索效率

小世界图

小世界网络是一种特殊的图结构,它具有较短的平均路径长度和较高的聚类系数。在HNSW中,每一层都是一个小世界图。这种结构使得在图中的任意两点之间都存在一条相对较短的路径,大大提高了搜索效率。

近似搜索

与传统的KNN(K-Nearest Neighbors)算法不同,HNSW通过牺牲一小部分精度来换取显著的速度提升。它不保证一定能找到真正的最近邻,但可以以极高的概率找到足够接近的点,而且搜索速度要快得多。

3. HNSW的工作原理

数据结构:多层图的构建过程

  1. HNSW从底层开始构建,每个数据点都会出现在底层。
  2. 对于每个新插入的点,算法会随机决定它是否应该出现在上一层。这个过程一直持续到某一层,该点不再被选中。
  3. 在每一层,新点会与该层的其他点建立连接,形成小世界图结构。

搜索过程:自顶向下的贪婪搜索

  1. 搜索从最顶层开始,选择一个随机起点。
  2. 在当前层进行贪婪搜索,不断移动到离目标更近的邻居。
  3. 当在当前层无法找到更近的点时,下降到下一层继续搜索。
  4. 重复这个过程直到达到底层,得到最终结果。

插入新向量的过程

  1. 确定新向量应该出现在哪些层。
  2. 从顶层开始,在每一层执行类似于搜索的过程,找到适合连接的邻居点。
  3. 建立连接,同时可能需要删除一些现有连接以维持图的结构特性。

    论文中的算法是这样的

  • 红色节点表示新插入的数据点。在这个例子中,新节点被插入到了层级0和层级1。

  • 红色实线表示新建立的同层连接。新节点与其邻近节点建立了连接。

  • 红色虚线表示新建立的跨层连接。新节点在不同层级之间建立了连接。

  • 绿色虚线箭头表示插入过程的路径。这条路径展示了算法如何从顶层开始,逐层下降,最终确定新节点的插入位置。

  • 其他颜色的节点和灰色的连接线表示原有的HNSW结构。

  • 插入过程从顶层开始,沿着绿色虚线所示的路径向下搜索。

  • 在每一层,算法都会寻找最近的邻居节点,并决定是否在该层插入新节点。

  • 在本例中,新节点被插入到了层级0(基础层)和层级1。这是因为HNSW使用概率方法来决定节点应该出现在哪些层级。

  • 插入后,新节点与其邻近节点建立连接(红色实线),以维持图的小世界特性。

  • 同时,新节点也与其在不同层级的对应节点建立跨层连接(红色虚线),以确保层级之间的快速访问。

4. HNSW的性能分析

时间复杂度分析

  • 搜索时间复杂度: O(log N),其中N是数据点的总数。
  • 插入时间复杂度: 平均情况下为O(log N)。

空间复杂度分析

  • 空间复杂度: O(N log N),因为上层节点数量呈指数衰减。

与其他ANN算法的比较

相比LSH(Locality-Sensitive Hashing)和Annoy等算法,HNSW在大多数场景下都能提供更好的查询性能和更高的准确率。然而,HNSW的内存消耗相对较高,这是它的一个潜在缺点。

5. HNSW的实际应用

在推荐系统中的应用

HNSW可以用于快速检索相似用户或物品,提高推荐系统的响应速度和准确性。例如,在音乐推荐中,可以用HNSW快速找到与用户喜好相似的歌曲。

在图像检索中的应用

在大规模图像数据库中,HNSW可以实现快速的相似图像搜索。这在图像搜索引擎、视觉商品搜索等场景中非常有用。

在自然语言处理中的应用

HNSW可以用于词嵌入或句子嵌入的快速检索,支持语义相似度计算、文本分类等任务。

6. HNSW的优化和变种

参数调优技巧

  • 层数选择:影响搜索速度和内存使用
  • 每层连接数:影响搜索准确度和构建时间
  • 候选集大小:影响搜索质量和速度的平衡

常见的HNSW变种算法介绍

  • NSW-G:改进了图的构建方法,提高了搜索效率
  • HCNNG:结合了层次聚类,提高了在某些数据集上的性能

7. 实现HNSW的挑战与解决方案

大规模数据集的处理

  • 使用外部存储和分批处理
  • 采用压缩技术减少内存占用

并行化和分布式实现

  • 搜索过程的并行化
  • 分布式索引构建和查询

动态更新和删除操作的处理

  • 软删除技术
  • 定期重建索引

8. 总结与展望

HNSW算法通过其独特的分层小世界图结构,在保证高准确率的同时实现了对高维向量数据的快速检索。它在推荐系统、图像检索、自然语言处理等多个领域都有广泛应用。

未来,向量数据库技术可能会朝着以下方向发展:

  1. 更高效的压缩和索引技术
  2. 更好的动态更新支持
  3. 与深度学习模型的更紧密集成
  4. 针对特定领域的优化变体

随着人工智能和大数据技术的不断发展,HNSW等高效的向量检索算法将在更广阔的应用场景中发挥重要作用。

发表于 分类于 阅读次数： Disqus：

因为买了两个NX30Pro，主要是奔着可以刷Openwrt，然后把两个都刷成了ImmortalWrt，结果发现要作为有线中继的话设置还有点麻烦，所以记录下
首先要设置个与主路由相同网段的静态地址，方便管理
在网络-LAN-基本设置-协议设置成“静态地址”
然后IPv4地址就是刚才说的静态地址，可以设个好记的
子网掩码就默认的，255.255.255.0，
IPv4网关就是主路由地址，DNS也设置成主路由地址
基础设置改成忽略此接口-不提供DHCP服务，由主路由提供
然后在高级设置中将IPv6的 路由通告服务和DHCPv6服务跟NDP代理禁用掉，
物理设置中勾选桥接接口
目前我是这样设置可以作为有线中继连通网络了，后续有变化继续更新

发表于 分类于 阅读次数： Disqus：

在学习向量数据库的时候，发现检索的算法 HNSW 是个比较重要且核心的概念，直接学习（面向小白）可能有一定的门槛，所以我们先通过常见算法的跳表来做个引入
跳表的前置基础就是最常见的序列结构之一的链表，链表的特点是添加插入元素效率非常高，查询检索则需要线性复杂度，比如Java中的hashmap，在jdk1.8以后就把
单纯链表的结构改成了链表和红黑树结合的方式，因为当链表比较长的时候，线性时间复杂度也是个比较慢的方法相比对数时间复杂度，而对于链表，也有直接在它基础
优化而来的跳表结构，跳表是在链表的基础上引入了分层的概念，通过投硬币概率来决定是否生成新层，先用比较通俗的话来讲一下我的理解
因为链表查找只能从前往后一个一个找（单向链表），那么有没有办法可以跳过一些，加速我的查找，那么引入了分层的结构，在更上层以更稀疏的数据链表来索引数据，
举个例子，我原来是一个

1
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9

这样的链表，我要查找8个元素是否存在，那我需要查找八次才能找到
如果我把结构改成

1
2
3
1 --------------> 4 --------------> 7 ---------> null 
|                 |                 |
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> null

变成这样的结构，我现在第一层找最后一个比8小的元素，就是7，然后再到下一层查找，这样我的查找路径就是 1 --> 4 --> 7 --> 8 速度加快了一倍
直观来说这样是能够提升很多查询效率，但是具体怎么实现我们也来看一下
首先定义个简单的Node

1
2
3
4
5
6
7
8
9
public class Node {
    public int data = -1;

    public Node[] forwards;

    public Node(int level) {
        forwards = new Node[level];
    }
}

接下去是SkipList的主体结构

1
2
3
4
5
6
7
8
public class SkipList {
    private static final int MAX_LEVEL = 16;

    private int currentLevel = 0;

    private Node head = new Node(MAX_LEVEL);

    private Random random = new Random();

包含最大层数，当前层数，头结点，跟随机值
生成随机层数参考了redis的zset实现方法

1
2
3
4
5
6
7
private int generateRandomLevel() {
        // 参考redis sorted set 实现
        int level = 1;
        while ((random.nextInt() & 0xFFFF) < (0.25 * 0xFFFF))
            level += 1;
        return Math.min(level, MAX_LEVEL);
    }

接下去先看下

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void insert(int value) {
        int level = generateRandomLevel();
        if (level >= currentLevel) {
            currentLevel = level;
        }

        Node newNode = new Node(level);
        newNode.setData(value);
        Node[] update = new Node[level];

        Arrays.fill(update, head);

        Node p = head;

        for (int i = level - 1; i >= 0; --i) {
            // 找到应该处在的位置，把前一元素记录为待更新
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            // 对应这一层，更新新的位置p
            update[i] = p;
        }
        
        // 每一层都处理前后链接
        for (int i = 0; i < level; i++) {
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }
    }

看下图片演示,类似于链表的插入，但是需要处理每一层的前后链接

查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Node search(int value) {
        Node p = head;
        // 逐层找到比目标元素小的最后一个元素
        // 然后再往下一层找
        for (int i = currentLevel - 1; i >= 0 ; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
        }
        // 此时如果前一元素就是目标元素就返回该元素
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        } else {
            return null;
        }
    }

也可以看下图里的演示，按红色的线寻找元素

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void delete(int value) {
        Node[] update = new Node[currentLevel];
        Node p = head;
        // 找到待删除元素的前一元素
        for (int i = currentLevel - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            update[i] = p;
        }
        // 判断如果该层有这个元素就更新链接
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            for (int i = currentLevel - 1; i >= 0; i--) {
                if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
                    update[i].forwards[i] = update[i].forwards[i].forwards[i];
                }
            }
        }
    }

删除操作就类似于插入操作。了解了跳表原理以后其实HNSW就是个在空间层面的跳表

发表于 分类于 阅读次数： Disqus：

将一个小点，在局域网中包括类似于homelab的或者仅仅只是搭一个用来当实验环境的，在局域网内机器比较少的时候大部分DHCP会给分配相同的ip，但是这不是一定的，当机器比较多，并且上下线比较频繁时就会出现ip地址变动，这对于一些使用场景比较讨厌，所以我想把ip固定下来，先简单引用下DHCP的原理，他分为下面几个阶段

DHCP发现（DISCOVER）

client在物理子网上发送广播来寻找可用的服务器。网络管理员可以配置一个本地路由来转发DHCP包给另一个子网上的DHCP服务器。该client实现生成一个目的地址为255.255.255.255或者一个子网广播地址的UDP包。

客户也可以申请它使用的最后一个IP地址（在下面的例子里为192.168.1.100）。如果该客户所在的网络中此IP仍然可用，服务器就可以准许该申请。否则，就要看该服务器是授权的还是非授权的。授权服务器会拒绝请求，使得客户立刻申请一个新的IP。非授权服务器仅仅忽略掉请求，导致一个客户端请求的超时，于是客户端就会放弃此请求而去申请一个新的IP地址。

DHCP提供（OFFER）

当DHCP服务器收到一个来自客户的IP租约请求时，它会提供一个IP租约。DHCP为客户保留一个IP地址，然后通过网络单播一个DHCPOFFER消息给客户。该消息包含客户的MAC地址、服务器提供的IP地址、子网掩码、租期以及提供IP的DHCP服务器的IP。

服务器基于在CHADDR字段指定的客户硬件地址来检查配置。这里的服务器，192.168.1.1，将IP地址指定于YIADDR字段。

DHCP请求（REQUEST）

当客户PC收到一个IP租约提供时，它必须告诉所有其他的DHCP服务器它已经接受了一个租约提供。因此，该客户会发送一个DHCPREQUEST消息，其中包含提供租约的服务器的IP。当其他DHCP服务器收到了该消息后，它们会收回所有可能已提供给该客户的租约。然后它们把曾经给该客户保留的那个地址重新放回到可用地址池中，这样，它们就可以为其他计算机分配这个地址。任意数量的DHCP服务器都可以响应同一个IP租约请求，但是每一个客户网卡只能接受一个租约提供。

DHCP确认（Acknowledge，ACK）

当DHCP服务器收到来自客户的REQUEST消息后，它就开始了配置过程的最后阶段。这个响应阶段包括发送一个DHCPACK包给客户。这个包包含租期和客户可能请求的其他所有配置信息。这时候，TCP/IP配置过程就完成了。

该服务器响应请求并发送响应给客户。整个系统期望客户来根据选项来配置其网卡。

DHCP释放（RELEASE）

客户端向DHCP服务器发送一个请求以释放DHCP资源，并注销其IP地址。鉴于客户端更多的时候并不清楚何时用户会将其从网络中移除，此协议不会托管“DHCP释放的发送”。

DHCP NAK

服务器回复客户，客户要求的IP不能被分配。

Ubuntu

而对于Ubuntu，现在较新版本的设置方式也有点变化，比如我用的是22.04

1
cd /etc/netplan/

先去这个目录下查看配置文件
我们要找的是这个 00-installer-config.yaml 文件

原本的是长这样

默认是通过dhcp分配ip
我们要改成静态ip

1
2
3
4
5
6
7
8
9
10
11
12
network:
  renderer: networkd
  ethernets:
    ens33:
      addresses:
        - 192.168.1.xx/24
      nameservers:
        addresses: [114.114.114.114, 233.5.5.5]
      routes:
        - to: default
          via: 192.168.1.1
  version: 2

解释一下 ethernets中的ens33表示我们的网卡接口的标识
可以通过 ip addr 查看

第一个是本地回环，第二个可以看下是否跟内网ip对应上，如果是的话就这个ens33
然后就是addresses填的地址，就是我们想要固定的ip地址，记得得是自己局域网网段的
上面只是个示例，然后是nameservers里的是dns服务器，也是按需填写
这里的114.114.114.114跟233.5.5.5分别是电信跟阿里云的，仅供参考
然后是routes就是网关地址，按自己的环境填写，网络没有任何特殊处理的一般就是路由器
接下去就是应用这个配置

1
sudo netplan apply

这样ip配置就生效了
可以通过
ip addr show ens33查看

0%