こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

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

次のような問題を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つの中で最も均等なのは

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

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

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

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

投稿日時 - 2018-06-06 22:36:54

QNo.9505825

困ってます

質問者が選んだベストアンサー

>回答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&

投稿日時 - 2018-06-15 04:02:19

お礼

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

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

投稿日時 - 2018-06-17 01:04:10

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(92)

ANo.92

>変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。

これは最大値最小値の場合であって、他の処理でも同様ではありません。

投稿日時 - 2018-07-04 10:24:45

ANo.91

>変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。

CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存し、パフォーマンスの良し悪しが変わります。

投稿日時 - 2018-07-04 10:08:38

ANo.90

条件付分岐で分岐予測が外れた場合、パイプラインのStall(ストール:停止状態)が発生します、これは製造ラインの製品の製造が失敗し、それを破棄すると言うことになります。
それなら条件付分岐自体を使わないで記述すれば製品の破棄はなくなります。
その どちらかが筋立てとしてスマートか と言うだけの話です。
ただし、実際は それほど単純ではなく、変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。
これらはパフォーマンスの良し悪しが変わるだけで、ハードに依存して実行結果が変わる訳ではありません。
そもそも条件付分岐で分岐予測が外れた場合、製品の製造が失敗して(そして その製品を破棄して)いますが、それでもハードに依存して実行結果が変わる訳ではありません。

投稿日時 - 2018-07-04 09:30:19

ANo.89

>gmmin = (gmt[m] & (-(long long)(gmt[m]<gmmin))) | (gmmin & ~(-(long long)(gmt[m]<gmmin)));
>gmmax = (gmt[m] & (-(long long)(gmmax<gmt[m]))) | (gmmax & ~(-(long long)(gmmax<gmt[m])));

「<」:係演算子、「&、|、~」:ビット演算子、「-」:四則演算子と、どれも非常に単純な演算子だけです、これでハードに依存したりしません。
もちろんBasic系のように「(long long)(gmt[m]<gmmin))」が真の時に「-1」になる場合はマイナスしてはダメですが。

投稿日時 - 2018-07-04 02:16:06

ANo.88

>変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生する

これは、変数がレジスターに割り当てられてないと、(コードを条件付分岐自体を使って記述しようが、コードを条件付分岐自体を使わないで記述しようが)パイプライン・ハザード(パイプラインの停止状態)が発生する、と言う意味です。

投稿日時 - 2018-07-03 10:50:28

ANo.87

>それなら条件付分岐自体を使わないで記述すれば製品の破棄はなくなると言うだけの事です。

つまり、条件付分岐自体を使わないで記述した方が、コードとしては筋立てが良いと言うことです。
ただし、実際は それほど単純ではなく、変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。

投稿日時 - 2018-07-03 10:31:37

ANo.86

>それってかなり環境依存ではないでしょうか?CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。

もしかして、Stall(ストール:停止状態)云々のことを言ってますか?
あれはパイプラインの問題です。
条件付分岐で分岐予測が外れた場合、パイプラインのStall(ストール:停止状態)が発生します、これは聖像ラインの製品の製造が失敗し、それを破棄すると言うことになります。
それなら条件付分岐自体を使わないで記述すれば製品の破棄はなくなると言うだけの事です。
ただし、実際は それほど単純ではなく、変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。
これらはハードの話に聞こえるかも知れませんが(まあ実際ハードの話ですが)、ハードに依存して実行結果が変わる訳ではありません(パフォーマンスが良くなるか悪くなるかと言うだけの話です)。
そもそも条件付分岐で分岐予測が外れた場合、製品の製造が失敗していると言うことに注意して下さい、それでもハードに依存して実行結果が変わる訳ではありません。

投稿日時 - 2018-07-03 07:25:31

ANo.85

>「(long long)(gmt[m]<gmmin))」が真の時に「1」なら(signedなら)マイナスにすれば「-1」と言うだけのことです((signedなら)「-1」と言うのは全ビット「1」と言う事)。

CPUは整数の加算・減算を「2の補数」で計算します(これはCPUの普遍的な仕様と言って良いほどの決まりごと)。
「2の補数」で「-1」と言うのは全ビット「1」と言う事です。

投稿日時 - 2018-07-02 23:18:07

ANo.84

>CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存します(自分でregister指定子を指定することでパフォーマンスが改善する可能性があるかもしれないと言う視点を持っていて損はないでしょう)。

パフォーマンスの良し悪しが、CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存すると言う意味で、コード自体はハードに依存してません。

投稿日時 - 2018-07-02 22:22:15

ANo.83

>>それってかなり環境依存ではないでしょうか?CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。

>CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存します(自分でregister指定子を指定することでパフォーマンスが改善する可能性があるかもしれないと言う視点を持っていて損はないでしょう)。

コード自体はハードに依存してません。
「(long long)(gmt[m]<gmmin))」が真の時に「1」なら(signedなら)マイナスにすれば「-1」と言うだけのことです((signedなら)「-1」と言うのは全ビット「1」と言う事)。
よってコード自体は全くハードに依存してません。
もちろんBasic系のように「(long long)(gmt[m]<gmmin))」が真の時に「-1」になる場合はマイナスしてはダメですが。

投稿日時 - 2018-07-02 22:14:57

ANo.82

>それってかなり環境依存ではないでしょうか?CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。

CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存します(自分でregister指定子を指定することでパフォーマンスが改善する可能性があるかもしれないと言う視点を持っていて損はないでしょう)。

投稿日時 - 2018-07-02 22:00:57

ANo.81

>自分でregister指定子を指定してみるのも良いかもしれません

その場合、レジスターを考慮した手動の最適化も考慮してみて良いかもしれません。

投稿日時 - 2018-07-02 16:46:11

ANo.80

>↑ここの変数がレジスターに割り当てられてない場合、最大値最小値を条件付分岐で記述した方が早い可能性がありますね(^_^;)

自分でregister指定子を指定してみるのも良いかもしれません、レジスターの数には限りがあるので、何でもかんでもregisterにしていするとパフォーマンスが下がる可能性があります(それなら自動割り当ての方がマシ)。

register指定子
http://home.a00.itscom.net/hatada/c-tips/register01.html

>register int n;
>のように宣言した場合、int *p = &n; のようなプログラムは書けなくなる。

投稿日時 - 2018-07-02 15:53:58

ANo.79

>回答No.78 amanojaku1

>>fb = -(long long)(gmt[m]<gmmin);
>>gmmin = (gmt[m] & fb) | (gmmin & ~fb);
>>fb = -(long long)(gmmax<gmt[m]);
>>gmmax = (gmt[m] & fb) | (gmmax & ~fb);

>gmmin = (gmt[m] & (-(long long)(gmt[m]<gmmin))) | (gmmin & ~(-(long long)(gmt[m]<gmmin)));
>gmmax = (gmt[m] & (-(long long)(gmmax<gmt[m]))) | (gmmax & ~(-(long long)(gmmax<gmt[m])));

↑ここの変数がレジスターに割り当てられてない場合、最大値最小値を条件付分岐で記述した方が早い可能性がありますね(^_^;)

投稿日時 - 2018-07-01 08:23:01

お礼

仰る意味はなんとなく分かるのですが、それってかなり環境依存ではないでしょうか?CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。
自分しか使わないツールならともかく、汎用ソフトで低レベルなハード仕様を意識したコードを書くのはどうでしょうか。

さて、当初の質問とずいぶん内容がずれてきています。
これはこれで大変興味深いテーマではありますが、そろそろこの辺で打ち切りましょう。

他の方から別の解法が投稿されなければ、今週中には質問を締め切らせて頂きます。

投稿日時 - 2018-07-02 20:58:56

ANo.78

とりあえず、イロイロ試してみて下さい。

>これだと代入の回数が増えませんか?

とりあえず、完全にfb変数を使わない方法も試してみて下さい。

>fb = -(long long)(gmt[m]<gmmin);
>gmmin = (gmt[m] & fb) | (gmmin & ~fb);
>fb = -(long long)(gmmax<gmt[m]);
>gmmax = (gmt[m] & fb) | (gmmax & ~fb);

gmmin = (gmt[m] & (-(long long)(gmt[m]<gmmin))) | (gmmin & ~(-(long long)(gmt[m]<gmmin)));
gmmax = (gmt[m] & (-(long long)(gmmax<gmt[m]))) | (gmmax & ~(-(long long)(gmmax<gmt[m])));

投稿日時 - 2018-07-01 01:11:51

ANo.77

少し見直してみたので、とりあえずカキコしておきます。


<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gp = 4;

gmq = Array(gp).fill(1);
gmp = Array(gp).fill(0);
gmt = Array(gp);
gtmq = Array(gp);

gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = Number.MAX_SAFE_INTEGER;
gppc = 0;
gmq[gmq.length-1] = gpa.length
for(let i = 0; i<(gmq.length-1); i++){
gmq[gmq.length-1] -= gmq[i];
}
while(0<gmq[gmq.length-1]){
// ↑このwhileループ内がボトルネックなので、それ以外は どうでも良い。
gppc++;
for(let h = 0; h<gmt.length; h++){
gmt[h] = 0;
}
gmc = 0;
pn = gmq[0];
for(let i = 0; i<gpa.length; i++){
if((gmc+1)<gmp.length && pn==i){
document.write(' | ');
gmc++;
pn += gmq[gmc];
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('>gmq='+gmq+'<br>');
document.write('gmt='+gmt+'<br>');
gmmin = gmt[0];
gmmax = gmt[0];
for(let m = 1; m<gmt.length; m++){
gmmin = Math.min(gmmin,gmt[m]);
gmmax = Math.max(gmmax,gmt[m]);
}
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if(gtmdif>gmmdif){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
for(let h = 0; h<gmq.length; h++){
gtmq[h] = gmq[h];
}
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('<br>');
k = 0;
gmq[gmq.length-1] = 0;
while(gmq[gmq.length-1]<=0 && k<(gmq.length-1)){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
}
gmq[gmq.length-1] = gpa.length;
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'<br>');
for(let i = 0; i<(gmq.length-1); i++){
gmq[gmq.length-1] -= gmq[i];
}
document.write('>gmq='+gmq+'<br>');
k++;
}
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
document.write('PatternCounter='+gppc+'<br>');
// gmp = gtmp;
gmq = gtmq;
gmt = Array(gp).fill(0);
gmc = 0;
pn = gmq[0];
for(let i = 0; i<gpa.length; i++){
if((gmc+1)<gmp.length && pn==i){
document.write(' | ');
gmc++;
pn += gmq[gmc];
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('>gmq='+gmq+'<br>');
document.write('gmt='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

投稿日時 - 2018-07-01 00:14:36

ANo.76

>かえって遅くなりました。これだと代入の回数が増えませんか?

もし、最適化でレジスターに割り当てられれば、それほどペナルティにはならないと思いますが、ダメでしたか。
条件付分岐を できるだけなくして、(分岐予測が外れた場合の)パイプラインのStall(ストール:停止状態)を できるだけ発生しないようにすると良いみたいなことが言われたりすることがあります。

命令パイプライン
https://ja.wikipedia.org/wiki/%E5%91%BD%E4%BB%A4%E3%83%91%E3%82%A4%E3%83%97%E3%83%A9%E3%82%A4%E3%83%B3

>実行コードに多数の条件分岐命令があると、パイプラインによるスループット向上は望めない。プロセッサが次に実行すべき命令を知ることができないため、条件分岐命令を実行して分岐先が決まるまで、パイプラインは空(バブル)になる。分岐先の計算が完了すると、次に実行すべき命令が決まり、パイプラインが再び機能するようになる。極端な場合、パイプラインの1ステージ以外全てのステージが空(バブル)になるなら、パイプラインのないプロセッサと性能に大差ない状況になり、むしろパイプラインのないプロセッサよりも性能は低下する(ステージ間のオーバーヘッドがあるため)。

投稿日時 - 2018-07-01 00:09:30

ANo.75

>回答No.73 amanojaku1

>全てその通りの結果になります。

もし最大値最小値を条件付分岐なしに記述できると微妙にパフォーマンスが良くなる可能性があります(あくまで可能性ですが)。

>gmmin = gmt[0];
>gmmax = gmt[0];
>for(let m = 1; m<gmt.length; m++){
>gmmin = Math.min(gmmin,gmt[m]);
>gmmax = Math.max(gmmax,gmt[m]);
>}

↑この

>gmmin = Math.min(gmmin,gmt[m]);
>gmmax = Math.max(gmmax,gmt[m]);

↑ここの部分を、多分 下記のように記述できると思います。
fbは「long long」で定義。

fb = -(long long)(gmt[m]<gmmin);
gmmin = (gmt[m] & fb) | (gmmin & ~fb);
fb = -(long long)(gmmax<gmt[m]);
gmmax = (gmt[m] & fb) | (gmmax & ~fb);

投稿日時 - 2018-06-30 16:23:55

お礼

かえって遅くなりました。これだと代入の回数が増えませんか?

投稿日時 - 2018-06-30 21:42:43

ANo.74

>bool型のtrueが全ビット1になるような言語や処理系があるのでしょうか?

随分 昔の話なので何か有ったハズだったと思うのですが、そう言われるとハッキリとは思い浮かびませんでした。
下記の記事からするとBasicだったかもしれません。

ブーリアン型
https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%BC%E3%83%AA%E3%82%A2%E3%83%B3%E5%9E%8B

>Visual Basic には Boolean 型があり、比較演算の結果はこの型となる。16ビット(2バイト)の整数として格納されるが、値は True(-1) と False(0) しかない。

シグマクレスト社員ブログ 論理演算
http://sigma-crest.com/blog/2013/07/30/logical_operation/

>ただし、trueが「0以外」だと定数として定義できないため、trueを1としている言語(多数)と、-1としている言語(BASIC系)があります。

投稿日時 - 2018-06-30 00:22:56

ANo.73

>もし最大値最小値を条件付分岐なしに記述できると微妙にパフォーマンスが良くなる可能性があります(あくまで可能性ですが)。

「(int)(0==0)」は「1」になると言うのは言語仕様ですか?(どんなC++でも共通ですか?)

下記は可能ですか?、bは「18446744073709551615」になりますか?

long long a = -((long long)(0==0) & 1);
unsigned long long b = _UI64_MAX;
b = a & b;

下記は可能ですか?、bは「18446744073709551615」になりますか?

long long a = -((long long)(0==0) & 1);
unsigned long long b = _UI64_MAX;
b = (unsigned long long)a & b;

下記は可能ですか?、bは「9223372036854775807」になりますか?

long long a = -((long long)(0==0) & 1);
long long b = _I64_MAX;
b = a & b;

投稿日時 - 2018-06-29 20:59:02

お礼

全てその通りの結果になります。

投稿日時 - 2018-06-30 14:10:03

ANo.72

>回答No.71 amanojaku1

もし最大値最小値を条件付分岐なしに記述できると微妙にパフォーマンスが良くなる可能性があります(あくまで可能性ですが)。
最大値最小値に条件付分岐自体がなければ、そこ(最大値最小値)でパイプラインのStall(ストール:停止状態)が発生することもない訳です。

投稿日時 - 2018-06-29 20:50:22

ANo.71

「(int)(0==0)」は「1」になると言うのは言語仕様ですか?(どんなC++でも共通ですか?)

下記は可能ですか?、bは「18446744073709551615」になりますか?

long long a = (long long)(0!=0);
unsigned long long b = _UI64_MAX;
a = (a & 1)-1;
b = (unsigned long long)a & b;

下記は可能ですか?、bは「9223372036854775807」になりますか?

long long a = (long long)(0!=0);
long long b = _I64_MAX;
a = (a & 1)-1;
b = a & b;

投稿日時 - 2018-06-29 19:58:36

ANo.70

下記は可能ですか?、bは「18446744073709551615」になりますか?

long long a = 0!=0;
unsigned long long b = _UI64_MAX;
a = (a & 1)-1;
b = a & b;

下記は可能ですか?、bは「9223372036854775807」になりますか?

long long a = 0!=0;
long long b = _I64_MAX;
a = (a & 1)-1;
b = a & b;

投稿日時 - 2018-06-29 19:37:11

ANo.69

>回答No.67 amanojaku1

セミコロンが全角になってました。

下記は可能ですか?、bは「18446744073709551615」になりますか?

long long a = 0==0;
unsigned long long b = _UI64_MAX;
b = a&b;

下記は可能ですか?、bは「18446744073709551615」になりますか?

unsigned long long a = 0==0;
unsigned long long b = _UI64_MAX;
b = a&b;

下記は可能ですか?、bは「9223372036854775807」になりますか?

long long a = 0==0;
long long b = _I64_MAX;
b = a&b;

投稿日時 - 2018-06-29 02:07:07

ANo.68

>回答No.45

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

↑少々疑問なんですが「ULLONG* gmp = new ULLONG[gp];」だけで、gmpはゼロ・クリアされないですか?

投稿日時 - 2018-06-29 02:02:50

お礼

C++はそういう言語仕様です。
Javaなら0で初期化されます。

投稿日時 - 2018-06-29 21:50:59

ANo.67

>回答No.66 amanojaku1

>signed long long a = 0==0;
>
>↑例えばこれで「-1」になりませんか?
>そうすれば最大値最小値を条件付分岐なしに記述できると思いますが。

long long a = 0==0;

↑例えばこれで「-1」になりませんか?

unsigned long long b = 0==0;

↑例えばこれで「18446744073709551615」になりませんか?

下記は可能ですか?、bは「18446744073709551615」になりますか?

long long a = 0==0;
unsigned long long b = _UI64_MAX;
b = a&b;

下記は可能ですか?、bは「18446744073709551615」になりますか?

unsigned long long a = 0==0;
unsigned long long b = _UI64_MAX;
b = a&b;

下記は可能ですか?、bは「9223372036854775807」になりますか?

long long a = 0==0;
long long b = _I64_MAX;
b = a&b;

投稿日時 - 2018-06-29 01:40:11

お礼

私の環境では全て1になります。bool型のtrueが全ビット1になるような言語や処理系があるのでしょうか?

投稿日時 - 2018-06-29 21:48:45

ANo.66

>これは特定のコンパイラでしか使えないpragmaですね。そもそもpragmaは言語仕様ではなく、コンパイラ固有のオプションのようなものですね。
>私の環境ではこのpragmaは使えませんでした。

駄目でしたか。

>最大値最小値を条件付分岐なしに記述できると良いのですが。

signed long long a = 0==0;

↑例えばこれで「-1」になりませんか?
そうすれば最大値最小値を条件付分岐なしに記述できると思いますが。

投稿日時 - 2018-06-29 01:04:37

お礼

これは1になりますね。C言語ではbool型は1バイトで内部表現はtrueが0x01、falseが0x00となります。
trueを0xffで表現するような自前のbool型を開発すれば、期待されている処理も可能かもしれませんが。
プリミティブ型のオーバーロード(?)は出来ないと思います。

投稿日時 - 2018-06-29 21:44:58

ANo.65

>分岐予測が外れStall(ストール:停止状態)が発生すると言うのはベルトコンベア上の"命令"の破棄です。

例えばパイプラインが15ステージだとすると、分岐予測が外れStall(ストール:停止状態)が発生すると、ベルトコンベア上の14個の"命令"が破棄されます。

投稿日時 - 2018-06-28 20:06:09

ANo.64

>ザックリと言うとCPUのパイプラインとはベルトコンベアのように"命令"を流れ作業で処理するとイメージして下さい。
>分岐予測が外れStall(ストール:停止状態)が発生すると言うのはベルトコンベア上の"命令"の破棄です。
>一番単純なパイプラインは3ステージです「フェッチ、デコード、実行」、実際のパイプラインは おおよそ10~20ステージ程度です。

製品の製造とはチョット違うのですが、下記のようなベルトコンベアをイメージすると分かりやすいでしょう。

投稿日時 - 2018-06-28 19:41:30

ANo.63

>分岐予測が外れたら(CPUの)パイプラインのStall(ストール:停止状態)が発生します。

ザックリと言うとCPUのパイプラインとはベルトコンベアのように"命令"を流れ作業で処理するとイメージして下さい。
分岐予測が外れStall(ストール:停止状態)が発生すると言うのはベルトコンベア上の"命令"の破棄です。
一番単純なパイプラインは3ステージです「フェッチ、デコード、実行」、実際のパイプラインは おおよそ10~20ステージ程度です。
Stall(ストール:停止状態)して10~20もパイプラインの"命令"が破棄されると言うのは、できるだけ避けるべきでしょう。

投稿日時 - 2018-06-28 18:38:30

ANo.62

>for(let k = 0; k<(gmq.length-1); k++){
>gmq[k]++;
>for(let i = 0; i<k; i++){
>gmq[i] = 1;
>}
>gmq[gmq.length-1] = gpa.length
>document.write(
>'k='+k+'; '+
>'gmq[k]='+gmq[k]+'; '+
>'<br>');
>// p = 0;
>for(let i = 0; i<(gmq.length-1); i++){
>gmq[gmq.length-1] -= gmq[i];
>// p += gmq[i];
>// gmp[i+1] = p;
>}
>document.write('>gmq='+gmq+'<br>');
>if(0<gmq[gmq.length-1]){
>break;
>}
>}

(分岐予測が外れたら(CPUの)パイプラインのStall(ストール:停止状態)が発生しますので)内部的な条件付分枝は減らすべきですね。

k = 0;
gmq[gmq.length-1] = 0;
while(gmq[gmq.length-1]<=0 && k<(gmq.length-1)){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
}
gmq[gmq.length-1] = gpa.length
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'<br>');
// p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gmq.length-1] -= gmq[i];
// p += gmq[i];
// gmp[i+1] = p;
}
document.write('>gmq='+gmq+'<br>');
k++;
}

投稿日時 - 2018-06-28 18:36:55

ANo.61

>最大値最小値を条件付分岐なしに記述できると良いのですが。

「std::min、std::max」の内部はアセンブラなので、その可能性があるかもしれないので、試してみて下さい。

投稿日時 - 2018-06-28 05:38:36

ANo.60

>下記を記述してみてコンパイルが通るか試してみては?
>
>#pragma forceinline std::min
>#pragma forceinline std::max

良く分かりませんが、例では行末のセミコロンは付いてないようです。

投稿日時 - 2018-06-28 00:09:22

ANo.59

>回答No.58 amanojaku1

>VisualC++では出来ないと思います。

下記を記述してみてコンパイルが通るか試してみては?

#pragma forceinline std::min
#pragma forceinline std::max

投稿日時 - 2018-06-28 00:05:56

ANo.58

>「#pragma forceinline」で定義すると関数をinline化できるみたいな記事がありましたので。

下記は「#pragma inline」の例です。

top>コンパイラ編>コンパイラ言語仕様>拡張言語仕様>拡張言語仕様の使用方法>関数のインライン展開(#pragma inline/#pragma noinline)
http://tool-support.renesas.com/autoupdate/support/onlinehelp/ja-JP/csp/V4.01.00/CS+.chm/Compiler-CCRL.chm/Output/cd_EXP_LANG16.html

>#pragma inline i_func
>
>static int i_func(int i)
>{
> return ++i;
>}

投稿日時 - 2018-06-27 23:57:20

お礼

これは特定のコンパイラでしか使えないpragmaですね。そもそもpragmaは言語仕様ではなく、コンパイラ固有のオプションのようなものですね。

私の環境ではこのpragmaは使えませんでした。

投稿日時 - 2018-06-28 21:13:54

ANo.57

>min_element,max_elementはSTLのライブラリ関数なのでinline化は出来ません。
>他の環境なら可能かも知れませんが、VisualC++では出来ないと思います。

「min_element,max_element」(はプープが入るので)ではなく「std::min、std::max」のほうです。
「#pragma forceinline」で定義すると関数をinline化できるみたいな記事がありましたので。

>関数呼び出しではなく最大値最小値を求めるロジックを直接whileループ中に書きました。つまり普通にinlineになっています。

分岐予測が外れたら(CPUの)パイプラインのStall(ストール:停止状態)が発生します。
最大値最小値を条件付分岐なしに記述できると良いのですが。

投稿日時 - 2018-06-27 23:42:56

ANo.56

>回答No.54 amanojaku1

>if((gmc+1)<gmp.length){
>if(pn==i){
>document.write(' | ');
>gmc++;
>pn += gmq[gmc];
>}
>}

(分岐予測が外れたら(CPUの)パイプラインのStall(ストール:停止状態)が発生しますので)内部的な条件付Jumpは減らすべきですね。

if((gmc+1)<gmp.length && pn==i){
document.write(' | ');
gmc++;
pn += gmq[gmc];
}

投稿日時 - 2018-06-27 23:31:34

ANo.55

>回答No.54 amanojaku1

>とにかくwhileループ内がボトルネック

つまり、それ以外は どうでも良い。

投稿日時 - 2018-06-27 23:12:50

ANo.54

>gmpは使用しない。

確かに良く考えたら無くても良いですね。
変な部分があったので修正しましたので一応 投稿します(とにかくwhileループ内がボトルネック)。



<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gp = 4;

gmq = Array(gp).fill(1);
gmp = Array(gp).fill(0);

gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = -1;
gppc = 0;
gmq[gmq.length-1] = gpa.length
for(let i = 0; i<(gmq.length-1); i++){
gmq[gmq.length-1] -= gmq[i];
}
while(0<gmq[gmq.length-1]){
gppc++;
gmt = Array(gp).fill(0);
gmc = 0;
pn = gmq[0];
for(let i = 0; i<gpa.length; i++){
if((gmc+1)<gmp.length){
if(pn==i){
document.write(' | ');
gmc++;
pn += gmq[gmc];
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('>gmq='+gmq+'<br>');
document.write('gmt='+gmt+'<br>');
gmmin = gmt[0];
gmmax = gmt[0];
for(let m = 1; m<gmt.length; m++){
gmmin = Math.min(gmmin,gmt[m]);
gmmax = Math.max(gmmax,gmt[m]);
}
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if((gtmdif<0)||(gtmdif>gmmdif)){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmq = gmq.slice();
// gtmp = gmp.slice();
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('<br>');
for(let k = 0; k<(gmq.length-1); k++){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
}
gmq[gmq.length-1] = gpa.length
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'<br>');
// p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gmq.length-1] -= gmq[i];
// p += gmq[i];
// gmp[i+1] = p;
}
document.write('>gmq='+gmq+'<br>');
if(0<gmq[gmq.length-1]){
break;
}
}
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
document.write('PatternCounter='+gppc+'<br>');
// gmp = gtmp;
gmq = gtmq;
gmt = Array(gp).fill(0);
gmc = 0;
pn = gmq[0];
for(let i = 0; i<gpa.length; i++){
if((gmc+1)<gmp.length){
if(pn==i){
document.write(' | ');
gmc++;
pn += gmq[gmc];
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('>gmq='+gmq+'<br>');
document.write('gmt='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

投稿日時 - 2018-06-27 22:55:54

ANo.53

>回答No.46 amanojaku1

>この結果、2000万パターンで

ちなみに、このように何千万回もループする場合、関数を呼ぶだけでも微妙に時間が かかるので、どうしても関数を呼ぶ必要が有る場合はインライン化してみて下さい。

投稿日時 - 2018-06-27 01:44:41

ANo.52

>回答No.51 amanojaku1

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

投稿日時 - 2018-06-27 01:08:10

お礼

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

投稿日時 - 2018-06-27 22:32:32

ANo.51

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

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

投稿日時 - 2018-06-27 00:32:57

ANo.50

>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」でインライン化を定義しておく
}

投稿日時 - 2018-06-26 17:13:33

お礼

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

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

投稿日時 - 2018-06-26 23:50:07

ANo.49

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

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

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

投稿日時 - 2018-06-26 00:53:54

ANo.48

>回答No.46 amanojaku1

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

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

投稿日時 - 2018-06-26 00:25:05

ANo.47

>回答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++;
}
}

投稿日時 - 2018-06-25 23:56:20

ANo.46

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

そこが問題でしたか。

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

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

>この結果、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++;
}

投稿日時 - 2018-06-25 23:30:05

ANo.45

>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」演算ではマスク処理が入り遅くなるだろうと推測される訳です。

投稿日時 - 2018-06-24 00:36:40

お礼

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

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

この結果、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;
}

投稿日時 - 2018-06-25 21:45:44

ANo.44

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

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;

投稿日時 - 2018-06-23 13:19:22

お礼

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

投稿日時 - 2018-06-23 14:47:00

ANo.43

訂正です

>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

投稿日時 - 2018-06-23 02:06:48

ANo.42

>C++で書き直したコードを載せます。行数の関係上、デバッグ出力部は省略しています。C++11な環境でしかビルド出来ないかも知れません。
>このコードで私の環境では2000万パターンを超えても5秒程度で結果が出ました。

>行数の関係上、デバッグ出力部は省略しています。

と言う事はデバッグ出力が残ってますか?、デバッグ出力で時間が掛かっている可能性があります、(ループ内にある)デバッグ出力は下記のように「#if~#endif」で囲ってみて下さい(ちなみに最適化は有効になってますか?)。

define hoge 0 ←デバッグ時は1以上に設定
#if (0<hoge)
デバッグ出力
#endif

詳細は下記参照。

ロベールのC++教室 - 第18章 if...2 - - Biglobe
http://www7b.biglobe.ne.jp/~robe/cpphtml/html03/cpp03018.html

投稿日時 - 2018-06-23 01:49:04

お礼

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

投稿日時 - 2018-06-23 09:24:14

ANo.41

>肝は どのパラメータを使うか、と言うか この手法が使えるパラメータを選択できるか(イメージできるか)です。
>
>例えばgmqとgmpは別の表現方法で本質は同じモノですが、gmpでは この手法は使えません。

gpaのパターンの2回目の桁の繰り上がりを する前までをイメージするとgmpでは この手法は使えない事がわかります、そこで このパターンに対応できるgmqが必要だろうと考えられます。
つまり何も無い所から このパターンをイメージできるかが肝になります。

5, | 2, | 7, | 12,6,15,4,
5,2, | 7, | 12, | 6,15,4,
5,2,7, | 12, | 6, | 15,4,
5,2,7,12, | 6, | 15, | 4,
5, | 2,7, | 12, | 6,15,4,
5,2, | 7,12, | 6, | 15,4,
5,2,7, | 12,6, | 15, | 4,

投稿日時 - 2018-06-20 16:37:54

ANo.40

>この手の応用力は訓練で磨くというより直観なんでしょうか。アルゴリズムに慣れた人なら何てことはないのでしょうが、普通に情報数学を勉強した程度の頭では現実の問題に応用するのは難しいです。

そこよりも、下記の方が重要です(もし、gmqを思いつかなければ この手法は使えないので)。

>肝は どのパラメータを使うか、と言うか この手法が使えるパラメータを選択できるか(イメージできるか)です。
>
>例えばgmqとgmpは別の表現方法で本質は同じモノですが、gmpでは この手法は使えません。

投稿日時 - 2018-06-20 05:36:34

ANo.39

>4桁が難しいなら、3桁の一部のパターンをイメージすれば良いでしょう。

桁数が多くて難しい場合は、桁数を減らして一部のパターンをイメージすれば良いでしょう。

投稿日時 - 2018-06-19 23:44:34

ANo.38

>この手の応用力は訓練で磨くというより直観なんでしょうか。アルゴリズムに慣れた人なら何てことはないのでしょうが、普通に情報数学を勉強した程度の頭では現実の問題に応用するのは難しいです。

人には得意・不得意と言うのがあるようで、N進数の応用は割りとできる方です。

>1,1,1,3
>2,1,1,2
>3,1,1,1
>4,1,1,0

↑この部分のパターンを見れば、最上位桁がゼロの場合に桁の繰り上がりが必要と言うのが分かります。
(全てのパターンを考える必要はありません)4桁が難しいなら、3桁の一部のパターンをイメージすれば良いでしょう。

投稿日時 - 2018-06-19 23:31:19

ANo.37

>ちなみにgmqの最上位桁がゼロの場合が桁の繰り上がり条件と言うのは非常に稀です。
>恐らく今後 一生 なかなか お目にかかれないアルゴリズムと言って良いでしょう。

つまり、gmqの最上位桁がゼロの場合が桁の繰り上がり条件と言うアルゴリズムは、今後 役に立つ機会は殆ど無いだろうと思われます。

投稿日時 - 2018-06-19 20:32:03

ANo.36

ちなみにgmqの最上位桁がゼロの場合が桁の繰り上がり条件と言うのは非常に稀です。
恐らく今後 一生 なかなか お目にかかれないアルゴリズムと言って良いでしょう。

投稿日時 - 2018-06-19 05:40:29

ANo.35

肝は どのパラメータを使うか、と言うか この手法が使えるパラメータを選択できるか(イメージできるか)です。

例えばgmqとgmpは別の表現方法で本質は同じモノですが、gmpでは この手法は使えません。

>自分なら最上位桁のさらに上に計算用の桁を追加してしまいそうですが

この場合は たまたまgmqの最上位桁がゼロが有り得ない値なので、そのまま使えましたが、場合によってはオバーフロー用の桁を追加したり、オバーフロー用のフラグ変数を別途用意する必要があります。

投稿日時 - 2018-06-17 14:53:19

ANo.34

>ざっくりとしたアルゴリズムは
>kの初期値は「0」
>kが示す「gmqの桁」(gmq[k])に1を加算
>下位の桁は1クリア
>gmqの最上位の桁(gmq[gp-1])の値を算出
>ついでにgmq要素の値を算出
>gmqの最上位の桁(gmq[gp-1])の値を算出、ゼロならループする(その場合kは加算(k++)される)

ざっくりとしたアルゴリズムは
kの初期値は「0」
kが示す「gmqの桁」(gmq[k])に1を加算
下位の桁は1クリア
gmqの最上位の桁(gmq[gp-1])の値を算出
ついでにgmq要素の値を算出
gmqの最上位の桁(gmq[gp-1])の値を算出、ゼロなら「k<(gmq.length-1)」までループする(その場合kは加算(k++)される)
ループ条件が「k<gmq.length」ではなく「k<(gmq.length-1)」になっている事に注意して下さい。
breakせずにループが完了した場合は、gmq要素の最上位の桁(gmq[gp-1])がゼロ(gmqがオバーフロー)となります

投稿日時 - 2018-06-17 12:30:45

お礼

N=6, GC=4で全パターンを並べてみました。
この場合は3桁の3進数ですね。

1,1,1,3
2,1,1,2
3,1,1,1
4,1,1,0
1,2,1,2 <=2桁目に繰り上がり
2,2,1,1
3,2,1,0
1,3,1,1
2,3,1,0
1,1,2,2 <=3桁目に繰り上がり
2,1,2,1
3,1,2,0
1,2,2,1
2,2,2,0
1,3,2,0
1,1,3,1
2,1,3,0
1,2,3,0
1,1,4,0 <=繰り上がり完了


実際に全パターンを並べてみれば、これがN進数を加算した時の各桁の並びに等しいことが分かりますね。
ただこの問題の場合は普通のN進数と異なり、無の桁が0ではなく1となるのでイメージしにくいのでした。全体的に1を引けば普通のN進数ですね。
最上位桁が0になることをもって桁上がりを判定するなど、面白いテクニックが詰まっていると思います。
この手の応用力は訓練で磨くというより直観なんでしょうか。アルゴリズムに慣れた人なら何てことはないのでしょうが、普通に情報数学を勉強した程度の頭では現実の問題に応用するのは難しいです。

ともあれ大変勉強になりました。他の方の解法もあるかも知れませんので、もうしばらくオープンにしておきます。

投稿日時 - 2018-06-19 21:47:11

ANo.33

>k=2; gmq[k]=2; ←「k=2」なので「gmq[2]++」で「gmq[1]=1」、下位の桁は1クリア

k=2; gmq[k]=2; ←「k=2」なので「gmq[2]++」で「gmq[2]=2」、下位の桁は1クリア

投稿日時 - 2018-06-17 11:34:47

ANo.32

>ついでにgmq要素の値を算出

ついでにgmp要素の値を算出

投稿日時 - 2018-06-17 11:28:37

ANo.31

>回答No.29 amanojaku1

>JavaScriptを実行してデバッグ表示からgmq要素の値の変化を見た方がイメージしやすいです

>回答No.30 amanojaku1

分かりやすそうな部分を説明します。
JavaScriptのプログラムと合わせて お読み下さい。
gmq要素の表示は左側が最下位の桁、右側が最上位の桁です。

5, | 2,7,12,6, | 15, | 4,
>gmq=1,4,1,1
gmt=5,27,15,4
gmmin=4; gmmax=27; gmmdif=23;
gtmin=6; gtmax=19; gtmdif=13;

まずパターンの生成処理に入る前のgmqは上記の「1,4,1,1」になってます。
下記のkが加算されるgmqの桁を示しています。
ざっくりとしたアルゴリズムは
kの初期値は「0」
kが示す「gmqの桁」(gmq[k])に1を加算
下位の桁は1クリア
gmqの最上位の桁(gmq[gp-1])の値を算出
ついでにgmq要素の値を算出
gmqの最上位の桁(gmq[gp-1])の値を算出、ゼロならループする(その場合kは加算(k++)される)

k=0; gmq[k]=2; ←「k=0」なので「gmq[0]++」で「gmq[0]=2」
>gmq=2,4,1,0 ←gmqの最上位の桁(gmq[gp-1])の値がゼロならループする(その場合kは加算(k++)される)
k=1; gmq[k]=5; ←「k=1」なので「gmq[1]++」で「gmq[1]=5」、下位の桁は1クリア
>gmq=1,5,1,0 ←gmqの最上位の桁(gmq[gp-1])の値がゼロならループする(その場合kは加算(k++)される)
k=2; gmq[k]=2; ←「k=2」なので「gmq[2]++」で「gmq[1]=1」、下位の桁は1クリア
>gmq=1,1,2,3 ←gmqの最上位の桁(gmq[gp-1])の値がゼロではないのでループからbreak

投稿日時 - 2018-06-17 11:23:52

お礼

目から鱗です。何とも美しいアルゴリズムですね。

最上位桁に最大値を入れておくというのがポイントですね。これがforループの最後の周回で0になった時点で下位桁の繰り上がりが全て終了し、パターンの網羅が完了すると。
自分なら最上位桁のさらに上に計算用の桁を追加してしまいそうですが、最上位桁は全体から残りを引けば自動的に計算出来ますね。

単純に要素数(N)を5、群の数(GC)を3にして並べてみると理解出来ました。4以上だと組み合わせも増えてきて頭の中では難しいですね。

1,1,5 <=初期状態

1,1,3 <=1番目のパターン
2,1,2
3,1,1
4,1,0 <=繰り上がり
1,2,2
2,2,1
3,2,0 <=繰り上がり
1,3,1
2,3,0 <=繰り上がり
1,4,0 <=繰り上がり(終了)

いつも見る2進数とビットの並びが逆なのでちょっと混乱してしまいましたが、分かればどうと言うことはないですね。実際は2進数ではなく(N-(GC-1))進数ですか。

投稿日時 - 2018-06-17 13:33:37

ANo.30

>実際にgmq要素の値を表示するように変更してもいいですし

<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gp = 4;

gmq = Array(gp).fill(1);
gmp = Array(gp).fill(0);

gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = -1;
gppc = 0;
// gtmp, gtmq, gppc
while(0<gmq[gp-1]){
gppc++;
// gmq[2] = gpa.length-(gmq[0]+gmq[1]);
gmq[gp-1] = gpa.length
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
gmt = Array(gp).fill(0);
gmc = 0;
pc = 1;
for(let i = 0; i<gpa.length; i++){
if(pc<gmp.length){
if(gmp[pc]==i){
pc++;
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('>gmq='+gmq+'<br>');
document.write('gmt='+gmt+'<br>');
gmm = gmt.slice().sort((a, b) => a-b);
gmmin = gmm[0];
gmmax = gmm[gmm.length-1];
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if((gtmdif<0)||(gtmdif>gmmdif)){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmq = gmq.slice();
gtmp = gmp.slice();
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('<br>');
for(let k = 0; k<(gmq.length-1); k++){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
}
gmq[gp-1] = gpa.length
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'<br>');
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
document.write('>gmq='+gmq+'<br>');
if(0<gmq[gp-1]){
break;
}
}
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
gppc
document.write('PatternCounter='+gppc+'<br>');
gmp = gtmp;
gmt = Array(gp).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
for(let j = 1; j<gmp.length; j++){
if(gmp[j]==i){
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gmt='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

投稿日時 - 2018-06-17 05:41:26

ANo.29

訂正です。

>// 「gtmdif、gtmin、gtmax、gtmq、gtmp」の保存

// 「gtmdif、gtmin、gtmax、gtmq、gtmp」への保存

>何となく分かってきました

パターンの生成は何となくで充分です。
それよりJavaScriptを実行してデバッグ表示からgmq要素の値の変化を見た方がイメージしやすいです(実際にgmq要素の値を表示するように変更してもいいですし)。
// gmq:gpaを分割する際の配列要素数(配列)
// 例えば{5},{2,7},{12,6,15,4}の場合、gmqは{1},{2},{4}

投稿日時 - 2018-06-17 02:45:33

ANo.28

>2進数の数学的特徴

どんなn進数でも良いですが、例は3進数です。
3桁の2進数なら「000、001、010、011、100、101、110、111」となります。

投稿日時 - 2018-06-17 02:17:44

ANo.26

>回答No.25 amanojaku1

>>分かりやすい説明のためです、どんなn進数でも良いです

>この場合のアルゴリズムは「n進数」と言う固定的なモノではなく、「可変進数」みたいな感じです。

パターンの詳細はJavaScriptを実行してデバッグ表示を参照して下さい。

投稿日時 - 2018-06-15 03:17:18

ANo.25

>回答No.23 amanojaku1

>分かりやすい説明のためです、どんなn進数でも良いです

この場合のアルゴリズムは「n進数」と言う固定的なモノではなく、「可変進数」みたいな感じです。

投稿日時 - 2018-06-15 03:14:48

ANo.24

>回答No.23 amanojaku1

>// 例えば3桁の3進数の全てのパターンを生成すると考えて下さい
>// 「000、001、002、010、011、012、020、021、022、100、…、222」となります。
>// 基本は1づつ加算していて、桁の繰り上がり時に下位の桁が全てクリアされます。
>// 「222」に1が加算されるとオバーフローとなってパターンの生成は完了します。
>// このアイデアを応用しています(そのまま使っている訳ではありません)
>// gmqを対象にパターンを生成しています、gmqの場合 桁の繰り上がり時に下位の桁はゼロ・クリアでは無く「1クリア」であると言う事に注意して下さい。

{5,2,7,12,6,15,4}で群の数を3にすると

まず、gmq[0]は1づつ加算されます
{5/2/7,12,6,15,4}
{5,2/7/12,6,15,4}
{5,2,7/12/6,15,4}
{5,2,7,12/6/15,4}
{5,2,7,12,6/15/4}
ここで桁が上がります
{5/2,7/12,6,15,4}
gmq[1]へ桁が繰り上がりgmq[1]が2、gmq[0]が「1クリア」されます。
パターンの詳細はJavaScriptを実行してデバッグ表示を参照して下さい。

投稿日時 - 2018-06-15 03:03:03

ANo.23

>C++に移植したところ、性能はかなり改善しました。実用的には十分です。
>ところで、提示頂いたプログラムですが、簡単なコメントを入れて頂くことは出来ますでしょうか?各変数の意味、ブロック単位の処理内容、while文を抜ける条件などが書いてあれば処理の流れを理解出来ると思います。

こちらでは文字数制限で投稿できないので下記に投稿しました。

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

投稿日時 - 2018-06-15 02:07:03

お礼

C++で書き直したコードを載せます。行数の関係上、デバッグ出力部は省略しています。C++11な環境でしかビルド出来ないかも知れません。
このコードで私の環境では2000万パターンを超えても5秒程度で結果が出ました。

全パターンを網羅せずに済む方法を考えてみましたがやはり難しいですね。gtmdif=0となれば以降の探索を打ち切るようにしましたが、このようなケースは稀でしょう。

この書き方だと、1番目のパターンのみfor文で生成しないため、少々特殊になってしまいます。まあ大した問題でもないですが。
コメントやデバッグ出力を除くと、アルゴリズムの肝であるwhile文は実質70行程度になりました。一見複雑と思える問題が、僅か数10行程度のシンプルなプログラムで記述出来ることに今更ながら感動しています。
数学力というよりは、問題の本質を見極めて、既知のアルゴリズムに当てはまるよう単純化する能力が必要ですね。

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;
typedef long long LLONG;

// n!
LLONG factorial(const LLONG n)
{
_ASSERT(n >= 0);
if (n == 0)return 1LL;

LLONG tmp = n;
for (LLONG i = 1; i < n - 1; ++i)
tmp *= (n - i);
return tmp;
}

void CalcOptimalGrouping(const vector<int> gpa, const int gp)
{
const size_t gpa_size = gpa.size();

if (gpa_size == 0 || gp >(int)gpa_size)
{
printf("Invalid input.");
return;
}

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;

LLONG gppc = 0;

// gtmp, gtmq, gppc
while (0 < gmq[gp - 1]) {
gppc++;

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

fill(gmt.begin(), gmt.end(), 0);
int gmc = 0;
size_t pc = 1;
bool filter = false;
for (size_t i = 0; i < gpa_size; i++) {
filter = false;
if ((pc < gmp_size) && (gmp[pc] == i)) {
pc++;
printf(" | ");
gmc++;
filter = true;
}
gmt[gmc] += gpa[i];

if (filter || i == 0)printf("%d", gpa[i]);
elseprintf(",%d", gpa[i]);
}

vector<int> gmm = gmt;
sort(gmm.begin(), gmm.end());
gmmin = gmm[0];
gmmax = gmm[gmm.size() - 1];
gmmdif = gmmax - gmmin;

if ((gtmdif < 0) || (gtmdif > gmmdif)) {
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmp = gmp;
}

if (gtmdif == 0)break;

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

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

if (0 < gmq[gp - 1]) {
break;
}
}
printf("\n");
}


// 全パターン網羅出来ているかチェック((要素数-1)から(グループ数-1)を選択する場合の数に等しい)
const LLONG gppc_calc = factorial(gpa_size - 1) / ((factorial(gp - 1) * factorial((gpa_size - 1) - (gp - 1))));// nCr = n! / (r! * (n-r)!)
_ASSERT(gppc_calc == gppc);

/********************* <<Answer>> *********************/

}

int main()
{
gpa = {5,2,7,12,6,15,4};
int gp = 3;
CalcOptimalGrouping(gpa, gp);
}

投稿日時 - 2018-06-22 23:33:08

ANo.22

どうでしょうか?、JavaScriptをCに変換できたでしょうか?

投稿日時 - 2018-06-14 18:44:25

お礼

C++に移植したところ、性能はかなり改善しました。実用的には十分です。
ところで、提示頂いたプログラムですが、簡単なコメントを入れて頂くことは出来ますでしょうか?各変数の意味、ブロック単位の処理内容、while文を抜ける条件などが書いてあれば処理の流れを理解出来ると思います。

投稿日時 - 2018-06-15 00:05:43

ANo.21

>参考にさせて頂きます。
言葉のキャッチボールが上手くできていないようです。
元データの数列(要素数が不定の整数値配列)を何処から持ってくるのかを補足して頂くこととグループの数(与えられた個数の群)をどのように定義するかを補足頂けないと一般化の可否が考え難いと言ったつもりです。
回答No.11のお礼にある下記の関数のコードが今回の質問の趣旨のように推測しました。
void GetOptimalCombination(int* pSrc, int nSize, int nBlock, int** ppResult);
従って、元データの数列とグループ数の組み合わせを数例提示して頂けるよう申し上げました。
別解(C言語以外での処理)の方法で対処することになったのであれば質問を締め切ってください。

投稿日時 - 2018-06-13 08:25:43

ANo.20

>任意のグループ数に対応出来ますか?
要素数とグループの数によってはループの多重化に限界があると思います。
グループ数が4以上になるとパターン数の計算にも工夫が増えますので専門のプログラマーに委託された方が良いでしょう。
パターン毎のグループ合計を配列変数に保存してすべての計算が済んでから組み合わせの判定をすれば良いでしょう。

>再帰を使うようなイメージだったのですが。
私はプログラマーではありませんので詳しいことは分かりませんが再帰を多重化したときにループから抜け出せなくなることもあるようですから方法論を良く検討してください。

>I/Fのイメージとしてはこんな感じです。
前述のようにプログラマーではないので提示の関数(サブルーチン)については理解できません。
何れにしてもmain()から関数へ条件を渡して戻り値で要素の配列とグループ数を得ると解釈します。
要素の配列とグループ数の模擬データを数組提示して頂ければ暇を見ながら考えたいと思います。(解決は難しいかも知れません)

投稿日時 - 2018-06-10 09:41:35

お礼

ご回答ありがとうございました。参考にさせて頂きます。

投稿日時 - 2018-06-13 01:03:59

ANo.19

>回答No.18 amanojaku1

ただし、デメリットもあります。
x64で「int_fast32_t」と定義した場合(8 バイト:64 ビット)と、386(32bit)で「int_fast32_t」と定義した場合(4 バイト:32 ビット)では、ザイズが変わってしまいます。
4 バイト (32 ビット)で符号付き整数値の範囲は「-2,147,483,648~2,147,483,647」
8 バイト (64 ビット)で符号付き整数値の範囲は「-9,223,372,036,854,775,808~9,223,372,036,854,775,807」
例えば、ビット演算でNOTを使ったりすると明確に違う値になります(当然、それ以外でも明確に違う値になる場合はあるでしょう)。

(「x64、386(32bit)」の両対応にしたい場合で)これが問題になる場合は基本的に「int_fast~_t」は使わないほうが良いでしょうが、どうしても必要な場合はプログラマーが それに対応できるプログラムを作る必要があります。

投稿日時 - 2018-06-10 08:03:55

お礼

ご回答ありがとうございました。参考にさせて頂きます。

投稿日時 - 2018-06-13 01:04:25

ANo.18

>回答No.17 amanojaku1

x64で「int_fast32_t」と定義しても、32bit演算にはならないと言う事に注意して下さい。
32bit以上のbit数が保障され、そのCPUの最速のbit数になります(x64なら64bit)。

投稿日時 - 2018-06-10 07:29:38

ANo.17

>回答No.16 amanojaku1

組み込みにおけるCプログラムの速度最適化
https://qiita.com/YankeeDeltaBravo225/items/274b92735fbafc060a75

>32bit CPUを使う前提で書きます。
>基本的に32bit CPUは32bit演算しかできません。
>(64bit演算もできるものはあったりしますが)
>では8bit,16bit変数の演算はどうなるかと言うと、
>32bitで演算した結果に対して0xFF (8bit) / 0xFFFF (16bit)の
>ビットマスクを掛けるので、その分遅くなります。

↑これは32bit CPUの話ですが、恐らく64bit CPUでも「32bit、16bit、8bit」演算ではマスク処理が入り遅くなると予想されます。

投稿日時 - 2018-06-10 07:18:39

ANo.16

>回答No.15 amanojaku1

x64だけで良いなら「int_fast64_t」で定義すれば良いですし、i386(32bit)も視野に入れたいなら「int_fast32_t」で定義しておけばi386(32bit)でコンパイルした時に極端に遅くなったりはしないと思われます(ただしi386(32bit)はレジスターが少ないのでレジスターによる最適化の恩恵は あんまり受けられないと思われますが…)

投稿日時 - 2018-06-10 05:51:49

ANo.15

>回答No.14 amanojaku1

最も速い数値型
http://cpp.aquariuscode.com/int_fast_t

>今やどこを見ても64bitCPUで溢れています。
>にも関わらず、多くの環境でintは4byteのままです。
>今の時代で引数に盲目的にintを指定することは、環境の変化に対応しきれていない可能性があります。
>幸いにも、どの環境でもなるべく高効率になる数値型を標準が用意してくれています。

>fastの後ろの数値が最低限保証するbit精度です。
>例えばuint_fast8_tは「最低でも8bitの精度が保証された中で最速のデータ幅」を持つ符号無し整数を表します。

投稿日時 - 2018-06-10 04:54:08

ANo.14

>>ただJavaScriptだと群の数が増えると急激に重くなりますね。Cに移植すれば高速になるでしょうか。

>コンパイラーなら問題ないと思いますよ。

x64の方がレジスターが多いので、x64で(最適化を有効にし)コンパイルすると良いらしいです。

コンパイラの最適化についてすべてのプログラマが知っておくべきこと (第 2 部)
https://msdn.microsoft.com/ja-jp/magazine/dn973015.aspx

>レジスタ割り当て
>レジスタ割り当てとは、変数用にメモリを確保する必要をなくし、使用可能なレジスタに一連の変数を割り当てるプロセスです。このプロセスは通常、1 つの関数全体のレベルで実行されます。ただし、リンク時のコード生成 (/LTCG) が有効になっている場合は特に、複数の関数にまたがってこのプロセスを実行して、さらに効率の高い割り当てが可能になる場合があります (ここでは、特に記載がない限り、変数はすべて自動変数、つまり構文上有効期間が決まる変数です)。
>
>レジスタ割り当ては、特に重要な最適化です。これを理解するために、さまざまなレベルのメモリへのアクセスにかかる時間を確認します。レジスタへのアクセスにかかる時間は 1 プロセッサ サイクル未満です。キャッシュへのアクセスは少し時間がかかり、数サイクル~数十サイクルです。(リモート) DRAM メモリへのアクセスはそれよりもずっと時間がかかります。さらに、ハード ドライブへのアクセスは非常に遅く、数百万サイクルかかります。また、メモリ アクセスによって共有キャッシュやメイン メモリとのトラフィックが増加します。レジスタ割り当てを行い、使用可能なレジスタをできる限り活用することで、メモリへのアクセス回数が減少します。
>
>コンパイラは各変数のレジスタへの割り当てを試みます。その変数が関係するすべての命令が実行されるまで、変数がレジスタに割り当たったままの状態が理想です。後ほど簡単に説明する理由からよく起こることですが、割り当て状態を維持できないと、1 つ以上の変数がメモリに吐き出され、読み込みと書き込みが頻繁に行われることになります。レジスタ負荷とは、レジスタの使用を維持できないために変数がメモリに吐き出されたレジスタの数を表します。レジスタ負荷が大きいほどメモリのアクセス回数が多くなり、メモリのアクセス回数が増えるとプログラム自体が遅くなるだけでなく、システム全体の処理速度が低下する可能性があります。
>
>最新の x86 プロセッサには、コンパイラが割り当てることができるレジスタとして、8 個の 32 ビット汎用レジスタ、8 個の 80 ビット浮動小数点レジスタ、および 8 個の 128 ビット ベクター レジスタがあります。すべての x64 プロセッサに、16 個の 64 ビット汎用レジスタ、8 個の 80 ビット浮動小数点レジスタ、および最低 16 個の (128 ビット幅以上の) ベクター レジスタがあります。最新の 32 ビット ARM プロセッサには、15 個の 32 ビット汎用レジスタと 32 個の 64 ビット浮動小数点レジスタがあります。すべての 64 ビット ARM プロセッサには、31 個の 64 ビット汎用レジスタ、32 個の 128 ビット浮動小数点レジスタ、および 16 個の 128 ビット ベクター レジスタ (NEON) があります。これらのレジスタはすべて、レジスタ割り当てに使用できます (また、グラフィック カードに用意されているレジスタもこの一覧に加えることができます)。使用可能なレジスタのどれにもローカル変数を割り当てられない場合、その変数はスタック上に割り当てられます。

投稿日時 - 2018-06-10 00:28:46

ANo.13

>ただJavaScriptだと群の数が増えると急激に重くなりますね。Cに移植すれば高速になるでしょうか。

コンパイラーなら問題ないと思いますよ。

投稿日時 - 2018-06-09 23:24:41

お礼

C++に移植したところ、性能はかなり改善しました。実用的には十分です。
ところで、提示頂いたプログラムですが、簡単なコメントを入れて頂くことは出来ますでしょうか?各変数の意味、ブロック単位の処理内容、while文を抜ける条件などが書いてあれば処理の流れを理解出来ると思います。

投稿日時 - 2018-06-14 18:38:02

ANo.12

>回答No.10 amanojaku1

ほんのチョッピリ(処理的に)スマートになりました。
デバッグ用の表示も分かりやすく変更してます。

>群の数をNに一般化出来るでしょうか?

「gp」に群の数を代入して下さい。
下記はJavaScriptです(「gp = 4」にしています)



<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gp = 4;

gmq = Array(gp).fill(1);
gmp = Array(gp).fill(0);

gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = -1;
gppc = 0;
// gtmp, gtmq, gppc
while(0<gmq[gp-1]){
gppc++;
// gmq[2] = gpa.length-(gmq[0]+gmq[1]);
gmq[gp-1] = gpa.length
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
gmt = Array(gp).fill(0);
gmc = 0;
pc = 1;
for(let i = 0; i<gpa.length; i++){
if(pc<gmp.length){
if(gmp[pc]==i){
pc++;
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gmt='+gmt+'<br>');
gmm = gmt.slice().sort((a, b) => a-b);
gmmin = gmm[0];
gmmax = gmm[gmm.length-1];
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if((gtmdif<0)||(gtmdif>gmmdif)){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmq = gmq.slice();
gtmp = gmp.slice();
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('<br>');
for(let k = 0; k<(gmq.length-1); k++){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
}
gmq[gp-1] = gpa.length
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'<br>');
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
document.write('gmq='+gmq+'<br>');
if(0<gmq[gp-1]){
break;
}
}
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
gppc
document.write('PatternCounter='+gppc+'<br>');
gmp = gtmp;
gmt = Array(gp).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
for(let j = 1; j<gmp.length; j++){
if(gmp[j]==i){
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gmt='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

投稿日時 - 2018-06-09 08:53:07

お礼

素晴らしいです。意外とシンプルに書けるものなんですね。
ただJavaScriptだと群の数が増えると急激に重くなりますね。Cに移植すれば高速になるでしょうか。

投稿日時 - 2018-06-09 22:29:59

ANo.11

>最後の結果出力のところに微妙にバグがあるような気がするのですが。
余分な行を削除しながら最終調整したときに修正ミスがあったようです。
printf("Group1 = {");
for(int i = 0; i < ik; i++) {
printf("%d,", arry[i]);
}
printf("%d}\n", arry[ik]);
printf("Group2 = {");
for(int l = ik; l < jk; l++) {
printf("%d,", arry[l]);
}
printf("%d}\n", arry[jk]);
printf("Group3 = {");
for(int l = jk; l < n-2; l++) {
printf("%d,", arry[l]);
}
printf("%d}\n",arry[n-1]);
    ↓
printf("Group1 = {");
for(int i = 0; i < ik; i++) {
printf("%d,", arry[i]);
}
printf("%d}\n", arry[ik]);
printf("Group2 = {");
for(int l = ik+1; l < jk; l++) {
printf("%d,", arry[l]);
}
printf("%d}\n", arry[jk]);
printf("Group3 = {");
for(int l = jk+1; l < n-1; l++) {
printf("%d,", arry[l]);
}
printf("%d}\n",arry[n-1]);

>ところでこれを群の数Nに一般化出来るでしょうか?
グループの数を任意に変えるためにはforループの多重化と関連しますのでグループの数に応じたforループを作成する必要があります。
結局、コードが長文になります。
汎用化するとグループの数や元の数列を何処から取得するのでしょう?

投稿日時 - 2018-06-09 08:00:27

お礼

>グループの数を任意に変えるためにはforループの多重化と関連しますのでグループの数に応じたforループを作成する必要があります。
任意のグループ数に対応出来ますか?再帰を使うようなイメージだったのですが。

>汎用化するとグループの数や元の数列を何処から取得するのでしょう?
関数の引数で渡します。I/Fのイメージとしてはこんな感じです。

void GetOptimalCombination(int* pSrc, int nSize, int nBlock, int** ppResult);

nBlockが群の数です。ppResultは区切り位置のインデックスの配列で、サイズはnBlock-1と予め分かっているので呼び出し側で確保します。関数内で確保しても良いですが。

投稿日時 - 2018-06-09 12:00:02

ANo.10

群の数をNに一般化出来るでしょうか?

「gp」に群の数を代入して下さい。
下記はJavaScriptです(「gp = 4」にしています)


<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gp = 4;

gmq = Array(gp).fill(1);
gmp = Array(gp).fill(0);

gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = -1;
gppc = 0;
// gtmp, gtmq, gppc
while(0<gmq[gp-1]){
gppc++;
// gmq[2] = gpa.length-(gmq[0]+gmq[1]);
gmq[gp-1] = gpa.length
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
gmt = Array(gp).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
for(let j = 1; j<gmp.length; j++){
if(gmp[j]==i){
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gmt='+gmt+'<br>');
gmm = gmt.slice().sort((a, b) => a-b);
gmmin = gmm[0];
gmmax = gmm[gmm.length-1];
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if((gtmdif<0)||(gtmdif>gmmdif)){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmq = gmq.slice();
gtmp = gmp.slice();
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('gtmq='+gtmq+'<br>');
document.write('gtmp='+gtmp+'<br>');
for(let k = 0; k<(gmq.length-1); k++){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
document.write(
'i='+i+'; '+
'<br>');
}
gmq[gp-1] = gpa.length
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'gmq[gp-1]='+gmq[gp-1]+'; '+
'<br>');
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
document.write(
'i='+i+'; '+
'p='+p+'; '+
'gmp[i+1]='+gmp[i+1]+'; '+
'<br>');
}
if(0<gmq[gp-1]){
break;
}
}
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
gppc
document.write('PatternCounter='+gppc+'<br>');
gmp = gtmp;
gmt = Array(gp).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
for(let j = 1; j<gmp.length; j++){
if(gmp[j]==i){
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gtmq='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

投稿日時 - 2018-06-09 01:32:40

ANo.9

>回答No.8 amanojaku1

>数値の数が増えると組み合わせの数も大幅に増えて

>条件として、与えられた数値列で隣り合う数値しか同じ群に含めることは出来ない。

↑良く考えて下さい、この条件だと組み合わせの数は膨大には増えません。

投稿日時 - 2018-06-08 22:53:01

お礼

そうですね。よく考えると等比級数的には増えていかないですね。

投稿日時 - 2018-06-09 12:02:40

ANo.8

>>>数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。

>>コンパイラーなら それほど心配する必要もないかと思いますが?

>同じパターンを2回以上作らないように注意する必要はあるでしょうが。

同じパターンを2回以上作らないようにすれば[5,2,7,12,6,15,4]でパターン数は「15」です。
下記はJavaScriptです(ファイル名は「test001.htm」などにして下さい)、パターン数は「PatternCounter」に表示されます。



<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gmq = Array(3).fill(1);
gmp = Array(3).fill(0);
// gmt = Array(3).fill(0);
gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = -1;
gppc = 0;
// gtmp, gtmq, gppc
while(0<gmq[2]){
gppc++;
gmq[2] = gpa.length-(gmq[0]+gmq[1]);
gmp[1] = gmq[0];
gmp[2] = gmq[0]+gmq[1];
gmt = Array(3).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
if(gmp[1]==i||gmp[2]==i){
document.write(' | ');
gmc++;
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gtmq='+gmt+'<br>');
gmm = gmt.slice().sort((a, b) => a-b);
gmmin = gmm[0];
gmmax = gmm[gmm.length-1];
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if((gtmdif<0)||(gtmdif>gmmdif)){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmq = gmq.slice();
gtmp = gmp.slice();
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('gtmq='+gtmq+'<br>');
document.write('gtmp='+gtmp+'<br>');
gmq[0]++;
gmq[2] = gpa.length-(gmq[0]+gmq[1]);
if(gmq[2]<=0){
gmq[0] = 1;
gmq[1]++;
}
gmq[2] = gpa.length-(gmq[0]+gmq[1]);
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
gppc
document.write('PatternCounter='+gppc+'<br>');
gmp = gtmp;
gmt = Array(3).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
if(gmp[1]==i||gmp[2]==i){
document.write(' | ');
gmc++;
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gtmq='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

投稿日時 - 2018-06-08 22:34:13

お礼

ご回答ありがとうございます。
提示頂いたプログラムで正しい結果が出力されました。まだ全部理解出来ていませんが、群の数をNに一般化出来るでしょうか?

投稿日時 - 2018-06-08 23:15:11

ANo.7

>お聞きしたかったのは、その組み合わせを網羅するコードはCでどのように書けば良いかということでした。
目的の結果を見つけ出すにはすべての組み合わせをチェックしなければなりません。
C言語に限らずコンピューターのプログラムはデジタル的に可否を判定しなければなりません。
典型的な例としてはforループやdoループですべての組み合わせをifの条件分岐で求める条件へ導きます。
従って、効果的な処理方法は無駄な繰り返しを行わないことです。
提示の数値配列で3つのグループの組み合わせで1つのパターンについてグループ1、グループ2の合計を求めれば予め求められる配列値の合計からグループ1とグループ2の合計を差し引けば残りの値がグループ3の合計になりますので計算手順が省略できます。
また、グループ1のパターン毎の合計を計算するループの中にグループ2のパターン毎の合計を求めるループを組み込めば重複計算になりません。

>さらに突っ込んで、全組み合わせを網羅せずに済む方法
それは無理かと思います。

>「均等」という概念をより数学的な条件に置き換えて効率的なアルゴリズムが組めないか
予め汎用のサブルーチンを作成しておかないとできないと思います。
それより、単純な比較演算を繰り返した方が快適に動くかも知れません。
取敢えず、全パターンを計算して各グループの合計値の差が最小の組み合わせを求めるC言語のコードを提示します。(リストはインデントが表示できませんので参考のために画像も添付します。)
/*
* sample.c
*/
#include <stdio.h>

int main(void) {
int arry[] = {5, 2, 7, 12, 6, 15, 4};
const int n = sizeof arry /sizeof arry[0];
int t0 = 0;
int pt = 0;
for(int i = 0; i < n; i++) {
t0 += arry[i];
if(i<n-2) pt = pt + i +1;
}
int t1 = 0;
int t3;
int k = 0;
int l;
int ik, jk;
int defmin =t0;
for(int i = 0; i < n-2; i++) {
t1 += arry[i];
int t2 = 0;
for(int j = i +1; j < n-1; j++) {
t2 += arry[j];
t3 = t0 -t1 -t2;
int min = t3;
k++;
if(t1 < min) min = t1;
if(t2 < min) min = t2;
int max = t3;
if(max < t1) max = t1;
if(max < t2) max = t2;
if(defmin > (max - min)) {
defmin = (max - min);
l = k;
ik =i;
jk =j;
}
}
}
printf("Minimum = [%d] (Pattern %d)\n", defmin, l);
printf("Group1 = {");
for(int i = 0; i < ik; i++) {
printf("%d,", arry[i]);
}
printf("%d}\n", arry[ik]);
printf("Group2 = {");
for(int l = ik; l < jk; l++) {
printf("%d,", arry[l]);
}
printf("%d}\n", arry[jk]);
printf("Group3 = {");
for(int l = jk; l < n-2; l++) {
printf("%d,", arry[l]);
}
printf("%d}\n",arry[n-1]);
return 0;
}

投稿日時 - 2018-06-08 21:20:45

お礼

ご回答ありがとうございます。
最後の結果出力のところに微妙にバグがあるような気がするのですが。ところでこれを群の数Nに一般化出来るでしょうか?

投稿日時 - 2018-06-08 23:21:59

ANo.6

>>数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。

>コンパイラーなら それほど心配する必要もないかと思いますが?

同じパターンを2回以上作らないように注意する必要はあるでしょうが。

投稿日時 - 2018-06-08 18:25:33

ANo.5

>全ての組み合わせを試すことなく答えにたどり着く方法があれば

多分 無いと思います。

>数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。

コンパイラーなら それほど心配する必要もないかと思いますが?

投稿日時 - 2018-06-08 17:43:45

ANo.4

>群の数Nに一般化できるでしょうか?
>Cのコードでどのような実装になるかご提示頂いた方が
>イメージしやすいと思います。

4以上、さらにNに一般化となると、
コード化以前にロジックが思いつきません。
失礼しました。

投稿日時 - 2018-06-08 08:52:40

ANo.3

>お聞きしたかったのは、その組み合わせを網羅するコードはCでどのように書けば良いかということでした。
私の回答は「考え方だけでも提示頂ければと思います。」に対するものであることを明示しています。
質問の数列の範囲であれば手作業で出来ていますのでC言語のコード化は可能と思います。
具体的なC言語のコードを提示するには実証してからでないと回答できません。
従って、無料指導を所望されても即答は難しいです。
暇があるときに少しずつコード化して纏ってからの回答で良ければ手掛けても良いです。(回答を待てる期限を示してください)

投稿日時 - 2018-06-07 21:39:16

お礼

ありがとうございます。すぐに必要というわけではありませんので気長に待ちます。

投稿日時 - 2018-06-07 22:54:08

ANo.2

>要素数が不定の整数値配列
整数ではなく、自然数という条件であれば、...

{5,2,7,12,6,15,4}  

・合計を求める 51
・3で割る   17
・各要素を左側から積み上げ
 17を超える箇所を求める:7と12の間 ※L1
・各要素を右側から積み上げ
 17を超える箇所を求める:4と15の間 ※R1

・続いて、※L1、※R1の1つ内側をそれぞれ見つけ
 ※L2、※R2とします。

以下、
※L1、※R1
※L1、※R2
※L2、※R1
※L2、※R2
の4通りを評価することで見つけることができるだろうと思います。

なお、
私自身がが論理的に証明できる方法ではなく、
ちょっと自信がありませんので、
可能なら、いくつかのパターンで検証してほしいところです。

投稿日時 - 2018-06-07 10:14:40

お礼

ご回答ありがとうございます。
数値列は整数ではなく自然数です。より具体的に言えば文字列の行数ですので確実に1以上の整数です。

さて、ご提示の方法は群の数が3の場合の例だと思いますが、群の数Nに一般化できるでしょうか?
Cのコードでどのような実装になるかご提示頂いた方がイメージしやすいと思います。

投稿日時 - 2018-06-07 21:01:04

ANo.1

>考え方だけでも提示頂ければと思います。
貼付画像は手作業で作成したものです。
同等の組み合わせ配列を配列変数に作成すれば判断できるはずです。
元の配列は大きくなれば作業に必要な配列が増えますので効率の良いアルゴリズムを考えてみると良いでしょう。
プログラムを組むときにフローチャートを書くと処理の誤りを防げると思います。

投稿日時 - 2018-06-07 09:04:15

お礼

ご回答ありがとうございます。
お聞きしたかったのは、その組み合わせを網羅するコードはCでどのように書けば良いかということでした。
さらに突っ込んで、全組み合わせを網羅せずに済む方法や、「均等」という概念をより数学的な条件に置き換えて効率的なアルゴリズムが組めないか考えて頂けると助かります。

投稿日時 - 2018-06-07 21:01:38

あなたにオススメの質問