Skip to content

Instantly share code, notes, and snippets.

@leftaroundabout
Last active September 11, 2017 12:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save leftaroundabout/6e746cc6b2787a3c9f209e32740547b9 to your computer and use it in GitHub Desktop.
Save leftaroundabout/6e746cc6b2787a3c9f209e32740547b9 to your computer and use it in GitHub Desktop.
Comparison of two ways to fold over unordered unique pairs in a collection of elements
#define N 50001
#include "stdio.h"
int main() {
int v[N];
for (int i=0; i<N; ++i) {
v[i] = i;
}
int b=0;
for (int i=0; i<N; ++i) {
for (int j=i+1; j<N; ++j) {
b += v[i] - v[j];
}
}
printf("%i", b);
return 0;
}
import qualified Data.Vector.Unboxed as U
import Data.Vector.Generic ((!))
import Data.List (foldl')
pairApply :: (U.Unbox a, U.Unbox b)
=> (b -> b -> b)
-> b
-> (a -> a -> b)
-> (U.Vector a)
-> b
pairApply combine neutral f v
= U.ifoldl' (\acc i p -> U.foldl' (\acc' q -> combine acc' $ f p q)
acc
(U.drop (i+1) v) )
neutral v
pairApplySum :: (Int -> Int -> Int) -> U.Vector Int -> Int
pairApplySum f v = foldl' (+) 0 [f (v ! i) (v ! j) | i <- [0..(n-1)], j <- [(i+1)..(n-1)]]
where n = U.length v
main = do
-- print $ pairApply (+) 0 (-) (U.fromList [0..50000] :: U.Vector Int)
print $ pairApplySum (-) (U.fromList [0..50000] :: U.Vector Int)

Vector-slices, with -O0

real  1m2.179s
user  1m2.036s
sys 0m0.140

LisL, with -O0

real  3m20.125s
user  3m19.640s
sys 0m0.468s

List (!), with -O2

real	0m1.899s
user	0m1.896s
sys	0m0.000

Vector-slices, with -O2

real	0m3.215s
user	0m3.208s
sys	0m0.004s

Reference C implementation, with gcc -O2

real	0m1.220s
user	0m1.216s
sys	0m0.000s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment