Авторское право (c) 2022 JEON Myoungjin
ЛИЦЕНЗИЯ: Лицензия открытого программного обеспечения 3.0
Между моими любимыми языками началась война …
Не очень точный бенчмарк
И я слишком одержим Как создавать комбинации в haskell.
Серия «Комбинации в Haskell
- Комбинации на Haskell (под названием «Хвост за хвостом»)
- История Tail After Tail (Combinations In Haskell)
Одна и та же теория; разная реализация
В мире программирования псевдокод или теория могут по-разному повлиять на вашу программную реализацию. Такое отвлечение делает программирование интересным.
Ранее я создал TailAfterTail.lhs.
И я обнаружил, что inits или tails не совсем необходимы, если я не полагаюсь на scanl или zipWith.
Наверное, общепризнанно, что некоторые различные реализации, состоящие даже из небольшого количества кодов, но выполняющиеся с очень высокой частотой, в конечном итоге покажут огромные провалы в производительности после многих итераций выполнения.
Вот примерно это я и обнаружил при реализации комбинаций Tail After Tail.
Модуль начинается
Во-первых, я собираюсь записать все функции, которые будут открыты.
{-# LANGUAGE BangPatterns #-}
module TailAfterTail
( combinationsWithScanl
, combinationsWithSingleStep
, combinations
, combinationsWithTwoSteps
, allCombinationsWithScanl
, allCombinationsWithSingleStep
, allCombinationsWithTwoSteps
, allCombinations
) where
import Data.List (tails, inits, scanl') -- only required for **WithScanl
Оригинальная версия (scanl)
Пожалуйста, найдите больше информации ЗДЕСЬ.
Однако, combinations1', flatten_allCombinationsGrouped и
combinations1' :: [a] -> [[[a]]]
combinations1' ms = [ [[m]] | m <- ms ]
flatten_allCombinationsGrouped allComboFunc = map concat . allComboFunc
genPart :: Foldable t => a -> t [[a]] -> [[a]]
genPart leader followerGroups = [ leader : followers
| followers <- concat followerGroups ]
И я определяю некоторые вспомогательные функции.
usefulTails :: [a] -> [[a]]
usefulTails = init . tails
genStep :: [[[a]]] -> [a] -> [[[a]]]
genStep prevTails members' =
zipWith genPart members' (usefulTails prevTails')
where
prevTails' = tail prevTails -- head is not useful
membersTails = reverse . tail . inits -- tail is used to skip empty list.
и, наконец, семейство combinationsWithScanl ниже.
allCombinationsWithScanl' :: [a] -> [[[[a]]]]
allCombinationsWithScanl' ms =
scanl' genStep (combinations1' ms) (membersTails ms)
allCombinationsWithScanlGrouped :: [a] -> [[[a]]]
allCombinationsWithScanlGrouped =
flatten_allCombinationsGrouped allCombinationsWithScanl'
allCombinationsWithScanl :: [a] -> [[a]]
allCombinationsWithScanl = concat . allCombinationsWithScanlGrouped
Чистая реализация без Scanl (SingleStep)
Следующий код создан без scanl или zipWith.
Он получает немного больше производительности при использовании (bang pattern: !).
О чем будет рассказано, возможно, в другой статье.
Но IMHO, это помогает уменьшить лень и использовать меньше стека.
unsafe_allCombinationsWithSingleStep :: [a] -> [[[[a]]]]
unsafe_allCombinationsWithSingleStep members =
let
helper ! cases = -- bang pattern added
let
genStep (m:ms) (_:cs:[]) = [ [ m : c | c <- cs ] ]
genStep (m:ms) (_:cs) =
-- note ^ : we don't use first element
genPart m cs : genStep ms cs
in
cases : helper (genStep members cases)
in
helper . combinations1' $ members
Как вы видите, функция helper является просто функцией-оберткой начального уровня и выполняет вызов рекурсии.
genStep фактически создает следующие случаи и действует как thunk, который оценивается позже благодаря лени в haskell.
Я специально назвал функцию unsafe_. Потому что вспомогательная функция на самом деле не знает, когда она остановится, и если вы запустите unsafe_allCombinationsWithSingleStep в голом контексте, это приведет к взрыву с исключением.
sh> ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/ :? for help
Loaded GHCi configuration from /your/home/.config/ghc/ghci.conf
λ> :l 2022-04-15-Combinations-TailAfterTail'.lhs
[1 of 1] Compiling TailAfterTail ( 2022-04-15-Combinations-TailAfterTail'.lhs, interpreted )
Ok, one module loaded.
λ> unsafe_allCombinationsWithSingleStep [1..5]
[[[[1]],[[2]],[[3]],[[4]],[[5]]],[[[1,2],[1,3],[1,4],[1,5]],[[2,3],[2,4],[2,5]],[[3,4],[3,5]],[[4,5]]],[[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5]],[[2,3,4],[2,3,5],[2,4,5]],[[3,4,5]]],[[[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5]],[[2,3,4,5]]],[[[1,2,3,4,5]]],[[]*** Exception: 2022-04-15-Combinations-TailAfterTail'.lhs:(120,9)-(122,52): Non-exhaustive patterns in function genStep
unsafe_allCombinationsWithSingleStepGrouped сплющивает результат, но при этом группирует по размеру выбора, это все еще небезопасно, но combinationsWith справится с этим.
unsafe_allCombinationsWithSingleStepGrouped :: [a] -> [[[a]]]
unsafe_allCombinationsWithSingleStepGrouped =
flatten_allCombinationsGrouped unsafe_allCombinationsWithSingleStep
Теперь мы можем получить все комбинации, сплющив результат еще раз.
allCombinationsWithSingleStep :: [a] -> [[a]]
allCombinationsWithSingleStep members =
concat
-- this makes unsafe_* safe by limiting the size of list.
. take (length members)
. unsafe_allCombinationsWithSingleStepGrouped
$ members
С двумя шагами
Это еще одна версия без scanl. Основное улучшение заключается в том, что
эта функция разделяет работу на две операции:
- создать первые случаи из предыдущих хвостов.
- создать остальные случаи и начать следующий следующий случай на основе результата.
allCombinationsWithTwoSteps' :: [a] -> [[[[a]]]]
allCombinationsWithTwoSteps'
members@(fm:rms) = -- ^ fm : first member; rms: rest members
let
initFirstCase = [[fm]]
initRestCases = combinations1' rms
genFirstCases = genPart fm
genRestCases _ [] = []
genRestCases (m:ms) rcs@(_:rcs') = -- ^ rcs : rest of cases
(genPart m $ rcs) : (genRestCases ms rcs')
Это выглядит почти идентично при сравнении с SingleStep, но
теперь функция helper точно знает, с чего начать, так как newTail уже
запоминается в данный момент. Это только экономит время для хвоста путем сопоставления с образцом
в SingleStep, но результаты распространяются, когда выбор растет.
BTW, tail по шаблону означает (_:cs) в следующем коде.
genStep (m:ms) (_:cs) =
-- note ^ : we don't use first element
[ m : c | c <- concat cs ] : genStep ms cs
И давайте соединим их с начальным регистром и вспомогательной функцией
helper [] = []
helper ! prevTail =
let
newTail = genRestCases rms (tail prevTail)
in
((genFirstCases prevTail) : newTail) : helper newTail
in (initFirstCase : initRestCases) : helper initRestCases
следующие шаги аналогичны другой реализации.
allCombinationsWithTwoStepsGrouped :: [a] -> [[[a]]]
allCombinationsWithTwoStepsGrouped =
flatten_allCombinationsGrouped allCombinationsWithTwoSteps'
allCombinationsWithTwoSteps :: [a] -> [[a]]
allCombinationsWithTwoSteps members =
concat . allCombinationsWithTwoStepsGrouped $ members
Еще одним преимуществом реализации TwoSteps является то, что мы можем остановиться
потому что теперь newTail всегда доступен, и мы можем знать, доступен ли следующий шаг.
следующий шаг доступен или нет. Мне больше не нужно называть это unsafe_.
Вариант комбинаций из каждой реализации
Теперь пришло время сделать select K из заданного выбора.
И я обнаружил, что это обычная вспомогательная функция:
combinationsWith
combinationsWith :: ([a] -> [[[a]]]) -> [a] -> Int -> Int -> [[a]]
combinationsWith allComboGroupedFunc ms n1@selectFrom n2@selectTo =
let
( isFlipped, n1', n2' ) = -- smaller value first
if n1 < n2 then ( False
, max n1 0
, max n2 0)
else ( True
, max n2 0
, max n1 0)
-- and ensure all range value are zero or positive by using `max`
rangeLength = n2' - n1' + 1
reverseIfNeeded
| isFlipped = reverse
| otherwise = id
in
-- note: read from the bottom
concat -- 4. final flattening
. reverseIfNeeded -- 3. if user put opposite way, reverse it.
. take rangeLength -- 2. takes only interested lists
. drop (pred n1') -- 1. ignore some
$ allComboGroupedFunc ms
И все варианты комбинаций* функции доступны ниже:
combinationsWithScanl = combinationsWith allCombinationsWithScanlGrouped
combinationsWithSingleStep = combinationsWith unsafe_allCombinationsWithSingleStepGrouped
combinationsWithTwoSteps = combinationsWith allCombinationsWithTwoStepsGrouped
Бенчмарк
вы можете найти код бенчмарка на моем репозитории github.
Чтобы сэкономить ваше время, ЭТО
один из результатов моего бенчмарка.
Выберите AllCombinations и комбинации по умолчанию
После бенчмаркинга я обнаружил, что AllcombinationsWithTwoSteps показывает лучший результат
во всех категориях (малая, средняя, большая) среди них.
allCombinations = allCombinationsWithTwoSteps
combinations = combinationsWithTwoSteps