재귀

Question

어쩌면 나 의사 C++ 내 상황을 진술 할 동적 크기 벡터 채우기 - 첫 번째 코드를 :

CONCAT 그냥, 음, 반환 된 벡터를 concats

std:vector<double> sample(someFunctor f, double lower, double upper) { 
    double t = (lower + upper)/2; 
    double newval = f(t); 

    if (f(upper) - newval > epsilon) 
     subsample1 = sample(f, t, upper); 
    if (newval - f(lower) > epsilon) 
     subsample2 = sample(f, lower, t); 

    return concat(subsample2, newval, subsample1); 
} 

. 기본적으로 두 가지 저장된 함수 값 사이에 작은 차이 만있는 방식으로 함수를 샘플링합니다.

모든 반복적 인 단계에서 꽤 많은 메모리 할당 (두 개의 서브 벡터를 할당 한 다음 이들과 다른 요소를 할당)이있는 것처럼 보이기 때문에 위의 방식에 만족하지 않습니다. 이 코드 조각은 성능 측면에서 중요한 알고리즘의 일부에서 실행해야합니다. upper - lower이 상당히 작 으면 f을 평가하는 데 많은 시간이 걸리지 않습니다.

그래서 내 질문 :

• 모든 재귀 호출에 동일한 데이터 구조를 사용하고 그냥 벡터의 현재 부분을 채우기 위해 영리한 방법을 볼 수 있습니까? (필요한 기능 평가의 수는 미리 알려지지 않았 음을 명심하십시오.) 이것에 대한 생각 :

  • 벡터 대신 목록 사용. 하지만 기억 정비가 단순히 복식을 저장하는 데 충분하지 않다고 생각합니다.
  • 벡터에 구멍을 유지하고 채워지는 항목을 나타내는 다른 벡터를 유지합니다. 재귀 호출의 끝은 subsample과 newval 사이에 구멍이 없도록 항목을 이동합니다. 하지만 이제는 두 번째 벡터에 대한 추가 작업으로 이동하여 복사를 전환합니다. 아마도 나쁜 아이디어 일 것입니다.

• 재귀를 완전히 없애는 방법이 있습니까? 그러나 정확성을 위해 위에서 언급 한 분할 정복 패턴을 사용하는 것이 중요합니다. 함수 f은 상한과 하한을 많이 사용하고 이로 인해 많은 성능을 얻습니다.

고맙습니다.

---

는 Space_C0wb0y의 요청에 따라 내 문제를 바꿔 봅시다. 어쩌면 첫 번째 설명이 명확하지 않을 수도 있습니다.

필자는 주어진 간격에서 샘플링 (예 : 특정 지점에서 평가)하려는 일부 기능을 수학적으로 가지고 있습니다.

간격이 [0,100]이라고 가정합니다. 나는 0에서 100까지의 함수 값을 알고있다. 아마도 f(0)=0과 f(100) = 40 일 것이다. 이제 간격 중간 점, 즉 50에서 함수를 평가합니다. 제 함수는 f(50)=10을 반환합니다. f(0)-f(50) <= 10으로, 나는 [0,50] 간격으로 더 이상의 샘플을 필요로하지 않습니다. 그러나, 간격 [50,100]에 대한 추가 계산이 필요합니다. 따라서 다음 (재귀 적) 단계에서 나는 f(75)을 평가합니다. 이제 위의 논리를 재귀 적으로 반복합니다. 끝에

나는 (이) 벡터 이런 대응하는 매개 변수와 함께 나에게 함수 값을주고 싶습니다 :

parameter = vector(0, 50, 56.25, 62.5, 75, 100) 
value  = vector(0, 10, 17.21, 25 34, 40) 

을 내가 (가장 성능이 좋은대로) 접근 방식이를 구축하기 위해 최선을 찾고 있어요 벡터 재귀 적으로.

희망 사항.

Answer 1

공간이 중요한 관심사가 아니므로 재귀를 사용하겠습니다.

1. copy by (return) 값 대신 copy by reference를 사용하십시오.

2. 상수이므로 펑터를 전달할 필요가 없습니다.

3. low 및 high이 정수인 경우 더 빠를 수 있습니다. 그것은 요구 사항에 따라 다르다.

// Thanks to Space_C0wb0y, here we avoid using a global vector 
    // by passing the vector as reference. It's efficient as there 
    // is no copy overhead as well.   
    void sample(vector<double>& samples, double low, double high) 
    { 
     // You can use shift operator if they're integers. 
     double mid = (low + high)/2; 

     // Since they're double, you need prevent them from being too close. 
     // Otherwise, you'll probably see stack overflow. 
     // Consider this case: 
     // f(x): x=1, 0<x<8; x*x, x<=0 or x>=8 
     // low = 1, high = 10, epsilon = 10 
     if (high - low < 0.5) 
     { 
      samples.push_back(f(mid)); 
      return; 
     } 

     // The order you write the recursive calls guarantees you 
     // the sampling order is from left to right. 
     if (f(mid) - f(low) > epsilon) 
     { 
      sample(samples, low, mid); 
     } 

     samples.push_back(f(mid)); 

     if (f(high) - f(mid) > epsilon) 
     { 
      sample(samples, mid, high); 
     } 
    } 

Answer 2

왜 당신이 목록 솔루션을 거절하는지 모르겠다. 최악의 경우 목록의 크기가 원시 데이터의 3 배가됩니다. 각 함수 호출에서 새 벡터를 만들 때 가지고있는 것보다 훨씬 적습니다. 둘 다의 인터페이스가 거의 같기 때문에 많이 변경하지 않아도되므로 사용해보십시오.

Answer 3

나는 다음과 같은 접근 방식을 추천 할 것입니다 :

1. 매개 변수와 값 표현하기 위해 두 벡터 만 쌍보다는 하나의 벡터 또는 사용자 정의 struct를 사용하지 마십시오 :

   struct eval_point { 
       double parameter; 
       double value; 
   }; 
   
   std::vector<eval_point> evaluated_points; 
   

2. 변경 평가 결과를 출력 반복자에 쓰는 알고리즘 :

   template<class F, class output_iterator_type> 
   void sample(F someFunctor, double lower, double upper, 
         output_iterator_type out) { 
       double t = (lower + upper)/2; 
       eval_point point = { t, f(t) }; 
   
       if (f(upper) - point.value > epsilon) { 
        *out = point; 
        ++out; 
        sample(f, t, upper, out); 
       } 
       if (point.value - f(lower) > epsilon) { 
        *out = point; 
        ++out; 
        subsample2 = sample(f, lower, t, out); 
       } 
   } 
   

   위는 출력 반복자를 사용할 때의 모습을 보여주는 의사 코드의 수정입니다. 그것은 테스트되지 않았으므로 정확한지 확신 할 수 없습니다. 원칙적으로 다음과 같이 호출 할 수 있습니다.

   이렇게하면 재귀 호출마다 새 벡터를 만들 필요가 없습니다. 샘플 수에 대한 적절한 하한을 추측 할 수있는 경우, 재 할당이 필요하지 않도록 사전 할당 할 수 있습니다. 이 경우 당신은 이런 식으로 부를 것이다 : 그러면 많은 샘플이 생성 된 방법을 추적하기 위해 별도의 카운터를 추가해야

   std::vector<eval_point> results(lower_bound_for_samples); 
   sample(someFunction, 0, 100, results.begin()); 
   

.