Refaktor perulangan ke vektor

Vektorisasi mencapai bentuk finalnya sebagai kebiasaan menyusun ulang kode: perulangan yang menghitung elemen demi elemen diubah menjadi pernyataan array yang menghitung seluruh data sekaligus. Topik ini membahas satu kasus lengkap berupa perhitungan jarak Euclid untuk semua pasangan titik serta tiga langkah refaktor yang menghubungkan versi perulangan dengan versi tervektorisasi. Topik ini juga membahas urutan kerja praalokasi lebih dahulu baru vektorisasi, serta batas kapan perulangan tetap dipertahankan demi keterbacaan. Hasil yang diperoleh adalah prosedur yang dapat diulang pada kasus lain, bukan sekadar satu contoh jadi.

Kasus: jarak semua pasangan titik#

Empat titik sudut persegi panjang disimpan sebagai baris-baris matriks titik, dan tugasnya adalah matriks jarak yang memuat jarak setiap pasangan. Jarak Euclid antara titik ke-$i$ dan ke-$j$ dirumuskan

sehingga matriks hasil berukuran $4 \times 4$ dan diagonalnya bernilai nol. Versi perulangan menjelajah seluruh pasangan dengan dua pencacah dan mengisi satu elemen hasil pada setiap langkah.

titik = [0 0; 3 0; 0 4; 3 4];
n = size(titik, 1);
D_perulangan = zeros(n);
for i = 1:n
  for j = 1:n
    dx = titik(i, 1) - titik(j, 1);
    dy = titik(i, 2) - titik(j, 2);
    D_perulangan(i, j) = sqrt(dx^2 + dy^2);
  end
end
disp(D_perulangan);

   0   3   4   5
   3   0   5   4
   4   5   0   3
   5   4   3   0

Titik-titik tersebut membentuk persegi panjang dengan sisi 3 dan 4, sehingga jarak antar titik hanya memuat tiga nilai: sisi pendek 3, sisi panjang 4, dan diagonal 5 sesuai tripel Pythagoras. Kode versi perulangan memuat dua hal yang nantinya dibedakan saat refaktor: pernyataan zeros(n) yang mengalokasikan hasil lebih dahulu, serta pengindeksan titik(i, 1) yang mengambil satu elemen tunggal dari data. Yang pertama adalah kebiasaan baik yang dipertahankan, sedangkan yang kedua adalah bahan baku yang akan diganti.

Tiga langkah refaktor#

Refaktor dari perulangan ke vektor mengikuti tiga langkah yang selalu berurutan.

1. Identifikasi operan array: telusuri isi perulangan dan temukan kumpulan data yang sebenarnya dioperasikan. Pada kasus ini, seluruh perhitungan hanya melibatkan kolom pertama dan kolom kedua titik sebagai vektor utuh.
2. Ganti pengindeksan skalar dengan operasi array: pernyataan titik(i, 1) - titik(j, 1) yang memasangkan dua elemen tunggal diganti menjadi titik(:, 1) - titik(:, 1)' yang memasangkan seluruh kolom pertama terhadap transposnya.
3. Buang pencacah: tanpa pengindeksan skalar, i dan j kehilangan tugas sehingga kedua perulangan hilang sekaligus.

Alur transformasi keseluruhan dirangkum oleh diagram berikut.

titik = [0 0; 3 0; 0 4; 3 4];
selisih_x = titik(:, 1) - titik(:, 1)';
selisih_y = titik(:, 2) - titik(:, 2)';
D_vektor = sqrt(selisih_x .^ 2 + selisih_y .^ 2);
disp(D_vektor);

   0   3   4   5
   3   0   5   4
   4   5   0   3
   5   4   3   0

Mekanisme penggantian pada langkah kedua bekerja melalui ekspansi implisit. Operan titik(:, 1) berukuran $4 \times 1$, sedangkan titik(:, 1)' berukuran $1 \times 4$. Pengurangan keduanya menghasilkan matriks $4 \times 4$ yang elemen $(i, j)$-nya berisi $x_i - x_j$, tepat pasangan yang dahulu dihitung pencacah i dan j. Matriks selisih yang sama dibentuk untuk kolom kedua, lalu .^ 2, penjumlahan, dan sqrt dikerjakan per elemen pada seluruh matriks sekaligus. Bentuk akhirnya membaca rumus $D_{ij}$ hampir baris demi baris, dan pemeriksaan berikut membuktikan kesetaraannya dengan versi perulangan.

fprintf('selisih maksimum kedua versi: %g\n', max(abs(D_perulangan(:) - D_vektor(:))));

selisih maksimum kedua versi: 0

Berkas utuh berikut merangkai kedua versi beserta pemeriksaan kesetaraannya dalam satu program yang dapat dijalankan langsung.

% jarak_pasangan.m: jarak Euclid semua pasangan titik, dua versi sekaligus

titik = [0 0; 3 0; 0 4; 3 4];
n = size(titik, 1);

% versi perulangan bertingkat dengan praalokasi hasil
D_perulangan = zeros(n);
for i = 1:n
  for j = 1:n
    dx = titik(i, 1) - titik(j, 1);
    dy = titik(i, 2) - titik(j, 2);
    D_perulangan(i, j) = sqrt(dx^2 + dy^2);
  end
end

% versi tervektorisasi dengan ekspansi implisit kolom terhadap baris
selisih_x = titik(:, 1) - titik(:, 1)';
selisih_y = titik(:, 2) - titik(:, 2)';
D_vektor = sqrt(selisih_x .^ 2 + selisih_y .^ 2);

fprintf('matriks jarak versi perulangan:\n');
disp(D_perulangan);
fprintf('matriks jarak versi tervektorisasi:\n');
disp(D_vektor);
fprintf('selisih maksimum kedua versi: %g\n', max(abs(D_perulangan(:) - D_vektor(:))));

matriks jarak versi perulangan:
   0   3   4   5
   3   0   5   4
   4   5   0   3
   5   4   3   0
matriks jarak versi tervektorisasi:
   0   3   4   5
   3   0   5   4
   4   5   0   3
   5   4   3   0
selisih maksimum kedua versi: 0

Praalokasi dulu, vektorisasi kemudian#

Urutan kerja yang benar ketika perulangan sulit dihilangkan sekaligus adalah praalokasi lebih dahulu, vektorisasi kemudian. Praalokasi dengan zeros memutus kebiasaan paling merugikan berupa array yang membesar sedikit demi sedikit di dalam perulangan, karena setiap pembesaran menyalin ulang seluruh isi yang sudah ada. Setelah tujuan hasil dialokasikan, vektorisasi dapat diterapkan bertahap pada bagian yang paling sering dikerjakan, biasanya perulangan paling dalam.

titik = [0 0; 3 0; 0 4; 3 4];
n = size(titik, 1);
D_antara = zeros(n);
for j = 1:n
  D_antara(:, j) = sqrt((titik(:, 1) - titik(j, 1)) .^ 2 + (titik(:, 2) - titik(j, 2)) .^ 2);
end
fprintf('selisih maksimum terhadap versi perulangan: %g\n', max(abs(D_antara(:) - D_perulangan(:))));

selisih maksimum terhadap versi perulangan: 0

Bentuk antara ini mempertahankan satu perulangan luar dan menggantikan perulangan dalam dengan satu operasi array: seluruh kolom jarak terhadap titik ke-j dihitung sekaligus melalui penyebaran skalar titik(j, 1) terhadap vektor titik(:, 1). Hasilnya tetap setara dengan kedua versi sebelumnya. Pada data yang lebih besar daripada contoh, bentuk seperti ini kerap menjadi titik henti yang wajar. Perulangan luar membaca alur logikanya dengan jelas, sementara perulangan dalam yang paling banyak dikerjakan sudah menjadi operasi array.

Keterbacaan tetap dijaga#

Versi tervektorisasi bukan tujuan yang mengalahkan segala pertimbangan lain. Rantai ekspansi implisit yang menjalar tiga atau empat tingkat menghasilkan satu baris yang panjang dan sulit diaudit, dan pada titik itu perulangan yang polos justru membawa maksud dengan lebih jujur. Perhitungan yang memang berurutan, misalnya nilai yang bergantung pada nilai sebelumnya, juga tidak dapat dipotong menjadi operasi array tanpa mengubah maknanya. Meskipun demikian, sebagian pola berurutan memiliki padanan siap pakai seperti cumsum untuk jumlah berjalan.

Patokan praktisnya adalah menjaga padanan antara rumus tertulis dan kode. Ketika satu pernyataan array masih dapat dibaca sebagai rumus $D_{ij}$ sebagaimana contoh pada topik ini, bentuk tervektorisasi layak dipertahankan. Ketika padanan itu hilang dan pembaca harus menelusuri bentuk antar ukuran di kepala, kembalikan satu tingkat perulangan dengan praalokasi. Komentar satu baris yang menyebut rumus yang diimplementasikan menolong kedua bentuk. Pengukuran waktu dengan profiler sebelum mengubah kode yang sudah benar dibahas pada modul praktik terbaik.

Kesalahan umum#

• Membiarkan array membesar di dalam perulangan. Kode berikut berjalan dan hasilnya benar, tetapi setiap y(end+1) menyalin ulang seluruh isi yang sudah terkumpul sehingga pekerjaan penyalinan tumbuh kuadratik terhadap banyak elemen.

y = [];
for k = 1:5
  y(end+1) = k^2;
end
disp(y);

    1    4    9   16   25

• Menukar orientasi saat menyiapkan operasi array. Bentuk titik(:, 1) - titik(:, 1)' sengaja memasangkan kolom terhadap baris untuk mengisi matriks pasangan penuh. Ketika yang dibutuhkan hanya selisih terhadap satu titik acuan, gunakan skalar titik(j, 1) agar penyebaran skalar bekerja dan hasil tetap berupa vektor kolom, bukan matriks besar yang tidak diminta.
• Memaksakan vektorisasi pada perhitungan yang berurutan. Ketergantungan antar elemen membuat urutan pengerjaan menjadi bagian dari makna perhitungan. Pertahankan perulangan dengan praalokasi, atau cari padanan siap pakai seperti cumsum atau filter hanya bila semantiknya benar-benar sama.

Ringkasan#

• Refaktor perulangan ke vektor berjalan tiga langkah: identifikasi operan array, ganti pengindeksan skalar dengan operasi array, lalu buang pencacah.
• Ekspansi implisit memasangkan kolom $4 \times 1$ terhadap baris $1 \times 4$ menjadi matriks selisih penuh, sehingga rumus berindeks ganda menjadi satu pernyataan array.
• Urutan kerja yang benar adalah praalokasi zeros lebih dahulu, kemudian vektorisasi pada perulangan yang paling dalam.
• Keterbacaan tetap menjadi batas: bentuk yang tidak lagi dapat dibaca sebagai rumus tertulisnya sebaiknya dikembalikan menjadi perulangan yang polos.

Referensi#

• Using Vectorization — MathWorks — Panduan resmi vektorisasi operasi array sebagai pengganti perulangan.
• Techniques for Improving Performance — MathWorks — Teknik peningkatan kinerja yang menempatkan praalokasi dan vektorisasi pada urutan awal.
• Array vs. Matrix Operations — MathWorks — Basis pemilihan operator matriks atau operator per elemen saat merakit pernyataan tervektorisasi.