Pertanyaan Haskell GHC: apa kompleksitas waktu dari pola yang cocok dengan konstruktor N?


Katakanlah kita memiliki Haskell berikut:

data T = T0 | T1 | T2 | ... | TN

toInt :: T -> Int
toInt t = case t of
  T0 -> 0
  T1 -> 1
  T2 -> 2
  ...
  TN -> N

Algoritma apa yang digunakan untuk melakukan pencocokan pola di sini? Saya melihat dua opsi:

(1) Pencarian linier, sesuatu seperti

if      (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...

(2) Pencarian biner, yang akan masuk akal dalam tugas khusus ini: mencari t.tag di set {TO...T1023}. Namun, di mana pencocokan pola secara umum memiliki banyak kemampuan dan generalisasi lainnya, ini mungkin tidak digunakan.

Kompilasi dengan GHC, algoritma apa yang digunakan, dan apa kompleksitas waktu dalam hal N, untuk pencocokan pola t di toInt?


32
2018-01-27 00:12


asal


Jawaban:


Sebuah tabel lompat digunakan, membuat pola-cocok dengan operasi waktu yang konstan.

Sayangnya saya tidak dapat menemukan kutipan terbaru untuk ini, meskipun halaman ini menyebutkan implementasi tingkat Cmm switch pernyataan sebagai tabel lompatan, dan dokumen desain pemberian tag lama ini menggunakan a case pada suatu Bool sebagai contoh, menghasilkan tabel lompat.


31
2018-01-27 00:19