Skip to content

Instantly share code, notes, and snippets.

@Janiczek

Janiczek/ListExtraBenchmark.elm Secret

Last active March 1, 2024 18:32
Show Gist options
  • Save Janiczek/b8e3f66cba281aac1dba4ea7dd80b709 to your computer and use it in GitHub Desktop.
Save Janiczek/b8e3f66cba281aac1dba4ea7dd80b709 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ListExtraBenchmark.elm
module ListExtraBenchmark exposing (main)
import Benchmark
import Benchmark.Runner.Alternative as BenchmarkRunner
impl =
{ orig =
{ groupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
let
thisGroup =
List.take size xs
in
if size == List.length thisGroup then
let
rest =
List.drop step xs
in
go rest (thisGroup :: acc)
else
List.reverse acc
in
go list []
, greedyGroupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
go
(List.drop step xs)
(List.take size xs :: acc)
in
go list []
}
, new =
{ groupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
let
thisGroup =
takeTailRec size xs
in
if size == List.length thisGroup then
let
rest =
List.drop step xs
in
go rest (thisGroup :: acc)
else
List.reverse acc
in
go list []
, greedyGroupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
go
(List.drop step xs)
(takeTailRec size xs :: acc)
in
go list []
}
}
takeTailRec : Int -> List a -> List a
takeTailRec n list =
List.reverse (takeReverse n list [])
takeReverse : Int -> List a -> List a -> List a
takeReverse n list kept =
if n <= 0 then
kept
else
case list of
[] ->
kept
x :: xs ->
takeReverse (n - 1) xs (x :: kept)
main =
BenchmarkRunner.program suite
toComparisons exponent =
let
listSize =
10 ^ exponent
range =
List.range 1 listSize
in
[ Benchmark.compare ("groupsOfWithStep 3 2 [1.." ++ String.fromInt listSize ++ "]")
"original"
(\() -> impl.orig.groupsOfWithStep 3 2 range)
"new"
(\() -> impl.new.groupsOfWithStep 3 2 range)
, Benchmark.compare ("greedyGroupsOfWithStep 3 2 [1.." ++ String.fromInt listSize ++ "]")
"original"
(\() -> impl.orig.greedyGroupsOfWithStep 3 2 range)
"new"
(\() -> impl.new.greedyGroupsOfWithStep 3 2 range)
]
suite =
Benchmark.describe "Tail recursive [greedy]groupsOf*: https://github.com/elmcraft/core-extra/pull/47" <|
List.concatMap toComparisons <|
List.range 1 4
Raw
ScaleBenchmark.elm
module ScaleBenchmark exposing (main)
import Benchmark
import Benchmark.Runner.Alternative as BenchmarkRunner
impl =
{ orig =
{ groupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
let
thisGroup =
List.take size xs
in
if size == List.length thisGroup then
let
rest =
List.drop step xs
in
go rest (thisGroup :: acc)
else
List.reverse acc
in
go list []
, greedyGroupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
go
(List.drop step xs)
(List.take size xs :: acc)
in
go list []
}
, new =
{ groupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
let
thisGroup =
takeTailRec size xs
in
if size == List.length thisGroup then
let
rest =
List.drop step xs
in
go rest (thisGroup :: acc)
else
List.reverse acc
in
go list []
, greedyGroupsOfWithStep =
\size step list ->
if size <= 0 || step <= 0 then
[]
else
let
go : List a -> List (List a) -> List (List a)
go xs acc =
if List.isEmpty xs then
List.reverse acc
else
go
(List.drop step xs)
(takeTailRec size xs :: acc)
in
go list []
}
}
takeTailRec : Int -> List a -> List a
takeTailRec n list =
List.reverse (takeReverse n list [])
takeReverse : Int -> List a -> List a -> List a
takeReverse n list kept =
if n <= 0 then
kept
else
case list of
[] ->
kept
x :: xs ->
takeReverse (n - 1) xs (x :: kept)
main =
BenchmarkRunner.program suite
toComparisons exponent =
let
listSize =
10 ^ exponent
range =
List.range 1 listSize
wantedScales =
[ 2, 20, 200 ]
|> List.filter (\scale -> scale < listSize)
in
if List.length wantedScales > 1 then
[ wantedScales
|> List.map (\scale -> ( String.fromInt scale, \() -> impl.orig.groupsOfWithStep scale 5 range ))
|> Benchmark.scale ("ORIG groupsOfWithStep <SCALE> 5 [1.." ++ String.fromInt listSize ++ "]")
, wantedScales
|> List.map (\scale -> ( String.fromInt scale, \() -> impl.new.groupsOfWithStep scale 5 range ))
|> Benchmark.scale ("NEW groupsOfWithStep <SCALE> 5 [1.." ++ String.fromInt listSize ++ "]")
, wantedScales
|> List.map (\scale -> ( String.fromInt scale, \() -> impl.orig.greedyGroupsOfWithStep scale 5 range ))
|> Benchmark.scale ("ORIG greedyGroupsOfWithStep <SCALE> 5 [1.." ++ String.fromInt listSize ++ "]")
, wantedScales
|> List.map (\scale -> ( String.fromInt scale, \() -> impl.new.greedyGroupsOfWithStep scale 5 range ))
|> Benchmark.scale ("NEW greedyGroupsOfWithStep <SCALE> 5 [1.." ++ String.fromInt listSize ++ "]")
]
else
[]
suite =
Benchmark.describe "Tail recursive [greedy]groupsOf*: https://github.com/elmcraft/core-extra/pull/47" <|
List.concatMap toComparisons <|
List.range 1 4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment