كيف يمكن أن ينفذ البحث التكراري فعال في هاسكل؟

Question

لدي مشكلة تحسين أريد حلها. لديك نوع من بنية البيانات:

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

ووظيفة التصنيف:

rateFoo :: myFoo -> Int

لا بد لي من تحسين نتيجة rateFoo عن طريق تغيير القيم في الهيكل. في هذه الحالة المحددة ، قررت استخدامها البحث التكراري لكي تحل هذه المشكلة. يتم إنشاء شجرة البحث (Infinite) للحصول على أفضل تحسين بواسطة وظيفة أخرى ، والتي تنطبق ببساطة جميع التغييرات الممكنة على الشجرة:

fooTree :: Foo -> Tree

وظيفة البحث الخاصة بي تبدو مثل هذا:

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

السؤال الذي كان لدي ، قبل أن أبدأ هو:

نظرًا لأنه يمكن إنشاء الشجرة بواسطة البيانات في كل نقطة ، فهل من الممكن أن يكون لديها فقط أجزاء الشجرة التي تم إنشاؤها ، والتي تحتاجها حاليًا بواسطة الخوارزمية؟ هل من الممكن تحرير الذاكرة وتجديد الشجرة إذا لزم الأمر من أجل حفظ الذاكرة (يمكن إنشاء إجازة في المستوى N O(n) و N لا يزال صغيرًا ، لكن ليس صغيرًا بما يكفي للحصول على الشجرة بأكملها في الذاكرة مع مرور الوقت)؟

هل هذا شيء يمكنني أن أظنه من وقت التشغيل؟ يمكن لوقت التشغيل لا يكرر التعبيرات (تحويل تعبير تم تقييمه إلى تعبير غير معروف)؟ أو ما هو الاختراق القذر الذي يجب أن أفعله لهذا؟

Answer 1

ها هي نصيحتي:

1. ما عليك سوى تنفيذ الخوارزمية بأكثر الطرق المباشرة الممكنة.
2. الملف الشخصي.
3. تحسين للسرعة أو استخدام الذاكرة إذا لزم الأمر.

لقد تعلمت بسرعة أنني لست ذكيًا و/أو خبرت بما يكفي لسبب ما ستفعله GHC أو كيف ستعمل جمع القمامة. في بعض الأحيان ، ستكون الأشياء التي أنا متأكد من أن العمل غير الكفاءة في الذاكرة بسلاسة في المرة الأولى ، ولا تتطلب كل منها في كثير من الأحيان-والتي تبدو بسيطة الكثير من الشروط الصارمة ، وما إلى ذلك.

ال العالم الحقيقي هاسكل الفصل على التنميط والتحسين مفيد بشكل لا يصدق بمجرد وصولك إلى الخطوتين 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. يبدو سريعًا بشكل معقول ويتطلب القليل جدًا من الذاكرة (الخطية مع العمق ، على ما أعتقد). لماذا لا تجرب شيئًا مثل هذا أولاً ثم انتقل إلى بنية بيانات أكثر تعقيدًا إذا لم تكن جيدة بما يكفي؟

Answer 2

وقت التشغيل لا يكرر التعبيرات.

هناك طريقة واضحة للحصول على ما تريد.

النظر في بنية تشبه السوستة لشجرتك. تحتفظ كل عقدة بقيمة وممثلة لأسفل ، لأعلى ، وما إلى ذلك. عند الانتقال إلى العقدة التالية ، يمكنك إما التحرك بشكل طبيعي (وضع قيمة العقدة السابقة في الفتحة المقابلة) أو ينسى (وضع تعبير يقييم إلى السابق العقدة في الفتحة اليمنى). ثم يمكنك السيطرة على مقدار "التاريخ" الذي تتمسك به.