Bagaimana pencarian pendalaman berulang dapat diterapkan secara efisien di Haskell?

Saya memiliki masalah pengoptimalan yang ingin saya selesaikan. Anda memiliki semacam struktur data:

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

dan fungsi peringkat:

rateFoo :: myFoo -> Int

Saya harus mengoptimalkan hasil rateFoo dengan mengubah nilai di struct. Dalam kasus khusus ini, saya memutuskan untuk menggunakan penelusuran mendalam berulang untuk memecahkan masalah tersebut. Pohon pencarian (tak terbatas) untuk pengoptimalan terbaik dibuat oleh fungsi lain, yang hanya menerapkan semua kemungkinan perubahan secara rekursif ke pohon:

fooTree :: Foo -> Tree

Fungsi pencarian saya terlihat seperti ini:

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

Pertanyaan yang saya miliki sebelum saya mulai adalah ini:

Karena pohon dapat dihasilkan oleh data di setiap titik, mungkinkah hanya bagian pohon yang dihasilkan, yang saat ini diperlukan oleh algoritme? Apakah mungkin untuk membebaskan memori dan pohon dibuat ulang jika diperlukan untuk menghemat memori (Cuti pada level n dapat dihasilkan di O(n) dan n tetap kecil, tetapi tidak cukup kecil untuk memiliki seluruh pohon di memori seiring waktu)?

Apakah ini sesuatu yang dapat saya harapkan dari runtime? Bisakah ekspresi tidak dievaluasi waktu berjalan (mengubah ekspresi yang dievaluasi menjadi ekspresi yang tidak dievaluasi)? Atau peretasan kotor apa yang harus saya lakukan untuk ini?


memory-management lazy-evaluation tree haskell iterative-deepening
person fuz    schedule 21.09.2010    source sumber
comment
Jika Anda merasa perlu tidak mengevaluasi sesuatu, desain algoritme Anda salah.   -  person jrockway    schedule 21.09.2010
comment
Runtime tidak mengevaluasi ekspresi. Namun, pertimbangkan struktur seperti ritsleting untuk pohon Anda. Setiap node menyimpan sebuah nilai dan sebuah tanda mewakili bawah, atas, dan seterusnya. Saat Anda berpindah ke node berikutnya, Anda dapat berpindah secara normal (menempatkan nilai node sebelumnya di slot yang sesuai) atau lupa (menempatkan ekspresi yang mengevaluasi ke node sebelumnya). simpul di slot kanan). Kemudian Anda memiliki kendali atas berapa banyak sejarah yang Anda simpan.   -  person sclv    schedule 21.09.2010
comment
Tentu saja. Namun, omong-omong, saya akan mempertimbangkan apakah cukup memproyeksikan struktur data ke vektor ganda dan menggunakan teknik optimasi numerik standar seperti Newton yang digeneralisasi. Bergantung pada fungsi pemeringkatan Anda, fungsi tersebut mungkin rentan terhadap diferensiasi otomatis :-)   -  person sclv    schedule 21.09.2010
comment
Tampaknya ada paket yang dapat membantu dalam hal ini, meskipun Anda dapat meluncurkan paket Anda sendiri, yang saya lakukan untuk tugas kursus tahun lalu.   -  person Thomas M. DuBuisson    schedule 21.09.2010

Jawaban (2)


arrow_upward
3
arrow_downward

Inilah saran saya:

  1. Cukup terapkan algoritma Anda dengan cara yang paling mudah.
  2. Profil.
  3. Optimalkan kecepatan atau penggunaan memori jika perlu.

Saya segera mengetahui bahwa saya tidak pintar dan/atau cukup berpengalaman untuk memikirkan apa yang akan dilakukan GHC atau cara kerja pengumpulan sampah. Kadang-kadang hal-hal yang saya yakin akan sangat tidak efisien dalam memori akan berjalan dengan lancar pada kali pertama, dan – lebih jarang – hal-hal yang tampak sederhana memerlukan banyak kerumitan dengan anotasi yang ketat, dll.

Bab Real World Haskell tentang pembuatan profil dan pengoptimalan sangat membantu setelah Anda mencapai langkah 2 dan 3.

Misalnya, inilah implementasi IDDFS yang sangat sederhana, di mana f memperluas turunan, p adalah predikat pencarian, dan x adalah titik awal.

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

Saya menguji dengan mencari "abbaaaaaacccaaaaabbaaccc" dengan children x = [x ++ "a", x ++ "bb", x ++ "ccc"] sebagai f. Tampaknya cukup cepat dan membutuhkan sedikit memori (menurut saya linier dengan kedalamannya). Mengapa tidak mencoba sesuatu seperti ini terlebih dahulu dan kemudian beralih ke struktur data yang lebih rumit jika itu tidak cukup baik?

person Travis Brown    schedule 21.09.2010
comment
Cara yang ingin saya lakukan (membangun pohon dengan segala cara yang mungkin) sebenarnya adalah cara paling mudah yang dapat saya lakukan. Alternatifnya adalah bekerja dengan subpohon lokal, namun hal ini dapat menimbulkan kekacauan. - person fuz; 21.09.2010

arrow_upward
4
arrow_downward

Runtime tidak mengevaluasi ekspresi.

Namun ada cara mudah untuk mendapatkan apa yang Anda inginkan.

Pertimbangkan struktur seperti ritsleting untuk pohon Anda. Setiap node menyimpan sebuah nilai dan sebuah tanda mewakili bawah, atas, dan seterusnya. Saat Anda berpindah ke node berikutnya, Anda dapat berpindah secara normal (menempatkan nilai node sebelumnya di slot yang sesuai) atau lupa (menempatkan ekspresi yang mengevaluasi ke node sebelumnya). simpul di slot kanan). Kemudian Anda memiliki kendali atas seberapa banyak "sejarah" yang Anda simpan.

person sclv    schedule 21.09.2010
comment
Bisakah Anda memperluas cara menggunakan ritsleting untuk membantu memperdalam pencarian secara berulang? Aku penasaran tapi aku tidak melihatnya. - person Travis Brown; 21.09.2010
comment
Ritsleting tidak menangani logika pencarian terlalu banyak. Hal ini hanya membantu menangkap data mana yang disimpan dan data mana yang perlu dibuang dan dibuat ulang sesuai permintaan. - person sclv; 21.09.2010