vectorコンテナに含まれたデータを平均で置き換えたい

前提・実現したいこと

4つの値を持つデータの整理に関する質問です。
データは４つの値を持つ構造体をvectorコンテナに格納することで管理しています。

<表１>のようなデータを<表4>のように整理する機能を実装したいと考えています。
下記のコードでは、
1)px,pyをソート<表２>
2)px,pyが重複しているC2Pのcx,cyをそのC2P内のcx,cyそれぞれの平均で置き換える<表３>
3)px,pyが重複しているデータの消去<表４>
という流れで機能を実装しました。しかし、C2Pの数が増えると2の平均で置き換える部分の処理に時間がかかってしまいます。この部分の高速化を行いたいです。
平均で置き換える部分に無駄が多く簡略化することで動作するのか？
そもそも、今回の1~3の流れで実装する方法がよくないのか?

また、最終的にはpx,pyの値が飛んでいる部分を補完することを考えています。
具体的には、表４の2行目と3行目の値に(cx,cy,px,py)=(2,13,3,0),(3,14,4,0),(4,14,5,0)といった形で補完することを考えています。cx,cyについては補間前の2行目と３行目の値(cx,cy)=(1,13),(5,14)の間に線形的?な補間を行いたいです。

アドバイスのほうよろしくお願いいたします。

<表１>元データ
|cx|cy|px|py|
|:--|:--:|--:|
1|13|2|0
3|18|1|0
5|2|9|0
8|17|4|1
3|6|4|1
5|14|6|0
0|7|1|1
1|3|1|1
7|14|2|1
4|13|8|0
4|10|4|1

<表２>ソート後のデータ
|cx|cy|px|py|
|:--|:--:|--:|
3|18|1|0
1|13|2|0
5|14|6|0
4|13|8|0
5|2|9|0
0|7|1|1
1|3|1|1
7|14|2|1
8|17|4|1
3|6|4|1
4|10|4|1

<表３>平均で置き換え
|cx|cy|px|py|
|:--|:--:|--:|
3|18|1|0
1|13|2|0
5|14|6|0
4|13|8|0
5|2|9|0
1|5|1|1
1|5|1|1
7|14|2|1
5|11|4|1
5|11|4|1
5|11|4|1

<表４>重複を消去

|cx|cy|px|py|
|:--|:--:|--:|
3|18|1|0
1|13|2|0
5|14|6|0
4|13|8|0
5|2|9|0
1|5|1|1
7|14|2|1
5|11|4|1

発生している問題・エラーメッセージ

該当のソースコード

C++
1#include <vector>
2#include <algorithm>
3#include <iostream>
4#include <fstream>
5#include <cstddef>
6
7using namespace std;
8
9//
10//    C2P構造体
11//
12struct C2P
13{
14    int cx;
15    int cy;
16    int px;
17    int py;
18
19    C2P(int camera_x, int camera_y, int proj_x, int proj_y)
20    {
21        cx = camera_x;
22        cy = camera_y;
23        px = proj_x;
24        py = proj_y;
25    }
26
27};
28
29
30//
31//    C2Pの初期値生成関数
32//
33vector<C2P> c2pList_factry(const size_t size_x, const size_t size_y)
34{
35    auto result = vector<C2P>();
36    result.reserve(size_x * size_y);
37
38    for (size_t x = 0; x < size_x; x++) for (size_t y = 0; y < size_y; y++)
39        result.push_back(C2P(x, y, rand() % 1000, rand() % 2000));
40
41    return result;
42}
43
44//
45//    最後尾から探索するfind_if
46//
47template<class Iterator, class Predicate>
48Iterator find_last_if(Iterator begin, Iterator end, Predicate pred)
49{
50    const auto rbegin = make_reverse_iterator(end);
51    const auto rend = make_reverse_iterator(begin);
52    auto found = find_if(rbegin, rend, pred);
53
54    return (found != rend) ? (++found).base() : end;
55}
56
57
58
59//
60//    main関数
61//
62int main()
63{
64    auto c2pList = c2pList_factry(1000, 2000);
65
66    //
67    //  データに含まれる最大値と最小値の取得
68    //
69    auto max_px = max_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.px < b.px;});
70    auto min_px = min_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.px < b.px;});
71    auto max_py = max_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.py < b.py;});
72    auto min_py = min_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.py < b.py;});
73
74    int max_px_num = max_px->px;
75    int min_px_num = min_px->px;
76    int max_py_num = max_py->py;
77    int min_py_num = min_py->py;
78
79    //
80    //  ソート
81    //
82    sort(c2pList.begin(), c2pList.end(),
83        [](C2P& a, C2P& b) {
84            return make_pair(a.py, a.px) < make_pair(b.py, b.px);
85        });
86
87    
88    //
89    //  平均での置き換え
90    //
91    for (int i = min_py_num;i <= max_py_num;i++)
92	{
93		for (int j = min_px_num;j <= max_px_num;j++)
94		{
95			auto first_itr = find_if(c2pList.begin(), c2pList.end(), [&i, &j](C2P& a) {return a.px == j && a.py == i;});//指定した(px,py)をもつC2Pの先頭を取得
96			auto last_itr = find_last_if(c2pList.begin(), c2pList.end(), [&i, &j](C2P& a) {return a.px == j && a.py == i;});//指定した(px,py)をもつC2Pの最後尾を取得
97
98			if (first_itr != last_itr)//重複しているか判定
99			{
100				int sum_cx = 0;
101				int sum_cy = 0;
102				auto total_num = count_if(c2pList.begin(), c2pList.end(), [&i, &j](C2P& a) {return a.px == j && a.py == i;});
103				for_each(first_itr, last_itr + 1, [&sum_cx, &sum_cy](C2P& a) {sum_cx += a.cx;sum_cy += a.cy;});
104				for_each(first_itr, last_itr + 1, [&sum_cx, &sum_cy, total_num](C2P& a) {a.cx = sum_cx / total_num;a.cy = sum_cy / total_num;});
105			}
106		}
107	}
108
109
110    //
111    //　重複の消去
112    //
113    auto p = unique(c2pList.begin(), c2pList.end(), [](const C2P& c2p_1, const C2P& c2p_2) {return (c2p_1.px == c2p_2.px);});
114    c2pList.erase(p, c2pList.end());
115
116    
117    return 0;
118}
119

episteme

2020/12/06 11:53

平均/補完を考えてるなら、cx,cyがintなのはマズくないですか?

episteme

2020/12/06 11:56

> C2Pの数が増えると2の平均で置き換える部分がうまく動作しません。「うまく動作しません」を説明してください。デバッグを丸投げしないで。

k.s.t

2020/12/06 12:33

>平均/補完を考えてるなら、cx,cyがintなのはマズくないですか? データを利用する際は整数部分のみを利用するのでint型で問題ありません。 >「うまく動作しません」を説明してください。デバッグを丸投げしないで。説明不足で申し訳ありません。動作自体はするのですが、C2Pの数を増やすと処理に時間がかかってしまうのでそこを高速化したいと考えています。

episteme

2020/12/06 12:51 編集

なぜ遅いか理由は明らかでは? Ｎ回loopをM回loopすればN*M回の繰り返しなんだから。

k.s.t

2020/12/06 17:34

自己解決できました。アドバイスありがとうございました。

行動規範の内容に同意します

回答2件

自己解決

下記のコードのようにループを減らすことで改善できました。
アドバイスをいただいた方ありがとうございました。

C++
1 
2    //  平均での置き換えと重複要素の消去
3    //
4    vector<C2P> c2pList_new;
5    int series_judge = c2pList[0].px;
6    int sum_cx = 0;
7    int sum_cy = 0;
8    C2P tmp(0,0,0,0);
9    int count = 0;
10    for (auto elem : c2pList)
11    {
12        if (series_judge == elem.px)
13        {
14            series_judge = elem.px;
15            count += 1;
16            sum_cx += elem.cx;
17            sum_cy += elem.cy;
18            tmp.cx = sum_cx / count;
19            tmp.cy = sum_cy / count;
20            tmp.px = elem.px;
21            tmp.py = elem.py;
22  
23        }
24        else
25        {
26            c2pList_new.push_back(tmp);
27            sum_cx = 0;
28            sum_cy = 0;
29            count = 1;
30
31            series_judge = elem.px;
32            sum_cx += elem.cx;
33            sum_cy += elem.cy;
34            tmp.cx = sum_cx / count;
35            tmp.cy = sum_cy / count;
36            tmp.px = elem.px;
37            tmp.py = elem.py;
38
39        }
40    }
41
42    c2pList_new.push_back(tmp);