Parse daftar string untuk kecepatan

Nov 30 2020

Latar Belakang

Saya memiliki fungsi yang disebut get_player_pathyang mengambil daftar string player_file_listdan nilai int total_players. Demi contoh, saya telah mengurangi daftar string dan juga mengatur nilai int ke angka yang sangat kecil.

Setiap string di player_file_listsalah satu memiliki year-date/player_id/some_random_file.file_extensionatauyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension

Isu

Apa yang pada dasarnya saya coba capai di sini adalah melalui daftar ini dan menyimpan semua year-date/player_idjalur unik dalam satu set sampai panjangnya mencapai nilaitotal_players

Pendekatan saya saat ini tampaknya tidak paling efisien bagi saya dan saya bertanya-tanya apakah saya dapat mempercepat fungsi saya get_player_path??

Kode

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))

Keluaran

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

Jawaban

PedroLobito Nov 30 2020 at 21:08

Saya akan meninggalkan solusi ini di sini yang dapat lebih ditingkatkan, semoga membantu.

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'}

Demo Python

1 janluke Nov 30 2020 at 22:25

Mari kita analisis fungsi Anda terlebih dahulu:

  • loop Anda harus mengambil waktu linier (O (n)) di sepanjang daftar input, dengan asumsi panjang jalur dibatasi oleh angka yang relatif "kecil";
  • penyortiran membutuhkan perbandingan O (n log (n)).

Dengan demikian pemilahan memiliki biaya dominan ketika daftarnya menjadi besar. Anda dapat mengoptimalkan mikro loop Anda sebanyak yang Anda inginkan, tetapi selama Anda tetap menyortirnya di akhir, upaya Anda tidak akan membuat banyak perbedaan dengan daftar besar.

Pendekatan Anda baik-baik saja jika Anda hanya menulis skrip Python. Jika Anda benar-benar membutuhkan pertunjukan dengan daftar besar, Anda mungkin akan menggunakan beberapa bahasa lain. Meskipun demikian, jika Anda benar-benar peduli dengan penampilan (atau hanya untuk mempelajari hal-hal baru), Anda dapat mencoba salah satu pendekatan berikut:

  • ganti algoritme pengurutan umum dengan sesuatu yang spesifik untuk string; lihat di sini untuk contoh
  • gunakan trie , menghilangkan kebutuhan untuk menyortir; ini bisa secara teoritis lebih baik tetapi mungkin lebih buruk dalam praktiknya.

Hanya untuk kelengkapan, sebagai pengoptimalan mikro, dengan asumsi tanggal memiliki panjang tetap 10 karakter:

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)

Jika ID juga memiliki panjang tetap, seperti dalam daftar contoh Anda, maka Anda tidak perlu membagi atau menemukan, cukup:

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]
...

EDIT: perbaiki LENGTHinisialisasi, saya lupa menambahkan 1

AajKaal Nov 30 2020 at 21:19

Gunakan dict sehingga Anda tidak perlu mengurutkannya karena daftar Anda sudah diurutkan. Jika Anda masih perlu mengurutkan, Anda selalu dapat menggunakan sortir dalam pernyataan return. Tambahkan import re dan ganti fungsi Anda sebagai berikut:

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]