• ベストアンサー
※ ChatGPTを利用し、要約された質問です（原文：数値を複数の群に分ける最適な組み合わせを求める方法）

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

このQ&Aのポイント
  • 数値を複数の群に分ける方法について説明します。与えられた数値列で隣り合う数値しか同じ群に含めることはできず、各群の合計値が最も均等になる組み合わせを求めることが目標です。
  • 例えば、数値列{5,2,7,12,6,15,4}を3つの群に分ける場合、{5,2,7},{12},{6,15,4}という組み合わせが最も均等です。
  • 実際の問題では、組み合わせの数が増えると計算時間に影響するため、全ての組み合わせを試さずに最適な組み合わせを求める方法を提示してください。

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

  • ベストアンサー
回答No.27

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

katorea21
質問者

お礼

コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。 それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。

すると、全ての回答が全文表示されます。

その他の回答 (91)

回答No.82

>それってかなり環境依存ではないでしょうか？CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。 CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存します(自分でregister指定子を指定することでパフォーマンスが改善する可能性があるかもしれないと言う視点を持っていて損はないでしょう)。

すると、全ての回答が全文表示されます。
回答No.81

>自分でregister指定子を指定してみるのも良いかもしれません その場合、レジスターを考慮した手動の最適化も考慮してみて良いかもしれません。

すると、全ての回答が全文表示されます。
回答No.80

>↑ここの変数がレジスターに割り当てられてない場合、最大値最小値を条件付分岐で記述した方が早い可能性がありますね(^_^;) 自分でregister指定子を指定してみるのも良いかもしれません、レジスターの数には限りがあるので、何でもかんでもregisterにしていするとパフォーマンスが下がる可能性があります(それなら自動割り当ての方がマシ)。 register指定子 http://home.a00.itscom.net/hatada/c-tips/register01.html >register int n; >のように宣言した場合、int *p = &n; のようなプログラムは書けなくなる。

すると、全ての回答が全文表示されます。
回答No.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]))); ↑ここの変数がレジスターに割り当てられてない場合、最大値最小値を条件付分岐で記述した方が早い可能性がありますね(^_^;)

katorea21
質問者

お礼

仰る意味はなんとなく分かるのですが、それってかなり環境依存ではないでしょうか？CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。 自分しか使わないツールならともかく、汎用ソフトで低レベルなハード仕様を意識したコードを書くのはどうでしょうか。 さて、当初の質問とずいぶん内容がずれてきています。 これはこれで大変興味深いテーマではありますが、そろそろこの辺で打ち切りましょう。 他の方から別の解法が投稿されなければ、今週中には質問を締め切らせて頂きます。

すると、全ての回答が全文表示されます。
回答No.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])));

すると、全ての回答が全文表示されます。
回答No.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>

すると、全ての回答が全文表示されます。
回答No.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ステージ以外全てのステージが空（バブル）になるなら、パイプラインのないプロセッサと性能に大差ない状況になり、むしろパイプラインのないプロセッサよりも性能は低下する（ステージ間のオーバーヘッドがあるため）。

すると、全ての回答が全文表示されます。
回答No.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);

katorea21
質問者

お礼

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

すると、全ての回答が全文表示されます。
回答No.74

>bool型のtrueが全ビット１になるような言語や処理系があるのでしょうか？ 随分 昔の話なので何か有ったハズだったと思うのですが、そう言われるとハッキリとは思い浮かびませんでした。 下記の記事からすると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系)があります。

すると、全ての回答が全文表示されます。
回答No.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;

katorea21
質問者

お礼

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

すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

注目のQ&A

カテゴリ

OKWAVE コラム

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

専門家に質問してみよう

職業から探して質問する
質問する