목록에있는 요소의 비율을 효율적으로 계산하십시오.

Question

이것은 긴 목록을 가지고 오래 걸립니다. 문제가되는 길이를 두 번 사용한다고 가정합니다.

ratioOfPrimes :: [Int] -> Double 
ratioOfPrimes xs = fromIntegral (length (filter isPrime xs))/ fromIntegral(length xs) 

더 효율적인 접근 방법은 무엇입니까?

Answer 1

여기서 length의 두 번 사용은 주된 문제가 아닙니다. 구현시 여러 번 통과하면 상수 요소가 생성되고 length 및 filter이면 평균 복잡도는 O(3n)입니다. Stream Fusion 덕분에 이미 Impredicative에서 언급 한 것처럼 O(2n)입니다.그러나 실제로 상수 요소가 성능에 큰 영향을 미치지 않으므로 단순히 무시하는 것이 일반적이기 때문에 구현은 여전히 ​​O(n)의 복잡성을 갖습니다. 여기서 n은 입력 목록의 길이입니다.

실제 문제는 여기 isPrime의 복잡도가 O(1) 인 경우에만 위의 내용이 모두 참이지만 그렇지 않습니다. 이 함수는 모든 소수의 목록을 통해 순회를 수행하므로 그 자체로 O(m)의 복잡성을 갖습니다. 따라서 여기서 극적인 성능 저하는 알고리즘이 O(n*m)의 최종 복잡도를 갖기 때문에 발생합니다. 입력 목록을 반복 할 때마다 모든 소수의 목록을 알려지지 않은 깊이로 트래버스해야하기 때문입니다.

최적화하려면 먼저 입력 목록 (O(n*log n) 걸림)을 정렬하고 모든 소수의 목록에서 사용자 지정 조회를 반복하여 각 반복에서 이미 방문한 숫자를 삭제하십시오. 이 방법을 사용하면 모든 소수의 목록에서 단일 탐색을 수행 할 수 있습니다. 이론적으로는 O(n*log n + n + m)의 복잡성을 부여 할 수 있습니다. 비용 센터를 강조함으로써 일반적으로 단순하게 O(n*log n)으로 생각할 수 있습니다.

Answer 2

그래서 여기에는 몇 가지 사항이 있습니다. 이제 관련된 작업의 일부를 살펴 보자 :

• length
• filter
• isPrime
도움하지 않을 두 번 length를 사용하여 당신이 말하는 것처럼
• length

, 그 이후 목록의 경우 O(n) 너는 두 번 그렇게 해. 그런 다음 이 있으며 이는 O(n)에 전체 목록을 전달합니다. 우리가하고 싶은 것은이 모든 것을 목록의 한 번에 통과하는 것입니다.

Data.List.Stream 모듈의 함수는 Stream Fusion이라는 기술을 구현합니다.이 기술은 예를 들어 (length (filter isPrime xs)) 호출을 단일 루프로 다시 작성합니다. 그러나 두 번째 호출 길이는 여전히 있습니다. 당신은 축전지의 한 쌍의이 모든 하나의 배에 일 (또는 주 또는 ST 모나드의 사용을) 다시 단일 패스에서이 작업을 수행 할 수 있습니다 :

ratioOfPrimes xs = let 
    (a,b) = foldl' (\(odd,all) i -> if (isPrime i) then (odd +1, all+1) else (odd, all+1)) (0,0) xs 
in a/b 

그러나이 경우 당신은 또한 멀리 움직일 수 목록을 사용하고 vector 라이브러리를 사용하십시오. 벡터 라이브러리는 중간 목록을 제거하기 위해 같은 스트림 융합 기술을 구현뿐만 아니라 다른 멋진 기능이 있습니다

• length는 Data.Vector.Unboxed 모듈은 당신이 (unboxable 유형을 저장할 수 있습니다 O(1)
• 입니다을하는 등 확실히 Int 같은 기본 유형) 박스형 표현의 오버 헤드없이. 따라서이 int 목록은 하위 레벨 Int 배열로 저장됩니다.

패키지 vector 패키지를 사용하면 위의 관용구 표현을 쓰고 단일 패스 번역의 성능보다 뛰어나다. 물론

import qualified Data.Vector.Unboxed as U 

ratioOfPrimes :: U.Vector Int -> Double 
ratioOfPrimes xs = (fromIntegral $ U.length . U.filter isPrime $ xs)/(fromIntegral $ U.length xs) 

은 언급되지 않은 것은 isPrime 기능, 그리고 진짜 문제 여부가 큰 n에 대한 느린 것입니다. 부적 절한 프라임 검사기는 목록 색인 생성에 대한 우려를 쉽게 풀 수 있습니다.