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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

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

Q&A

解決済

2回答

1429閲覧

Pythonの高速化

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

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

0グッド

0クリップ

投稿2019/08/09 07:19

編集2019/08/09 07:56

#※すみません、質問内容に記載したコードの変数等が意味をなしていないので変更しました。あと、さらなる問題が発覚したので追記しました。

###時間のかかる以下のコードを改善したいです↓

python3

1 2import more_itertools 3 4amino_acid = 'L'*4 + 'A'*4 + '-'*13 5gen = more_itertools.distinct_permutations(amino_acid) 6all_patarn = list(gen) 7 8patarn_list = [] 9 10for each_patarn in all_patarn: 11 string_aminoacid = "" 12 for each_patarn_word in each_patarn: 13 string_aminoacid += each_patarn_word 14 print(string_aminoacid) 15 patarn_list.append(string_aminoacid) 16 string_aminoacid = ""

これで14,244,300通りの計算をしたことになるのですが、かなり時間がかかってしまいます。(5~6分前後)
もっと、高速化するためにforを2回繰り返しているところを改善したいのですが、どのようにすると良いでしょうか?
ご教授ください。

さらにここから、以下のコードに完成したデータを代入する予定です。
amino_acidは21個の文字列でできているため、14,244,300*21通りの処理をすることとなり、かなり遅くなってしまうことが確実です。

Python3

1import more_itertools 2 3amino_acid = 'L'*4 + 'A'*4 + '-'*13 4gen = more_itertools.distinct_permutations(amino_acid) 5all_patarn = list(gen) 6 7patarn_list = [] 8 9for each_patarn in all_patarn: 10 string_aminoacid = "" 11 for each_patarn_word in each_patarn: 12 string_aminoacid += each_patarn_word 13 # print(string_aminoacid) 14 patarn_list.append(string_aminoacid) 15 string_aminoacid = "" 16 17↑上記コードと同様 18------------------------------------------- 19↓上記の結果を利用するコード 20 21seq_num_1 = len(patarn_list[0]) 22seq_num = len(patarn_list) 23seq_list = [] 24for create_seq in range (0,seq_num_1): 25 seq_unit = "" 26 for create_seq_1 in range (0,seq_num): 27 seq = patarn_list[create_seq_1][create_seq] 28 seq_unit += seq 29 seq_list.append(seq_unit) 30 seq_unit = "" 31print(seq_list)

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

y_waiwai

2019/08/09 07:22

そのコードはなにをしようとしてるんでしょうか。
退会済みユーザー

退会済みユーザー

2019/08/09 07:48 編集

♦︎コードの上側で実施していること 上のコードで、「L」を4文字、「A」を4文字、「-」を13文字含む文字列について、その並び方を全て生成しています。 ゆえに、21C4*17C4通りの並べ方が存在するため、約1400万通りの文字列が生成されています。 ※ここでの「C」はcombination計算をすることを意味しています。 ♦︎「-」で区切った下側で実施していること さらに、追記したコードでは、それぞれの並べ方に対して、先頭の1文字目から最後の文字までを縦に一列ずつ取得するためのコードです。文字列は21文字に設定しているため、1400万*21通りの処理を行うことになります。 1400万通りだけで5分程度待たないといけないので、その数に21をかけた処理を行うのにどれだけの時間がかかるのか、想像しただけで寒気がするので質問させていただきました。
tiitoi

2019/08/09 07:49

後半のコードが column_list 等が定義されていない (質問のコードに含まれていない) ためエラーとなります。
退会済みユーザー

退会済みユーザー

2019/08/09 07:57

すみませんでした。column_listを修正しました。
barobaro

2019/08/10 14:52

素朴な疑問なのですがこのデータって転置する意味があるのでしょうか? 転置した場合 21!/4!/4!/13! = 14244300 どこの列を切り出しても L=2713200 4/21 A=2713200 4/21 -=8817900 13/21 ソートされているわけでもないし組み合わせの意味がないような気がするのですが 同じものを含む順列でしたらリストひとつずつ枝刈していけば計算量を減らすことはできます。
退会済みユーザー

退会済みユーザー

2019/08/10 15:57 編集

♦︎簡潔に説明すると以下です。 「このデータを作成する意味は、データからアミノ酸の保存度を算出する際に、答えあわせ用に存在するサイトで算出される値と自分のプログラムに同じデータを通した時の値を比較、検討することです。 そして、転置しないと、自分のプログラムと比較する答えあわせ用のサイトに通らない」 からです。 つまり、データとして適しているものを作成。そのあとに、そのデータを答えあわせするサイトに通すために転置するという手順を取っています。 これ以上、目的や何をしているのか?を説明するとなると、実際にアミノ酸保存度に関する論文を読んでいただく方が早いかと思います。
barobaro

2019/08/10 16:19

ご説明どうもありがとうございます。 確認のため必要なのですね。すっきりしました。
guest

回答2

0

ベストアンサー

前半部分に関しては、以下のようにすることで、一部コピーなどを回避することで 53秒 → 17秒に短縮できました。

文字のリストは join() で結合できます。

python

1lst = ["A", "B", "C"] 2print("".join(lst)) # ABC

python

1import more_itertools 2 3amino_acid = "L" * 4 + "A" * 4 + "-" * 13 4gen = more_itertools.distinct_permutations(amino_acid) 5 6patterns = ["".join(p) for p in gen] 7print(len(patterns)) # 14244300 8# 17.8 s

追記

後半でやっていることは、行と列を入れ替える、つまり、転置をとってるということですよね。
そうであれば、前半で一旦結合しないで、そのまま list(gen) で (14244300, 21) の2次元のリストにして、転置して (21, 14244300) の2次元配列にすればいいと思います。
必要であれば、そのあと join() で文字列にしてください。

python

1import numpy as np 2import more_itertools 3 4amino_acid = "L" * 4 + "A" * 4 + "-" * 13 5gen = more_itertools.distinct_permutations(amino_acid) 6 7# 全パターン生成する。 8patterns = np.array(list(gen)) 9print(len(patterns)) # 14244300 10 11# 転置をとる。 12trans = patterns.T 13 14# 文字列にしたい場合は結合する。 15ret = ["".join(x) for x in trans]

投稿2019/08/09 07:48

編集2019/08/09 08:15
tiitoi

総合スコア21954

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2019/08/09 07:52 編集

ありがとうございます!導入します! genの中の要素をリスト内でjoinして、そのままリストに格納する方法ですね! 理解しました!
hayataka2049

2019/08/09 08:19 編集

あ、なるほど転置なのかこれ。気づきませんでした。
退会済みユーザー

退会済みユーザー

2019/08/09 08:26

おっしゃる通りです。これが転置という言葉で表せることを知りませんでした。 初めから転置でお伝えできればよかったです、勉強になりました。 コードもありがとうございます。
tiitoi

2019/08/09 08:29

1文字4バイトなので、全部で 1196521200 bytes = 9.5GB になりますね。 かなり巨大な配列なので、このあとなにか計算する際は注意しないとメモリが足りなくなりそうです。
退会済みユーザー

退会済みユーザー

2019/08/09 08:40

お気遣いありがとうございます。 ここからさらに自作のプログラムに通すのですが・・・ 足りなくなるかもしれないです・・・
hayataka2049

2019/08/09 08:42 編集

ん、計算ミスってませんか? 普通に1GB前後かと。ただ、ほぼ同容量のpythonオブジェクトもあるので、実際のメモリ消費は数GBくらいになりますが。
退会済みユーザー

退会済みユーザー

2019/08/09 08:44 編集

メモリ8GBなんで、なんとか足りますね・・・
tiitoi

2019/08/09 08:44

すみません。たしかに1.19Gですね、間違えていました。 1Gぐらいならそこまで心配する必要はないですね。
退会済みユーザー

退会済みユーザー

2019/08/09 08:45

お二人ともありがとうございました。
guest

0

これで十分です。

python

1import more_itertools 2 3amino_acid = 'L'*4 + 'A'*4 + '-'*13 4all_patterns = list(map("".join, more_itertools.distinct_permutations(amino_acid)))

~~ただし、組み合わせの数が大きいので、21倍するとそもそもメモリに乗るかどうかというところでしょう。
~~
何をするにしてもこんな大きいものをナイーブに扱っていたらバカ遅いので、アルゴリズムの面で工夫しないといけない気がします。

追記

実測した感じ、numpyで転置取るよりはzipの方が倍くらい速かったです。

python

1import more_itertools 2 3amino_acid = "L" * 4 + "A" * 4 + "-" * 13 4gen = more_itertools.distinct_permutations(amino_acid) 5 6patterns = list(map("".join, zip(*gen))) 7

投稿2019/08/09 07:56

編集2019/08/09 08:47
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2019/08/09 08:02

ご回答ありがとうございます。 そうですね、扱う数が大きすぎるのは確かに問題です。文字列を作成する前提から見直す必要があるかもしれません。 アルゴリズムの工夫について調べてみました。 http://research.nii.ac.jp/~uno/algo_3.htm 確かに書いてある内容についてはなるほどと思いましたが、今回のコードに応用できる考え方をすぐに思いつけないのが自分の悲しいところです。少し考えてみます。
hayataka2049

2019/08/09 08:05

ぜんぶの組み合わせを生成して終わりじゃなくて、それ使って何かやるんじゃないですか? それなら、何かしら効率のいいやり方があるだろうなと思うのですが。
退会済みユーザー

退会済みユーザー

2019/08/09 08:13 編集

そうです、生成されたデータを使ってそのデータをもう一度組み直します。 ただ、組み直した先のデータは、作成した元データがないと作成できないと考えられます。 21文字の文字列の中で、どの場所にどの文字があるのか?がとても重要な情報で、この手順を踏まずに得たいものを効率よく得られると考えられないと思います。もっと単純に考えられればいいのですが、難しいかと思われます。
hayataka2049

2019/08/09 08:20

tiitoiさんの回答のやり方で行けそうですね。データ量が21倍になる訳ではないなら、なんとかなるか。
退会済みユーザー

退会済みユーザー

2019/08/09 08:25

tiitoiさんのおっしゃる通り、行と列を入れ替えることと同義です。 なんとかなるようでよかったです。方針を変更せざるを得ないかと思いました(汗) それにしてもhayataka2049さんは実務でPythonを使っているから、こんなにも早く解決策等を思いつくのでしょうか?もっとPython、もといプログラミングに慣れるのはどうしていったらよいでしょうか? Atcoederとか解くべきですかね・・
hayataka2049

2019/08/09 08:30

やれば慣れます。それより、最初から(21, 14244300)で生成する方法がないかを考えているのですが、なかなか思いつきません。効率のいい方法が見つかったら追記しておきます。
退会済みユーザー

退会済みユーザー

2019/08/09 08:37

精進します。 ありがとうございます。お時間ある時にお願いします。
hayataka2049

2019/08/09 08:45

とりあえず安直なのを一つ。
退会済みユーザー

退会済みユーザー

2019/08/09 08:49

ありがとうございます。そもそも何やってるのかよくわかってないので、移動するのですぐにはできませんが、到着し次第、調べます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問