pythonで連続する１を数える方法
コーディングテストの中で、連続する1を数える関数を作成する必要がありました。「python 連続する1を数える」と検索し、出てきたものを安易にコピペしてもうまくいかなかったので、自分で考えて解決しました。安易にコピペした反省と備忘録を兼ねて、この記事を執筆します。
連続する1を数えたいシチュエーション
A君は三日坊主です。
そこで、aというリストを用意し、ちゃんと勉強ができた日は'1'を、できなかった日は'0'を追加しました。
A君が連続で勉強できた日数の最大を求めよう！
a = [1,1,1,1,0,0,0,1,0,1,0,1,1,1,1]
1. 実際にコードを書いてみる
リストに連続する1を数える関数を作ります。この関数では、直前が1であれば、その数を足していき、最終的にその最大値を出力しています。
a = [1,1,1,1,0,0,0,1,0,1,0,1,1,1,1] #連続する１を数えたいリスト
def mikkabozu(x):
for i in range(len(x) - 1):
if x[i+1] == 1:
x[i+1] += x[i]
print(str(max(x)) + '日続きました')
mikkabozu(a)
#output
#4日続きました
この方法で、連続する1を数えることができました。
しかしながら、この方法ではもとのリストに上書きしていて、少々お行儀がよくないです。
2. 書いたコードをリファクタリングする
current_countで現在の連続する1の数をカウントし、max_countでその最大値を求めるようにします。
def max_consecutive_ones(a):
max_count = 0 # 最大の連続1の数を格納する変数
current_count = 0 # 現在の連続1の数をカウントする変数
for num in a:
if num == 1:
current_count += 1 # 1ならカウントを増加
max_count = max(max_count, current_count) # 最大カウントを更新
else:
current_count = 0 # 0が出たらカウントをリセット
return max_count # 最大連続1の数を返す
print(f"{max_consecutive_ones(a)}日続きました")
このコードでは、もとのリストを上書きすることなく連続する1の数を求めることができるようになりました。
3. 正規表現を使った方法
正規表現のメタ文字 + は、直前の文字が「1回以上」連続するパターンにマッチします。そのことを用いて、連続する1の数を求めることができると考えました。
調べると、reモジュールには、findallという関数があり、これを用いると、指定したパターンに一致するすべての部分をリストとして返してくれることがわかりました。
import re
def max_consecutive_ones_regex(a):
# リストを文字列に変換
binary_str = ''.join(map(str, a))
# 連続する1のパターン "1+" を検索し、各マッチの長さを取得
ones_sequences = re.findall(r'1+', binary_str)
# 各マッチの長さの最大値を取得
max_count = max(len(seq) for seq in ones_sequences) if ones_sequences else 0
return max_count
作成したアルゴリズムの比較
2つ関数を作成したので、どちらが優れているか比較したいと思います。
この2つの関数は、リスト内での連続する1の最大数を計算する目的は同じですが、考え方や効率性、コードの簡潔さにおいては違いがあります。
比較表
| 特徴 | 2. リファクタリング後 |
3. 正規表現を使った方法 |
|---|---|---|
| メモリ効率 | 〇 | △ |
| 実行速度 | 〇 | △ |
| コードの簡潔さ | △ | 〇 |
使い分け
2. リファクタリング後は直感的なアルゴリズムで、計算量はO(n)と効率的です。一方、3. 正規表現を使った方法は正規表現と文字列変換が必要なため、平均実行時間がやや長くなります。ただし、他のパターン検索にも応用でき、コードが簡潔である点は優れていそうです。
-
参考文献
オーダー記法O(n)について
教訓
ラクしようとして、検索をかけたものを理解しないままコピペしない！
ラクをしようと検索したものをそのままコピペした結果、うまくいかず無駄な時間を過ごしました。今後は気を付けます。