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

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

新規登録して質問してみよう
ただいま回答率
85.35%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

4回答

761閲覧

競プロ どこが計算量を食っているのか

kay_ventris4

総合スコア269

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/12/09 12:26

編集2021/12/09 12:30

###問題
イメージ説明
問題リンク

(概要)
長さnの英小文字列sが与えられ、そこから最終的にちょうどk文字を取り除きたい。取り除く順番のルールは、まずaが存在する限り左から取り除く。aがなくなったらbが存在する限り左から取り除く。bがなくなったら…。yがなくなったらzが存在する限り左から取り除く。といった手法を用いる。最終的に得られるsはどのようなものか。

#コード

Python

1n, k = map(int, input().split()) 2s = list(str(input())) 3 4length = 0 5li = [] 6for i in range(97, 97 + 26): 7 for j in range(n): 8 if s[j] == chr(i): 9 li.append(j) 10 length += 1 11 if length == k: 12 break 13 else: 14 continue 15 break 16 17li = set(li) 18 19ans = '' 20for i in range(n): 21 if i not in li: 22 ans += s[i] 23 24print(ans)

#方針
aからzの順に、かつ左から右の順に、取り除かれる要素のインデックスをリストliに追加していき、最後はそのli(setに変換後)にインデックスが含まれていないものだけを文字列ansに追加していき出力する。

#疑問
制限時間は2秒となっており、10^8回程度の計算は耐えられるかなと思い、nが高々4×10^5であることに鑑みて、a-zとの二重ループでも問題はないだろうという風に鷹を括っていたのですが、どの部分が具体的に計算時間を増幅させてしまっているのでしょうか。それとも、そもそもの話としてもう少し余裕をもったコードに書き換えた方が良いのでしょうか(その場合は一から考え直すのですが…)。素人質問にて恐縮ですが、お力添えいただける点がございましたら、何卒よろしくお願い申し上げます。

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

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

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

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

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

guest

回答4

0

ベストアンサー

otnさんの言う通りで、プロファイラを使いましょう。

適当に40万文字から20万文字を削除するデータを作って、

text

1$ python3 -m cProfile -s tottime test.py < test.txt

のように実行したら、このように表示されました。

text

1 5408377 function calls in 8.425 seconds 2 3 Ordered by: internal time 4 5 ncalls tottime percall cumtime percall filename:lineno(function) 6 1 4.754 4.754 8.425 8.425 test.py:1(<module>) 7 5208223 3.515 0.000 3.515 0.000 {built-in method builtins.chr} 8 200000 0.135 0.000 0.135 0.000 {method 'append' of 'list' objects} 9 2 0.015 0.007 0.015 0.008 {built-in method builtins.input} 10 1 0.005 0.005 0.005 0.005 {built-in method builtins.print} 11 49 0.000 0.000 0.000 0.000 {built-in method _codecs.utf_8_decode} 12 49 0.000 0.000 0.001 0.000 codecs.py:319(decode) 13 49 0.000 0.000 0.000 0.000 codecs.py:331(getstate) 14 1 0.000 0.000 8.425 8.425 {built-in method builtins.exec} 15 1 0.000 0.000 0.000 0.000 {method 'split' of 'str' objects} 16 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}

これを見れば、chrがあやしいと分かるでしょう。

追記

こちらの環境だと、chrの修正だけで1秒強にまで縮んだのですが、不十分でしたか。
もう少しだけ高速化してみましたが、ここまでやらなくてはいけない時点で何かおかしい気はします。

  • リストを事前確保してappendをやめる (プロファイラを外したらほとんど効果がなかったので取り下げます)
  • if length == k:の判定を、lengthが増えた時だけにする

python

1n, k = map(int, input().split()) 2s = list(str(input())) 3 4length = 0 5li = [] 6for i in range(97, 97 + 26): 7 c = chr(i) 8 for j in range(n): 9 if s[j] == c: 10 li.append(j) 11 length += 1 12 if length == k: 13 break 14 else: 15 continue 16 break 17 18li = set(li) 19 20ans = '' 21for i in range(n): 22 if i not in li: 23 ans += s[i] 24 25print(ans)

投稿2021/12/09 14:54

編集2021/12/11 02:50
actorbug

総合スコア2429

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

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

kay_ventris4

2021/12/09 15:13

後ほどプロファイラについては理解を深めようとしておりましたが、その見方まで示して頂きありがとうございました。 built-in関数を呼び出す回数を減らす手法で、再度トライして見たいと思います。
otn

2021/12/09 15:14

chrはループの外に出せますが、appendは無理ですね。
kay_ventris4

2021/12/09 15:18 編集

今、ループ中でのchr()の呼び出しを避けるため、あらかじめ dic = {} for i in range(97, 97 + 26):   dic[i] = chr(i) としてアルファベット参照用の辞書を用意し、ループ中のchr(i)をdic[i]に変えたのですが、問題を提出したところ同じく2000msオーバーとなってしまいました。この方法ではchr()の呼び出し回数を減らしたことにならないのでしょうか。
otn

2021/12/09 15:21

ループの外に出すというのは、 for i in range(97, 97 + 26): _ci = chr(i) _for j in range(n): __if s[j] == ci: です。
kay_ventris4

2021/12/09 15:26

残念ながら、こちらに変えても時間切れとなりました。 あとは疑わしいとしたらやはり.append()くらいしかないでしょうか…
kay_ventris4

2021/12/09 15:28

一応自己解決の欄に別途累積和を用いたコードを貼ったのですが、こちらが正解扱いとなったのは、.append()による処理回数が非常に少ないという特徴があります。
guest

0

どの部分が具体的に計算時間を増幅させてしまっているのでしょうか。

こういうツールを使います。
Python プロファイラ — Python 3.10.0b2 ドキュメント

#追記
違う考え方でのコード。

Python

1n, k = map(int, input().split()) 2s = list(str(input())) 3 4a = [0]*(ord("z")+1) 5for i in s: 6 a[ord(i)] += 1 7 8b = 0 9for c in range(ord("a"),ord("z")+1): 10 b += a[c] 11 if b >= k: 12 break 13d = a[c]-(b-k) 14 15ans = "" 16for i in s: 17 e = ord(i) 18 if e > c: 19 ans += i 20 elif e == c: 21 if d > 0: 22 d -= 1 23 else: 24 ans += i 25print(ans)

投稿2021/12/09 13:29

編集2021/12/10 00:00
otn

総合スコア85901

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

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

otn

2021/12/09 13:31

と、回答してから質問文のコードを見ましたが、この短さ・単純さであれば調べるまでも無いかと。
kay_ventris4

2021/12/09 13:34

ご回答ありがとうございます。 プロファイラーというものについては初見でしたので、後ほどゆっくりと時間をかけて勉強させて頂きたいと思います。 質問文のコードについてですが、このままの提出だと時間切れを起こしてしまうのは、どのような原因が考えられるか、ご教授頂くことは可能でしょうか。
otn

2021/12/09 13:45

2秒で終わらないデータというのは n と k はどれくらい?
kay_ventris4

2021/12/09 13:58

n, k = 400000, 123456 のテストケースで実行時間が2000msを超えてしまいました。
otn

2021/12/09 14:56 編集

n が大きいとすると、s を1文字ずつスキャンする回数を抑えないといけないので、 2回だけにする方法でやってみると、 (最初のスキャンで削除する文字範囲を決めた後、2回目で実際に削除処理) n, k = 218525 123456 のデータで、 質問のコードで real 0m0.732s user 0m0.719s sys 0m0.009s が、こうなりました。 real 0m0.127s user 0m0.121s sys 0m0.005s
kay_ventris4

2021/12/09 15:21

追記頂いたコードを試しに提出してみたのですが、実行時間超過となりました。
otn

2021/12/09 15:35

sを最後まで見ないと削除する文字範囲が決まらないため、2回スキャンするのは必須だと思うので、あとは細かいチューニングでしょうか。 あらかじめ、 t = [ord(x) for x in s] とordしたリストを作ってそれを使うことで数%は速くなりますね。
otn

2021/12/09 23:53

回答に吊られて、range使ったけど、for i in s: にすれば速いか。 書き直しておきます。
kay_ventris4

2021/12/10 01:16

ありがとうございます。
guest

0

ヒントを欲しいという質問ではないようですので、Yes/Noで回答します。

  • そもそもの話としてもう少し余裕をもったコードに書き換えた方が良いのでしょうか

はい。

投稿2021/12/09 12:42

ppaul

総合スコア24670

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

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

kay_ventris4

2021/12/09 12:45

ご回答ありがとうございます。 逆に言えば、該当コード中のここさえ直せば計算時間を大きく減らせるという箇所は特にないという理解でよろしいでしょうか。
guest

0

一応、累積和などを使ってぐちゃぐちゃ書いていたら正解はしました。
しかし、上のコードの時間切れ理由は未だわからずという状況です。

Python

1from itertools import accumulate 2 3n, k = map(int, input().split()) 4s = list(str(input())) 5 6dic = {} 7for i in range(97, 97 + 26): 8 dic[chr(i)] = 0 9for el in s: 10 dic[el] += 1 11 12li = list(dic.values()) 13li_ = list(accumulate(li)) 14 15final = float('inf') 16for i in range(26): 17 if li_[i] > k: 18 final = i 19 break 20 21if final != 0 and final != float('inf'): 22 remove = [] 23 for i in range(final): 24 remove.append(i) 25 remove = set(remove) 26 27 s = [el for el in s if ord(el) - 97 not in remove] 28 29 final_length = k - li_[final - 1] 30 final_remove = [] 31 length = 0 32 for i in range(len(s)): 33 if length == final_length: 34 break 35 if s[i] == chr(final + 97): 36 final_remove.append(i) 37 length += 1 38 final_remove = set(final_remove) 39 40 s = [s[i] for i in range(len(s)) if i not in final_remove] 41 42 print(''.join(s)) 43 44elif final == 0: 45 bye = [] 46 for i in range(len(s)): 47 if s[i] == 'a': 48 bye.append(i) 49 bye = bye[:k] 50 bye = set(bye) 51 52 s = [s[i] for i in range(len(s)) if i not in bye] 53 54 print(''.join(s)) 55 56elif final == float('inf'): 57 print('')

投稿2021/12/09 13:30

kay_ventris4

総合スコア269

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.35%

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

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

質問する

関連した質問