주어진 벡터의 최소값 찾기

Question

주어진 벡터 세트에서 각 열의 가장 작은 값을 효율적으로 찾는 방법은 무엇입니까?

예를 들어, 다음과 같은 프로그램을 고려 :

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <cstdlib> 
using namespace std; 

typedef vector<double> v_t; 

int main(){ 

v_t v1,v2,v3; 

for (int i = 1; i<10; i++){ 
v1.push_back(rand()%10); 
v2.push_back(rand()%10); 
v3.push_back(rand()%10); 
} 

copy(v1.begin(), v1.end(), ostream_iterator<double>(cout, " ")); 
    cout << endl; 
copy(v2.begin(), v2.end(), ostream_iterator<double>(cout, " ")); 
    cout << endl; 
copy(v3.begin(), v3.end(), ostream_iterator<double>(cout, " ")); 
    cout << endl; 
} 

나는 모든 컬럼의 가장 작은 값을 찾으려는 출력이 프로그램에서

3 5 6 1 0 6 2 8 2 
6 3 2 2 9 0 6 7 0 
7 5 9 7 3 6 1 9 2 

을하자를 (3 개 주어진 벡터) 그것을 벡터에 넣으십시오. 이 작업을 수행 할 수있는 효율적인 방법은

3 3 2 1 0 0 1 7 0 

있습니까 : 나는 벡터 v_t vfinal를 정의하려면이 프로그램에서 그 값을 가질 것인가? 내 프로그램은 매우 많은 수의 벡터 중에서 가장 작은 값을 찾아야하기 때문에 효율적이라고 말합니다. 고맙습니다.

는

업데이트 : 나는 내 이전 프로그램 중 하나에서 사용하는 다음과 같은 것을 사용하려고 해요

는

int count = std::inner_product(A, A+5, B, 0, std::plus<int>(), std::less<int>()); 

이 두 배열 A와 B 사이의 최소 요소의 수를 계산 최소의 값을 찾기 위해 유사한 종류의 함수를 반복하고 사용할 수 있다면 충분히 효율적이지 않습니까? 내가 할 수 있다고 주장하지 않습니다. 그것은 개선 될 수있는 아이디어 일 뿐이지 만 어떻게해야할지 모르겠다.

Answer 1

이 경우 std::transform을 사용할 수 있습니다. 루프는 여전히 존재하며, 알고리즘 내부에 숨겨져 있습니다. 처리 할 각 추가 벡터는 std::transform에 대한 호출입니다.

두 선형 패스에서 예제 문제가 있습니다.

typedef std::vector<double> v_t; 

int main() 
{ 
    v_t v1,v2,v3,vfinal(9); // note: vfinal sized to accept results 

    for (int i = 1; i < 10; ++i) { 
     v1.push_back(rand() % 10); 
     v2.push_back(rand() % 10); 
     v3.push_back(rand() % 10); 
    } 

    std::transform(v1.begin(), v1.end(), v2.begin(), vfinal.begin(), std::min<double>); 
    std::transform(v3.begin(), v3.end(), vfinal.begin(), vfinal.begin(), std::min<double>); 
} 

참고 :이 내가 GCC 4.3에 대한 min 펑터를 제공했다 MSVC++ 2010에서 작동합니다.

Answer 2

벡터에서 가장 작은 숫자를 찾으려면 각 요소를 차례로 살펴 봐야합니다. 적어도 알고리즘 관점에서 볼 때 더 빠른 방법은 없습니다.

실제 성능면에서 캐시 문제 이 여기에 영향을 미칩니다. 주석에서 언급했듯이, 행 단위가 아닌 열 방향으로 벡터를 저장할 수 있다면 캐시 효율성이 더 좋아질 것입니다. 또는, 모든 최소 검색을 병렬로 수행하여 캐시 누락을 최소화 할 수 있습니다. 즉, 오히려 이것보다 :

foreach (col) 
{ 
    foreach (row) 
    { 
     x_min[col] = std::min(x_min[col], x[col][row]); 
    } 
} 

은 아마 당신은이 작업을 수행해야합니다 min_element() : STL 이미이 작업을 수행 할 수있는 좋은 기능을 제공하는

foreach (row) 
{ 
    foreach (col) 
    { 
     x_min[col] = std::min(x_min[col], x[col][row]); 
    } 
} 

참고.

Answer 3

나는 n이 벡터의 수와 m 각 벡터의 요소가 어디에 문제의 하한은, O(n*m)라고 생각합니다.

(다른 벡터의 동일한 인덱스에서 요소를 비교하는) 간단한 알고리즘은 가능한 한 효율적입니다.

구현하는 가장 쉬운 방법은 모든 벡터를 일부 데이터 구조 (단순한 C와 유사한 배열 또는 벡터 벡터 일 수 있음)에 배치하는 것입니다.

Answer 4

이 작업을 수행하는 방법은 벡터 벡터를 사용하고 단순한 루핑을 사용하는 것입니다.

void find_mins(const std::vector<std::vector<int> >& inputs, std::vector<int>& outputs) 
{ 
    // Assuming that each vector is the same size, resize the output vector to 
    // change the size of the output vector to hold enough. 
    output.resize(inputs[0].size()); 

    for (std::size_t i = 0; i < inputs.size(); ++i) 
    { 
     int min = inputs[i][0]; 
     for (std::size_t j = 1; j < inputs[i].size(); ++j) 
      if (inputs[i][j] < min) min = inputs[i][j]; 
     outputs[i] = min; 
    } 
}