速度のために文字列のリストを解析する

Question

バックグラウンド

私は、呼び出された関数持つget_player_path文字列のリストになりますplayer_file_listし、int型の値をtotal_players。例として、文字列のリストを減らし、int値を非常に小さい数に設定しました。

player_file_listいずれかの各文字列には、year-date/player_id/some_random_file.file_extensionまたはyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension

問題

私がここで本質的に達成しようとしているのは、このリストをyear-date/player_id調べて、長さがの値に達するまで、すべての一意のパスをセットに格納することです。total_players

私の現在のアプローチは私にとって最も効率的ではないようで、とにかく私の機能をスピードアップできるかどうか疑問に思っていますか？get_player_path

コード

def get_player_path(player_file_list, total_players):
    player_files_to_process = set()
    for player_file in player_file_list:
        player_file = player_file.split("/")
        file_path = f"{player_file[0]}/{player_file[1]}/"
        player_files_to_process.add(file_path)
        if len(player_files_to_process) == total_players:
            break
    return sorted(player_files_to_process)


player_file_list = [
    "2020-10-27/31001804320549/31001804320549.json",
    "2020-10-27/31001804320549/IDATs/204825150047/foo_bar_Red.idat",
    "2020-10-28/31001804320548/31001804320549.json",
    "2020-10-28/31001804320548/IDATs/204825150123/foo_bar_Red.idat",
    "2020-10-29/31001804320547/31001804320549.json",
    "2020-10-29/31001804320547/IDATs/204825150227/foo_bar_Red.idat",
    "2020-10-30/31001804320546/31001804320549.json",
    "2020-10-30/31001804320546/IDATs/123455150047/foo_bar_Red.idat",
    "2020-10-31/31001804320545/31001804320549.json",
    "2020-10-31/31001804320545/IDATs/597625150047/foo_bar_Red.idat",
]

print(get_player_path(player_file_list, 2))

出力

['2020-10-27/31001804320549/', '2020-10-28/31001804320548/']

Answer 1

このソリューションはここに残しておきますが、さらに改善することができます。お役に立てば幸いです。

player_file_list = (
    "2020-10-27/31001804320549/31001804320549.json",
    "2020-10-27/31001804320549/IDATs/204825150047/foo_bar_Red.idat",
    "2020-10-28/31001804320548/31001804320549.json",
    "2020-10-28/31001804320548/IDATs/204825150123/foo_bar_Red.idat",
    "2020-10-29/31001804320547/31001804320549.json",
    "2020-10-29/31001804320547/IDATs/204825150227/foo_bar_Red.idat",
    "2020-10-30/31001804320546/31001804320549.json",
    "2020-10-30/31001804320546/IDATs/123455150047/foo_bar_Red.idat",
    "2020-10-31/31001804320545/31001804320549.json",
    "2020-10-31/31001804320545/IDATs/597625150047/foo_bar_Red.idat",
)

def get_player_path(l, n):
  pfl = set()
  for i in l:
    i = "/".join(i.split("/")[0:2])
    if i not in pfl:
      pfl.add(i)
    if len(pfl) == n:
      return pfl

  
  if n > len(pfl):
    print("not enough matches")
    return

print(get_player_path(player_file_list, 2))
# {'2020-10-27/31001804320549', '2020-10-28/31001804320548'}

Pythonデモ

Answer 2

最初に関数を分析しましょう：

• パスの長さが比較的「小さい」数で制限されていると仮定すると、ループは入力リストの長さで線形時間（O（n））を取る必要があります。
• ソートはO（n log（n））の比較を行います。

したがって、リストが大きくなると、ソートのコストが大きくなります。ループを必要なだけマイクロ最適化できますが、最後にその並べ替えを維持している限り、大きなリストでは大きな違いはありません。

Pythonスクリプトを書いているだけなら、あなたのアプローチは問題ありません。膨大なリストを含むパフォーマンスが本当に必要な場合は、おそらく他の言語を使用しているでしょう。それでも、パフォーマンスに本当に関心がある場合（または単に新しいことを学ぶため）は、次のいずれかのアプローチを試すことができます。

• 一般的なソートアルゴリズムを文字列に固有のものに置き換えます。たとえばここを参照してください
• トライを使用して、並べ替えの必要性を排除します。これは理論的には良いかもしれませんが、実際にはおそらくもっと悪いでしょう。

完全を期すために、マイクロ最適化として、日付の長さが10文字に固定されていると仮定します。

def get_player_path(player_file_list, total_players):
    player_files_to_process = set()
    for player_file in player_file_list:
        end = player_file.find('/', 12)       # <--- len(date) + len('/') + 1
        file_path = player_file[:end]         # <---
        player_files_to_process.add(file_path)
        if len(player_files_to_process) == total_players:
            break
    return sorted(player_files_to_process)

例のリストのように、IDの長さも固定されている場合は、分割や検索は必要ありません。次のようにするだけです。

LENGTH = DATE_LENGTH + ID_LENGTH + 1   # 1 is for the slash between date and id
...
for player_file in player_file_list:
    file_path = player_file[:LENGTH]
...

編集：LENGTH初期化を修正しました、私は1を追加するのを忘れていました

Answer 3

リストはすでに並べ替えられているため、並べ替える必要がないようにdictを使用します。それでもソートが必要な場合は、returnステートメントでいつでもsortedを使用できます。import reを追加し、次のように関数を置き換えます。

def get_player_path(player_file_list, total_players):
    dct = {re.search('^\w+-\w+-\w+/\w+',pf).group(): 1 for pf in player_file_list}
    return [k for i,k in enumerate(dct.keys()) if i < total_players]