Ленивая оценка и временная сложность

предположим minimum' :: (Ord a) => [a] -> (a, [a]) - это функция, которая возвращает наименьший элемент в списке вместе со списком с удаленным элементом. Ясно, что это можно сделать за O(n) время. Если вы затем определите sort как

sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs')
    where
      (xmin, xs') = minimum' xs

тогда ленивая оценка означает, что в (head . sort) xs вычисляется только первый элемент. Этот элемент, как вы видите, просто (первый элемент) пары minimum' xs, который вычисляется в O (n) времени.

конечно, как точки delnan выход, сложность зависит о реализации sort.

вы получили большое количество ответов, которые будут касаться специфики head . sort. Я просто добавлю еще пару общих положений.

С нетерпеливой оценкой вычислительные сложности различных алгоритмов составляют простым способом. Например, наименьшая верхняя граница (LUB) для f . g должна быть сумма смазок для f и g. Таким образом, вы можете лечить f и g как черные ящики и причина исключительно с точки зрения их смазок.

С ленивая оценка, однако,f . g может иметь луб лучше, чем сумма f и gС LUBs. Вы не можете использовать рассуждения черного ящика для доказательства LUB; вы должны проанализировать реализации и их взаимодействие.

таким образом, часто цитируемый факт, что сложность ленивой оценки гораздо труднее рассуждать, чем для нетерпеливой оценки. Просто подумайте о следующем. Предположим, вы пытаетесь улучшить асимптотическую производительность фрагмента кода, форма которого f . g. В нетерпеливый язык, есть очевидная стратегия, которой вы можете следовать, чтобы сделать это: выберите более сложный из f и g, и улучшить это в первую очередь. Если вы преуспеете в этом, вы преуспеете в f . g задач.

в ленивом языке, с другой стороны, вы можете иметь таких ситуациях:

• вы улучшаете более сложный из f и g, а f . g не улучшаться (или даже хуже).
• вы можете улучшить f . g в пути это не помогает (или даже ухудшит)f или g.

объяснение зависит от реализации sort, и для некоторых реализаций это не будет верно. Например, при сортировке вставки, которая вставляется в конце списка, ленивая оценка не помогает. Итак, давайте выберем реализацию для просмотра, и для простоты, давайте использовать selection sort:

sort [] = []
sort (x:xs) = m : sort (delete m (x:xs)) 
  where m = foldl (\x y -> if x < y then x else y) x xs

функция явно использует время O (n^2) для сортировки списка, но так как head нужен только первый элемент списка sort (delete x xs) никогда оценили!

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

один интересный способ увидеть это на практике-проследить функцию сравнения.

import Debug.Trace
import Data.List

myCmp x y = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare x y

xs = [5,8,1,3,0,54,2,5,2,98,7]

main = do
    print "Sorting entire list"
    print $ sortBy myCmp xs

    print "Head of sorted list"
    print $ head $ sortBy myCmp xs

во-первых, обратите внимание на то, как вывод всего списка чередуется с сообщениями трассировки. Во-вторых, обратите внимание, как сообщения трассировки похожи при простом вычислении головы.

Я только что прогнал это через Ghci, и это не совсем O(n): требуется 15 сравнений, чтобы найти первый элемент, а не 10, которые должны потребоваться. Но его все еще меньше, чем O(n log n).

Edit: как Витус указывает ниже, принимая 15 сравнений вместо 10 не то же самое, что сказать его не O(n). Я просто имел в виду, что это занимает больше, чем теоретический минимум.

вдохновленный ответом Пола Джонсона, я построил график темпов роста для двух функций. Сначала я изменил его код, чтобы напечатать один символ для сравнения:

import System.Random
import Debug.Trace
import Data.List
import System.Environment

rs n = do
    gen <- newStdGen
    let ns = randoms gen :: [Int]
    return $ take n ns

cmp1 x y = trace "*" $ compare x y
cmp2 x y = trace "#" $ compare x y

main = do
    n <- fmap (read . (!!0)) getArgs
    xs <- rs n
    print "Sorting entire list"
    print $ sortBy cmp1 xs

    print "Head of sorted list"
    print $ head $ sortBy cmp2 xs

считать * и # символы мы можем попробовать сравнение подсчетов в равномерно расположенных точках (извините мой python):

import matplotlib.pyplot as plt
import numpy as np
import envoy

res = []
x = range(10,500000,10000)
for i in x:
    r = envoy.run('./sortCount %i' % i)
    res.append((r.std_err.count('*'), r.std_err.count('#')))

plt.plot(x, map(lambda x:x[0], res), label="sort")
plt.plot(x, map(lambda x:x[1], res), label="minimum")
plt.plot(x, x*np.log2(x), label="n*log(n)")
plt.plot(x, x, label="n")
plt.legend()
plt.show()

запуск скрипта даст нам следующий график:

наклон нижней линии есть..

>>> import numpy as np
>>> np.polyfit(x, map(lambda x:x[1], res), deg=1)
array([  1.41324057, -17.7512292 ])

..1.41324057 (предполагая, что это линейная функция)