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

Ответ 1

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

В частности. mergesort, сначала n номера списка будут сравниваться попарно, тогда победители будут спарены и сравнены (n/2 numbers), затем новые победители (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: ленивая оценка может метафорически рассматриваться как вид idiom производителя/потребителя ¹ с независимым запоминающим устройством хранения в качестве посредника. Любое производительное определение, которое мы пишем, определяет производителя, который будет поэтапно производить свой вывод по мере необходимости его потребителем (ами), но не раньше. Независимо от того, что производится, запоминается, так что, если другой потребитель потребляет одинаковый результат в разном темпе, он обращается к тому же хранилищу, которое было заполнено ранее.

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

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

Ответ 2

Предположим, что 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) времени.

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

Ответ 3

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

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

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

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

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

• Вы улучшаете более сложные f и g, но f . g не улучшается (или даже ухудшается).
• Вы можете улучшить f . g способами, которые не помогают (или даже ухудшаются) f или g.

Ответ 4

Объяснение зависит от реализации 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) никогда не оценивается!

Ответ 5

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

Ответ 6

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

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): для поиска первого элемента требуется не более 10 сравнений, а не 10, которые должны быть требуемыми. Но его еще меньше O (n log n).

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

Ответ 7

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

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

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

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()

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

Наклон нижней линии...

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

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