Factorial Factors Versi C

ACM-884Saya masih penasaran dengan soal nomor 884 Factorial Factors di UVA Online Judge. Artikel di blog ini membahas soal tersebut pada 2006. Hasil terbaik (setelah Online Judge pindah tempat) pada 21 Agustus 2011 di urutan 3, dengan waktu 0.044 detik. Masalahnya, peringkat pertama hanya membutuhkan waktu 0.020 detik atau 2x lebih cepat.

Sebenarnya waktu 0.044 detik dengan bahasa Pascal hanyalah tipuan belaka. Rutin di dalamnya, khususnya inti algoritma dan operasi I/O, adalah Assembly. Bahasa Pascal secara default tidak berdaya mengungguli bahasa lain seperti C. Langkah-langkah mempercepat operasi I/O di Free Pascal memang membantu, tapi tidak cukup untuk masuk ke papan atas, tercantum di 20 besar pun tidak. Bukan menjelekkan Pascal, tapi di soal ini Pascal memang jelek.

Nah, untuk mencoba memperbaiki peringkat, berikut langkah-langkah yang dilakukan:

  1. Mengganti Pascal dengan C;
  2. Mengganti operasi I/O di C (baca/tulis angka);
  3. Memperkecil penggunaan memory.

Operasi I/O standar di C secara normal menggunakan scanf dan printf. Meskipun cukup cepat, tapi khusus untuk pembacaan angka-angka desimal masih bisa dioptimasi lebih lanjut. Secara algoritma, karakter ASCII ‘0’ s/d ‘9’ tinggal diubah menjadi 0 s/d 9, dan dilakukan pengalian atau pembagian berulang terhadap basis 10. Pembacaan I/O dapat dilakukan secara gelondongan menggunakan fgets (per baris) dan fputs (dengan buffer besar) terhadap stdin dan stdout. Khusus Linux, fungsi-fungsi non thread-safe seperti fgets_unlocked dan fputs_unlocked dapat lebih mempercepat.

Langkah memperkecil penggunaan memory dengan menerapkan array berlapis. Bila di algoritma awal, array Hasil menyimpan jumlah faktor sebesar 4 byte (int) per angka ganjil (sehingga 1/2 dari sejuta hasil), array ini bisa diperkecil menjadi 2 byte (short). Dibutuhkan array tambahan (dinamakan Bagi) untuk menyimpan angka awal, sehingga array Hasil hanya menyimpan selisih dengan batas maksimal angka short (64K). Memory semakin kecil artinya akses data semakin sedikit dan semakin cepat. Besarnya cakupan angka di soal ini, yaitu 1 juta, memang menjadi tantangan tersendiri.

Hasil dari optimasi lebih lanjut dapat dilihat di program di bawah. Fungsi CariPrima() sengaja dikosongkan karena ini adalah inti dari pemecahan soal. Hasil dari optimasi ini dapat mendongkrak penggunaan waktu menjadi 0.032 di urutan 3. Meskipun tidak besar, setidaknya dapat memperkecil selisih waktu dari yang tercepat. Memang rasa ini masih ada, yaitu penasaran bagaimanakah algoritma dari peringkat 1 dan 2? Biarlah waktu yang akan menjawab.


#include <stdio.h>

#define MaksAngka   1000000
#define MaksAkar    1000
#define MaksBufR    32
#define MaksBufW    (1024 * 16)
#define MaksBagi    (1024 * 8)
#define fgets_x     fgets_unlocked
#define fgets_xx    fgets
#define fputs_x     fputs_unlocked
#define fputs_xx    fputs

unsigned char Faktor[MaksAngka/2];
unsigned short Hasil[MaksAngka/2];
unsigned int Bagi[MaksAngka/MaksBagi];

char Bufread[MaksBufR];
char Bufwrit[MaksBufW];
int JumBuf = 0;

int read_int()
{
  char *pc;
  if (!(pc = fgets_x(Bufread, MaksBufR, stdin))) return EOF;
  int a = 0;
  while (*pc>33) {
    a = a*10 + *pc-'0';
    pc++;
  }
  return a;
}

char* itoa_x(int i){
  char const digit[] = "0123456789";  
  char *p = Bufwrit + JumBuf;
  int shifter = i;
  int len = 0;
  do { 
    len++;
    shifter = shifter/10;
  } while (shifter);
  p += len;
  *p = '\n';
  JumBuf += len + 1;
  do {
    *--p = digit[i%10];
    i = i/10;
  } while (i);
  if (JumBuf + 12 > MaksBufW) {
    Bufwrit[JumBuf] = '';
    JumBuf = 0;
    return Bufwrit;
  }
  return NULL;
}

void CariPrima()
{
  ...
}

int main(int argc, char **argv)
{
  int angka;
  char *pbuf;
  CariPrima();

  while ((angka = read_int()) != EOF) {
    pbuf = itoa_x(angka & 1 ? Bagi[(angka/2) / MaksBagi] + Hasil[angka/2] + Faktor[angka/2] : Bagi[(angka/2) / MaksBagi] + Hasil[angka/2]);
    if (pbuf) fputs_x(pbuf, stdout);
  }
  if (!pbuf) {
    Bufwrit[JumBuf] = '';
    fputs_x(Bufwrit, stdout);
  }
  return 0;
}

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s