對成員函數的結果進行迭代

Question

我的代碼創建了幾個對象實例（每個實例都有一個適應值等等），我想從中根據它們的適應值使用加權選擇對N個獨特對象進行採樣。然後丟棄所有未採樣的物體（但它們需要初始創建以確定其適應值）。

我當前的代碼看起來是這樣的：

vector<Item> getItems(..) { 
    std::vector<Item> items 
    .. // generate N values for items 
    int N = items.size(); 

    std::vector<double> fitnessVals; 
    for(auto it = items.begin(); it != items.end(); ++it) 
     fitnessVals.push_back(it->getFitness()); 

    std::mt19937& rng = getRng(); 
    for(int i = 0, i < N, ++i) { 
     std::discrete_distribution<int> dist(fitnessVals.begin() + i, fitnessVals.end()); 
     unsigned int pick = dist(rng); 
     std::swap(fitnessVals.at(i), fitnessVals.at(pick)); 
     std::swap(items.at(i), items.at(pick)); 
    } 
    items.erase(items.begin() + N, items.end()); 
    return items; 
} 

通常〜萬個實例最初創建的，其中N〜200。適應值是非負的，通常估值爲70。它可能高達3000，但更高的價值越來越不可能。

有沒有一種優雅的方式來擺脫fitnessVals矢量？或者更好的方法來做到這一點？效率很重要，但我也很好奇C++編碼的良好做法。

Answer 1

如果你問你是否可以只使用items向量中的項目來做到這一點，答案是肯定的。以下是一個相當可怕的但卻是非常有效的方式：我爲密度事先道歉。

這包裹在我們自己的設備的另一個迭代器中的毫無防備的容器迭代器;將其與您選擇的成員函數配對。您可能需要在此跳舞const才能使其與您的會員功能選項一起正常工作。我的任務留給你。

template<typename Iter, typename R> 
struct memfn_iterator_s : 
    public std::iterator<std::input_iterator_tag, R> 
{ 
    using value_type = typename std::iterator_traits<Iter>::value_type; 

    memfn_iterator_s(Iter it, R(value_type::*fn)()) 
     : m_it(it), mem_fn(fn) {} 

    R operator*() 
    { 
     return ((*m_it).*mem_fn)(); 
    } 

    bool operator ==(const memfn_iterator_s& arg) const 
    { 
     return m_it == arg.m_it; 
    } 

    bool operator !=(const memfn_iterator_s& arg) const 
    { 
     return m_it != arg.m_it; 
    } 

    memfn_iterator_s& operator ++() { ++m_it; return *this; } 

private: 
    R (value_type::*mem_fn)(); 
    Iter m_it; 
}; 

生成函數如下創建上述畸形：

template<typename Iter, typename R> 
memfn_iterator_s<Iter,R> memfn_iterator(
    Iter it, 
    R (std::iterator_traits<Iter>::value_type::*fn)()) 
{ 
    return memfn_iterator_s<Iter,R>(it, fn); 
} 

這是什麼給你買了就是這樣做的能力：

auto it_end = memfn_iterator(items.end(), &Item::getFitness); 
for(unsigned int i = 0; i < N; ++i) 
{ 
    auto it_begin = memfn_iterator(items.begin()+i, &Item::getFitness); 
    std::discrete_distribution<unsigned int> dist(it_begin, it_end); 
    std::swap(items.at(i), items.at(i+dist(rng))); 
} 
items.erase(items.begin() + N, items.end()); 

無需臨時數組。成員函數在離散分佈需要時調用相應的項目（通常會保留它自己的權重向量，因此重複該努力將是多餘的）。

不知道，如果你能從中得到任何有用的或有用的東西，但想起來很有趣。

Answer 2

它們在STL中有一個分散的分佈是非常好的。據我所知，從一組加權對象（即，與權重成比例的概率）抽樣的最有效的算法是別名方法。這裏有一個Java實現：http://www.keithschwarz.com/interesting/code/?dir=alias-method

我懷疑這就是STL discrete_distribution使用它的原因。如果你打算頻繁地調用你的getItems函數，你可能需要創建一個「FitnessSet」類或其他東西，這樣你就不必在每次你想從同一個集合中抽樣時建立你的分佈。

編輯：另一個建議...如果你想能夠刪除項目，你可以把你的對象存儲在二叉樹。每個節點將包含其下面的子樹中權重的總和，並且對象本身可以在樹葉中。您可以通過一系列日誌（N）投幣來選擇一個對象：在給定節點上，選擇一個介於0和node.subtreeweight之間的隨機數。如果它小於node.left.subtreeweight，則向左;否則向右走。遞歸地繼續，直到你到達葉子。

Answer 3

我會嘗試類似如下（見代碼註釋）：

#include <algorithm>     // For std::swap and std::transform 
#include <functional>    // For std::mem_fun_ref 
#include <random>     // For std::discrete_distribution 
#include <vector>     // For std::vector 
size_t 
get_items(std::vector<Item>& results, const std::vector<Item>& items) 
{ 
    // Copy the items to the results vector. All operations should be 
    // done on it, rather than the original items vector. 
    results.assign(items.begin(), items.end()); 

    // Create the fitness values vector, immediately allocating 
    // the number of doubles required to match the size of the 
    // input item vector. 
    std::vector<double> fitness_vals(results.size()); 

    // Use some STL "magic" ... 
    // This will iterate over the items vector, calling the 
    // getFitness() method on each item, and storing the result 
    // in the fitness_vals vector. 
    std::transform(results.begin(), results.end(), 
        fitness_vals.begin(), 
        std::mem_fun_ref(&Item::getFitness)); 

    // 
    std::mt19937& rng = getRng(); 
    for (size_t i=0; i < results.size(); ++i) { 
     std::discrete_distribution<int> dist(fitness_vals.begin() + i, fitness_vals.end()); 
     unsigned int pick = dist(rng); 
     std::swap(fitness_vals[ii], fitness_vals[pick]); 
     std::swap(results[i], results[pick]); 
    } 

    return (results.size()); 
} 

代替返回結果向量，調用者提供進入其結果應該添加一個載體。另外，原始矢量（作爲第二個參數傳遞）保持不變。如果這不是你所關心的事情，你可以隨時傳遞一個向量並直接使用它。

我沒有看到一種方法沒有適應值向量; discrete_distribution構造函數需要有開始和結束迭代器，所以從我所知道的情況來看，您需要擁有這個向量。

其餘部分基本相同，返回值是結果向量中的項目數，而不是向量本身。

這個例子使用了我發現很有用的一些STL特性（算法，容器，函數），並且是我日常開發的一部分。

---

編輯：調用items.erase()是多餘的; items.begin() + N其中N == items.size()等於items.end()。撥打items.erase()的電話將等同於禁用。