Codewars kata - "Repetitive Sequence"

Question

Saya mencoba untuk memecahkan kata Codewars berikut .

Kami diberi daftar sebagai
seq = [0, 1, 2, 2]

Kami harus menulis fungsi yang akan, pertama, menambahkan elemen dalam daftar menggunakan logika berikut.
jika n = 3 dan sebagai seq [n] = 2, list baru akan menjadi seq = [0, 1, 2, 2, 3, 3]
jika n = 4 dan sebagai seq [n] = 3, list baru akan be seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
jika n = 5 dan sebagai seq [n] = 3, list baru akan menjadi seq = [0, 1, 2, 2 , 3, 3, 4, 4, 4, 5, 5, 5] dan seterusnya.

Kemudian fungsi tersebut akan mengembalikan elemen ke-n dari daftar.

Beberapa elemen dari daftar:
[0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8 , 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13 , 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17 , 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20 , 20, 20, 21, 21, 21, 21, 21, 21, 21, 21]

Batasan untuk Python:
0 <= n <= 2 ^ 41

Kode saya berjalan dengan sukses di sistem saya untuk nilai n apa pun, termasuk n = 2 ^ 41 (dalam 2.2s). Tapi waktu habis di Codewars. Adakah yang bisa membantu saya dalam mengoptimalkan kode saya? Terima kasih sebelumnya.

Kode saya:

def find(n):
    arr = [0, 1, 2, 2]
    if n <= 3:
        return arr[n]
    else:
        arr_sum = 5
        for i in range(3, n+1):
            arr_sum += i * arr[i]
            if arr_sum >= n:
                x = (arr_sum - n) // i
                return len(arr) + arr[i] - (x+1)
            else:
                arr += [i] * arr[i]

Answer 1

Membuat daftar membutuhkan banyak waktu. Perhatikan bahwa Anda arr += [i] * arr[i]mengulangi nilai yang sama iberulang kali. Ini dapat banyak dikompresi hanya dengan menyimpan repeat(i, arr[i]). Ini berhasil dalam waktu sekitar 6 detik, jauh di bawah batas 12 detik mereka:

from itertools import chain, repeat

def find(n):
    if n <= 3:
        return [0, 1, 2, 2][n]
    arr = [[2]]
    arr_sum = 5
    arr_len = 4
    for i, arr_i in enumerate(chain.from_iterable(arr), 3):
        arr_sum += i * arr_i
        if arr_sum >= n:
            x = (arr_sum - n) // i
            return arr_len + arr_i - (x+1)
        arr.append(repeat(i, arr_i))
        arr_len += arr_i

Perhatikan bahwa dalam n > 3kasus ini, kita sudah mulai dengan angka 3, menambahkannya dua kali ke daftar. Jadi dari urutan awal [0, 1, 2, 2]kita hanya perlu [2], jadi saya mulai dengan arr = [[2]](yang lebih pendek dari [repeat(2, 1)], dan chaintidak keberatan).

---

Atau ... perhatikan bahwa Anda memperpanjang arrlebih cepat daripada saat Anda mengonsumsinya. Untuk n = 2 ⁴¹ , Anda menumbuhkannya menjadi lebih dari 51 juta elemen, tetapi sebenarnya Anda membaca kurang dari 70 ribu pertama. Jadi Anda bisa berhenti benar-benar memperluas daftar pada saat itu. Ini berhasil dalam sekitar 4,7 detik:

def find(n):
    arr = [0, 1, 2, 2]
    if n <= 3:
        return arr[n]
    arr_sum = 5
    arr_len = 4
    for i in range(3, n+1):
        arr_sum += i * arr[i]
        if arr_sum >= n:
            x = (arr_sum - n) // i
            return arr_len + arr[i] - (x+1)
        arr_len += arr[i]
        if arr_len < 70_000:
            arr += [i] * arr[i]

---

Dan ... Anda dapat menggabungkan dua perbaikan di atas, yaitu, menerapkannya if arr_len < 70_000:ke repeat-versi. Itu kemudian berhasil dalam waktu sekitar 4,5 detik.

Hasil benchmark pada PC saya untuk n = 2 ⁴¹ :

Your original:   1.795 seconds
My first one:    0.043 seconds (42 times faster)
My second one:   0.041 seconds (44 times faster)
The combination: 0.026 seconds (69 times faster)

---

Oh dan komentar gaya: Anda melakukan ini dua kali:

if ...:
    return ...
else:
    ...

Dan elselekukan dari semua kode yang tersisa tidak diperlukan dan saya akan menghindarinya. Saya telah melakukannya dalam solusi di atas.