Pointer cepat dan lambat

Dua penunjuk tidak selalu bergerak dari dua ujung yang berlawanan. Pola pointer cepat dan lambat menempatkan keduanya searah dengan kecepatan berbeda, satu langkah lawan dua langkah setiap putaran. Penunjuk cepat menempuh dua kali jarak lambat, sehingga jarak keduanya melebar secara teratur pada data lurus dan menyusut secara teratur pada data melingkar. Setelah topik ini, elemen tengah array dapat ditemukan dalam satu lintasan tanpa menghitung panjangnya lebih dahulu, dan argumen mengapa dua penunjuk pada siklus pasti bertemu, inti dari cycle detection ala Floyd, dapat dijelaskan dengan aritmetika sederhana.

Dua kecepatan pada satu lintasan#

Pointer cepat dan lambat memakai dua indeks yang bergerak searah, tetapi cepat maju dua langkah setiap putaran sedangkan lambat cukup satu. Selisih langkah keduanya bertambah satu setiap putaran, sehingga jaraknya melebar dengan pola yang mudah diperkirakan. Perbedaan kecepatan itulah yang menjadi alat ukurnya, karena posisi cepat selalu dua kali jarak yang sudah ditempuh lambat. Nama lambat dan cepat menyatakan kecepatan, bukan posisi, karena keduanya berangkat dari indeks yang sama dan baru terpisah setelah putaran pertama.

Sisi yang menentukan kondisi berhenti juga selalu sisi cepat, sebab hanya lompatan cepat yang berpotensi melewati batas data. Diagram berikut memperlihatkan kedua penunjuk pada array tujuh elemen, dengan jarak yang melebar satu indeks setiap putaran.

Pada diagram, lambat berdiri di indeks 2 dan cepat di indeks 4, persis keadaan setelah dua putaran pada demo elemen tengah. Kedua panah menunjuk ke kanan, berbeda dari pola konvergen yang panahnya saling mendekat dari dua ujung. Arah yang sama dengan kecepatan berbeda inilah yang membedakan kedua pola tersebut.

Elemen tengah dalam satu lintasan#

Hubungan dua kali itu memberi cara menemukan elemen tengah tanpa menghitung panjang data lebih dahulu. Selama cepat masih mampu melompat dua indeks, keduanya bergerak, dan ketika lompatan itu tidak mungkin lagi, cepat berada di dekat ujung sedangkan lambat berada tepat di tengah. Berkas berikut menelusuri array tujuh elemen dan mencetak posisi kedua penunjuk pada setiap putaran.

# Pointer cepat dan lambat mencari elemen tengah array.
# Lambat maju satu indeks, cepat melompat dua indeks setiap putaran.

def cari_tengah(data):
    n = len(data)
    lambat, cepat = 0, 0
    print(f"awal    : lambat di indeks {lambat}, cepat di indeks {cepat}")
    while cepat + 2 < n:
        lambat += 1
        cepat += 2
        print(f"putaran : lambat di indeks {lambat}, cepat di indeks {cepat}")
    return lambat

data = [8, 3, 12, 5, 7, 21, 4]
tengah = cari_tengah(data)
print("array :", data)
print("nilai tengah:", data[tengah], "pada indeks", tengah)

awal    : lambat di indeks 0, cepat di indeks 0
putaran : lambat di indeks 1, cepat di indeks 2
putaran : lambat di indeks 2, cepat di indeks 4
putaran : lambat di indeks 3, cepat di indeks 6
array : [8, 3, 12, 5, 7, 21, 4]
nilai tengah: 5 pada indeks 3

Setelah tiga putaran, cepat mencapai indeks 6 dan tidak dapat melompat dua lagi, sedangkan lambat berhenti di indeks 3, nilai 5 yang memang menjadi tengah array tujuh elemen. Jumlah putarannya sekitar $n/2$, sehingga biayanya $O(n)$ waktu dengan $O(1)$ memori tambahan. Pada linked list, yaitu rantai simpul yang saling dihubungkan referensi, disiplin yang sama berlaku, hanya saja indeks diganti referensi simpul dan setiap lompatan wajib diperiksa agar tidak menabrak ujung kosong.

Mengapa cepat pasti menyusul lambat#

Deret melingkar dapat dibentuk dengan fungsi penerus $f(i) = (i + 1) \bmod n$, yang memetakan setiap posisi ke posisi berikutnya dan kembali ke nol setelah posisi $n - 1$. Kedua penunjuk berangkat dari titik yang sama, cepat mengeksekusi $f$ dua kali setiap putaran sedangkan lambat sekali. Setelah $t$ putaran, lambat telah menempuh $t$ langkah dan cepat $2t$ langkah, sehingga jarak dari cepat menuju lambat searah perjalanan adalah $(t - 2t) \bmod n$, yang bernilai $n - t$ selama $0 < t \le n$. Penyusutan itu berlangsung tepat satu setiap putaran sehingga tidak mungkin melompati nol, dan jarak pasti mencapai nol paling lambat pada putaran ke-$n$. Demo berikut menjalankan skenario itu untuk $n = 7$ dan mencetak posisi kedua penunjuk beserta jaraknya.

# Pratinjau deteksi siklus ala Floyd pada deret indeks yang berputar.
# Fungsi berikutnya f(i) = (i + 1) mod n memetakan indeks ke indeks lain
# pada deret yang sama, dan dua pointer menelusurinya dengan kecepatan beda.

def berikutnya(i, n):
    return (i + 1) % n

def deteksi_siklus(mulai, n):
    lambat, cepat = mulai, mulai
    putaran = 0
    while True:
        lambat = berikutnya(lambat, n)                # satu pemanggilan f
        cepat = berikutnya(berikutnya(cepat, n), n)   # dua pemanggilan f
        putaran += 1
        jarak = (lambat - cepat) % n
        print(f"putaran {putaran}: lambat={lambat}, cepat={cepat}, jarak={jarak}")
        if lambat == cepat:
            return putaran

n = 7
print(f"n = {n}, f(i) = (i + 1) mod {n}, mulai dari 0")
putaran = deteksi_siklus(0, n)
print(f"bertemu pada putaran {putaran}")

n = 7, f(i) = (i + 1) mod 7, mulai dari 0
putaran 1: lambat=1, cepat=2, jarak=6
putaran 2: lambat=2, cepat=4, jarak=5
putaran 3: lambat=3, cepat=6, jarak=4
putaran 4: lambat=4, cepat=1, jarak=3
putaran 5: lambat=5, cepat=3, jarak=2
putaran 6: lambat=6, cepat=5, jarak=1
putaran 7: lambat=0, cepat=0, jarak=0
bertemu pada putaran 7

Kolom jarak pada keluaran menyusut 6, 5, 4, sampai 0 tanpa satu pun lompatan, sesuai rumus $n - t$. Posisi cepat berputar 2, 4, 6, 1, 3, 5, lalu 0 karena dihitung modulo 7, sedangkan posisi lambat naik satu langkah biasa saja. Pertemuan terjadi persis pada putaran ketujuh, sama seperti prediksi putaran ke-$n$ pada argumen di atas.

Bentuk data seperti itulah yang muncul pada deteksi siklus sungguhan, dan pola cepat-lambat ala Floyd di atas menjadi fondasinya. Perhitungan jarak juga memperlihatkan kebiasaan yang penting, yaitu selisih posisi pada data melingkar selalu diputar dengan modulo panjang siklusnya, sebagaimana baris jarak = (lambat - cepat) % n. Tanpa pemutaran itu, selisihnya bernilai negatif dan kesimpulannya menyesatkan.

Kesalahan umum#

1. Melompat dua langkah sekaligus tanpa penjagaan batas. Pada array, kondisi cepat + 2 < n harus diuji sebelum lompatan, dan pada linked list pemeriksanya dua lapis seperti diingatkan di atas. Lompatan yang tanpa pengawasan berakhir dengan error indeks maupun referensi kosong.
2. Menganggap kedua penunjuk pasti bertemu pada data apa pun. Tanpa siklus, cepat mencapai ujung lebih dahulu, sehingga perulangan wajib memiliki kondisi keluar berdasarkan batas. Pertemuan hanya dijamin ketika jalannya melingkar.
3. Memakai pola tengah pada panjang genap tanpa konvensi. Prosedur di atas berhenti pada indeks kiri dari sepasang tengah, sedangkan soal bisa meminta pasangan kanannya. Tetapkan pilihan itu sejak awal agar jawabannya konsisten.
4. Menghitung jarak melingkar tanpa modulo. Selisih lambat - cepat mentah bernilai negatif ketika cepat sudah memutar melewati nol, dan argumen penyusutan menjadi tidak terpelihara. Bungkus selisihnya dengan % n sebelum dipakai.
5. Menjalankan pola tengah tanpa memeriksa panjang data. Data kosong membuat fungsi tengah mengembalikan indeks 0 yang tidak sah, dan akses elemennya langsung berakhir dengan error. Periksa panjang data sebelum pola dijalankan.

Ringkasan#

• Pointer cepat dan lambat bergerak searah dengan kecepatan dua lawan satu, sehingga jaraknya melebar satu indeks setiap putaran pada data lurus.
• Invarian posisi cepat dua kali jarak lambat menempatkan lambat di elemen tengah ketika cepat tak dapat melompat lagi, dalam $O(n)$ waktu dan $O(1)$ memori.
• Pada siklus berpanjang $n$, jarak dari cepat menuju lambat bernilai $n - t$ setelah $t$ putaran, sehingga pertemuan pasti terjadi paling lambat pada putaran ke-$n$.
• Demo dengan $n = 7$ menunjukkan jarak 6 sampai 0 yang menyusut tepat satu per putaran, sesuai prediksi argumen modularnya.

Referensi#

• Cycle detection — Wikipedia — ulasan algoritma Floyd, dikenal sebagai tortoise and hare, beserta argumen pertemuan dua penunjuknya.
• VisuAlgo — National University of Singapore — visualisasi linked list untuk melihat dua penunjuk bergerak pada simpul sungguhan.