首先，我想說(shuō)我不是在尋找代碼，我是在尋找算法。動(dòng)機(jī)：我正在編寫(xiě)復(fù)雜實(shí)時(shí)軟件系統(tǒng)的頂級(jí)測(cè)試。它運(yùn)行所有軟件組件（約 20 個(gè)進(jìn)程，約 100 個(gè)線程），設(shè)置假數(shù)據(jù)源（rtsp 視頻源）并將準(zhǔn)備好的數(shù)據(jù)（視頻文件）提供給系統(tǒng)，記錄系統(tǒng)響應(yīng)（事件），然后停止系統(tǒng)準(zhǔn)備好的測(cè)試數(shù)據(jù)已發(fā)送。由于測(cè)試數(shù)據(jù)始終相同，我希望測(cè)試的系統(tǒng)能夠在正確的時(shí)間（從測(cè)試開(kāi)始）提供正確的響應(yīng)（事件）。然后，我將生成的響應(yīng)（事件）與預(yù)期事件（手動(dòng)準(zhǔn)備）進(jìn)行比較，我希望這些事件都在那里，可能會(huì)有一些小的時(shí)間差異，我會(huì)限制一些給定的時(shí)間差異，比如說(shuō) 5 秒time-tolerance。假設(shè)測(cè)試的系統(tǒng)應(yīng)該在 1500 秒長(zhǎng)的視頻中檢測(cè)動(dòng)物，我觀看了它并記下了 5 種動(dòng)物以及它們出現(xiàn)在視頻中的時(shí)間：at 10s - a sparrowat 20s - a catat 50s - a rabbitat 100s - an owlat 1000s - a bear基于此，我會(huì)編寫(xiě)expected_events集合：expected_events = [ Event(10, 'sparrow'), Event(20, 'cat'), Event(50, 'rabbit'), Event(100, 'owl') Event(1000, 'bear')]我希望能夠知道真實(shí)檢測(cè)到的事件（這將受到處理器負(fù)載、磁盤(pán)使用、網(wǎng)絡(luò)使用 atd 的影響，因?yàn)檫@是真實(shí)計(jì)算機(jī)上的多進(jìn)程系統(tǒng)）與這些事件的匹配程度expected_eevents。假設(shè)測(cè)試的系統(tǒng)返回：detected_events = [ Event(10.1, 'sparrow'), Event(19.5, 'cat'), Event(50.2, 'rabbit'), Event(99.3, 'owl') Event(1000.2, 'bear')]我認(rèn)為這是正確的，與預(yù)期事件 100% 匹配，所有事件都存在，時(shí)間差異如下time-tolerance：matches = [ {'name': 'sparrow', 'detected': 10.1, 'expected': 10, 'time-diff': 0.1}, {'name': 'cat', 'detected': 19.5, 'expected': 20, 'time-diff': 0.5}, {'name': 'rabbit', 'detected': 50.2, 'expected': 50, 'time-diff': 0.2}, {'name': 'owl', 'detected': 99.3, 'expected': 100, 'time-diff': 0.7}, {'name': 'bear', 'detected': 1000.2, 'expected': 1000, 'time-diff': 0.2},]如果測(cè)試的系統(tǒng)返回：detected_events = [ Event(10.1, 'sparrow'), Event(50.2, 'rabbit'), Event(99.3, 'owl') Event(1010.5, 'bear')]我認(rèn)為這是失敗的，因?yàn)椋核鼪](méi)有檢測(cè)到貓熊被發(fā)現(xiàn)晚了 10.5 秒因此，只有 5 個(gè)中的 3 個(gè)真正匹配，結(jié)果應(yīng)該是 60% 匹配因此，我需要一種評(píng)估方法，detected_events以便expected_events能夠評(píng)估被測(cè)試系統(tǒng)的工作效果。簡(jiǎn)單化由于匹配事件類型對(duì)于解決問(wèn)題至關(guān)重要，并且可以單獨(dú)匹配每個(gè)事件類型，因此我將進(jìn)行以下簡(jiǎn)單說(shuō)明：所有事件都是相同的 - 即只有事件的時(shí)間很重要，因此事件將僅由時(shí)間戳表示時(shí)間戳將使其int更易于閱讀我認(rèn)為什么是“好的”匹配：正如你們?cè)S多人在評(píng)論中指出的那樣，除了忽略具有時(shí)間差 > 的匹配之外，實(shí)際上我沒(méi)有評(píng)估最終匹配的指標(biāo)time-tolerance。這使得它變得有點(diǎn)困難，但我認(rèn)為它很直觀 - 我知道什么時(shí)候應(yīng)該發(fā)生什么，我將其與實(shí)際事件進(jìn)行比較，我會(huì)嘗試盡可能地匹配它們以確保：匹配盡可能多的預(yù)期事件每個(gè)detected_event匹配expected_event必須在給定的時(shí)間容限內(nèi)同時(shí)發(fā)生。所以我會(huì)考慮“正確”匹配（有 5 秒的時(shí)間容差）：
2 回答
慕斯王
TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超2個(gè)贊
我將遵循您的要求，并提供一種非編程方法，但僅是我認(rèn)為的邏輯（半數(shù)學(xué)）方法。
算法步驟：
讓我們將閾值定義為
T用無(wú)關(guān)值填充較小的列表（例如無(wú)） - 只是為了確保尺寸一致
通過(guò)取一個(gè)列表中每個(gè)元素與另一個(gè)列表中元素的絕對(duì)值來(lái)創(chuàng)建相似度矩陣，我們將矩陣定義為 S。
澄清：S[i,j]指的是列表A中的第i個(gè)元素與列表B中的第j個(gè)元素之間的差異
創(chuàng)建二進(jìn)制矩陣 B，其中滿足閾值 Critirea 的每個(gè)元素為 1，否則為 0 (MATLAB-> B=S<L)
例如：
???????0?0?0 ???B?=???0?1?1 ???? ???????1?0?0
假設(shè) X 維度代表列表 A，Y 維度代表列表 B，則：
B[2]?===?A[2] B[2]?===?A[3] B[3]?===?A[1]?(===?means?that?two?elements?satisfy?the?criteria?of?similarity)
現(xiàn)在 - 問(wèn)題變得更加數(shù)學(xué)化，為了找到最佳匹配，您可以使用以下建議之一：
蠻力（我認(rèn)為不太優(yōu)雅的方法）：
選擇為 1 的元素（在未標(biāo)記的行和列中）
將他的整個(gè)列和行標(biāo)記為已標(biāo)記
繼續(xù)選擇另外1個(gè)，直到?jīng)]有合法位置為止，求和為
score對(duì)所有選項(xiàng)迭代執(zhí)行此操作并選擇最高的選項(xiàng)
score
更優(yōu)雅的方法：
迭代所有列的排列（對(duì)于 B 矩陣）
如果 Trace 或?qū)蔷€等于 len(A) 則完成（找到所有元素的匹配）
選擇具有最高 TRACE（或相反對(duì)角線）的排列 最壞情況下的排列數(shù)量當(dāng)然是 N?。ㄆ渲蠳是B的維度）
正如文檔所述 - 該算法試圖找到所有可能的矩陣排列的最小跟蹤 - 因此只需將其-B作為參數(shù)即可。
總體示例（最后一步采用更優(yōu)雅的方法）：
A = [1,5,7]
B = [6,6,2]
T = 2
S =?
5 5 1?
1 1 3
1 1 5
B =?
0 0 1
1 1 0
1 1 0
permutations of columns:
1-?
0 0 1
1 1 0
1 1 0
Trace = 1
other-diagonal = 3
Done -- > no need for more permutations because len(other-diagonal) == 3
A[1] =1 === B[3] =2
A[2] =5 === B[2] =6
A[3] =7 === B[1] =6
請(qǐng)隨意詢問(wèn)，或提供您可能有的任何見(jiàn)解
慕仙森
TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊
我剛剛發(fā)現(xiàn) scipy python 包中“匈牙利算法”（賦值問(wèn)題）有很好的實(shí)現(xiàn)：
https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html
示例（對(duì)于expected, detected，metric請(qǐng)參閱問(wèn)題的示例代碼）：
from scipy.optimize import linear_sum_assignment
...
def match_events(expected, detected, metric, tolerance=5):
# some arbitrary large value used to prevent impossible matches
dont_match = 1000 * tolerance
def modified_metric(e, d):
dt = metric(e, d)
return dt if dt <= tolerance else dont_match
cost_matrix = [
[
modified_metric(exp, det)
for det in detected
]
for exp in expected
]
row_idx, col_idx = linear_sum_assignment(cost_matrix)
for e_idx, d_idx in zip(row_idx, col_idx):
dt = cost_matrix[e_idx][d_idx]
if dt <= time_tolerance:
yield (expected[e_idx], detected[d_idx], dt)
它不是很優(yōu)雅，因?yàn)槲冶仨氁阅撤N方式將匹配限制為tolerance，但匈牙利算法僅適用于所有可能組合的矩陣，因此我使用dont_matchvalue 來(lái)標(biāo)記這些情況。
添加回答
舉報(bào)
0/150
提交
取消