C++相談室 part139

2018/10/06(土) 00:59:48.54

次スレを立てる時は本文の1行目に以下を追加して下さい。
!extend:on:vvvvv:1000:512

C++に関する質問やら話題やらはこちらへどうぞ。
ただし質問の前にはFAQに一通り目を通してください。
IDE (VC++など)などの使い方の質問はその開発環境のスレにお願いします。

前スレ
C++相談室 part137 (正しくはpart138)
http://mevius.5ch.net/test/read.cgi/tech/1535353320/

このスレもよろしくね。
【初心者歓迎】C/C++室 Ver.103【環境依存OK】
https://mevius.5ch.net/test/read.cgi/tech/1530384293/

■長いソースを貼るときはここへ。■
　http://codepad.org/
　https://ideone.com/

[C++ FAQ]
https://isocpp.org/wiki/faq/
http://www.bohyoh.com/CandCPP/FAQ/ (日本語)

----- テンプレここまで -----

VIPQ2_EXTDAT: default:vvvvv:1000:512:----: EXT was configured

2018/10/17(水) 07:43:25.83

>>260
敵車両の破壊には有効だが

2018/10/17(水) 07:57:03.78

今の戦車にゃ効かんだろ

2018/10/17(水) 08:18:18.25

対戦車壕でも掘るか

2018/10/17(水) 09:23:52.75

RPGってあれだろ、IBMの作ったCOBOLもどきだろ、確かに時間の無駄だし戦車には効かんだろ

2018/10/17(水) 09:25:52.61

ん、ソ連製だよ

2018/10/17(水) 17:39:50.55

OpenCVのtemplatematchingについてなのですが、
しきい値を決めて類似度がしきい値以上の物を全探索で複数探すものはあったのですが、
類似度の上位2つのみを探す方法って無いですかね？
全探索は遅いので上位複数個だけ取れたらいいなと

2018/10/17(水) 18:57:16.89

最後の一個が最大だったらどうするの

2018/10/17(水) 19:02:36.72

閾値を適用するコードを探してチャチャっと改造すればいいんじゃね？
つか、最大値を求めるアルゴリズムも知らないのにOpenCVやってんの？

2018/10/17(水) 19:12:33.43

高速に判定できる軽量版データ(部分画像、低解像度、モノクロなど)がありうるなら
それで箸にも棒にもかからないものを高速にふるい落としてから
残ったものだけをちゃんと調べればいいよ

2018/10/17(水) 20:15:44.53

並べ替えて上位複数個取り出すんじゃダメなん？

2018/10/17(水) 21:50:01.45

>>266は、閾値以上の値を全部取ってくる関数の代わりとして
上位n個(nは定数)を取ってくる関数はないか、ってことだろ？

> 全探索は遅いので
と書いちゃうから誤読されてそう。上位n個の場合でも全部見る必要はあるんだから

**デフォルトの名無しさん** (JP 0Hbf-CE2c) · 2018/10/17(水) 21:56:50.45

このゲームすぐ持ち物いっぱいになるな
http://egg.5ch.net/test/read.cgi/dqo/1539336435/

使い道のないアイテム（無駄なコード）が多すぎやしないか？

2018/10/17(水) 22:16:11.68

>>271
だよね。
全部閾値以下って可能性考慮しても、並べ替えて上位から閾値以上か確認しながら取り出した方が早いべ。

2018/10/17(水) 22:41:59.25

>>273
ソートは要らない

2018/10/17(水) 23:07:41.45

>>274
んじゃどうすんの？
最大値を見つけた後に、最大値省いたリストなり配列から次の最大値(2番目に大きい数)探すにしたって、最大値を省くために最大値が有った場所を覚えておいて、そこを削除するなりしないと駄目でしょ？
面倒くさいし、速いと思えないんだけど。

2018/10/17(水) 23:12:11.03

https://teratail.com/questions/68835

2018/10/17(水) 23:17:55.90

。。。。。え“
5番目の大きさまでさがすとなら、5個もelse if書けと？
任意の個数なら、毎回書き直しか？
アホかと。

2018/10/17(水) 23:23:37.00

バブルソートを知っていれば、任意個数でもいける。しかし、抽出個数を任意にすると、まあちょびっと遅くなる。

2018/10/17(水) 23:23:37.66

>>275
元の質問が2個取り出すだけだからそれを前提にしてたすまん
n個を取り出すならソートしないとだめだな

2018/10/17(水) 23:25:33.43

テンプレートの再帰を知ってれば遅くならずに任意個数いける。

2018/10/17(水) 23:37:39.44

元データをソートしなくても、結果用にn個のソート済み配列(flat_setとして提案されてるやつ)を用意して
そこに追加していきゃいいのでは。既に閾値以上のがn個集まってたら以降は最小のと比較して交換

2018/10/18(木) 00:31:36.03

>>281
n個のソート済み配列って、ソート済み配列を何個も用意してどうする。。。と言う言いたいこと分かるけど、書き間違いでおかしな事言ってるっぽくなってるっていうツッコミは置いといて。。。
閾値が在るんだから、先に閾値以上の物だけ別の配列に入れてソートすれば良いってのは確かに任意個数で一番速そう。

2018/10/18(木) 00:47:10.59

交換が発生する度にn個中の最小を検索する必要がある
閾値以上のを1回ソートとあまり変わらないような・・・データ次第か
全ソートして上から閾値見ながら、で充分じゃね？
選択部を工夫してもたいして効果なさそう

2018/10/18(木) 00:52:16.35

>>283
ソート「済み」配列なので最小は必ず端にあるから検索の必要はないよ
代わりに追加の度に二分探索をする
それをイメージしてもらうためにflat_mapって書いたんだが未策定のものは伝わらないな、うん

>>282
すまん、要素数n個のソート済み配列を1個、で

2018/10/18(木) 00:59:51.74

s/flat_map/flat_set/

orz

**266** (ｵｲｺﾗﾐﾈｵ MM1b-MrPr) · 2018/10/18(木) 01:37:39.33

すみませんありがとうございます
ここに出てたの試してみます

2018/10/18(木) 01:42:23.05

>>283
正直、追加の話見るまで最小と交換って私も「？」になった。
要するに1回目はソート済み配列が無いので >>282 をする。
要素を追加する度に、閾値以上かを見て、閾値以上ならソート済み配列で小さい順から二分探索して順番になる位置に挿入。

全要素1000で閾値以上が100とかなら、ソートするのが100だけだから、かなり高速化する。
追加もソート済みに入れるだけなので、遅くは無いし、次に取り出す事考えると(追加と同時にソート済みにしておく)、ソート済みから取り出すだけになるので全体として速くなる。

と言う考えであってる。。。と思う。

2018/10/18(木) 02:00:19.06

>>287
近くなったがまだちょっと違う
結果用の配列は要素数nしか確保しない。閾値以上が100個あってもn=2なら要素数2
で、元データを順に見ていって、3個目以降が見つかったら結果用の配列に入り切らないので
後から見つけたのが結果用の配列の中の最小よりも大きければ、最小のを捨てた上で二分探索した位置に挿入する
……というつもりだった

元データに後から追加があったら、みたいなことを考えて書いたわけではないです

2018/10/18(木) 02:11:57.61

std::upper_bounds とかで挿入位置を決めて挿入、
n個を超えたら小さい方を1つ切り捨てるって感じだよね
たかだか数件ならループで位置を決めてもいい

2018/10/18(木) 03:05:15.05

>>288
なるほど。
今全部分かった。

うーん。
それは任意の個数nと閾値以上の個数が近くないと、n個目以降が見つかる度に比較、探索、挿入を繰り返す事に。。。
データによりけりではあるけど、微妙。

>>282 は、イメージとしてはクイックソートの最初のピボットを閾値にして、閾値以下はソートしない様に変形させた感じ。

どっちがどうとかは、実測しないとなんとも言えなさそう。

2018/10/18(木) 05:26:46.31

それってQuickselectみたいな感じ?
https://en.wikipedia.org/wiki/Quickselect

2018/10/18(木) 07:53:42.77

>>291
そっちのが凄い。
任意のnーmまでの範囲だけクイックソートっぽくソートするのか。
最上位(m)からn位までのソートでおkじゃないか。

2018/10/18(木) 08:01:48.62

標準にstd::partial_sortってのがあってな

2018/10/18(木) 19:43:13.60

ほとんど中身を知られていないalgorithmさん

2018/10/18(木) 20:00:49.79

それは >>282,>>290,>>292 書いた私の事だろうか。
そんな呼び名がつくのは光栄だけど、高卒で基本アルゴリズムしか知らないんだ。
その割には悪く無い処理を考えられたと自画自賛してたんだけど、やっぱ頭のいい人の考えるアルゴリズムは凄いね。

2018/10/18(木) 21:00:06.41

ヘッダファイルさんのことだと思うよ…

2018/10/19(金) 01:06:20.80

partial_sortなんてあったのか……orz
でもquickselectは元データを並び替えてしまうから
それができないならこのスレに書かれた方法でもいいけどな(負け惜しみ)

負け惜しみついでに>>290の議論だが、mは元データの個数、nは欲しい個数として
>>282の閾値以上を抽出してから一括してソートは
最速のソートが使えるのでオーダーはO(m log m)、空間使用量は元データと同じ作業領域がいるのでmに比例
>>288(俺)のソート済み配列に追加していくのは
挿入ソートを小分けにしてるわけだからオーダーはO(m*n)、空間使用量はnに比例

nとmが近いかそもそものデータ量が小さければ>>282が、そうでなければ>>288有利かな
……で良いと思う

2018/10/19(金) 01:22:58.84

>>297
大丈夫、私も同じく沈んだw
純粋に貴方と私のロジックでは、貴方の方が有利という試算なのね。
おk。了解した。

2018/10/19(金) 01:38:12.56

いやまああくまで最悪計算量なんで、結局実際のところは実測しないとだけどもね
オーダー上は挿入でnに比例するから二分探索に意味はない、と書きながら気付いたりもしてる(苦笑)

2018/10/19(金) 11:38:23.88

>>294
地味に標準指定のアルゴリズムも改善されてて追いきれないよぉ

2018/10/19(金) 15:50:31.89

そして誰からも忘れられているstd::nth_element

2018/10/20(土) 00:02:17.58

ていうか4位同順が10万画素ぐらいあったらどうするんじゃスレ主、

2018/10/20(土) 11:06:48.96

ttps://www.magezinepublishing.com/equipment/images/equipment/H6D50c-6100/highres/Hasselblad_SHOT_01_F1_RGB_1460032379.jpg
一枚一億画素
jpg一枚で25MB

FFでは開けた

2018/10/20(土) 13:36:14.45

専ブラのプレビューでも相当時間掛かった
リンクを踏む気は無い

2018/10/20(土) 14:20:59.31

できたので貼る
Insertion sortで上位5件の相関値と座標(x, y)を表示するやつ：
ttps://ideone.com/L0fXH2
これは、同着があっても上位5位に入れば全部出力する。

get_top_N_pixels()がご本尊の関数
get_top_N_pixels_exp()が比較用に作ったバージョンで、std::sortで全画素並べ替えて上位5件を出力する。

上位5位以内に同着があまりに多いとget_top_N_pixels_exp()の方のが早いが
適当に作ったランダムな値の条件でQVGAぐらいの画像サイズだったらget_top_N_pixels()の方が8倍ぐらい早いっぽ

2018/10/20(土) 14:29:43.99

>>303
Edge@androidでも開ける

**305** (ﾜｯﾁｮｲ 6abd-9c8P) · 2018/10/21(日) 13:32:51.16

訂正 s/同着/同順/g

で、同順がそれなりにある前提でパホーマンスをちゃんと計ったら8倍どころではなかったわ3000倍以上早かったわ；
条件は以下の通り

■ 画像サイズ:
W=320 - 10, H=240 - 10
(Number of pixels=71300)

■ データ
値域[-5000.0F, 5000.0F]の一様分布。データ重複無し。

■ Basic design の結果（get_top_N_pixels_exp(): 全画素std::sort()）
387 sec @ 反復回数ntimes=100, TOP_N=256 --> ntimesを10倍にすると3870 secの見込み

■ Practical designの結果（get_top_N_pixels(): TOP_N画素のInsertion sort
1 sec @ 反復回数ntimes=1000, TOP_N=256
14 sec @ 反復回数ntimes=10000, TOP_N=256

とゆーわけで、今回は一様分布かつデータ重複無しでこうだったので、TOP_N=256は一般条件における128と解釈するとして、
上位5位に入るデータの個数が128個以下なら>>305のpractical designで上記のパホーマンスが出る見込み

**305** (ﾜｯﾁｮｲ 6abd-9c8P) · 2018/10/21(日) 13:46:01.97

ごめwwwwwデータ訂正および結論は480倍早かった、に訂正、

■ Practical designの結果（get_top_N_pixels(): TOP_N画素のInsertion sort
1 sec @ 反復回数ntimes=1000, TOP_N=256
8 sec @ 反復回数ntimes=10000, TOP_N=256 -- 3870 / 8 = 483.75
14 sec @ 反復回数ntimes=10000, TOP_N=65536

**305** (ﾜｯﾁｮｲ 6abd-9c8P) · 2018/10/21(日) 14:18:55.75

ごめｗｗｗｗｗｗ結論は3000倍以上早かった、で訂正の必要はなかったorz

Basic designの結果
　387 sec @ 反復回数ntimes=100, TOP_N=256
に対して、Practical designの結果
　8 sec @ 反復回数ntimes=10000, TOP_N=256
は、(387/100) / (8/10000) = 4837.5倍早い

今日日のCPUアーキテクチャーとinsertion sort様様じゃ

2018/10/22(月) 08:41:03.37

江添と2ちゃんねらーどっちが頭いいですか？

2018/10/22(月) 08:50:48.56

お前が最高だよ

2018/10/22(月) 09:11:16.83

>>311
ありがとう//

2018/10/22(月) 15:27:10.69

STLってもはやスクリプト言語などと変わらない使用感でプログラム書けるな

最高過ぎる

2018/10/22(月) 15:49:25.60

tupleが便利だけどまだちょっと物足りない

2018/10/22(月) 17:48:12.06

C++17の構造化束縛を使うときありがたい

2018/10/22(月) 18:11:37.07

インライン変数って使ってる？

2018/10/22(月) 19:19:03.71

c標準ライブラリの関数ってstd名前空間にあるのに必ずしもstd::をつける必要ないよね
なぜか分かる人いない？

2018/10/22(月) 19:25:06.82

C言語との互換性のため。
using使っているから。

2018/10/22(月) 19:32:50.75

cstdio → stdで囲まれる
stdio.h → 囲まれない

2018/10/22(月) 19:39:34.29

横から納得w
古いC++(C互換重視)と新しいC++(新世界の王に俺はなるモード)の互換のためか。
ナル。

2018/10/22(月) 21:20:30.74

>>318
なるほど
ありがとう

2018/10/23(火) 18:14:01.09

directory_recursive_iteratorで各ディレクトリを読み込むと読み込み順がおかしくなりますが、これvectorに突っ込んでソートしないと辞書順に戻せないのですか？

2018/10/23(火) 18:22:08.06

>>322
戻すっていうか、普通のファイルシステムでは辞書順に並ばないことの方が多いんじゃないの。知らんけど。
言語仕様的には recursive_directory_iterator が辿る順序は未規定。

2018/10/23(火) 21:40:23.22

二次記憶装置のデータをいちいちソート済みに保とうとするとオーバーヘッドが無茶苦茶だからな
読み込み順がおかしくなるんじゃなく、いつもOSがソートして見せてくれてたのが元のまま出てきただけだ
DOSの時代はdirに/oスイッチが追加されたとき便利になったものだと思ったよ

**デフォルトの名無しさん** (ｽﾌｯ Sd8a-nQMY) · 2018/10/23(火) 21:41:56.02

C++こそ至高

2018/10/23(火) 22:17:33.35

毎日毎日ソートして表示してくれてる ls や dir.exe や exproler.exe には頭が上がりません

2018/10/23(火) 23:09:18.58

総統も相当ソートがお好きですなあ
ｶﾞﾊﾊﾊﾊﾊﾊ、

2018/10/23(火) 23:09:49.99

ピキン

2018/10/23(火) 23:15:54.90

また低学歴知恵遅れたちは頭わるいこといってるわ。。。
ｄｉｒ．ｅｘｅ？
ｄｉｒはｃｍｄ．ｅｘｅの内部ｺﾏﾝﾄﾞだからな
ｄｉｒ．ｅｘｅなんかあるﾜｹがない

ｿｰﾄするのはｃｍｄ．ｅｘｅがｄｉｒｺﾏﾝﾄﾞを受けつけたときの機能で
OS自体の機能じゃないからな

ﾎﾝﾄな低学歴知恵遅れたちは基本的なことが分かってない

2018/10/24(水) 01:34:13.78

半角さん全角で書いてる・・・

2018/10/24(水) 01:53:57.74

>>330
最近飽きられてきたから(構ってもらえなくなったから)、芸風を変えてきたんだろ。触らないのがよろしいかと。

2018/10/24(水) 22:50:08.00

全角の部分を半角で書き込むと403ではじかれる

わかった？

低学歴知恵遅れの書き込みはいつも浅はか

2018/10/24(水) 23:09:52.03

ｃｍｄ．ｅｘｅを半角で書いたら、
コマンドが実行されて、サーバーをハッキングされるとか、
5ch・サーバーの運営は、頭おかしい

素人がシステム・サーバーの運営構築してる

漏れは、何十冊も本を読んでいるけど、
ｃｍｄ．ｅｘｅを送ったら、ハッキングできるという記事を見たことがない

2018/10/24(水) 23:31:31.21

dir　.exe
dir
cmd.　exe
OS
ﾎﾝﾏや！弾かれた！！

2018/10/24(水) 23:34:37.74

サニタイズの最先端・ユーザーに入力させない←いまここ

いや知らんけど多分、

2018/10/24(水) 23:36:41.49

326はどうやって書き込んだのか

2018/10/24(水) 23:42:29.72

dir.exeは実在しないから

2018/10/24(水) 23:45:51.61

cmd.exe

2018/10/24(水) 23:47:41.25

5chのNGワードチェックには文字参照という抜け穴が空いてる。

2018/10/24(水) 23:47:52.54

dir.exe とかはどうだろう

2018/10/24(水) 23:49:12.41

間違えた cmd.exe か
>>339
実体参照は書き込めない短縮url貼ったりするときにも使えるよね

2018/10/24(水) 23:49:46.74

cmd.exe か

2018/10/25(木) 00:27:44.75

©

2018/10/25(木) 01:10:25.04

文字実体参照・数値文字参照なら、コマンドが実行されて、5ch サーバーをハッキングされる事もない

cmd.exe

dot, period は、ascii コード、46 (0x2E)

2018/10/25(木) 01:38:31.34

☝

**デフォルトの名無しさん** (JP 0H4b-q7gB) · 2018/10/25(木) 11:03:54.05

戻り値がオブジェクトの関数書きました。
すると上司が、変更があったとき不具合の原因になるからポインタで返せと。
これ本当でしょうか。stackoverflowとか覗いてるんですがオブジェクトで返すかスマポで返すかみたいな論調ばかりです。
少なくとも生ポインタ使えという意見は見当たりません。
（生）ポインタ使ったほうがいいケースというのは実際にあるんでしょうか。

2018/10/25(木) 11:14:40.21

>>346
malloc してるやつなら
FILE * とかな

2018/10/25(木) 11:14:58.15

ああ
もちろんスマポは否定しない

2018/10/25(木) 11:19:20.78

>>346
参照返しでもポインタ返しでもプログラムの堅牢性は大差ない気がする。
ちなみに俺は、NULLを返すケースがある関数はポインタ返し、
NULLを返すケースがない関数は参照返しにしてる。

2018/10/25(木) 11:36:26.68

c++ の標準のスマートポインタでは循環参照を持つもの、
例えば get_child() と get_parent() を持つような木構造やリスト構造は扱えない
で、大抵の場合これらは単に生ポインタで実装される。

2018/10/25(木) 11:52:04.34

>>346
C++ のミスりやすい箇所ってのはメモリ管理が多くを占めるので、
生ポインタは面倒くさいわってのが普通の感覚だと思うし、
不具合の原因になるってのはよくわからん言い分なので、
もっと掘り下げて聞かないとなんとも言えん。

共有オブジェクト (DLL) のインターフェイスにする場合なんかだと
ABI の都合とかでおかしなことになったりすることもあるかもしれんなぁ
みたいな可能性を想像することは出来るが、
書いてるプログラムや開発環境の性質に固有の事情はわからん。

一般的には、生ポインタにせざるを得ないことは有っても生ポインタの方が良いってことはあんまりなさそう。

2018/10/25(木) 12:00:30.29

ファクトリー関数は生ポインタ返すように作るのが良いと思う

2018/10/25(木) 12:24:55.50

たしかにどこも指してない参照を返したいときは
NULLポ使えるポインタ返しにする

ダミーの空オブジェクト作れるように
C++が最初からルートオブジェクト基底してくれてればよかったのにと思うことはある

2018/10/25(木) 12:31:40.62

struct Point{int x; int y;};
みたいな単純なPOD構造体をstructだからって教条的にいちいちnewとポインタで取り回してるプログラムは時々見かけるけど
そういうのは危ないし遅いしウザいからやめてほしい

2018/10/25(木) 12:36:58.91

そんなの参照と値渡しでいいということには同意するが
point 型を new / delete してるコード見た経験はないな

2018/10/25(木) 13:10:30.18

>>346の上司が言ってるのは、コピーコンストラクトや代入が正しく機能するということを
保証しなくちゃならなくなるから、ってことだろ
そこまで気にかけてる暇はないし、生ポで書くのが一般的な職場だというならそれに倣うしかない

2018/10/25(木) 13:17:16.94

そういえば俺コピー不可のクラス書いてもちゃんと private だ何だで実際に代入できないようにしてないな…

2018/10/25(木) 15:12:05.05

コピー不可で思い出したけど、コピーコンストラクタと代入演算子をprivateにしたクラスを
vectorにpush_back()する記述がコンパイルエラーになるよね。

vector<Hoge> hogeVec;
hogeVec.push_back(Hoge()); // コンパイルエラー

これってどうすればいいの？

2018/10/25(木) 15:24:01.65

emplace_back使うとか

2018/10/25(木) 15:28:42.80

friend