毎朝Codewars@2019.05.29(水): Scramblies

毎朝ちびちびCodewars。

[5 kyu] Scramblies www.codewars.com

今日のお題：

""" scramble(s1, s2)
文字列s1 を構成する文字を使って 文字列s2 が作れるならTrue、そうでないなら Falseを返す。
構成文字は1回しか使えない（s2に'a'が2回出現するなら、s1に2個以上'a'がないとNG）

Args:  
    s1 (str):  小文字a-z からなる文字列
    s2 (str):  小文字a-z からなる文字列
Returns:  
    判定結果（Boolean)
"""

コード

me1: count()で文字の出現数を数えて比較

def scramble(s1, s2):
    for c2 in set(s2):
        if s2.count(c2) > s1.count(c2):
            return False
    return True

me2: index()関数で該当する文字の位置を取得する

# index()関数で該当する文字の位置を取得する方法
def scramble(s1, s2):
    ls1 = list(s1)
    for c2 in s2:
        try:
            ls1[ls1.index(c2)] = '*'
        except ValueError:
            return False
    return True

• 最初この方法で書いたのだけど、ランダムテストがタイムアウトして突破できなかった

印象に残った他ユーザのコード

from collections import Counter
def scramble(s1,s2):
    # Counter basically creates a dictionary of counts and letters
    # Using set subtraction, we know that if anything is left over,
    # something exists in s2 that doesn't exist in s1
    return len(Counter(s2)- Counter(s1)) == 0

• この解法をBest PracticesやCleverにしてる人が多かった。確かにクレバーだと思ったけど、ちょっと納得いかなかった。
• というのも timeitで処理時間を計測すると、文字列が短い時はcount()やindex()を使う方法の倍ぐらい時間がかかる。当然ランダムテストの制限時間に収まらない（タイムアウトする）はずなんだが、実際やってみるとなぜかindex()を使う方法だとタイムアウトして、Counter()方式は問題なく時間内にパスするんだよね。

• 6/1(土）の #rettypy でこの話をし、

  • 対象文字数が処理時間に影響があるから文字数を振ってみて計測してはどうか？
  • 方法3のtry-except ValueError を使うやり方は内部処理に予想外の時間がかかる可能性あり
  • count(), Conter()などのメソッドのコアの処理はCで書かれていることがある（速い）が、Pythonのバージョンによってもその状態が異なる可能性あり
  • index()方式は（この関数の内部処理のしかた的に）効率悪いかもね などのアドバイスを貰った。

• あ、そうか、処理対象の文字数が一定数を超えると処理時間が逆転するのか！

アルゴリズムを変えて実行時間を計測

• 4パターンの解決方法について文字列が短い時（20文字）、長い時（2000文字）のそれぞれについて処理時間がどうなるかを実測した。
  1. count()で文字列s1, s2の各文字の出現回数を数えて比較する方法
  2. 上記と同じことをcollections.Counter()を使って行う方法
  3. index()関数で該当する文字の位置を取得し、"*"に置き換えていく方法
  4. 3と同じことを、forを愚直に回して該当する文字の位置を取得する方法
• 結果:
  短い文字列のうちは「index()関数で該当する文字の位置を取得する方法」の方がCounter()を使う方法よりも遙かに速いが、長い文字になると逆転する。ランダムテストでは文字数6000文字でチェックしていたから、この方法ではパスしないことがわかる。

• 実測だけでなく、ソースを読んで時間計算量を見積もるとベターなんだが時間がとれなかったのでtimeitだけで済ませた。

文法、関数・メソッドnote

collections.Counter([iterable-or-mapping])

collections --- コンテナデータ型 — Python 3.7.3 ドキュメント

• ハッシュ可能なオブジェクトをカウントする dict のサブクラス

from collections import Counter

c1 = Counter('gallahad') 
c2 = Counter({'red': 4, 'blue': 2})
print(c2['red'])    # -> 4

# 存在しない要素に対して KeyError の代わりに 0 を返す
print(c2['green'])    # -> 0

# 0をセットしても要素は取り除かれない。取り除くにはdelを使う
c2['blue'] = 0            # counter entry with a zero count
print(c2['blue'], c2)  # ->0 Counter({'red': 4, 'blue': 0})
 
del c2['blue']
print(c2['blue'], c2) # -> 0 Counter({'red': 4})

str.count(sub[, start[, end]])

https://docs.python.org/ja/3/library/stdtypes.html?highlight=count#str.count - 部分文字列 sub が重複せず出現する回数を返す。 - スライス表記同様の書き方[start, end] で評価対象範囲を指定できる。

list.index(x[, start[, end]])

https://docs.python.org/ja/3/tutorial/datastructures.html - リスト中で x と等しい値を持つ最初の要素の位置をゼロから始まる添字で返す。 - スライス表記同様の書き方[start, end] で評価対象範囲を指定できる。 - 該当する要素がなければ ValueError になる。