如何使這個向量枚舉代碼更快？

我有三個大型矢量集：A，B1和B2。這些集存儲在磁盤上的文件中。對於A的每個向量a，我需要檢查它是否可以表示爲a = b1 + b2，其中b1來自B1並且b2來自B2。向量有20個組件，所有組件都是非負數。如何使這個向量枚舉代碼更快？

如何我現在解決這個問題的（僞）：

foreach a in A 
    foreach b1 in B1 
    for i = 1 to 20 
     bt[i] = a[i] - b1[i] 
     if bt[i] < 0 then try next b1 
    next i 

    foreach b2 in B2 
     for i = 1 to 20 
     if bt[i] != b2[i] then try next b2 
     next i 

     num_of_expansions++ 
    next b2 
    next b1 
next a

我的問題：
1.如何使更快，如果任何想法？
2.如何使它平行？
3.對於B1，B2，...，Bk，k> 2時的問題1，2？

來源

2011-05-08 Leo

散列呢？這並沒有完全想到，但我在想：（1）散列b1 + b2的所有組合，並將總和b1和b2放入散列表中。然後檢查A的每個元素。如果它在表格中，則抓住b1 + b2組合。不知道你會做什麼，如果你需要索引...哈希？ – 2011-05-08 03:20:30

集合有多大？你能從磁盤讀取所有的文件，然後將它們保存在內存中嗎？ – svick 2011-05-08 12:47:42

@mattkc：謝謝，這是要考慮的事情。 @svick：set A擁有數百萬個向量，每個向量包含數十萬個向量。是的，我可以將它們加載到內存中，從而加快搜索速度。 – Leo 2011-05-08 15:59:08

您可以按照規範對B1和B2進行排序。如果a = b1 + b2，那麼|| a || = || b1 + b2 || < = || b1 || + || b2 ||，因此對於任何a和b1，都可以有效地消除所有具有標準的B2的元素< || a || - || b1 ||。在B1和B2中也可能有一些方法來使用規範的分佈來決定是否切換這兩組中的角色。（我沒有看到如何做到這一點，但在我看來，如果B1和B2中的規範分佈顯着不同，那麼類似這樣的事情應該會持續下去。）

至於使它平行，它似乎每個循環都可以變成一個並行計算，因爲一個內部迭代的所有計算都獨立於所有其他迭代。

編輯

繼續分析：因爲B2 = A - B1，我們也有|| B2 || < = || a || + || b1 ||。因此，對於任何給定的a和b1，您可以將B2中的搜索限制爲那些範圍爲|| a ||的範數的元素± || b1 ||。這表明，對於B1你應該選擇平均範數最小的集合。

來源

2011-05-08 03:36:47

謝謝，這可能會有用。 – Leo 2011-05-08 15:59:58

如何使這個向量枚舉代碼更快？

回答

相關問題