عند إنشاء قيمة وسيطة يجب علي تخزينها؟

Question

أحاول أن أتعلم F # لذلك دفعت زيارة مشروع Euler وأنا أعمل حاليا على المشكلة 3..

العوامل الرئيسية لعام 13195 هي 5 و 7 و 13 و 29.

ما هو أكبر عامل رئيسي للرقم 600851475143؟

بعض الأشياء التي يجب مراعاتها:

1. أولويتي الأولى هي تعلم عادات وظيفية جيدة.
2. الأولوية الثانية هي أنني أود أن تكون سريعة وفعالة.

ضمن التعليمات البرمجية التالية قمت بتمييز القسم هذا السؤال فيما يتعلق.

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L) 

let greatestPrimeFactor(n:int64) =
    let nextPrime(prime:int64):int64 = 
        seq { for i = prime + 1L to System.Int64.MaxValue do if isPrime(i) then yield i }  
        |> Seq.skipWhile(fun v -> n % v <> 0L) 
        |> Seq.hd
    let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else 
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))    
            //*************               
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p) 
            //*************
    findNextPrimeFactor(n, 2L) 

تحديث

استنادا إلى بعض التعليقات التي قمت بإعادتها إلى زيادة التعليمات البرمجية 10 مرات بشكل أسرع.

module Problem3

module private Internal =
    let execute(number:int64):int64 = 
        let rec isPrime(value:int64, current:int64) = 
            current > value / 2L or (value % current <> 0L && isPrime(value, current + 1L))   
        let rec nextPrime(prime:int64):int64 = 
            if number % prime = 0L && isPrime(prime, 2L) then prime else nextPrime(prime + 1L)       
        let rec greatestPrimeFactor(current:int64, prime:int64):int64 =
            if current = 1L then prime else nextPrime(prime + 1L) |> fun p -> greatestPrimeFactor(current / p, p)
        greatestPrimeFactor(number, 2L)


let execute() = Internal.execute(600851475143L)

تحديث

أود أن أشكر الجميع على المشورة. هذا الإصدار الأخير هو تجميع لجميع النصائح التي تلقيتها.

module Problem3

module private Internal =
    let largestPrimeFactor number = 
        let rec isPrime value current = 
            current > value / 2L || (value % current <> 0L && isPrime value (current + 1L))   
        let rec nextPrime value =
            if number % value = 0L && isPrime value 2L then value else nextPrime (value + 1L) 
        let rec find current prime =
            match current / prime with
            | 1L -> prime
            | current -> nextPrime (prime + 1L) |> find current
        find number (nextPrime 2L)            

let execute() = Internal.largestPrimeFactor 600851475143L

Answer 1

تصبح البرمجة الوظيفية أسهل وأكثر تلقائيا مع ممارسة، لذلك لا تعرق ذلك إذا لم تحصل عليه تماما في المحاولة الأولى.

مع وضع ذلك في الاعتبار، دعونا نأخذ رمز العينة الخاص بك:

let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else 
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))    
            //*************               
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p) 
            //*************

لك no variable الإصدار غريب فقط، لا تستخدمه. أنا أحب الإصدار الخاص بك مع الترجمات الكبرية.

طريقة أخرى لكتابة ذلك سيكون:

nextPrime(prime) |> fun p -> findNextPrimeFactor(number / p, p)

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

let rec findNextPrimeFactor number prime =
    match number / prime with
    | 1L -> prime
    | number' -> nextPrime(prime) |> findNextPrimeFactor number'

لا مزيد من اسمه args :)

---

حسنا، الآن لدينا ذلك بعيدا عن الطريق، دعونا ننظر إلى isPrime وظيفة:

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L) 

ربما سمعت استخدام العودية بدلا من الحلقات، وهذا هو الصحيح. ولكن، أينما كان ذلك ممكنا، يجب عليك مجردة العودية مع طيات أو خرائط أو وظائف ترتيب أعلى. سببين لهذا:

1. انها أكثر قليلا قراءة، و

2. ستؤدي العودية المكتوبة بشكل غير صحيح إلى تجاوز سعة مكدس. على سبيل المثال، وظيفتك ليست ذيل متكررة، لذلك سوف تفجر على قيم كبيرة من n.

أنا أعيد كتابة isPrime مثله:

let isPrime n = seq { 2L .. n / 2L } |> Seq.exists (fun i -> n % i = 0L) |> not

في معظم الأحيان، إذا كنت تستطيع مجردة حلقاتك الصريحة، فأنت فقط قم بتطبيق التحولات على تسلسل الإدخال الخاص بك حتى تحصل على نتائجك:

let maxFactor n =
    seq { 2L .. n - 1L }                        // test inputs
    |> Seq.filter isPrime                       // primes
    |> Seq.filter (fun x -> n % x = 0L)         // factors
    |> Seq.max                                  // result

ليس لدينا حتى المتغيرات المتوسطة في هذا الإصدار. البول!

---

الأولوية الثانية هي أنني أود أن تكون سريعة وفعالة.

معظم الوقت، ستكون F # قابلة للمقارنة مع C # من حيث السرعة، أو سيكون "سريع بما فيه الكفاية". إذا وجدت رمزك وقتا طويلا للتنفيذ، فربما يعني أنك تستخدم بنية البيانات الخاطئة أو خوارزمية سيئة. مثال ملموس، اقرأ التعليقات على هذا السؤال.

لذلك، فإن القانون الذي كتبته هو "أنيق" بمعنى أن موجزة، يمنح النتائج الصحيحة، ولا يعتمد على أي خداع. لسوء الحظ، ليس بسرعة كبيرة. للبداية:

• يستخدم قسم التجربة لإنشاء سلسلة من الأعداد الأولية، عندما يكون غربال eratosthenes أسرع بكثير. [تحرير: كتبت نسخة ساذجة إلى حد ما من هذا الغربال الذي لم يعمل من أجل الأرقام أكبر من int32.maxvalue، لذلك قمت بإزالة التعليمات البرمجية.

• قراءة مقال ويكيبيديا على وظيفة العد البريطانية, ، سوف يعطيك مؤشرات حول حساب الأول n الأعداد الأولية وكذلك تقدير الحدود العلوية والسفلية ل nth رئيس الوزراء.

تحرير: تضمنت بعض التعليمات البرمجية بتنفيذ ساذج إلى حد ما من غربال eratosthenes. يعمل فقط من أجل المدخلات أقل من INT32.MaxValue، لذلك ربما ليس مناسبا لمشروع مشروع Euler.

Answer 2

فيما يتعلق ب "عادة وظيفية جيدة" أو ممارسة جيدة إلى حد ما أرى ثلاثة أشياء ثانوية. استخدام العائد في التسلسل الخاص بك هو أصعب قليلا القراءة من مجرد تصفية. يؤدي التوضيحات من النوع غير الضرورية في لغة مصنوعة من النوع إلى إعادة صياغة وتجعل الكود أصعب قراءته. لا تذهب في الخارج ومحاولة إزالة كل التفاصيل التوضيحية على الرغم من أنك تجد صعوبة في ذلك. وأخيرا جعل وظيفة Lambda التي تأخذ قيمة لاستخدامها فقط كأقل من درجة الحرارة يقلل من قابلية القراءة.

بقدر ما يذهب النمط الشخصي إلى المزيد من المساحات واستخدام الحجج المزدوجة فقط عندما تكون البيانات المنطقية مجمعة معا.

سأكتب التعليمات البرمجية الأصلية مثل هذا.

let isPrime n = 
    let rec check i = 
        i > n / 2L || (n % i <> 0L && check (i + 1L))
    check 2L

let greatestPrimeFactor n =
    let nextPrime prime = 
        seq {prime + 1L .. System.Int64.MaxValue}
        |> Seq.filter isPrime
        |> Seq.skipWhile (fun v -> n % v <> 0L) 
        |> Seq.head

    let rec findNextPrimeFactor number prime =
        if number = 1L then 
            prime 
        else 
            let p = nextPrime(prime)
            findNextPrimeFactor (number / p) p

    findNextPrimeFactor n 2L

الرمز المحدث الخاص بك هو الأمثل لنهجك. يجب عليك استخدام خوارزمية مختلفة مثل إجابة Yin Zhu للذهاب بشكل أسرع. كتبت اختبارا للتحقق لمعرفة ما إذا كان F # يجعل "الشيك" ذيل وظيفة العودية

Answer 3

ال عامل P هو في الواقع اسم ملزم، وليس متغير. استخدام ملزمة الاسم ليس نمطا سيئا. وهو أكثر قابلية للقراءة. أسلوب كسول من nextPrime جيد، واختبار كل رقم فعليا مرة واحدة فقط خلال البرنامج بأكمله.

بلدي الحل

let problem3 = 
    let num = 600851475143L
    let rec findMax (n:int64) (i:int64) =
        if n=i || n<i then
            n
        elif n%i=0L then
            findMax (n/i) i
        else
            findMax n (i+1L)
    findMax num 2L

أنا أساسا تقسيم الأساس من 2، 3، 4 .. ولا تعتبر أي أرقام أولية. لأنه إذا قمنا بتقسيم الكل 2 من Num، فلن نتمكن من تقسيمها بنسبة 4،8، إلخ.

على هذا الرقم، حلاي أسرع:

> greatestPrimeFactor 600851475143L;;
Real: 00:00:01.110, CPU: 00:00:00.702, GC gen0: 1, gen1: 1, gen2: 0
val it : int64 = 6857L
> 
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val problem3 : int64 = 6857L

Answer 4

أعتقد أن الكود مع الربط المؤقت أسهل بكثير القراءة. من غير المعتاد أن تخلق وظيفة مجهولة ثم قم بتطبيقها على الفور على قيمة كما تفعل في الحالة الأخرى. إذا كنت ترغب حقا في تجنب استخدام قيمة مؤقتة، أعتقد أن الطريقة الأكثر اعتصايا للقيام بذلك في F # ستكون استخدام (|>) المشغل على توجيه القيمة إلى الوظيفة المجهولة، ولكن ما زلت أعتقد أن هذا ليس قريرا تماما.