중개 값을 만들 때 저장해야합니까?

StackOverflow https://stackoverflow.com/questions/2036073

문제

나는 f#를 배우려고 노력하고있어서 방문했다. 프로젝트 오일러 그리고 저는 현재 작업 중입니다 문제 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
도움이 되었습니까?

해결책

기능적 프로그래밍은 연습을 통해 더 쉽고 자동으로 작동하므로 첫 번째 시도에서 절대적으로 제대로 얻지 못하면 땀을 흘리지 마십시오.

이를 염두에두고 샘플 코드를 사용해 봅시다.

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 버전은 이상합니다. 사용하지 마십시오. 나는 명백한 Let Binding과 함께 귀하의 버전을 좋아합니다.

글을 쓰는 또 다른 방법은 다음과 같습니다.

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보다 큰 숫자에 대해 효과가없는이 체의 다소 순진한 버전을 썼으므로 코드를 제거했습니다.

  • Wikipedia의 기사를 읽으십시오 주요 카운팅 기능, 첫 번째 계산에 대한 포인터를 줄 것입니다 n 프라임뿐만 아니라 nth 초기.

편집 : 나는 Eratosthenes의 체를 다소 순진한 구현으로 일부 코드를 포함시켰다. int32.maxvalue보다 적은 입력에만 적용되므로 Project Euler에 적합하지 않을 것입니다.

다른 팁

"좋은 기능적 습관"또는 오히려 모범 사례와 관련하여 나는 세 가지 사소한 것들을 봅니다. 시퀀스에서 수율을 사용하는 것은 단순한 필터보다 읽기가 어렵습니다. 유형의 언어 유형의 불필요한 유형 주석은 리팩토링이 어려워지고 코드를 읽기가 더 어려워집니다. 어려운 일이라면 배 밖으로 나가지 말고 모든 유형 주석을 제거하십시오. 마지막으로 온도 변수로 사용하는 데만 값을 취하는 람다 함수를 만들면 가독성이 줄어 듭니다.

개인적인 스타일이 진행되는 한 나는 더 많은 공간을 선호하고 데이터가 함께 그룹화 될 때 튜플 인수 만 사용합니다.

나는 당신의 원본 코드를 이렇게 쓸 것입니다.

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#이 "점검"기능 테일을 재귀시키는 지 확인하기 위해 테스트를 작성했습니다.

그만큼 변하기 쉬운 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

나는 기본적으로 NUM을 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

임시 바인딩이있는 코드는 읽기가 훨씬 쉽다고 생각합니다. 익명 기능을 만들고 다른 경우와 같이 즉시 값에 적용하는 것은 매우 드문 일입니다. 일시적인 가치를 사용하지 않으려면 F#에서 가장 관용적 인 방법은 다음을 사용하는 것입니다. (|>) 운영자는 값을 익명 기능으로 파이프로 파이프하지만 여전히 읽을 수 없다고 생각합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top