Я реализовал count функции в Haskell, и мне интересно, будет ли это плохо себя вести на больших списках:Haskell «количество вхождений»
count :: Eq a => a -> [a] -> Int
count x = length . filter (==x)
Я считаю, что функция length работает в линейном времени, это правильно?
Edit: Refactor предложил @Higemaru
Длина работает в линейном времени до размера списка, да.
Как правило, вы были бы обеспокоены тем, что ваш код должен был пройти два прохода по списку: сначала для фильтрации, а затем для подсчета длины результирующего списка. Однако я считаю, что этого не происходит, потому что фильтр не является строгим в структуре списка. Вместо этого функция длины заставляет элементы отфильтрованного списка двигаться, делая фактический счет за один проход.
Я не думаю, что это лень, но поток слияния. Если вы посмотрите на вывод '-ddump-simpl', то на' -O0' это два отдельных вызова, а на '-O2' это один рабочий. –
Хмм, не будет ли это еще один проход даже без * потокового слияния, просто из-за того, что фильтр ленив? Возможно, я просто не понимаю, как это будет оцениваться. –
Да, это единственный проход, даже без слияния. Слияние только помогает избавиться от распределения памяти в этом проходе. – augustss
Это действительно зависит от списка. Для нормального, лениво оцененного списка Int s на моем компьютере я вижу, что эта функция работает примерно через 2 секунды для 10^9 элементов, 0,2 секунды для 10^8 и 0,3 секунды для 10^7, поэтому она, похоже, работает в линейное время. Вы можете проверить это самостоятельно, передав флаги +RTS -s -RTS вашему исполняемому файлу при его запуске из командной строки.
Я также попытался запустить его с большим количеством ядер, но он, похоже, ничего не делает, но немного увеличивает использование памяти.
Добавленный бонус ленивых вычислений состоит в том, что вы делаете только один проход над списком. filter и length превращаются в один цикл компилятором (при включенной оптимизации), поэтому вы сохраняете память и эффективность.
«Это действительно зависит от списка» - пример? Что такое список, который не «нормальный, лениво оцененный»? Даже если вы имеете в виду «ранее оцененный список», тогда это должно иметь линейное время исполнения. (Сокращение графа делает * меньше * работы, чем сокращение аппликативного порядка - проблема, как правило, в утечке пространства.) Что касается работы с большим количеством ядер, Haskell не выполняет автоматическое распараллеливание последовательного однопоточного кода. В любом случае, обход списка занимает линейное время, поэтому можно ожидать (не более) постоянного коэффициента. Наконец, лень все еще выигрывает (вы не форсируете промежуточный список, как на строгом языке) ... – Fixnum
независимо от того, включите ли вы оптимизацию. Извините за звучание критически - ваш пост немного расплывчато.Давайте не будем делать производительность Haskell более темным искусством, чем это должно быть :) С другой стороны, ваш эмпирический подход также весьма необходим ... – Fixnum
@Fixnum Ну, вместо использования встроенного типа списка GHC вы можете использовать векторы (boxed and unboxed), предварительно отсортированные списки и различные другие структуры данных, подобные спискам. Я также знаю, что GHC (а не Haskell, поскольку мы являемся техническими) не может распараллелить все, но я написал алгоритмы, которые по-разному работают с '-threaded' и' + RTS -N -RTS', даже если там не является явным параллелизмом. Наконец, я добавил комментарий о включении оптимизаций, потому что я не был уверен в всех оптимизациях, которые GHC мог бы сделать по сравнению с отключением их. Извините за неопределенность. – bheklilr
Я думаю, что вы можете сделать его немного короче
count :: Eq a => a -> [a] -> Int
count x = length . filter (x==)
(я бы написал (кроткий) комментарий, если я мог)
(длина.). фильтр. (==);) Ха, просто шучу. – Jxek
@ Jepcats Я не могу заставить его работать в ghci при интерактивном вводе его. С правильной подписью типа (и загружаемой из файла на диске) он работает, но не является следующим нечетным? 'Prelude>: t (длина.). фильтр. (==) ' ' (длина.). фильтр. (==) :: Eq a => a -> [a] -> Int' 'Prelude> let count = (length.). фильтр. (==) ' ' Prelude>: t count' 'count ::() -> [()] -> Int' (извините, похоже, не получается форматировать правильно) – Higemaru
Это странно. Я не вижу то же самое в своем GHCI. Я могу ввести следующие команды: 'λ>: t (length.). фильтр. (==) 'который выводит ' (длина.). фильтр. (==) :: Eq a => a -> [a] -> Int', а также 'λ> пусть count = (length.). фильтр. (==) ', за которым следует' λ>: t count', который выводит 'count :: Eq a => a -> [a] -> Int', как и ожидалось. Стоит отметить, что если я положу определение free county в файле .hs, он не скомпилируется без сигнатуры типа. – Jxek
Если вы действительно параноик, вы всегда можете сделать эквивалент один цикл: 'count needle haystack = foldl '(\ acc elem -> if elem == игла, затем acc + 1 else acc) 0 haystack'. – kqr
Вы не можете считать n элементов быстрее, чем O (n), поэтому я не уверен, что вы беспокоитесь. – augustss
@augustss - мое беспокойство было, если я делал двойной проход над списком. –