作者：小小明
10年編碼經(jīng)驗(yàn)，熟悉Java、Python和Scala，非常擅長(zhǎng)解決各類復(fù)雜數(shù)據(jù)處理的邏輯，各類結(jié)構(gòu)化與非結(jié)構(gòu)化數(shù)據(jù)互轉(zhuǎn)，字符串解析匹配等等。
至今已經(jīng)幫助至少百名數(shù)據(jù)從業(yè)者解決工作中的實(shí)際問題，如果你在數(shù)據(jù)處理上遇到什么困難，歡迎評(píng)論區(qū)與我交流。
某MOOC課程網(wǎng)站的老師需要統(tǒng)計(jì)每個(gè)學(xué)生成績(jī)最相近的10個(gè)學(xué)生，距離計(jì)算公式是每門課程的成績(jī)之差的絕對(duì)值求和。
例如，學(xué)生1的成績(jī)?yōu)?83,84,86,99,87)，學(xué)生2的成績(jī)?yōu)?83,84,86,99,87)
兩個(gè)學(xué)生的距離為|83-83|+|84-84|+|86-86|+|99-99|+|87-87|=0則判定為這兩個(gè)學(xué)生成績(jī)距離完全相同，這個(gè)距離越大說明兩個(gè)學(xué)生的成績(jī)差異越大。
下面僅使用模擬數(shù)據(jù)展示。
首先讀取數(shù)據(jù)：
import pandas as pd
import numpy as np
import heapq
df = pd.read_csv("學(xué)生成績(jī).csv", encoding="gbk")
df.head()
結(jié)果：
這位老師管理的小班，僅100個(gè)學(xué)生。
采用雙重for循環(huán)遍歷每個(gè)學(xué)生與所有學(xué)生進(jìn)行匹配計(jì)算，也僅1萬次循環(huán)的計(jì)算量，下面我將遍歷每個(gè)學(xué)生，然后內(nèi)層循環(huán)再遍歷每個(gè)學(xué)生進(jìn)行笛卡爾積計(jì)算，最終計(jì)算出每個(gè)學(xué)生分?jǐn)?shù)最接近的10個(gè)學(xué)生。
data = df.values
length = data.shape[0]
names = data[:, 0]
scores = data[:, 1:]
result = []
# 遍歷取出每一行的數(shù)據(jù)
for i in range(length):
# 分別取出當(dāng)前遍歷出來的姓名和成績(jī)列表
name, score = names[i], scores[i]
# 用一個(gè)最小堆保存最接近的10學(xué)生
min_similar_10 = []
for j in range(length):
if i == j:
# 跳過對(duì)自己的比較
continue
# 被比較的學(xué)生姓名和成績(jī)
find_name, find_scores = names[j], scores[j]
# 計(jì)算兩個(gè)學(xué)生成績(jī)的距離
sim_value = np.abs(score-find_scores).sum()
# 將被比較的學(xué)生和對(duì)應(yīng)距離保存到最小堆中
heapq.heappush(min_similar_10, (find_name, sim_value))
# 取出10個(gè)距離最小的學(xué)生
min_similar_10 = heapq.nsmallest(10, min_similar_10, key=lambda x: x[1])
name_distance_dict = dict(min_similar_10)
name_similars, distances = list(
name_distance_dict.keys()), list(name_distance_dict.values())
result.append((name, name_similars, distances))
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
result
最終結(jié)果：
僅耗時(shí)120毫秒以內(nèi)，說明雙重for循環(huán)的算法在100數(shù)據(jù)量時(shí)，可以順利解決這個(gè)問題的。
下面簡(jiǎn)單介紹一下最小堆：
堆是數(shù)據(jù)結(jié)構(gòu)中最常見的一種數(shù)據(jù)結(jié)構(gòu)，是一個(gè)完全二叉樹。最小堆中每一個(gè)節(jié)點(diǎn)的值都小于等于其子樹中每個(gè)節(jié)點(diǎn)的值。
具體的原理，學(xué)過數(shù)據(jù)結(jié)構(gòu)的讀者都懂，沒有學(xué)過的也不用深究。
上面的代碼中使用最小堆的目的是為了避免排序，采用堆化方式查找N個(gè)最小值，基于最小堆的查找，時(shí)間復(fù)雜度在O(logN)~O(N)之間，
遠(yuǎn)比排序的時(shí)間復(fù)雜度O(nlogN)快。
關(guān)于heapq的官方文檔：https://docs.python.org/zh-cn/3/library/heapq.html?highlight=heapq#module-heapq
heapq的實(shí)現(xiàn)源碼：https://github.com/python/cpython/blob/3.9/Lib/heapq.py
如果你對(duì)堆的實(shí)現(xiàn)原理感興趣，可以參考數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記：
https://datastructure.xiaoxiaoming.xyz/#/16.%E5%A0%86
好景不長(zhǎng)，該MOOC網(wǎng)站的管理員后面又希望把歷史班級(jí)所有學(xué)生的分?jǐn)?shù)最接近的10個(gè)學(xué)生都找出來，大概有1W以上的學(xué)生。用上面的代碼跑了一下，10分鐘左右也跑出了結(jié)果，感覺我的代碼處理效果還不錯(cuò)。
我自己也測(cè)試了一下1萬條測(cè)試數(shù)據(jù)：
df = pd.read_csv("學(xué)生成績(jī)_10000.csv", encoding="gbk")
data = df.values
length = data.shape[0]
names = data[:, 0]
scores = data[:, 1:]
result = []
# 遍歷取出每一行的數(shù)據(jù)
for i in range(length):
# 分別取出當(dāng)前遍歷出來的姓名和成績(jī)列表
name, score = names[i], scores[i]
# 用一個(gè)最小堆保存最接近的10學(xué)生
min_similar_10 = []
for j in range(length):
if i == j:
# 跳過對(duì)自己的比較
continue
# 被比較的學(xué)生姓名和成績(jī)
find_name, find_scores = names[j], scores[j]
# 計(jì)算兩個(gè)學(xué)生成績(jī)的距離
sim_value = np.abs(score-find_scores).sum()
# 將被比較的學(xué)生和對(duì)應(yīng)距離保存到最小堆中
heapq.heappush(min_similar_10, (find_name, sim_value))
# 取出10個(gè)距離最小的學(xué)生
min_similar_10 = heapq.nsmallest(10, min_similar_10, key=lambda x: x[1])
name_distance_dict = dict(min_similar_10)
name_similars, distances = list(
name_distance_dict.keys()), list(name_distance_dict.values())
result.append((name, name_similars, distances))
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
result
結(jié)果：
耗時(shí)是12.5分鐘。
雖然網(wǎng)站管理員對(duì)這個(gè)代碼已經(jīng)滿意，但對(duì)于我來說速度還是太慢，要跑這么大的數(shù)據(jù)量，代碼還是優(yōu)化一下比較好，于是我使用numpy向量化操作，使程序在2分鐘內(nèi)對(duì)1萬條數(shù)據(jù)跑出了結(jié)果。下面是處理代碼：
考慮到部分讀者沒有看懂最小堆的操作，這次我將分步拆解下面這套代碼的處理邏輯。
首先對(duì)本文開頭的100條數(shù)據(jù)進(jìn)行測(cè)試，獲取源數(shù)據(jù)的姓名和分?jǐn)?shù)數(shù)組：
import pandas as pd
import numpy as np
import heapq
df = pd.read_csv("學(xué)生成績(jī).csv", encoding="gbk")
data = df.values
length = data.shape[0]
names = data[:, 0]
scores = data[:, 1:]
print(names[:5])
print(scores[:5])
結(jié)果：
['學(xué)生1' '學(xué)生2' '學(xué)生3' '學(xué)生4' '學(xué)生5']
[[71 82 81 84 73 95 62 96 96 87 61 78 79 89 98 80]
[57 91 99 74 93 93 58 74 89 84 63 62 78 57 94 74]
[72 59 76 60 99 71 73 74 72 74 85 79 100 88 80 91]
[71 62 81 80 57 84 92 95 63 59 84 64 90 58 60 75]
[83 62 95 76 57 75 97 57 65 63 84 73 74 59 62 93]]
遍歷第一次就break結(jié)束，取出第一個(gè)學(xué)生用于測(cè)試：
for i in range(length):
name, score = names[i], scores[i]
print(name, score)
break
結(jié)果：
學(xué)生1 [77 89 60 99 83 80 95 93 94 82 92 93 96 98 70 84]
利用numpy廣播變量的特性一次性求出該學(xué)生與所有學(xué)生（含自己）的距離：
score_diff = np.abs(scores-score).sum(axis=1)
score_diff
結(jié)果：
array([0, 322, 248, 203, 215, 366, 198, 224, 299, 229, 274, 240, 253, 238,
183, 239, 223, 344, 320, 221, 291, 264, 273, 309, 307, 243, 258,
231, 225, 185, 234, 324, 315, 247, 247, 232, 179, 210, 238, 261,
175, 252, 259, 254, 330, 270, 193, 248, 252, 214, 175, 219, 262,
256, 265, 249, 263, 180, 270, 294, 260, 195, 272, 240, 213, 181,
252, 292, 261, 233, 238, 205, 237, 241, 244, 234, 255, 151, 228,
241, 173, 174, 221, 248, 191, 249, 243, 224, 252, 266, 229, 231,
228, 346, 232, 273, 269, 336, 294, 277], dtype=object)
由于上面的距離包含自身，所以先取出距離最短的11個(gè)學(xué)生的索引，再刪除自身的索引：
min_similar_index = np.argpartition(score_diff, 11)[:11].tolist()
min_similar_index.remove(i)
min_similar_index
結(jié)果：
[77, 80, 81, 40, 50, 36, 57, 65, 14, 29]
根據(jù)這10個(gè)學(xué)生的索引讀取所需要的數(shù)據(jù)：
name_similars = names[min_similar_index]
distances = score_diff[min_similar_index]
print(name_similars)
print(distances)
結(jié)果：
['學(xué)生78' '學(xué)生81' '學(xué)生82' '學(xué)生41' '學(xué)生51' '學(xué)生37' '學(xué)生58' '學(xué)生66' '學(xué)生15' '學(xué)生30']
[151 173 174 175 175 179 180 181 183 185]
這樣我們就已經(jīng)計(jì)算出該學(xué)生成績(jī)最接近的10個(gè)學(xué)生的姓名和距離。
然后整理一下完整處理代碼：
import pandas as pd
import numpy as np
import heapq
df = pd.read_csv("學(xué)生成績(jī).csv", encoding="gbk")
data = df.values
length = data.shape[0]
names = data[:, 0]
scores = data[:, 1:]
result = []
for i in range(length):
name, score = names[i], scores[i]
score_diff = np.abs(scores-score).sum(axis=1)
min_similar_index = np.argpartition(score_diff, 11)[:11].tolist()
min_similar_index.remove(i)
name_similars = names[min_similar_index]
distances = score_diff[min_similar_index]
result.append((name, name_similars, distances))
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
result
結(jié)果：
下面再針對(duì)一萬條數(shù)據(jù)跑一跑：
df = pd.read_csv("學(xué)生成績(jī)_10000.csv", encoding="gbk")
data = df.values
length = data.shape[0]
names = data[:, 0]
scores = data[:, 1:]
result = []
for i in range(length):
name, score = names[i], scores[i]
score_diff = np.abs(scores-score).sum(axis=1)
min_similar_index = np.argpartition(score_diff, 11)[:11].tolist()
min_similar_index.remove(i)
name_similars = names[min_similar_index]
distances = score_diff[min_similar_index]
result.append((name, name_similars, distances))
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
result
結(jié)果：
可以看到耗時(shí)為1分48秒，相對(duì)直接使用笛卡爾積快了很多倍。
雖然上面的優(yōu)化已經(jīng)大幅度提升了程序性能，但畢竟仍然需要雙重遍歷O(n^2)時(shí)間復(fù)雜度的方法。萬一哪天網(wǎng)站要求對(duì)10萬個(gè)學(xué)生進(jìn)行計(jì)算呢？時(shí)間又要多翻了幾十倍，耗時(shí)要達(dá)到好幾個(gè)小時(shí)。我轉(zhuǎn)而一想直接用KNN內(nèi)部的ball_tree來解決這個(gè)問題吧。
（關(guān)于使用KNN查找最近點(diǎn)的問題可參考很早之前的一篇文章：https://blog.csdn.net/as604049322/article/details/112385553）
先使用10000條學(xué)生成績(jī)的數(shù)據(jù)進(jìn)行測(cè)試，讀取這10000條學(xué)生成績(jī)數(shù)據(jù)：
df = pd.read_csv("學(xué)生成績(jī)_10000.csv", encoding="gbk")
df
結(jié)果：
然后取出需要被訓(xùn)練的數(shù)據(jù)：
# 取出用于被KNN訓(xùn)練的數(shù)據(jù)
data = df.iloc[:, 1:].values
# y本身用于標(biāo)注每條數(shù)據(jù)屬于哪個(gè)類別，但我們并不使用KNN的分類功能，所以統(tǒng)一全部標(biāo)注為類別0
y = np.zeros(data.shape[0], dtype='int8')
print(data[:5])
print(y[:5])
結(jié)果：
[[ 77 89 60 99 83 80 95 93 94 82 92 93 96 98 70 84]
[ 90 63 72 57 100 85 63 62 67 77 82 68 81 79 100 71]
[ 71 71 82 72 62 70 82 63 92 69 97 97 82 69 63 57]
[ 88 78 88 61 72 61 77 93 94 88 86 95 84 70 73 94]
[ 66 67 59 70 75 67 79 74 57 84 96 67 93 87 58 83]]
[0 0 0 0 0]
創(chuàng)建KNN訓(xùn)練器，并進(jìn)行訓(xùn)練：
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=1, algorithm='ball_tree', p=1)
knn.fit(data, y)
distance, similar_points = knn.kneighbors(
data, n_neighbors=11, return_distance=True)
distance = distance.astype("int", copy=False)
print(distance[:5])
print(similar_points[:5])
結(jié)果：
訓(xùn)練耗時(shí)為3.4秒。
n_neighbors是KNN用來分類的參數(shù)，我們并不使用分類，將其指定的越小，越能減少無用的計(jì)算量，但是這個(gè)參數(shù)必須比0大，所以我指定為1。
而需求方要求的距離計(jì)算公式顯然就等價(jià)于曼哈頓距離，所以我將p指定為1。
knn.kneighbors則用來計(jì)算最近的點(diǎn)，n_neighbors指定為11是因?yàn)榻Y(jié)果會(huì)包含自身，后面去除自身后結(jié)果是10。
由于sklearn最終計(jì)算出來的距離是float浮點(diǎn)數(shù)類型，而這個(gè)需求只可能產(chǎn)生整數(shù)距離，所以將其轉(zhuǎn)換為整數(shù)。
上面訓(xùn)練完就相當(dāng)于已經(jīng)計(jì)算出了結(jié)果，下面我再將結(jié)果整理成需要的格式：
names = df['姓名']
result = []
for i, name in names.iteritems():
name_similar_indexs = similar_points[i].tolist()
self_index = name_similar_indexs.index(i)
name_similar_indexs.pop(self_index)
name_similars = names[name_similar_indexs].tolist()
distances = distance[i].tolist()
distances.pop(self_index)
result.append((name, name_similars, distances))
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
result
結(jié)果：
對(duì)于10000條數(shù)據(jù)ball_tree的計(jì)算總耗時(shí)為5秒左右?？梢娤鄬?duì)于前面的雙重遍歷的方法速度已經(jīng)提高了N倍。
關(guān)于KD-tree算法和Ball-tree算法的原理可參考：
https://www.cnblogs.com/eyeszjwang/articles/2429382.html
https://www.cnblogs.com/lesleysbw/p/6074662.html
https://www.zhihu.com/question/30957691
為了測(cè)試方便，不再用excel來生成數(shù)據(jù)，而是直接使用python。
python直接生成測(cè)試數(shù)據(jù)的方法，以生成10條數(shù)據(jù)為例：
size = 100000
data = np.c_[np.arange(1, size+1).reshape((-1, 1)),
np.random.randint(56, 101, size=(size, 16))]
df = pd.DataFrame(data, columns=["姓名", "Python", "C/C++", "Java", "Scala", "數(shù)據(jù)結(jié)構(gòu)", "離散數(shù)學(xué)",
"計(jì)算機(jī)體系結(jié)構(gòu)", "編譯原理", "計(jì)算機(jī)網(wǎng)絡(luò)", "數(shù)據(jù)庫原理", "計(jì)算機(jī)圖形學(xué)",
"自然語言處理", "嵌入式系統(tǒng)及應(yīng)用", "網(wǎng)絡(luò)信息與安全", "計(jì)算機(jī)視覺", "人工智能"])
df["姓名"] = "學(xué)生"+df["姓名"].astype(str)
df
結(jié)果：
然后使用上面相同的代碼分別測(cè)試1w條、2w條、3w條、…、10w條：
1萬條耗時(shí)5.3秒。
2萬條耗時(shí)15.8秒。
3萬條耗時(shí)32.3秒。
4萬條耗時(shí)60.75秒。
這時(shí)間增長(zhǎng)趨勢(shì)好像也不是線性增長(zhǎng)而是指數(shù)增長(zhǎng)，下面先就記錄一下多少條記錄時(shí)耗時(shí)多久吧：
import pandas as pd
import numpy as np
import time
from sklearn.neighbors import KNeighborsClassifier
times = {}
for size in np.r_[np.arange(1000, 10001, 1000), np.arange(20000, 60001, 10000)]:
data = np.c_[np.arange(1, size+1).reshape((-1, 1)),
np.random.randint(56, 101, size=(size, 16))]
df = pd.DataFrame(data, columns=["姓名", "Python", "C/C++", "Java", "Scala", "數(shù)據(jù)結(jié)構(gòu)", "離散數(shù)學(xué)",
"計(jì)算機(jī)體系結(jié)構(gòu)", "編譯原理", "計(jì)算機(jī)網(wǎng)絡(luò)", "數(shù)據(jù)庫原理", "計(jì)算機(jī)圖形學(xué)",
"自然語言處理", "嵌入式系統(tǒng)及應(yīng)用", "網(wǎng)絡(luò)信息與安全", "計(jì)算機(jī)視覺", "人工智能"])
df["姓名"] = "學(xué)生"+df["姓名"].astype(str)
start_time = time.perf_counter()
# 取出用于被KNN訓(xùn)練的數(shù)據(jù)
data = df.iloc[:, 1:].values
# y本身用于標(biāo)注每條數(shù)據(jù)屬于哪個(gè)類別，但我并不使用KNN的分類功能，所以統(tǒng)一全部標(biāo)注為類別0
y = np.zeros(data.shape[0], dtype='int8')
knn = KNeighborsClassifier(n_neighbors=1, algorithm='ball_tree', p=1)
knn.fit(data, y)
distance, similar_points = knn.kneighbors(
data, n_neighbors=11, return_distance=True)
distance = distance.astype("int", copy=False)
names = df['姓名']
result = []
for i, name in names.iteritems():
name_similar_indexs = similar_points[i].tolist()
self_index = name_similar_indexs.index(i)
name_similar_indexs.pop(self_index)
name_similars = names[name_similar_indexs].tolist()
distances = distance[i].tolist()
distances.pop(self_index)
result.append((name, name_similars, distances))
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
take_time = time.perf_counter()-start_time
print(f"{size}條數(shù)據(jù)耗時(shí){take_time:.2f}秒")
times[size] = take_time
time_df = pd.DataFrame.from_dict(times, orient='index', columns=["time"])
結(jié)果：
1000條數(shù)據(jù)耗時(shí)0.29秒
2000條數(shù)據(jù)耗時(shí)0.59秒
3000條數(shù)據(jù)耗時(shí)0.98秒
4000條數(shù)據(jù)耗時(shí)1.40秒
5000條數(shù)據(jù)耗時(shí)1.97秒
6000條數(shù)據(jù)耗時(shí)2.44秒
7000條數(shù)據(jù)耗時(shí)3.00秒
8000條數(shù)據(jù)耗時(shí)3.74秒
9000條數(shù)據(jù)耗時(shí)4.41秒
10000條數(shù)據(jù)耗時(shí)5.23秒
20000條數(shù)據(jù)耗時(shí)15.92秒
30000條數(shù)據(jù)耗時(shí)31.75秒
40000條數(shù)據(jù)耗時(shí)64.25秒
50000條數(shù)據(jù)耗時(shí)132.26秒
60000條數(shù)據(jù)耗時(shí)220.87秒
從這走勢(shì)來看有點(diǎn)像二次函數(shù)或冪次函數(shù)，我們假設(shè)這是一個(gè)二次函數(shù)然后使用numpy擬合這條曲線，并預(yù)估10萬數(shù)據(jù)的耗時(shí)：
from numpy import polyfit, poly1d
import matplotlib.pyplot as plt
%matplotlib inline
x = np.arange(1000, 100001, 1000)
y = poly1d(polyfit(time_df.index, time_df.time, 2))
plt.figure(figsize=(10, 6))
plt.plot(time_df.index, time_df.time, 'rx')
plt.plot(x, y(x), 'b:')
plt.show()
print(f"10萬條數(shù)據(jù)預(yù)計(jì)耗時(shí){y(100000):.2f}秒")
結(jié)果：
預(yù)計(jì)耗時(shí)11分鐘。
不過實(shí)際測(cè)試了一下，12分鐘也并沒有出結(jié)果，說明曲線擬合的效果還不是太準(zhǔn)。
認(rèn)真觀察原始數(shù)據(jù)（紅色點(diǎn)）和擬合曲線（藍(lán)色線），可能這個(gè)曲線實(shí)際并不是二次函數(shù)，而是三次以上的函數(shù)或冪次函數(shù)，下面使用3次函數(shù)進(jìn)行擬合：
from numpy import polyfit, poly1d
import matplotlib.pyplot as plt
%matplotlib inline
x = np.arange(1000, 100001, 1000)
y = poly1d(polyfit(time_df.index, time_df.time, 3))
plt.figure(figsize=(10, 6))
plt.plot(time_df.index, time_df.time, 'rx')
plt.plot(x, y(x), 'b:')
plt.show()
print(f"10萬條數(shù)據(jù)預(yù)計(jì)耗時(shí){y(100000):.2f}秒")
結(jié)果：
預(yù)估耗時(shí)為17分鐘。
實(shí)際耗時(shí)呢？
import pandas as pd
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
size = 100000
data = np.c_[np.arange(1, size+1).reshape((-1, 1)),
np.random.randint(56, 101, size=(size, 16))]
df = pd.DataFrame(data, columns=["姓名", "Python", "C/C++", "Java", "Scala", "數(shù)據(jù)結(jié)構(gòu)", "離散數(shù)學(xué)",
"計(jì)算機(jī)體系結(jié)構(gòu)", "編譯原理", "計(jì)算機(jī)網(wǎng)絡(luò)", "數(shù)據(jù)庫原理", "計(jì)算機(jī)圖形學(xué)",
"自然語言處理", "嵌入式系統(tǒng)及應(yīng)用", "網(wǎng)絡(luò)信息與安全", "計(jì)算機(jī)視覺", "人工智能"])
df["姓名"] = "學(xué)生"+df["姓名"].astype(str)
# 取出用于被KNN訓(xùn)練的數(shù)據(jù)
data = df.iloc[:, 1:].values
# y本身用于標(biāo)注每條數(shù)據(jù)屬于哪個(gè)類別，但我并不使用KNN的分類功能，所以統(tǒng)一全部標(biāo)注為類別0
y = np.zeros(data.shape[0], dtype='int8')
knn = KNeighborsClassifier(n_neighbors=1, algorithm='ball_tree', p=1)
knn.fit(data, y)
distance, similar_points = knn.kneighbors(
data, n_neighbors=11, return_distance=True)
distance = distance.astype("int", copy=False)
names = df['姓名']
結(jié)果：
訓(xùn)練耗時(shí)13分鐘。
from tqdm.notebook import tqdm
result = []
pbar = tqdm(total=size)
for i, name in names.items():
pbar.update(1)
name_similar_indexs = similar_points[i].tolist()
self_index = name_similar_indexs.index(i)
name_similar_indexs.pop(self_index)
name_similars = names[name_similar_indexs].tolist()
distances = distance[i].tolist()
distances.pop(self_index)
result.append((name, name_similars, distances))
pbar.close()
result = pd.DataFrame(result, columns=["姓名", "分?jǐn)?shù)最接近的10個(gè)學(xué)生", "距離"])
result
整理結(jié)果耗時(shí)半分鐘，實(shí)際耗時(shí)是14分鐘。
雖然14分鐘也比較慢，但相對(duì)前面的笛卡爾積的算法需要耗時(shí)好幾小時(shí)而言已經(jīng)大幅度提升程序計(jì)算性能，節(jié)約了計(jì)算時(shí)間。
今天我向你演示了如何使用最小堆和numpy來快速計(jì)算每個(gè)學(xué)生分?jǐn)?shù)最接近的10個(gè)學(xué)生，可以看到在數(shù)據(jù)量小于一萬時(shí)，這種笛卡爾積的算法還可以接受，但一旦達(dá)到2萬以上，基本上就慢的難以忍受了。所以我使用ball_tree來計(jì)算這個(gè)距離，1W數(shù)據(jù)量?jī)H耗時(shí)5秒。
但是當(dāng)數(shù)據(jù)量達(dá)到5萬以上時(shí)，ball_tree也有點(diǎn)慢了，但也相對(duì)笛卡爾積的算法還是快了很多。
最后，我使用numpy擬合時(shí)間曲線，在二次函數(shù)的擬合下預(yù)估10w數(shù)據(jù)量時(shí)ball_tree的耗時(shí)為12分鐘，三次函數(shù)的擬合下是17分鐘。而實(shí)際測(cè)試的結(jié)果是14分鐘，介于2者之間。
歡迎下方留言或評(píng)論，分享你的看法。
聯(lián)系客服
