Repository navigation
A version of findIndex for the last matching element. - #174
Conversation
| -- | /O(n)/ Yield 'Just' the index of the /last/ element matching the predicate | ||
| -- or 'Nothing' if no such element exists. | ||
| findIndexR :: Vector v a => (a -> Bool) -> v a -> Maybe Int | ||
| {-# INLINE findIndexR #-} |
There was a problem hiding this comment.
I'm actually not sure if it makes sense to inline this. dolio remarked that this function won't be able to use any stream fusion. I know too little about vector's optimisations to judge this.
|
|
The results confirm that the `streamR` based implementation is
significantly faster than a manual recursion loop (at least
without any non-obvious optimisations) and much faster than a naïve
implementation with `foldl`.
```
benchmarking findIndexR
time 592.0 μs (589.8 μs .. 594.7 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 591.3 μs (589.8 μs .. 593.0 μs)
std dev 5.563 μs (4.182 μs .. 7.344 μs)
benchmarking findIndexR_naïve
time 15.87 ms (15.66 ms .. 16.08 ms)
0.999 R² (0.998 R² .. 1.000 R²)
mean 16.01 ms (15.92 ms .. 16.17 ms)
std dev 316.9 μs (207.2 μs .. 490.3 μs)
benchmarking findIndexR_manual
time 977.0 μs (968.0 μs .. 987.1 μs)
0.999 R² (0.999 R² .. 1.000 R²)
mean 978.0 μs (973.1 μs .. 986.6 μs)
std dev 21.65 μs (13.65 μs .. 34.29 μs)
variance introduced by outliers: 12% (moderately inflated)
```
The benchmark was requested by cartazio
haskell#174 (comment)
|
The benchmark suggests that this function is indeed worthwhile, in that it's 40% faster than a manual loop (it's possible that I've missed some optimisation that should be used in the loop, though. But then, that could also happen to other people, so...) |
1dd142f to
b49f7e3
Compare
The results confirm that the `streamR` based implementation is
significantly faster than a manual recursion loop (at least
without any non-obvious optimisations) and much faster than a naïve
implementation with `foldl`.
```
benchmarking findIndexR
time 592.0 μs (589.8 μs .. 594.7 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 591.3 μs (589.8 μs .. 593.0 μs)
std dev 5.563 μs (4.182 μs .. 7.344 μs)
benchmarking findIndexR_naïve
time 15.87 ms (15.66 ms .. 16.08 ms)
0.999 R² (0.998 R² .. 1.000 R²)
mean 16.01 ms (15.92 ms .. 16.17 ms)
std dev 316.9 μs (207.2 μs .. 490.3 μs)
benchmarking findIndexR_manual
time 977.0 μs (968.0 μs .. 987.1 μs)
0.999 R² (0.999 R² .. 1.000 R²)
mean 978.0 μs (973.1 μs .. 986.6 μs)
std dev 21.65 μs (13.65 μs .. 34.29 μs)
variance introduced by outliers: 12% (moderately inflated)
```
The benchmark was requested by cartazio
haskell#174 (comment)
Bodigrim
left a comment
Bodigrim
left a comment
There was a problem hiding this comment.
@leftaroundabout could you possibly rebase?
| {-# NOINLINE findIndexR #-} | ||
| findIndexR = uncurry V.findIndexR | ||
|
|
||
| findIndexR_naïve :: (Double -> Bool, Vector Double) -> Maybe Int |
There was a problem hiding this comment.
Let's avoid Unicode in function names.
The results confirm that the `streamR` based implementation is
significantly faster than a manual recursion loop (at least
without any non-obvious optimisations) and much faster than a naïve
implementation with `foldl`.
```
benchmarking findIndexR
time 592.0 μs (589.8 μs .. 594.7 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 591.3 μs (589.8 μs .. 593.0 μs)
std dev 5.563 μs (4.182 μs .. 7.344 μs)
benchmarking findIndexR_naïve
time 15.87 ms (15.66 ms .. 16.08 ms)
0.999 R² (0.998 R² .. 1.000 R²)
mean 16.01 ms (15.92 ms .. 16.17 ms)
std dev 316.9 μs (207.2 μs .. 490.3 μs)
benchmarking findIndexR_manual
time 977.0 μs (968.0 μs .. 987.1 μs)
0.999 R² (0.999 R² .. 1.000 R²)
mean 978.0 μs (973.1 μs .. 986.6 μs)
std dev 21.65 μs (13.65 μs .. 34.29 μs)
variance introduced by outliers: 12% (moderately inflated)
```
The benchmark was requested by cartazio
haskell#174 (comment)
|
@Bodigrim done |
|
This looks good to me. @Bodigrim do you have any more suggestions? The ones you've pointed out have already been taken care of. I'll merge the PR in a few days if I don't hear form you. |
4 participants
Discussed in
#172