지연 평가 및 시간 복잡성

지연 평가 및 시간 복잡성

---

Stackoverflow Non-Trivial Lazy Evaluation을 둘러보고 Keegan McAllister의 프레젠테이션 : Why learn Haskell . 슬라이드 8에서 그는 다음과 같이 정의 된 최소 함수를 보여줍니다.

minimum = head . sort

그리고 그것의 복잡성이 O (n)이라고 명시합니다. 대체 정렬이 O (nlog n) 인 경우 복잡성이 선형이라고 말하는 이유를 이해할 수 없습니다. 게시물에 언급 된 정렬은 데이터에 대해 아무 것도 가정하지 않기 때문에 선형 일 수 없습니다. 정렬 계산과 같은 선형 정렬 방법에 필요하기 때문입니다.

여기에서 게으른 평가가 신비한 역할을 하는가? 그렇다면 그 뒤에있는 설명은 무엇입니까?

---

에서는 minimum = head . sort의는 sort그것을 할 수 없기 때문에, 완벽하게 수행되지 않습니다 선행 . 는 sort에서 요구하는 첫 번째 요소를 생성하는 데 필요한만큼만 수행됩니다 head.

예를 들어 병합 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]

---

편집 : 게으른 평가는 은유 적으로 일종의 생산자 / 소비자 관용구 ¹ 로 볼 수 있으며, 중개자로서 독립적 인 메모 저장을 사용합니다. 우리가 작성하는 모든 생산적인 정의는 소비자가 요구하는대로 비트 단위로 출력을 생성 할 생산자를 정의하지만 더 빨리는 아닙니다. 생성 된 내용이 모두 메모되므로 다른 소비자가 동일한 출력을 다른 속도로 소비하는 경우 이전에 채워진 동일한 저장소에 액세스합니다.

스토리지를 참조하는 소비자가 더 이상 남아 있지 않으면 가비지 수집됩니다. 때로는 최적화를 통해 컴파일러가 중간 저장소를 완전히 제거하여 중간 사람을 제거 할 수 있습니다.

¹ 참조 : Oleg Kiselyov, Simon Peyton-Jones 및 Amr Sabry의 단순 생성기 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' xsO (n) 시간에 계산되는 쌍의 첫 번째 요소입니다 .

물론 delnan이 지적했듯이 복잡성은 sort.

---

의 세부 사항을 다루는 많은 답변을 얻었습니다 head . sort. 몇 가지 일반적인 문구를 추가하겠습니다.

열렬한 평가를 통해 다양한 알고리즘의 계산 복잡성이 간단한 방식으로 구성됩니다. 예를 들어, 상기 상한 (LUB)을 위해 f . g대한 LUBS의 합이어야 f하고 g. 따라서 당신 은 그들의 LUB 측면에서 독점적으로 블랙 박스로 취급 f하고 g추론 할 수 있습니다 .

그러나 지연 평가를 사용하면 및 의 f . gLUB 합계보다 더 나은 LUB를 가질 수 있습니다 . LUB를 증명하기 위해 블랙 박스 추론을 사용할 수 없습니다. 구현 및 상호 작용을 분석해야합니다.fg

따라서 지연 평가의 복잡성이 열성 평가보다 추론하기가 훨씬 어렵다는 자주 인용되는 사실입니다. 다음을 생각해보십시오. 형식이 인 코드 조각의 점근 적 성능을 향상 시키려고한다고 가정 해 보겠습니다 f . g. 열성적인 언어에서는이를 수행하기 위해 따를 수있는 분명한 전략이 있습니다. 더 복잡한 fand를 선택하고 g먼저 개선하십시오. 그 일에 성공하면 그 일에 성공합니다 f . g.

반면에 게으른 언어에서는 다음과 같은 상황이 발생할 수 있습니다.

• 더 복잡한 f및을 개선 g하지만 f . g개선되지는 않습니다 (또는 더 나빠집니다 ).
• 당신은 향상시킬 수 있습니다 f . g도움 (또는하지 않는 방법으로 나빠 ) f또는 g.

---

설명은의 구현에 따라 다르며 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)보다 작습니다.

편집 : Vitus가 아래에서 지적했듯이 10 대신 15 비교를 취하는 것은 O (n)이 아니라고 말하는 것과 동일하지 않습니다. 나는 단지 이론적 최소값 이상이 필요하다는 것을 의미했습니다.

---

Paul Johnson의 답변에서 영감을 받아 두 함수의 성장률을 플로팅했습니다. 먼저 비교 당 한 문자를 인쇄하도록 그의 코드를 수정했습니다.

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

Running the script would give us the following graph:

The slope of the lower line is..

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

..1.41324057 (assuming it's a linear function)

참고URL : https://stackoverflow.com/questions/12057658/lazy-evaluation-and-time-complexity