술어와 일치하는 요소를 가장 빨리 계산하는 방법

Question

오늘 나는 성능과 관련하여 Mathematica에 idiomatic way to count elements matching predicate 함수가 있는지 묻습니다.

PredCount1[lst_, pred_] := Length@Select[lst, pred]; 

나는 다른 lst 크기와 pred로 대신

PredCount2[lst_, pred_] := Count[lst, x_/;pred@x]; 

나는 이러한 기능을 프로파일 링 시작을 사용하는 제안을 얻었 : 주어진 조건 pred에 대한

내 초기 접근 방식은 다음이었다 함수를 정의하고 두 가지 정의를 더 추가했습니다.

PredCount3[lst_, pred_] := Count[Thread@pred@lst, True]; 
PredCount4[lst_, pred_] := Total[If[pred@#, 1, 0] & /@ lst]; 

내 데이터 샘플의 범위는 1 천만 개에서 1 천만 개까지이며, 테스트 기능은 EvenQ, #<5& 및 PrimeQ입니다. 다음 그래프는 취해진 시간을 보여줍니다.

EvenQ

PredCount2가 느리다

, 3, 4 듀크 그것을.

비교 술어 : 그것은 내 실제 문제에서 필요에 가까운이기 때문에 # < 5 &

나는,이 기능을 선택했습니다. 이것이 바보 같은 테스트 함수라는 것에 대해 걱정하지 마라. 실제로 네 번째 함수가 약간의 장점을 가지고 있음을 증명한다. 나는 실제로 그것을 내 솔루션에서 사용했다.

EvenQ과 동일

하지만 3이 단지 기괴한 명확보다 느린 4

PrimeQ

입니다. 모든 것이 뒤집혔다. 최악의 값은 마지막으로 계산 된 함수에 대한 것이므로 여기서 캐싱을 의심하는 것은 아닙니다.

따라서 주어진 조건부 함수와 일치하는 목록의 요소 수를 계산하는 가장 빠른 방법은 무엇입니까?

Answer 1

자동 편집 결과가 표시됩니다.

첫째는 Listable 함수 등 EvenQ 및 Thread의 PrimeQ 사용은 불필요하다 :

는

EvenQ[{1, 2, 3}] 

{False, True, False} 

이 이러한 기능에 PredCount3 수행 잘 이유를 설명한다. (이들은 내부적으로 목록에 대한 스레딩에 최적화되어 있습니다.)

이제 타이밍을 살펴 보겠습니다.우리가 Map 내에서 자동 컴파일을 방지하고 다시 테스트를 실행하는 시스템 옵션을 변경하는 경우

dat = RandomInteger[1*^6, 1*^6]; 

test = # < 5 &; 

First@Timing[#[dat, test]] & /@ {PredCount1, PredCount2, PredCount3, PredCount4} 

{0.343, 0.437, 0.25, 0.047} 

:

SetSystemOptions["CompileOptions" -> {"MapCompileLength" -> Infinity}] 

First@Timing[#[dat, test]] & /@ {PredCount1, PredCount2, PredCount3, PredCount4} 

{0.343, 0.452, 0.234, 0.765} 

을 당신은 명확하게 할 수 compi없이 보자. PredCount4은 훨씬 느립니다. 간단히 말해, 테스트 함수가 으로 컴파일 될 수 있다면 Mathematica 이것은 좋은 옵션입니다.

Here are some other examples of fast counting using numeric functions.

Answer 2

목록에서 정수의 본질은 달성 가능한 타이밍에 상당한 영향을 미칠 수 있습니다. Tally을 사용하면 정수 범위가 제한되면 성능이 향상 될 수 있습니다. 이하가되는 경우 0.1 초 이상

도 10^8 크기의 목록에서, 소수는로 계산 될 수 있음을 표시 : PrimeQ 들어

(* Count items in the list matching predicate, pred *) 

PredCountID[lst_, pred_] := 
Select[Tally@lst, pred@First@# &]\[Transpose] // Last // Total 

(* Define the values over which to check timings *) 
ranges = {100, 1000, 10000, 100000, 1000000}; 
sizes = {100, 1000, 10000, 100000, 1000000, 10000000,100000000}; 

이 함수는 다음의 타이밍을 준다 {0, ..., 100000}의 정수 집합에 속하며 1에서 100 등의 작은 범위 내에있는 경우 Timing의 해상도보다 작습니다.

술어는세트값의 경우이 접근법은 정확한 술어 기능에 상대적으로 민감하지 않습니다.