数値を複数の群に分ける最適な組み合わせを求める方法

質問

次のような問題をCで記述するにはどのようにすればいいでしょうか？

要素数が不定の整数値配列がある。
この配列の各要素を、与えられた個数の群に分ける。
条件として、与えられた数値列で隣り合う数値しか同じ群に含めることは出来ない。

例：
数値列は{5,2,7,12,6,15,4}
群の個数を3とする。

(1) {5,2},{7,12,6},{15,4}
(2) {5},{2,7},{12,6,15,4}
(3) {5,2,7},{12},{6,15,4}
・・・

と複数の組み合わせがある。
これらの組み合わせのうち、各群の合計値が最も均等になるような組み合わせを求める。最大値と最小値の差が最小となる組み合わせを最も均等と考える。

上の例であれば、各群の合計値と、合計値の最大値と最小値の差は、

(1) {5,2},{7,12,6},{15,4} ==> 7,25,19 (25-7=18)
(2) {5},{2,7},{12,6,15,4} ==> 5,9,37 (37-5=32)
(3) {5,2,7},{12},{6,15,4} ==> 14,12,25 (25-12=13) ☆

のようになり、この３つの中で最も均等なのは

(3) {5,2,7}{12}{6,15,4}

となる。
実際は、これ以外の組み合わせでより均等となるものがあるかと思います。

この問題そのものが必要なわけではなく、この結果を利用して別のある問題を解決しようとしています。

数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。
全ての組み合わせを試すことなく答えにたどり着く方法があれば、考え方だけでも提示頂ければと思います。

回答No.27

amanojaku1 · ベストアンサー

>回答No.23　amanojaku1

「2018/06/15 03:48:47」の時点で修正しました。
それ以前にコピーしている場合は注意して下さい。

数値を複数の群に分ける最適な組み合わせを求める方法
http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&

お礼

コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。

それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。

回答No.52

amanojaku1

>回答No.51　amanojaku1

分岐予測が外れたら(CPUの)パイプラインのStall(ストール：停止状態)が発生します。
「min、max」ライブラリ関数が内部的に どうなってるか分かりませんが、もし内部的に分岐が使われてないとすれば(インライン化すれば)パフォーマンスが良い可能性があります(あくまで可能性ですが)。
なので どうなるか試してみて下さい。

お礼

min_element,max_elementはSTLのライブラリ関数なのでinline化は出来ません。他の環境なら可能かも知れませんが、VisualC++では出来ないと思います。自分がやったのは、関数呼び出しではなく最大値最小値を求めるロジックを直接whileループ中に書きました。つまり普通にinlineになっています。

回答No.51

amanojaku1

>ライブラリ関数は使わず

(インライン化したライブラリ関数がパフォーマンスが良い可能性もあるかもしれないので)一応「min、max」ライブラリ関数をインライン化して どうなるか試してみて下さい。

回答No.50

amanojaku1

>gmmin = *min_element(gmt, gmt+gp);　←内部でループしてると思われる
>gmmax = *max_element(gmt, gmt+gp);　←内部でループしてると思われる

下記はJavaScriptです。
インライン化は良く分からないので、「#pragma forceinline」で良いのか良く分かりません。
上記はループが2つ、下記はループが1つ、なのでパフォーマスが改善する"可能性"があります(あくまで"可能性"ですが…)。

gmmin = gmt[0];
gmmax = gmt[0];
for(let m = 1; m<gmt.length; m++){ // 1からスタートしていることに注意して下さい。
gmmin = Math.min(gmmin,gmt[m]); // ←「min」関数を「#pragma forceinline」でインライン化を定義しておく
gmmax = Math.max(gmmax,gmt[m]); // ←「max」関数を「#pragma forceinline」でインライン化を定義しておく
}

お礼

やってみたら1.8秒→1.5秒に改善しました。ライブラリ関数は使わず自前で全部書いてみました。

なかなか奥が深いですね。たったこれだけで２割も早くなります。
単純な処理と思っていたものが、ループの中だとかなりのインパクトになるのですね。こうした純粋なアルゴリズムでは、ブラックボックスなライブラリやクラスは一切使用しない方が良さそうです。

回答No.49

amanojaku1

まあ、細かい事を言っていても、恐らく大してパフォーマスには影響ないでしょう。

>gmmin = *min_element(gmt, gmt+gp);
>gmmax = *max_element(gmt, gmt+gp);

↑ここがパフォーマスの肝になると分かったのですから、手動で最適化してみて試してみるのも良いかもしれません。

回答No.48

amanojaku1

>回答No.46　amanojaku1

>if ((qc < gp) && (i == (gmq_st + gmq[qc]))) {
>gmq_st += gmq[qc];
>qc++;gmc++;
>}

実際のパフォーマス的にどうでしょうか？
もし、パフォーマス的に変わらないならスマートな記述をオススメします。

回答No.47

amanojaku1

>回答No.46　amanojaku1

変数を減らすならpcを減らすほうがスマートです(パフォーマス的に どうかは分かりませんが)。

>if(pc<gmp.length){
>if(gmp[pc]==i){
>pc++;
>gmc++;
>}
>}

if((gmc+1)<gmp.length){
if(gmp[(gmc+1)]==i){
gmc++;
}
}

回答No.46

amanojaku1

>配列のソートに時間がかかっていたようです。

そこが問題でしたか。

>最大値、最小値の算出にソートは必要ないですね。

そう言われると、そうですね(^_^;)。

>この結果、2000万パターンで約1.8秒まで改善しました。ちなみに要素数28、グループ数14で約2000万パターンとなります。

これで充分に実用的ですね。

>gmpは使用しない。

>if ((qc < gp) && (i == (gmq_st + gmq[qc]))) {
>gmq_st += gmq[qc];
>qc++;gmc++;
>}

かえって処理が複雑になってますが、変数を減らした方が良いと言う判断ですか。
gmq_stが増えているので、どちらが良いとも一概には言えないかもしれません。
まあ、全体の処理からすれば些細な事でしょうが。

if(gmp[pc]==i){
pc++;
gmc++;
}

回答No.45

amanojaku1

>C言語はサッパリというのは？
>そもそもここはC/C++/C#のスレッドですが。

C言語(C++も)とか、サッパリ分からないのでJavaScriptで組んだ訳です、JavaScript→C++への変換も それほど難しくないだろうと思ったので…。

>それだけの知識がありながら

プリプロセッサ指令に関してはパスカル系で同様なコンパイラ・スイッチ？みたいなモノが有ったので、当然 C++にも同様なモノが有るだろうとググっただけです。
386(32bit)ではコンパイラーによる最適化の恩恵はあまり受けらないと言う批判を受けて、Intelはx64ではレジスタを倍増したと言うのは割りと有名な話です。
今回、たまたまググっていてC言語？(C++？)でx64でもintは32bitだと言う記事を どこかで読みました(マジか？と本当にビックリしました)。
今回、たまたまググっていてC言語で386(32bit)で「16bit、8bit」演算ではマスク処理が入り遅くなると言う記事を見つけたので、x64でも「32bit、16bit、8bit」演算ではマスク処理が入り遅くなるだろうと推測される訳です。

お礼

アルゴリズムの改善を少し頑張ってみました。具体的にはwhileループの中の次のような見直しをしました。
・std::vectorをやめて普通の配列にする。
・gmpは使用しない。gmqだけで記述可能なので。
・gmqの最大値、最小値の算出時にソートをしない。

また全ての数値を64bit型に変更しました。
whileループは最終的に約50行となりました。１番最初のパターンのみ特殊扱いになってしまうのが気になりますが。

この結果、2000万パターンで約1.8秒まで改善しました。ちなみに要素数28、グループ数14で約2000万パターンとなります。(27_C_13=20058300)
既に現実の応用範囲を超えており、プログラムの勉強みたいな感じになっていますが。

配列のソートに時間がかかっていたようです。最大値、最小値の算出にソートは必要ないですね。

#include <algorithm>

using namespace std;
typedef unsigned long long ULLONG;

void CalcOptimalGrouping(const ULLONG* gpa, const ULLONG gpa_size, const ULLONG gp)
{
ULLONG* gmq = new ULLONG[gp];
fill(gmq, gmq + gp, 1);

ULLONG* gmp = new ULLONG[gp];
fill(gmp, gmp + gp, 0);

ULLONG* gmt = new ULLONG[gp];
ULLONG* gtmp = new ULLONG[gp];

ULLONG gmmin = -1, gmmax = -1, gmmdif = -1;
ULLONG gtmin = -1, gtmax = -1, gtmdif = -1;

ULLONG gppc = 0;

while (0 < gmq[gp - 1]) {
gppc++;
fill(gmt, gmt+gp, 0);

if (gppc == 1) {
gmq[gp - 1] = gpa_size;
for (size_t i = 0; i < (gp - 1); i++) {
gmq[gp - 1] -= gmq[i];
}
}

ULLONG gmc = 0;
size_t qc = 0;
ULLONG gmq_st = 0;
for (size_t i = 0; i < gpa_size; i++) {
if ((qc < gp) && (i == (gmq_st + gmq[qc]))) {
gmq_st += gmq[qc];
qc++; gmc++;
}
gmt[gmc] += gpa[i];
}

gmmin = *min_element(gmt, gmt+gp);
gmmax = *max_element(gmt, gmt+gp);
gmmdif = gmmax - gmmin;

if ((gtmdif < 0) || (gtmdif > gmmdif)) {
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
copy(gmq, gmq+(ULLONG)gp, gtmp);
}

for (size_t k = 0; k < (gp - 1); k++) {
gmq[k]++;
for (size_t i = 0; i < k; i++) {
gmq[i] = 1;
}
gmq[gp - 1] = (ULLONG)gpa_size;

for (size_t i = 0; i < (gp - 1); i++) {
gmq[gp - 1] -= gmq[i];
}

if (0 < gmq[gp - 1]) break;
}
}

//<<Answer>>

delete[] gmq;
delete[] gmp;
delete[] gmt;
delete[] gtmp;
}

回答No.44

amanojaku1

>説明不足でした。計測時はデバッグ出力は全て無効化しています。最適化は最大の/O2としています。この状態で2000万パターンが５～６秒程度でした。コードもかなり最適化したつもりですが、まだ計算量を減らせる部分があるでしょうか。

C言語(C++も)とか、サッパリ分かりませんが、「回答No.17　amanojaku1」で言及したようにx64で下記のように「int」では遅くなるのではないかと思われます(ちなみに386(32bit)では最適化の恩恵はあまり受けられません)。
「int_fast64_t」の定義がない場合、「64bit」幅の変数を定義してみて下さい。

>vector<int> gmq(gp, 1);
>const size_t gmq_size = gmq.size();
>vector<int> gmp(gp, 0);
>const size_t gmp_size = gmp.size();
>vector<int> gmt(gp);
>const size_t gmt_size = gmt.size();
>
>vector<int> gtmp;
>int gmmin = -1;
>int gmmax = -1;
>int gmmdif = -1;
>int gtmin = -1;
>int gtmax = -1;
>int gtmdif = -1;

お礼

amanojaku1さんは何者ですか？
それだけの知識がありながらC言語はサッパリというのは？
そもそもここはC/C++/C#のスレッドですが。

回答No.43

amanojaku1

訂正です

>define hoge 0

#define hoge 0

下記では「#define」になってますね。

もう一度基礎からC言語 第14回 ヘッダファイルとプリプロセッサ指令 > 主なプリプロセッサ指令
https://www.grapecity.com/tools/support/powernews/column/clang/014/page02.htm

#if、#elif、#else、および #endif ディレクティブ (C/C++)
https://msdn.microsoft.com/ja-jp/library/ew2hz0yd.aspx