前言

最近在使用 Golang 实现 HNSW 算法的多属性支持，在其中用到的 map 结构。然后 Map 并不是线程安全的，使用多线程的话在新版本的 Golang 中会直接出现 panic。

sync.Map 这个数据结构是线程安全的，它填补了 Map 线程不安全的缺陷，不过最好只在需要的情况下使用。它一般用于并发模型中对同一类 map 结构体的读写，或其他适用于 sync.Map 的情况。

关于 sync.Map 的源码解析文章：Go 1.9 sync.Map揭秘

sync.Map使用方法

1. Store 存 key，value
2. LoadOrStore 取&存—具体看代码
3. Load 取 key 对应的 value
4. Range 遍历所有的 key，value
5. Delete 删除 key，及其 value

归并排序

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
31
32
33
34
35
36
37
38
39
40
41
42

def merge_sort(li):
    # 不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
    if len(li) == 1:
        return li

    # 取拆分的中间位置
    mid = len(li) // 2
    # 拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]

    # 对拆分过后的左右再拆分 一直到只有一个元素为止
    # 最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = merge_sort(left)
    rl = merge_sort(right)

    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
    return merge(ll, rl)

# 这里接收两个列表
def merge(left, right):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left) > 0 and len(right) > 0:
        # 为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result


if __name__ == '__main__':
    li = [5, 4, 30, 2, 1]
    li2 = merge_sort(li)
    print(li2)

前言

HashMap是Java中常用的数据结构，是集合类中的重要存在，其中包含了散列表、链表和红黑树。散列表解决冲突的方法是链地址法，即将散列值相同的元素存放在一个链表中。当冲突过多，链表过长会造成查找效率降低，因此Java8中在HashMap中引入红黑树进行优化，当某个散列值下的链表长度过长（长度大于8），会将其转变为红黑树存储，优化查询。涉及到红黑树的操作不会再这里细讲

前言

近期服务器不太稳定，于是需要找一些工具检测服务器状态，避免服务挂掉。这里介绍一些服务器检测工具 Monit 的使用。

安装

在 Monit官网 下载安装包，我这里推荐服务器是 CentOS 7，选择 linux-x64 版本。可以在服务器直接下载，我这里本地电脑下载好以后使用 Transmit 传到服务器。

在服务器中我放在了 /data 路径下，因为关于推荐的文件都放在这里，把监控服务放这里比较好管理。解压文件：

1
2

tar -zvxf monit-5.25.2-linux-x64.tar.gz
mv monit-5.25.2 monit

这时候就可以使用了。

前言

近期在研究近似最近邻算法 HNSW 的源码和论文，这里结合论文中的伪代码做一下 HNSW 主要的几个算法的解读，这将对读懂源码十分有帮助。本文介绍以下算法：

• $\tt INSERT(\it hnsw, q, M, M_{max}, efConstruction, m_L \tt)$ : 新元素 $q$ 插入算法。
• $\tt SEARCH\ LAYER(\it q, ep, ef, l_c \tt)$ : 在第 $l_c$ 层查找距离 $q$ 最近邻的 $ef$ 个元素。
• $\tt SELECT\ NEIGHBORS\ SIMPLE( \it q, C, M \tt) $ : 在候选点集合 $C$ 中 选取距离 $q$ 最近邻的 $M$ 个元素。
• $\tt SELECT\ NEIGHBORS\ HEURISTIC(\it q, C, M, lc, extendCandidates, keepPrunedConnections \tt)$ : 探索式寻找最近邻。
• $\tt KNN\ SEARCH(\it hnsw, q, K, ef \tt)$ : 在 $hnsw$ 索引中查询距离 $q$ 最近邻的 $K$ 个元素。

前言

实验室一直在用到推荐系统，其中最重要的一部分就是利用近似最近邻算法（ANN）在大量论文/专利/项目中找到最相似的的论文/专利/项目进行推荐。

之前的 ANN 算法一直是 gensim 中使用的 Annoy。但是鉴于基于图的 HNSW 在 ANN Benchmarks 中的优异表现，需要对其进行学习并且进行一定修改，最后应用到推荐系统中。

KNN 和 ANN

• k-Nearest Neighbor, KNN

  • K最近邻算法，可用作聚类、回归等。

• Approximate nearest neighbor, ANN

  • 目前在高维度度量空间中没有有效精确 NNS 的方法。这背后的原因在于维度的“诅咒” 。为了避免维数的诅咒，减少对 kNN 问题解决方案的要求，使其近似（ANN），精度允许的条件下通过牺牲准确率来换取比暴力搜索要快的多的搜索速度。
  • ANN 应用：推荐系统。

错排问题

$n$ 个有序的元素应有 $n!$ 个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排，有的叫重排。

方法一：递推式

任给一个 $n$，求出 $1,2,…,n$ 的错排个数 $D(n)$ 共有多少个。

递归关系式为：

前言

今天要做的是一个具有搜索功能的前端页面，通过调用 Solr 搜索的接口来实现搜索功能。其中为了解决跨域的问题，利用 Python 写了一个简单的 Flask 服务器来请求 Solr，而前端页面仅需请求 Flask 服务器。

之前用 Vue.js 搭建过一个数据可视化平台，本来今天的搜索只需在之前的项目中添加一个 Tab 就可以了，但是这次的要求是初学者比较容易理解和上手，所以这次我们选用了 jQuery ，Bootstrap 4 来构建本次页面。

jQuery —— 简化的 JavaScript

jQuery 曾经是最流行的 Web 前端 JavaScript 库，可是现在无论是国内还是国外他的使用率正在渐渐被其他的基于 MVVM 思想的 JavaScript 库（例如 Vue，React，Angular）所代替，随着浏览器厂商对 HTML5 规范统一遵循以及 ECMA6 在浏览器端的实现，jQuery 的使用率将会越来越低。

jQuery 是使用选择器 $ 选取 DOM（文档对象模型，可以理解成 HTML 中的元素）对象，对其进行赋值、取值、事件绑定等操作，其实和原生的 JavaScript 的区别只在于可以更方便的选取和操作 DOM 对象，而数据和界面是在一起的。比如需要获取 label 标签的内容：$("lable").val(); ，它还是依赖 DOM 元素的值。

基本用法在 jQuery 教程 | 菜鸟教程。

前言

初步学习 Docker 以后，我将尝试使用 Docker 部署之前构建的 Vue.js 应用。在实际部署的时候采用的是 vue-cli-service 打包，用 Nginx 作为代理服务器。

打包 Vue 应用

首先在 Vue 项目路径利用 vue-cli-service 打包 Vue 应用：

1

$ vue-cli-service build

这样在路径中会生成 dist 文件夹，里面的文件经过了压缩和混淆，可以加快项目运行速度并且保护代码不被轻易拷贝。