การค้นหาเชิงลึกแบบวนซ้ำสามารถนำไปใช้อย่างมีประสิทธิภาพใน haskell ได้อย่างไร

ฉันมีปัญหาในการเพิ่มประสิทธิภาพที่ฉันต้องการแก้ไข คุณมีโครงสร้างข้อมูลบางประเภท:

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

และฟังก์ชันการให้คะแนน:

rateFoo :: myFoo -> Int

ฉันต้องปรับผลลัพธ์ของ rateFoo ให้เหมาะสมโดยการเปลี่ยนค่าในโครงสร้าง ในกรณีนี้ ฉันตัดสินใจใช้การค้นหาแบบเจาะลึกซ้ำเพื่อแก้ไขปัญหา แผนผังการค้นหา (ไม่สิ้นสุด) เพื่อการเพิ่มประสิทธิภาพที่ดีที่สุดถูกสร้างขึ้นโดยฟังก์ชันอื่น ซึ่งใช้การเปลี่ยนแปลงที่เป็นไปได้ทั้งหมดกับแผนผังแบบเรียกซ้ำ:

fooTree :: Foo -> Tree

ฟังก์ชั่นการค้นหาของฉันมีลักษณะดังนี้:

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

คำถามที่ฉันมีก่อนที่จะเริ่มคือ:

เนื่องจากข้อมูลในแต่ละจุดสามารถสร้างแผนภูมิได้ จึงเป็นไปได้ไหมที่จะมีเฉพาะส่วนของแผนภูมิที่สร้างขึ้นซึ่งอัลกอริธึมจำเป็นต้องใช้ในปัจจุบัน เป็นไปได้หรือไม่ที่หน่วยความจำจะว่างและต้นไม้ถูกสร้างใหม่หากจำเป็นเพื่อบันทึกหน่วยความจำ (การลาที่ระดับ n สามารถสร้างได้ใน O(n) และ n ยังคงเล็ก แต่ไม่เล็กพอที่จะมีทั้งต้นไม้ในหน่วยความจำเมื่อเวลาผ่านไป)

นี่เป็นสิ่งที่ฉันคาดหวังได้จากรันไทม์หรือไม่ นิพจน์รันไทม์ ประเมินค่าไม่ได้ สามารถ (เปลี่ยนนิพจน์ที่ได้รับการประเมินให้เป็นนิพจน์ที่ไม่ได้รับการประเมิน) ได้หรือไม่ หรือแฮ็คสกปรกที่ฉันต้องทำเพื่อสิ่งนี้คืออะไร?


memory-management lazy-evaluation tree haskell iterative-deepening
person fuz    schedule 21.09.2010    source แหล่งที่มา
comment
หากคุณคิดว่าจำเป็นต้องประเมินบางสิ่งใหม่ การออกแบบอัลกอริทึมของคุณนั้นผิด   -  person jrockway    schedule 21.09.2010
comment
รันไทม์ไม่ได้ประเมินนิพจน์ อย่างไรก็ตาม ให้พิจารณาโครงสร้างแบบซิปสำหรับต้นไม้ของคุณ แต่ละโหนดเก็บค่าและก้อนที่แสดงถึงขึ้นลง ฯลฯ เมื่อคุณย้ายไปยังโหนดถัดไป คุณสามารถย้ายได้ตามปกติ (วางค่าโหนดก่อนหน้าในช่องที่เกี่ยวข้อง) หรือลืมไป (วางนิพจน์ที่ประเมินค่าไปยังโหนดก่อนหน้า โหนดในช่องด้านขวา) จากนั้นคุณสามารถควบคุมได้ว่าคุณจะเก็บประวัติไว้มากน้อยเพียงใด   -  person sclv    schedule 21.09.2010
comment
แน่นอน. อย่างไรก็ตาม ฉันจะพิจารณาว่าจะเพียงพอหรือไม่ที่จะฉายโครงสร้างข้อมูลเป็นเวกเตอร์ขนาดสองเท่า และใช้เทคนิคการหาค่าเหมาะที่สุดเชิงตัวเลขมาตรฐาน เช่น นิวตันทั่วไปบางประเภท ขึ้นอยู่กับฟังก์ชันการให้คะแนนของคุณ มันอาจจะไวต่อการสร้างความแตกต่างโดยอัตโนมัติ :-)   -  person sclv    schedule 21.09.2010
comment
ดูเหมือนว่าจะมีแพ็กเกจที่จะช่วยในเรื่องนี้ แม้ว่าคุณจะสามารถนำออกใช้เองก็ได้ ซึ่งฉันทำเพื่องานหลักสูตรเมื่อปีที่แล้ว   -  person Thomas M. DuBuisson    schedule 21.09.2010

คำตอบ (2)


arrow_upward
3
arrow_downward

นี่คือคำแนะนำของฉัน:

  1. เพียงใช้อัลกอริธึมของคุณในวิธีที่ตรงไปตรงมาที่สุดเท่าที่จะเป็นไปได้
  2. ประวัติโดยย่อ.
  3. ปรับความเร็วหรือการใช้หน่วยความจำให้เหมาะสมหากจำเป็น

ฉันเรียนรู้อย่างรวดเร็วว่าฉันไม่ฉลาดและ/หรือมีประสบการณ์มากพอที่จะให้เหตุผลว่า GHC จะทำอะไรหรือวิธีเก็บขยะทำงานอย่างไร บางครั้งสิ่งที่ฉันแน่ใจว่าจะเป็นหน่วยความจำที่ไม่มีประสิทธิภาพอย่างร้ายแรงจะทำงานได้อย่างราบรื่นในครั้งแรก และ (ไม่บ่อยนัก) สิ่งที่ดูเหมือนเรียบง่ายจะต้องยุ่งยากมากกับคำอธิบายประกอบที่เข้มงวด เป็นต้น

บทที่ Real World Haskell เกี่ยวกับการสร้างโปรไฟล์และการเพิ่มประสิทธิภาพ มีประโยชน์อย่างเหลือเชื่อเมื่อคุณไปถึงขั้นตอนที่ 2 และ 3

ตัวอย่างเช่น ต่อไปนี้เป็นการใช้งาน IDDFS แบบง่ายๆ โดยที่ f ขยายรายการย่อย p เป็นเพรดิเคตการค้นหา และ x เป็นจุดเริ่มต้น

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)

ฉันทดสอบโดยค้นหา "abbaaaaaacccaaaaabbaaccc" ด้วย children x = [x ++ "a", x ++ "bb", x ++ "ccc"] เป็น f ดูเหมือนเร็วพอสมควรและต้องใช้หน่วยความจำน้อยมาก (ผมคิดว่าเป็นเส้นตรงกับความลึก) ทำไมไม่ลองทำอะไรแบบนี้ก่อนแล้วค่อยย้ายไปยังโครงสร้างข้อมูลที่ซับซ้อนกว่านี้ถ้ามันไม่ดีพอล่ะ

person Travis Brown    schedule 21.09.2010
comment
วิธีที่ฉันต้องการทำ (การสร้างต้นไม้ในทุกวิถีทางที่เป็นไปได้) จริงๆ แล้วเป็นสิ่งที่ดูเหมือนจะตรงไปตรงมาที่สุดที่ฉันสามารถทำได้ ทางเลือกอื่นคือการทำงานกับแผนผังย่อยในเครื่อง แต่นี่อาจเป็นเรื่องยุ่งจริงๆ - person fuz; 21.09.2010

arrow_upward
4
arrow_downward

รันไทม์ไม่ได้ประเมินนิพจน์

มีวิธีตรงไปตรงมาเพื่อให้ได้สิ่งที่คุณต้องการ

พิจารณาโครงสร้างคล้ายซิปสำหรับต้นไม้ของคุณ แต่ละโหนดเก็บค่าและก้อนที่แสดงถึงขึ้นลง ฯลฯ เมื่อคุณย้ายไปยังโหนดถัดไป คุณสามารถย้ายได้ตามปกติ (วางค่าโหนดก่อนหน้าในช่องที่เกี่ยวข้อง) หรือลืมไป (วางนิพจน์ที่ประเมินค่าไปยังโหนดก่อนหน้า โหนดในช่องด้านขวา) จากนั้นคุณสามารถควบคุมได้ว่าคุณจะยึดถือ "ประวัติศาสตร์" ไว้มากเพียงใด

person sclv    schedule 21.09.2010
comment
คุณช่วยอธิบายเพิ่มเติมเกี่ยวกับวิธีใช้ซิปเพื่อช่วยในการค้นหาแบบเจาะลึกซ้ำๆ ได้ไหม ฉันอยากรู้แต่ฉันไม่เห็นมัน - person Travis Brown; 21.09.2010
comment
ซิปไม่รองรับตรรกะในการค้นหามากนัก แต่เพียงช่วยในการจับภาพว่าข้อมูลใดถูกเก็บไว้และข้อมูลใดที่ต้องถูกทิ้งและสร้างใหม่ตามความต้องการ - person sclv; 21.09.2010