Annoy 是由 spotify 開源的一個Python第三方模塊，它能用于搜索空間中給定查詢點的近鄰點。

此外，眾所周知，Python由于GIL的存在，它的多線程最多只能用上一個CPU核的性能。如果你想要做性能優化，就必須用上多進程。

但是多進程存在一個問題，就是所有進程的變量都是獨立的，B進程訪問不到A進程的變量，因此Annoy為了解決這個問題，增加了一個靜態索引保存功能，你可以在A進程中保存Annoy變量，在B進程中通過文件的形式訪問這個變量。

1.準備

開始之前，你要確保Python和pip已經成功安裝在電腦上，如果沒有，可以訪問這篇文章：超詳細Python安裝指南 進行安裝。

**(可選1) **如果你用Python的目的是數據分析，可以直接安裝Anaconda：Python數據分析與挖掘好幫手—Anaconda，它內置了Python和pip.

**(可選2) **此外，推薦大家用VSCode編輯器，它有許多的優點：Python 編程的最好搭檔—VSCode 詳細指南。

請選擇以下任一種方式輸入命令安裝依賴 ：

1. Windows 環境 打開 Cmd (開始-運行-CMD)。
2. MacOS 環境 打開 Terminal (command+空格輸入Terminal)。
3. 如果你用的是 VSCode編輯器 或 Pycharm，可以直接使用界面下方的Terminal.

pip install annoy

2.基本使用

Annoy使用起來非常簡單，學習成本極低。比如我們隨意生成1000個0,1之間的高斯分布點，將其加入到Annoy的索引，并保存為文件:

# 公眾號：Python 實用寶典
from annoy import AnnoyIndex
import random

f = 40
t = AnnoyIndex(f, 'angular') # 用于存儲f維度向量
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

t.build(10) # 10 棵樹，查詢時，樹越多，精度越高。
t.save('test.ann')

這樣，我們就完成了索引的創建及落地。Annoy 支持4種距離計算方式：
"angular"，"euclidean"，"manhattan"，"hamming"，或"dot"，即余弦距離、歐幾里得距離、曼哈頓距離、漢明距離及點乘距離。

接下來我們可以新建一個進程訪問這個索引：

from annoy import AnnoyIndex

f = 40
u = AnnoyIndex(f, 'angular')
u.load('test.ann')
print(u.get_nns_by_item(1, 5))
# [1, 607, 672, 780, 625]

其中，**u.get_nns_by_item(i, n, search_k=-1, include_distances=False) **返回第 i 個 item 的n個最近鄰的item。在查詢期間，它將檢索多達search_k（默認n_trees * n）個點。

如果設置include_distances為True，它將返回一個包含兩個列表的元組，第二個列表中包含所有對應的距離。

3.算法原理

構建索引 ：在數據集中隨機選擇兩個點，用它們的中垂線來切分整個數據集。再隨機從兩個平面中各選出一個頂點，再用中垂線進行切分，于是兩個平面變成了四個平面。以此類推形成一顆二叉樹。當我們設定樹的數量時，這個數量指的就是這樣隨機生成的二叉樹的數量。所以每顆二叉樹都是隨機切分的。

查詢方法 ：

1. 將每一顆樹的根節點插入優先隊列；
2. 搜索優先隊列中的每一顆二叉樹，每一顆二叉樹都可以得到最多 Top K 的候選集；
3. 刪除重復的候選集；
4. 計算候選集與查詢點的相似度或者距離；
5. 返回 Top K 的集合。

4.附錄

下面是Annoy的所有函數方法：

1.** AnnoyIndex(f, metric) **返回可讀寫的新索引，用于存儲f維度向量。metric 可以是 "angular"，"euclidean"，"manhattan"，"hamming"，或"dot"。2. a.add_item(i, v) 用于給索引添加向量v，i 是指第 i 個向量。

3.** a.build(n_trees) ** 用于構建 n_trees 的森林。查詢時，樹越多，精度越高。在調用build后，無法再添加任何向量。

4.** a.save(fn, prefault=False) **將索引保存到磁盤。保存后，不能再添加任何向量。

5.** a.load(fn, prefault=False) ** 從磁盤加載索引。如果prefault設置為True，它將把整個文件預讀到內存中。默認值為False。

6.** a.unload() **釋放索引。

7.** a.get_nns_by_item(i, n, search_k=-1, include_distances=False) **返回第 i 個item的 n 個最近鄰的item。

8.** a.get_nns_by_vector(v, n, search_k=-1, include_distances=False) **與上面的相同，但按向量v查詢。

9. **a.get_item_vector(i) **返回第i個向量。

10.** a.get_distance(i, j) ** 返回向量i和向量j之間的距離。

11.** a.get_n_items() **返回索引中的向量數。

12.** a.get_n_trees() **返回索引中的樹的數量。

13.** a.on_disk_build(fn) **用以在指定文件而不是RAM中建立索引（在添加向量之前執行，在建立之后無需保存）。