F # باستخدام مخبأ تسلسل بشكل صحيح

Question

وأنا أحاول أن استخدام Seq.cache مع وظيفة الذي أدليت به وترجع سلسلة من يعبي تصل إلى عدد من N باستثناء عدد 1. أواجه صعوبة في معرفة كيفية الحفاظ على تسلسل مؤقتا في نطاق لكن لا تزال تستخدم في تعريف بلدي.

let rec primesNot1 n = 
    {2 .. n} 
    |> Seq.filter (fun i -> 
        (primesNot1 (i / 2) |> Seq.for_all (fun o -> i % o <> 0)))
    |> Seq.append {2 .. 2}
    |> Seq.cache

وأي أفكار كيف يمكن استخدام Seq.cache لجعل هذا أسرع؟ حاليا فإنه يحتفظ اسقاط من نطاق ويتباطأ فقط في الأداء.

Answer 1

وSeq.cache تخزين مثيل IEnumerable<T> بحيث يتم حساب كل عنصر في تسلسل مرة واحدة فقط. في الحالة الخاصة بك، على الرغم من أنك التخزين المؤقت تسلسل إرجاعها بواسطة وظيفة، وفي كل مرة كنت استدعاء الدالة تحصل على الجديد تسلسل مؤقتا، والتي لا تفعل أي خير لكم. لا أعتقد التخزين المؤقت هو في الحقيقة النهج الصحيح للمشكلة كما كنت المبينة فيه؛ بدلا من ذلك ربما يجب عليك النظر في التحفيظ.

إذا بدلا من تحديد وظيفة إعطاء يعبي أقل من n تريد تحديد تسلسل enumerable لا حصر له من الأعداد الأولية، ثم التخزين المؤقت أكثر منطقية. ومن شأن ذلك أن تبدو أكثر مثل هذا:

let rec upFrom i =
  seq { 
    yield i
    yield! upFrom (i+1)
  }

let rec primes =
  seq { 
    yield 2
    yield!
      upFrom 3 |>
      Seq.filter (fun p -> primes |> Seq.takeWhile (fun j -> j*j <= p) |> Seq.forall (fun j -> p % j <> 0))
  }
  |> Seq.cache

وأنا لم مقارنة أداء هذه الطريقة مقارنة لك.

Answer 2

وأنا أحسب كيفية حل مشكلتي مع أضعاف ولكن ليس لي فكرة استخدام seq.cache.

let primesNot1 n = 
    {2 .. n}
    |> Seq.fold (fun primes i ->
        if primes |> Seq.for_all (fun o -> i % o <> 0) then
            List.append primes [i]
        else
            primes) [2]

Answer 3

هل اتخذت نظرة على LazyList؟ يبدو انها مصممة على حل المشكلة نفسها. انها في باور.