Как избежать ненужных вычислений?

Question

Мне нужно вернуть false, если тест завершился неудачно для более чем 3 элементов в списке. Есть ли что-нибудь, что я могу сделать для оптимизации?

isItemOk :: Integer -> Boolean 
isItemOk = (some costly opernation) 

Это функция Я пытаюсь оптимизировать,

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ([ 1 | x <- [1.1000], isItemOk x ]) 

Моя попытка оптимизации, предполагая, что взять, если он находит 4 элемента не будет искать больше.

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum (take 4 [ 1 | x <- [1.1000], isItemOk x ]) 

Спасибо.

Answer 1

Вы можете просто использовать filter с чем-то, что проверяет наличие неудовлетворительных элементов, то take 4 и посмотреть, сколько элементов у вас есть с length.

Lazy оценка означает, что он не будет проверять что-либо после обнаружения этих четырех, так что вы закончили. Конечно, если тест терпит неудачу для трех или менее элементов, он проверяет весь список, но вы ничего не можете с этим поделать.

Важная вещь, чтобы избегать - это что-то вроде «подсчет элементов, которые не проходят тест», или «фильтр, а затем получить длину результата» или что-то в этом роде. Не используя take или что-то подобное, сделайте это, чтобы проверить весь список. Это более общая версия «использование null или сопоставление шаблонов для проверки на наличие пустых списков», которые часто даются начинающим. Но похоже, что вы уже избегаете этой ошибки!

Answer 2

Для небольшого числа, такого как 3, вы можете просто использовать сопоставление с образцом.

case filter isItemOk xs of 
    x1 : x2 : x3 : _ -> ... 
    _    -> ... 

Answer 3

Позвольте мне сначала переписать вашу функцию немного, так как

isListOk :: Bool 
isListOk = length (filter isItemOk [1 .. 1000]) <= 3 

, возможно, более идиоматических, чем версии. (Обратите внимание, что я также изменил тип подписи, как у вас было неправильно. Кроме того, вы должны быть написаны 1 .. 1000, а не 1.1000.)

Ленивые вычисления ваш лучший друг здесь, как правило убедитесь, что никаких ненужных вычислений не будет выполнено.

К сожалению, использование вами length (или отображение каждого элемента из списка в 1, а затем суммирование итогового списка, как вы это делаете) находится здесь. То есть length является строгим в списке позвоночника: он может производить только длину списка, если он оценивает его до самого конца, что в данном случае означает, что ваша программа должна будет выполнить вашу проверку тысячу раз ,

Решение состоит в объединении вычисления длины (т.е., Обход позвоночника списка) и тест ли вычисленная длина не превышает заданный порог в одну функцию, которая на самом деле ленивым в позвоночнике своего списка аргументов:

isNotLongerThan :: [a] -> Integer -> Bool 
isNotLongerThan []  n = n >= 0 
isNotLongerThan (_ : xs) n = n >= 1 && isNotLongerThan xs (n - 1) 

, а затем записать

isListOk :: Bool 
isListOk = filter isItemOk [1 .. 1000] `isNotLongerThan` 3 

Для многоразового решения, вы можете, конечно, абстрактный над как предиката и порога:

forNoMoreThan :: (a -> Bool) -> Integer -> [a] -> Bool 
forNoMoreThan p n = (`isNotLongerThan` n) . filter p 

isListOk :: Bool 
isListOk = (isItemOk `forNoMoreThan` 3) [1 .. 1000] 

Наконец, как Хаммар указывает, если молотить старый достаточно мал и исправлен, вы можете просто использовать сопоставление образцов, чтобы определить, достаточно ли список.

Answer 4

Я хотел бы воспользоваться этой возможностью, чтобы обмануть lazy natural numbers. Используя эту библиотеку и genericLength, мы можем просто написать

import Data.Number.Natural 
import Data.List 
isListOk = (3 :: Natural) >= genericLength (filter isItemOk [1..1000]) 

и он не будет делать не больше работы, чем она должна: эта функция будет найти более четырех в порядке вещей, прежде чем вернуться. Например:

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined)) 
False