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


я осматривал нетривиальную ленивую оценку stackoverflow, которая привела меня к презентации Keegan McAllister:зачем учить Хаскелл. На слайде 8 он показывает минимальную функцию, определенную как:

minimum = head . sort

и утверждает, что его сложность равна O(n). Я не понимаю, почему сложность называется линейной, если сортировка по замене равна O(nlog n). Сортировка, указанная в сообщении, не может быть линейной, поскольку она ничего не предполагает о данных, как это было бы требуется линейными методами сортировки, такими как подсчет сортировки.

ленивая оценка играет здесь загадочную роль? Если это так, чему есть объяснение позади него?

7 69

7 ответов:

на minimum = head . sort на sort не будет сделано полностью, потому что это не будет сделано вперед. Элемент sort будет сделано только столько, сколько необходимо для производства самого первого элемента, требуемого head.

например, mergesort, сначала n номера списка будут сравниваться попарно, затем победители будут объединены в пары и сравнены (n/2 номера), то новые победители (n/4) и т. д. В общем,O(n) сравнения для получения минимального элемент.

mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
  where
    pairs (x:y:t) = merge x y : pairs t
    pairs xs      = xs
    merge (x:xs) (y:ys) | less y x  = y : merge (x:xs) ys
                        | otherwise = x : merge  xs (y:ys)
    merge  xs     []                = xs
    merge  []     ys                = ys

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

mgsort xs = go $ map ((,) 0) xs  where
  go [] = []
  go xs = head $ until (null.tail) pairs [[x] | x <- xs]   where
    ....
    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (a+c+1,d) : merge ((a+1,b):xs) ys    -- cumulative
            | otherwise = (a+c+1,b) : merge  xs ((c+1,d):ys)   --   cost
    ....

g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]]   -- a little scrambler

запуск его для нескольких длин списка мы видим, что действительно ~ n:

*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]

чтобы увидеть, является ли сам код сортировки составляет ~ n log n, мы изменяем его так, что каждый произведенный номер несет только собственную стоимость, и общая стоимость затем найдено суммированием по всему отсортированному списку:

    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (c+1,d) : merge ((a+1,b):xs) ys      -- individual
            | otherwise = (a+1,b) : merge  xs ((c+1,d):ys)     --   cost

вот результаты для списков различной длины,

*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]

*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]

показывает эмпирические порядки роста для увеличения длины списка, n, которые быстро уменьшаются, как это обычно проявляется ~ n log n вычислений. Смотрите также этот блог. Вот быстрая корреляция проверьте:

*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in 
                                    map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]

edit: ленивая оценка может метафорически рассматриваться как своего рода "производителей/потребителей" фразеологизм1, с независимым memoizing хранением как посредник. Любое производительное определение, которое мы пишем, определяет производителя, который будет производить свою продукцию, шаг за шагом, как и когда это требуется его потребителем(ами) - но не раньше. Все, что производится, запоминается, так что если другой потребитель потребляет ту же продукцию с разной скоростью, он получает доступ к тому же хранилище, заполненное ранее.

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

1 Читайте также: простые генераторы V ленивая оценка Олег Киселев, Саймон Пейтон-Джонс и Амр Сабри.

предположим 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()

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

growth rates

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

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

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