質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.35%

  • Python 3.x

    2407questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

計算量を少なくするアイデア

解決済

回答 4

投稿 2017/12/04 10:42 ・編集 2017/12/06 17:57

  • 評価
  • クリップ 2
  • VIEW 293

Looove

score 2

前提・実現したいこと

処理速度を早くする方法を知りたいです。

36個の形が違う石を箱に詰めていきます。それぞれ1〜36の番号をつけます。
箱の大きさは一辺2mの立方体です。
まず、石2〜5個の組み合わせを考え、ある条件を満たしている組み合わせのみ配列に格納します。これがおおよそ800通り程あります。
その後、この800の組み合わせからさらに、5〜19個の組み合わせを考えます。この時1〜36の数字が必ず一つずつ入るような組み合わせを求めたいです。

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

計算量が膨大すぎて結果を出すのにあまりにも時間がかかる。

if k[1][0] == k[2][0]:この記述だと不完全なのはわかっていますが、どうかけばいいのかアイデアをいただきたいです。

該当のソースコード

import xlrd
import os.path
import numpy as np
import itertools
import sys
import openpyxl

xlfile = "結果.xlsx"
if os.path.exists(xlfile):
    xls = xlrd.open_workbook(xlfile)
    sheet1 = xls.sheet_by_index(0)
    nrows = sheet1.nrows
    ncols = sheet1.ncols 
    data = np.zeros(ncols*nrows).reshape((nrows, ncols))
    surablist = []
    atusalist = []
    seibunlist = []
    taisekilist = []
    kekkalist = []
    kekkalist4 = []

    for r in range(0, nrows):
        for c in range(0, ncols):
            data[r,c] = sheet1.cell(r,c).value

    for r in range(0, nrows):
        surablist.append(data[r,0])
        atusalist.append(data[r,2])
        seibunlist.append(data[r,3])
        taisekilist.append(data[r,5])

    for i, _ in enumerate(surablist, 2):
        if i == 6:
         break
        for j in itertools.combinations(surablist, r=i):
              if i == 2:
               n = int(j[0]-1)
               m = int(j[1]-1)
               if data[n,3] == data[m,3] and data[n,2] + data[m,2] <= 2.0 and data[n,5] + data[m,5] <=2.56:

 #               kekkalist.append(j)
                pass

              elif i == 3:
               o = int(j[0]-1)
               p = int(j[1]-1)
               v = int(j[2]-1)
               if data[o,3] == data[p,3] and data[o,3] == data[v,3] and data[p,3] == data[v,3] and data[o,2] + data[p,2] + data[v,2] <= 2.0 and data[o,5] + data[p,5] + data[v,5] <= 2.56:
 #               kekkalist.append(j)
                 pass


              elif i == 4:
               g = int(j[0]-1)
               u = int(j[1]-1)
               z = int(j[2]-1)
               a = int(j[3]-1)
               if data[g,3] == data[u,3] and data[g,3] == data[a,3] and data[g,3] == data[z,3] and data[u,3] == data[z,3] and data[a,3] == data[u,3] and data[z,3] == data[a,3] and data[g,2] + data[u,2] + data[z,2] + data[a,2] <= 2.0 and data[g,5] + data[u,5] + data[z,5] + data[a,5] <= 2.56:
                kekkalist4.append(j)

              else:
               q = int(j[0]-1)
               w = int(j[1]-1)
               e = int(j[2]-1)
               f = int(j[3]-1)
               h = int(j[4]-1)
               if data[q,3] == data[w,3] and data[q,3] == data[f,3] and data[q,3] == data[e,3] and data[q,3] == data[h,3] and data[w,3] == data[e,3] and data[f,3] == data[w,3] and data[h,3] == data[w,3] and data[e,3] == data[f,3] and data[e,3] == data[h,3] and data[f,3] == data[h,3] and data[q,2] + data[w,2] + data[e,2] + data[f,2] + data[h,2] <= 2.0 and data[q,5] + data[w,5] + data[e,5] + data[f,5] + data[h,5] <= 2.56:
                 kekkalist.append(j)







z = 0
a = 0
b = 0
c = 0
d = 0
e = 0
f = 0
g = 0
h = 0
j = 0
l = 0
m = 0
n = 0
o = 0
p = 0
q = 0
r = 0
s = 0
t = 0
u = 0
v = 0
w = 0
x = 0
ab=0
ac=0
ad=0
ae=0
af=0
ag=0
ah=0
ai=0
aj=0
ak=0
al=0
am=0
an=0
ao=0

for i, _ in enumerate(kekkalist4,9):
          if i == 10:
           break

          for k in itertools.combinations(kekkalist4, r=i):
             for y in range(0,9):
                 z += len(k[y])
 #               if z == 43:
 #                print(k)

                 if y == 0:
                   z = 0
                   a = 0
                   b = 0
                   c = 0
                   d = 0
                   e = 0
                   f = 0
                   g = 0
                   h = 0
                   j = 0
                   l = 0
                   m = 0
                   n = 0
                   o = 0
                   p = 0
                   q = 0
                   r = 0
                   s = 0
                   t = 0
                   u = 0
                   v = 0
                   w = 0
                   x = 0
                   ab=0
                   ac=0
                   ad=0
                   ae=0
                   af=0
                   ag=0
                   ah=0
                   ai=0
                   aj=0
                   ak=0
                   al=0
                   am=0
                   an=0
                   ao=0 

                 if k[y].count(1.0) == 1:
                        a += 1
                 if k[y].count(2.0) == 1:
                        b += 1
                 if k[y].count(3.0) == 1:
                        c += 1
                 if k[y].count(4.0) == 1:
                        d += 1
                 if k[y].count(5.0) == 1:
                        e += 1
                 if k[y].count(6.0) == 1:
                        f += 1
                 if k[y].count(7.0) == 1:
                        g += 1
                 if k[y].count(8.0) == 1:
                        h += 1
                 if k[y].count(9.0) == 1:
                        j += 1
                 if k[y].count(10.0) == 1:
                        l += 1
                 if k[y].count(11.0) == 1:
                        m += 1
                 if k[y].count(12.0) == 1:
                        n += 1
                 if k[y].count(13.0) == 1:
                        o += 1
                 if k[y].count(14.0) == 1:
                        p += 1
                 if k[y].count(15.0) == 1:
                        q += 1
                 if k[y].count(16.0) == 1:
                        r += 1
                 if k[y].count(17.0) == 1:
                        s += 1
                 if k[y].count(18.0) == 1:
                        t += 1
                 if k[y].count(19.0) == 1:
                        u += 1
                 if k[y].count(20.0) == 1:
                        v += 1
                 if k[y].count(21.0) == 1:
                        w += 1
                 if k[y].count(22.0) == 1:
                        x += 1
                 if k[y].count(23.0) == 1:
                        ab += 1
                 if k[y].count(24.0) == 1:
                        ac += 1
                 if k[y].count(25.0) == 1:
                        ad+= 1
                 if k[y].count(26.0) == 1:
                        ae += 1
                 if k[y].count(27.0) == 1:
                        af += 1
                 if k[y].count(28.0) == 1:
                        ag += 1
                 if k[y].count(29.0) == 1:
                        ah += 1
                 if k[y].count(30.0) == 1:
                        ai += 1
                 if k[y].count(31.0) == 1:
                        aj += 1
                 if k[y].count(32.0) == 1:
                        ak += 1
                 if k[y].count(33.0) == 1:
                        al += 1
                 if k[y].count(34.0) == 1:
                        am += 1
                 if k[y].count(35.0) == 1:
                        an += 1
                 if k[y].count(36.0) == 1:
                        ao += 1
                        if all([a,b,c,d,e,f,g,h,j,l,m,n,o,p,q,r,s,t,u,v,w,x,ab,ac,ad,ae,af,ag,ah,ai,aj,ak,al,am,an,ao]) == True:
                            print (k)
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Looove

    2017/12/04 11:31

    はいその通りです。

    キャンセル

  • ozwk

    2017/12/04 12:40

    でもコード見ると石のパラメータは厚さとsurab(?)と成分の3つしかないようですが。直方体+化学成分なら4つあるはずですよね?

    キャンセル

  • Looove

    2017/12/04 14:03

    石の設定としては厚さ、長さ、化学成分、幅がありますが、幅と長さは全て条件を満たしているので省いています。またsurabは1~36の番号を示しています。

    キャンセル

回答 4

checkベストアンサー

0

石2〜5個の組み合わせを考え、ある条件を満たしている組み合わせのみ配列に格納します。

ある条件とは「全てが同一成分で厚さの合計が2[m]以下」でよいでしょうか?
であれば、同一成分でグループ化し、各グループ毎に2~5個の組み合わせを列挙したほうがよいです。
さらに各成分毎のグループ内の要素を厚さ順にソートしておけば、厚さ順に組合せ列挙走査する過程で2[m]を超えたら足切りできるので、全組合せを列挙する必要もなくなります。

その後、この800の組み合わせからさらに、5〜19個の組み合わせを考えます。

この部分に該当するソースがよく理解できなかったのですが、まずは石を足した合計が36個かの判定を加えることで走査数は減ると思われます。

投稿 2017/12/04 18:28

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

問題を小さくして考えて、それを一般化した方がよいかと思います。
一辺2mの立方体の中に石は全部収まるのでしょうか。
何をされたいのかがいまいちイメージできませんでした。

もし石が立方体からあふれるのであれば、ナップザック問題のような考え方をされるとよいのではないかと思います。

投稿 2017/12/04 10:50

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/04 10:53

    言葉が足らず申し訳ありません。一辺2mの立方体はたくさんあります。ですができるだけ少ない箱数で36個の石を全て収めたいということです。

    キャンセル

  • 2017/12/04 11:12

    実際の石の形まで考慮した計算をされようとしていますか?
    それとも立方体のパターンで近似されますか?パターンの数は限定されますか?
    このあたりの考慮によって計算のやりやすさは変わってきます。
    最初の答えが yes の場合は計算は大変かと思います。
    次の答えがどちらも yes であれば、解くのはそれほど難しくはないかもしれません。

    キャンセル

  • 2017/12/04 11:24

    石の長さ、厚さ、幅、化学成分を考慮した計算をしようとしています。立方体のパターンで近似されません。

    キャンセル

  • 2017/12/04 12:34

    聞いた感じですと、3Dモデルを作って物理演算をシミュレーションしてみるというのが案外手軽そうに思います。

    キャンセル

0

アルゴリズム的にはナップサック問題でよく用いられる動的計画法を使うのがよいかと思います。

計算時間を短縮したいのであれば、C言語で書き直すとそれだけで10分の1程度の実行時間になります。
この問題、あまりpythonは得意ではありません。


他にも

g = int(j[0]-1)
u = int(j[1]-1)


のようなものを予めキャストしておくなどが考えられます。

投稿 2017/12/04 13:06

編集 2017/12/04 13:09

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

36個の形が違う石を箱に詰めていきます
処理速度を早くする方法を知りたいです

  1. 要件を整理する
  2. 速い言語で書く
  3. 速いアルゴリズムで書く

まず、要件定義を詰めるだけで、結果的に速くなる場合があります。
「化学成分」という、重要そうなキーワードが質問文にないあたり、
質問者の方の中でも、整理しきれていないように感じます。

要件しだいで速くなるというのは、たとえば、要件が許容する範囲で、
整数化したり、グリッド化(マス目に当てはめ)したり、近似化することです。

次に、実行速度が速い言語で書くだけで、何十倍も速くなる場合があります。
C/C++、C#、Javaとかです。PythonやRubyなどの動的言語は遅い。

そして、速いアルゴリズムで書くことも大事です。
今回は「ナップサック問題」っぽいので、「動的計画法(DP)」などが向いています。


また、分かりやすさにも言及したいと思います。
質問文のサンプルコードが、非常に読みにくいです。
たとえば、横に長いIF文、縦に長いIF文(の列)とか……。

もしかしたら、多少速い書き方で、わざとそう書いたのかもしれません。
しかし、遅い言語で分かりにくく書くよりも、
速い言語で分かりやすく書いた方が、はるかに早くて楽です。

多少のオーバーヘッドは無視して、
まず分かりやすく書いて、次に速く書き直す方が、
開発速度も含めて総合的には、良い結果が出ることが多いです。


この問題、要件によっては、私なら「遺伝的アルゴリズム(GA)」で書くかも。
パフォーマンスだけ見れば、動的計画法に負けることもよくあるんですが、
とにかく分かりやすいから、複雑な問題になるほど、GAの方を選びます。

具体的にどう書くか、概要を言いますと、GA部分と評価部分を分けます。
評価部分はたとえば、GUIがない自動操作の「三次元テトリス」のイメージです。
上からガッチョンガッチョン石を落として、埋まったら密度とかでスコアを評価。

GAの方は、たとえば石の選び方を遺伝子に持ちます。
(配列)変数が36個あり、箱の番号が書いてあるとか。
そうして、評価AIの効率化と、GAの効率化を別々に進めます。

GAはDPより冗長になるかもしれませんが、実装しやすいし、
変更時に何を変更するか分かりやすいので、変更しやすいです。

たとえば、化学成分の相性を判定する場合でも、
GAモジュールの方は独立してるので、変更がないわけです。

それに、判定部分にDPを使うとか、併用することも可能です。
あるいは、評価部分にもGAを使うとか、多重で使うことも可能です。

実際の実用で使うプログラムなら、たとえば変な積み方をすると、
石の重さで割れるから、構造力学的に形状と重量も考慮するとか、
サンプルよりはるかに複雑になるし、仕様変更も生じます。

「化学成分」みたいな、隠れた仕様がまだ出てきそうなので、
複雑になるようなら、GAも選択肢としてアリだと思います。

投稿 2017/12/05 04:43

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

ただいまの回答率

91.35%

関連した質問

  • 解決済

    logファイルから情報を抽出して他のファイルに出力する

    あるソフトを使いシミュレーションをしています.そのシミュレーションではlogファイルが生成され,各時刻と平均の物理量の値が記述されています.(ここでは,logファイルのStep10

  • 解決済

    不正解の理由が分からない(2次元配列問題)

    会津オンラインジャッジ(AOJ)にコードを提出するとWrong Answerとなってしまいます。 Pycharm上で同内容を実行してみると正解しているように見えます。 何が原因

  • 解決済

    pythonを使って、ExcelでUTF-8のCSVファイルを文字化けせずに開きたい

    pythonでExcelでUTF-8のCSVファイルを文字化けせずに開くシステムを作っています。 ここに記載されていることを自動化したいです。 https://teachm

  • 解決済

    python 標準入力

    初歩的な質問で申し訳ありません pythonで 1234 5678 9999 のように入力したとき 配列 e[0][0]=1 e[0][1]=2 e[0][2]=3 ... e[2

  • 解決済

    1行で表せるコードを分割して書きたい

    1行で表せるコードを分割して書きたいです。 # coding: utf-8 import itertools a = [2,5,7,3,6] b = [1,3,6,8,4]

  • 受付中

    大量のCSVデータの処理方法

    100個ほどCSVファイルがあり、 それぞれのファイルで、30×30のセルに数値が入力されています。 この100個のCSVファイルに対して、同じセル座標について最大値最小値を計算し

  • 解決済

    空欄の行をはじいて解析する

    前提・実現したいこと あるデータの解析をしたいと思っています。 745164EA 80 00 00 00 31 00 32 00 7332CD3F 080159.008 07081

  • 解決済

    うるう年を20個表示させる方法

    「YEAR」の部分にある数字を入れると、その翌年以降の閏年を20個表示するプログラムを作りたいです。 条件をif文で示すことはできているかと思うのですが、20個表示させてそこで止め

同じタグがついた質問を見る

  • Python 3.x

    2407questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。