Медиана нескольких векторов double (C++, vector <vector <double>>)

Question

У меня есть структура данных, содержащая вектор векторов, каждый из которых содержит около ~ 16000000 двойных значений.

Теперь я хочу срединно-объединить эти векторы, что означает, что каждый из исходных векторов я принимаю значения в месте i, вычисляет их медиану, а затем сохраняет в результирующем векторе в месте i.

У меня уже есть прямой вперед решение, но это невероятно медленно:

vector< vector<double> > vectors; //vectors contains the datavectors 
vector<double> tmp; 
vector<double> result; 
vector<double> tmpmedian; 
double pixels = 0.0; 
double matrixcount = vectors.size(); 

    tmp = vectors.at(0); 
    pixels = tmp.size(); 
    for (int i = 0; i < pixels; i++) { 
     for (int j = 0; j < matrixcount; j++) { 
      tmp = vectors.at(j); 
      tmpmedian.push_back(tmp.at(i)); 
     } 
     result.push_back(medianOfVector(tmpmedian)); 
     tmpmedian.clear(); 
    } 

return result; 

И medianOfVector выглядит следующим образом:

double result = 0; 

if ((vec.size() % 2) != 0) { 
    vector<double>::iterator i = vec.begin(); 
    vector<double>::size_type m = (vec.size()/2); 

    nth_element(i, i + m, vec.end()); 
    result = vec.at(m); 
} else { 
    vector<double>::iterator i = vec.begin(); 
    vector<double>::size_type m = (vec.size()/2) - 1; 

    nth_element(i, i + m, vec.end()); 
    result = (vec.at(m) + vec.at(m + 1))/2; 
} 

return result; 

Я есть алгоритм или способ сделать это быстрее , для этого требуется почти целая вечность.

---

Edit: Спасибо за ваши ответы, в случае, если кому-то интересно здесь фиксированная версия, теперь он занимает около 9sec медианной объединить три вектора с ~ 16000000 элементов, значит, объединение занимает около 3 секунд:

vector< vector<double> > vectors; //vectors contains the datavectors 
vector<double> *tmp; 
vector<double> result; 
vector<double> tmpmedian; 

    tmp = &vectors.at(0); 
    int size = tmp->size(); 
    int vectorsize = vectors.size(); 
    for (int i = 0; i < size; i++) { 
     for (int j = 0; j < vectorsize; j++) { 
      tmp = &vectors.at(j); 
      tmpmedian.push_back(tmp->at(i)); 
     } 
     result.push_back(medianOfVector(tmpmedian)); 
     tmpmedian.clear(); 
    } 
return result; 

И medianOfVector:

double result = 0; 

if ((vec.size() % 2) != 0) { 
    vector<double>::iterator i = vec.begin(); 
    vector<double>::size_type m = (vec.size()/2); 

    nth_element(i, i + m, vec.end()); 
    result = vec.at(m); 
} else { 
    vector<double>::iterator i = vec.begin(); 
    vector<double>::size_type m = (int) (((vec.size() - 1)/2)); 
    nth_element(i, i + m, vec.end()); 
    double min = vec.at(m); 
    double max = *min_element(i + m + 1, vec.end()); 
    result = (min + max)/2; 
} 

return result; 
} 

Answer 1

пар точек, и вытекающий из того, что вы определили tmp как вектор вместо (к примеру) ссылка.

vector<double> tmp; 

tmp = vectors.at(0); 
pixels = tmp.size(); 

Здесь вы копируете полноту vectors[0] в tmp просто извлечь размер. Вы почти наверняка получить некоторую скорость, избегая копирования:

pixels = vectors.at(0).size(); 

Вместо того, чтобы копировать весь вектор только, чтобы получить его размер, это просто получает ссылку на первый вектор, и получает размер, что существующий вектор.

for (int i = 0; i < pixels; i++) { 
    for (int j = 0; j < matrixcount; j++) { 
     tmp = vectors.at(j); 
     tmpmedian.push_back(tmp.at(i)); 
    } 

Здесь вы снова копируя полноту vectors.at(j) в tmp. Но (опять же) вам не нужна новая копия всех данных - вы просто извлекаете один элемент из этой копии. Вы можете получить данные, которые нужны непосредственно из исходного вектора, не копируя все это:

tmpmedian.push_back(vectors.at(j).at(i)); 

Возможного следующий шаг будет переключаться с помощью .at к operator[]:

tmpmedian.push_back(vectors[j][i]); 

Это намного больше однако, скорее всего, он вряд ли получит почти столько же, и теряет часть безопасности (проверка диапазона) в этом процессе. Чтобы избежать потери безопасности, вы можете рассмотреть (например) использование циклов for на основе диапазона вместо подсчитанных циклов for в вашем текущем коде.

В отличие от других линий, вместо этого вы можете вместоиспользовать небольшую обертку вокруг вектора, чтобы дать 2D-адресацию в один вектор.Используя это с подходящим итератором по столбцам, вы могли бы избежать создания tmpmedian, как в основном копии столбца исходной 2D-матрицы, вместо этого вы передали бы столбцовый итератор в medianOfVector и просто перебирали столбец исходные данные на месте.