Рекомендации алгоритма Haskell и предложения по альтернативным решениям
Я оставляю описание проблемы ниже, но я редактирую все несоответствующие биты, когда я иду.
1) Благодаря dfeuer, я смог полностью избавиться от этой программы. Я дошел до 9.2 секунд с 10.1.
2) Благодаря модификации того, что SO user приложение опубликовано, я смог сэкономить до 7,0 секунд, сделав IO как очень эффективный.
3) Благодаря другой версии groupBy нашла здесь, теперь я нахожусь на 6.2 секунды.
4) Повторная реализация выходного файла построителя и теперь через 5.8 секунды.
import qualified Data.ByteString.Builder as BB
import qualified Data.ByteString.Lazy.Char8 as DB
import qualified Data.Function as DF
import Control.Applicative
import Data.Monoid
import System.IO
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy rel [] = []
groupBy rel (x:xs) = (x:ys) : groupBy rel zs
where (ys,zs) = groupByAux x xs
groupByAux x0 (x:xs)
| rel x0 x = (x:ys, zs)
where (ys,zs) = groupByAux x xs
groupByAux y xs = ([], xs)
filterLengthBy :: (Int -> Bool) -> [[a]] -> [[a]]
filterLengthBy fn = filter (flb fn)
where flb fn xs = fn $ length xs
buildOutput x y = BB.intDec x <> BB.char7 ' ' <> BB.intDec y <> BB.char7 '\n'
tensAndHundreds :: [[[Int]]] -> [BB.Builder]
tensAndHundreds [] = []
tensAndHundreds (x:xs)
| length x /= 10 = tens x ++ tensAndHundreds xs
| otherwise = buildOutput (head $ head x) 100 : tensAndHundreds xs
tens :: [[Int]] -> [BB.Builder]
tens = foldr (\x acc -> buildOutput (head x) 10 : acc) []
dbIntVals :: DB.ByteString -> [Int]
dbIntVals xs =
case (DB.readInt xs) of
Just (x', xs') -> x' : dbIntVals (DB.tail xs')
Nothing -> if xs == DB.empty
then []
else dbIntVals (DB.tail xs)
generateResults :: [Int] -> [BB.Builder]
generateResults xs = tensAndHundreds
$ groupBy ((==) `DF.on` (`quot` 100) . head)
$ filterLengthBy (== 10)
$ groupBy ((==) `DF.on` (`quot` 10)) xs
displayResults :: [BB.Builder] -> IO ()
displayResults xs = BB.hPutBuilder stdout $ mconcat xs
main :: IO ()
main = DB.getContents >>=
displayResults . generateResults . dbIntVals
Мои два вопроса, которые были в нижней части исходного сообщения:
-
Учитывая подход, который я опубликовал выше, есть ли что-то, что я пропустил, что повысит эффективность и, следовательно, производительность этой программы? Является ли выделение пространства окончательным узким местом? Другими словами, прошел ли метод groupBy?
-
Какие еще способы я мог бы рассмотреть эту проблему, которая повысила бы эффективность, все еще пытаясь избежать счётчиков в традиционном смысле? Я еще не знаком с продвинутыми функциями Haskell, но, пожалуйста, не стесняйтесь предлагать указатели.
Это оригинальная проблема. Я оставил первую версию кода, но удалил все материалы профайлера
Я начал изучать Haskell (снова) и решил попробовать некоторые случайные проблемы, которые я нашел. Одна из проблем, которые я разработал на форумах Arch Linux, выглядит следующим образом:
Учитывая набор уникальных, восходящих, но не обязательно непрерывных целых чисел, для каждого потенциального поддиапазона 100, начинающегося с 0 (0-99, 100-199, 1300-1399 и т.д.), если этот субдиапазон имеет все 100 элементов, напечатайте начальное значение, а затем 100:
0 100
145600 100
В противном случае для каждого непрерывного набора 10 в том же диапазоне, начиная с 0 (0-9, 10-19, 15430-15439 и т.д.), напечатайте головку этого диапазона, а затем 10:
30 10
70 10
145620 10
145650 10
Пример вывода из крошечного набора тестов выглядит следующим образом:
0 10
19000 100
20320 10
54540 100
В моем основном тестовом файле 56,653,371 ints, из которых 290,197 наборов из десяти и четырех наборов из 100. Тест-машина оснащена процессором AMD 1090T и 8 ГБ ОЗУ и работает с GHC 7.8.3 на 64-разрядном Linux, Единственными используемыми флагами компилятора являются "-O2 -fflvm".
Есть одна важная вещь, которую нужно отметить: я намеренно избегаю использования счетчиков, которые часто используются в программировании. Например, имея счетчики, которые отслеживают 10 и 100: "если счет один == 100, то...". Я бы хотел избежать отслеживания состояния этих счетчиков и использовать только доступные функции /HOF.
Вот моя лучшая попытка. Завершает задачу за 10,1 секунды (в настоящее время на 5,8 секунды). Чтобы представить это в перспективе, версия C из потока, который я упомянул, заканчивается через 9.4 секунды. Там еще одна версия Haskell, которую я не писал, использует счетчики, которые завершают ее на 8.1 секунды ( в настоящее время на 4.7). Это мое вдохновение (спасибо Xyne за это и преподавание, где заявления о случаях приходят в их собственные).
** РЕДАКТИРОВАТЬ **
Я забыл упомянуть, что он делает. Он разбивает входные данные с использованием межсекторного деления на потенциальные диапазоны в десять и помещает их в список списков (отредактированный для уточнения расщепления luqui). Итак:
1 4 7 9 -> [1,4,7,9]
1 2 3 8 -> [1,2,3,8]
0 1 2 3 4 5 6 7 8 9 -> [0,1,2,3,4,5,6,7,8,9]
7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 27 -> [7,8,9] [10,11,12,13,14,15,16,17,18,19] [20,25,27]
filterLengthBy затем удаляет все, что не является длиной 10, потому что оно нам не нужно. Полученный список разбивается на списки списков, основанные на целочисленном делении головы. Итак:
[[0,1,2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17,18,19],[100,101,102,103,104,105,106,107,108,109]]
становится:
[[[0,1,2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17,18,19]],[[100,101,102,103,104,105,106,107,108,109]]]
Если второй уровень длины списка равен 10, то соответствует набор из 100 и выводится на набор решений. В противном случае этот список имеет списки из 10 и должен быть индивидуально добавлен к набору решений.
Старая версия кода
import qualified Data.ByteString.Lazy.Char8 as DB
import qualified Data.Function as DF
import qualified Data.List as DL
import Control.Applicative
groupByEqOn :: Eq b => (a -> b) -> [a] -> [[a]]
groupByEqOn fn = DL.groupBy ((==) `DF.on` fn)
filterLengthBy :: (Int -> Bool) -> [[a]] -> [[a]]
filterLengthBy fn = filter (flb fn)
where flb fn xs = fn $ length xs
tensAndHundreds :: [[[Int]]] -> [(Int, Int)]
tensAndHundreds [] = []
tensAndHundreds (x:xs)
| length x /= 10 = tens x ++ tensAndHundreds xs
| otherwise = (head $ head x, 100) : tensAndHundreds xs
tens :: [[Int]] -> [(Int, Int)]
tens = map (\x -> (head x, 10))
dbEmpty :: DB.ByteString
dbEmpty = DB.empty
dbIntVals :: [DB.ByteString] -> [Int]
dbIntVals [] = []
dbIntVals (x:xs) =
case (DB.readInt x) of
(Just (x', dbEmpty)) -> x' : dbIntVals xs
_ -> error "*** Error: Non-integer input ***"
generateResults :: [Int] -> [(Int, Int)]
generateResults xs = tensAndHundreds
$ groupByEqOn ((`quot` 100) . head)
$ filterLengthBy (== 10)
$ groupByEqOn (`quot` 10) xs
displayResults :: [(Int, Int)] -> IO ()
displayResults = mapM_ (\(a, b) -> putStrLn (show a ++ " " ++ show b))
main :: IO ()
main = dbIntVals <$> DB.lines <$> DB.getContents >>=
displayResults . generateResults
Единственные две вещи, которые удивляют меня от профилировщика, - это в первую очередь то, насколько быстро выполняется filterLengthBy. Главным удовольствием для всех людей, участвующих в получении фильтра, было так быстро. Это действительно замечательная вещь, учитывая, сколько данных я выбрал. В этом отношении замечательно, что то, что я написал, так же быстро, как и есть. Другой сюрприз - это то, насколько медленны dbIntVals. Я действительно выполнял правильную проверку ошибок, и это делает вещи немного медленнее, но я все еще удивляюсь. Кроме этого, он, похоже, читается точно так же, как мой код.
Ответы
Ответ 1
Я в значительной степени делаю эту тему. Я пришел сюда, чтобы узнать, что может предложить сообщество SO Haskell, и я получил полезные ответы. За это я благодарен.
Последняя версия кода, который я опубликовал, показывает, что, учитывая хороший код, GHC может создавать быстрые, точные программы, используя только функциональные идиомы. Это может показаться очевидным, но это первая программа Haskell, которую я когда-либо писал с нуля (с очевидной копией и вставкой groupBy).
Что я узнал?
Из dfeuer мне напомнили о том, чтобы быть осторожным с временами, когда полагаться только на встроенную функцию, такую как карта, возможно, не самый лучший подход. Иногда полезно комбинировать логику. В этом случае я получил очень значительное увеличение производительности.
Из приложения я узнал об эффективном выходе. Увеличение производительности было потрясающим.
Если какой-нибудь разработчик Haskell/GHC читает это:
На мой взгляд, groupBy здесь должен быть включен в стандартную библиотеку и не отброшен в Hackage. Зачем? Он работает быстро, сохраняя точность. Для той же операции над миллионами элементов и с получением одинаковых результатов было увеличение производительности на 8,2%. Я понимаю, что он не делает то же самое; Я все еще думаю, что стоит взглянуть.
Действительно ли это действительно имеет смысл? Я видел увеличение производительности на 10% по сравнению с тем же набором данных, что и выше, с точностью 100%. Я понимаю, что "rem" и "mod" делают разные вещи и что они имеют тенденцию крутиться в разных "направлениях", но первый из них выполняет это по огромным полям. Вероятно, я не понимаю этого, но 10% довольно сложно игнорировать.
