멤버 함수의 결과 반복하기

Question

필자는 피트니스 값을 기반으로 한 가중치 적용 선택을 사용하여 N 개의 고유 오브젝트를 샘플링하려는 여러 오브젝트 인스턴스 (각 인스턴스가 적합도 값을 갖는 인스턴스)를 만드는 코드를 가지고 있습니다. 샘플링되지 않은 모든 객체는 버려집니다 (그러나 처음에는 체력 값을 결정하기 위해 만들어야합니다). N은 ~ 200 인으로,

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; 
} 

는 일반적으로 ~ 10,000 인스턴스가 처음 생성됩니다

내 현재 코드는 다음과 같이 보인다. 적합도 값은 음수가 아니며 대개 ~ 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()); 

합니다. 멤버 함수는 불연속 분포 (대개 가중치 벡터를 유지하므로 그 노력이 중복 될 수 있도록)가 필요할 때 각 항목에 대해 호출됩니다.

Dunno에서 도움이되거나 도움이 될만한 것이 있다면 생각해 보는 것이 재미있었습니다.

Answer 2

STL에 이산 분포가있어서 꽤 좋습니다. 필자가 아는 한, 가중치가있는 객체 집합 (즉, 가중치에 비례하는 확률)에서 샘플링하는 가장 효율적인 알고리즘이 별칭 메서드입니다. Java 구현은 다음과 같습니다. http://www.keithschwarz.com/interesting/code/?dir=alias-method

STL discrete_distribution은 어쨌든 사용합니다. getItems 함수를 자주 호출하려는 경우 "FitnessSet"클래스 또는 다른 것을 만들어서 같은 세트에서 샘플링 할 때마다 배포판을 만들지 않아도됩니다.

EDIT : 다른 제안 ... 항목을 삭제하려면 개체를 이진 트리에 저장할 수 있습니다. 각 노드는 하위 트리에있는 가중치의 합계를 포함하고 오브젝트 자체는 잎에있을 수 있습니다. 일련의 로그 (N) 코인 토스 (tosses)를 통해 오브젝트를 선택할 수 있습니다. 주어진 노드에서 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 생성자에는 begin과 end 반복자가 있어야하므로, 내가 알 수있는 바로는이 벡터가 있어야합니다.

나머지는 기본적으로 동일하며 반환 값은 벡터 자체가 아니라 결과 벡터의 항목 수입니다.

이 예제는 유용한 것으로 밝혀진 수많은 STL 기능 (알고리즘, 컨테이너, 펑터)을 사용하며 일상적인 개발 과정의 일부입니다.

---

편집 : items.erase()에 대한 호출이 불필요합니다. items.begin() + N 여기서 N == items.size()은 items.end()과 같습니다. items.erase()으로 전화하면 아무 것도 할 수 없습니다.