누구든지 명령형이 아닌 순전히 기능적으로 프로그래밍 할 때 발생할 수있는 최악의 점근 적 둔화가 무엇인지 알고 있습니까 (예 : 부작용 허용)?
itowlson에 의한 주석의 설명 : 가장 잘 알려진 비파괴 알고리즘이 가장 잘 알려진 파괴 알고리즘보다 무질서하게 악화 되는 문제가 있습니까?
답변
Pippenger [1996] 에 따르면 , 순전히 기능적이며 (평가 게으름이 아닌 엄격한 평가 의미를 갖는) Lisp 시스템을 데이터를 돌연변이시킬 수있는 시스템과 비교할 때 O ( n ) 에서 실행되는 불순한 Lisp에 대해 작성된 알고리즘을 변환 할 수 있습니다 O에서 실행 (즉 순수한 리스프의 알고리즘 N 로그 N 시간 ()에 기초하여 작업 벤 아므람과 Galil [1,992] 전용 포인터를 사용하여 랜덤 액세스 메모리에 대한 시뮬레이션). Pippenger는 또한 여러분이 할 수있는 최선의 알고리즘이 있음을 확립합니다. 순수한 시스템에서는 Ω ( n log n ) 인 불순 시스템 에는 O ( n )의 문제가 있습니다 .
이 논문에 대해 몇 가지주의 사항이 있습니다. 가장 중요한 것은 Haskell과 같은 게으른 기능적 언어를 다루지 않는다는 것입니다. Bird, Jones and De Moor [1997] 는 Pippenger가 구성한 문제가 O ( n ) 시간 에 게으른 기능 언어로 해결 될 수 있지만, 게으른 기능적 언어는 돌연변이가있는 언어와 동일한 점근 적 실행 시간의 모든 문제를 해결할 수 없습니다.
Pippenger가 구성한 문제는 Ω ( n log n )이이 결과를 달성하기 위해 구체적으로 구성되며 실제 실제 문제를 나타내는 것은 아닙니다. 약간 예상치 못한 문제에 대한 몇 가지 제한 사항이 있지만 증명이 작동하는 데 필요합니다. 특히, 문제는 미래의 입력에 접근 할 수없는 결과가 온라인으로 계산되고 입력이 고정 된 크기 세트가 아닌 무한한 가능한 원자 세트로부터의 원자 시퀀스로 구성되어야한다는 것을 요구한다. 그리고 논문은 선형 실행 시간의 불순한 알고리즘에 대해서만 결과를 설정합니다 (하한). 더 긴 실행 시간이 필요한 문제의 경우 추가 O (log n) 선형 문제에서 나타나는 계수는 실행 시간이 더 큰 알고리즘에 필요한 추가 작업 프로세스에서 “흡수”될 수 있습니다. 이러한 설명과 공개 된 질문은 Ben-Amram [1996]에 의해 간략히 탐구됩니다 .
실제로, 많은 알고리즘은 가변 데이터 구조를 가진 언어와 동일한 효율로 순수한 기능 언어로 구현 될 수 있습니다. 순전히 기능적인 데이터 구조를 효율적으로 구현하기 위해 사용하는 기술에 대한 좋은 참고 자료는 Chris Okasaki의 “순수한 기능적 데이터 구조”[Okasaki 1998] (그 논문의 확장 된 버전 [Okasaki 1996] )를 참조하십시오.
순전히 기능적인 데이터 구조에 알고리즘을 구현해야하는 사람은 오카 사키를 읽어야합니다. 균형 잡힌 이진 트리를 사용하여 가변 메모리를 시뮬레이트하여 작업 당 항상 O (log n ) 속도 저하를 겪을 수 있지만 대부분의 경우 그보다 훨씬 더 잘 수행 할 수 있습니다. 할부 상환을하는 사람은 점진적으로 일합니다. 순전히 기능적인 데이터 구조는 작업 및 분석이 약간 어려울 수 있지만 컴파일러 최적화, 병렬 및 분산 컴퓨팅 및 버전 관리, 실행 취소 및 롤백과 같은 기능 구현에 도움이되는 참조 투명성과 같은 많은 이점을 제공합니다.
또한이 모든 것은 점근 적 실행 시간 만 설명합니다. 순전히 기능적인 데이터 구조를 구현하는 많은 기술은 작동에 필요한 추가 부기 및 해당 언어의 구현 세부 사항으로 인해 일정한 양의 일정한 요소 속도 저하를 제공합니다. 순전히 기능적인 데이터 구조의 이점은 이러한 일정한 요소 속도 저하를 능가 할 수 있으므로 일반적으로 문제의 문제에 따라 균형을 조정해야합니다.
참고 문헌
- Ben-Amram, Amir and Galil, Zvi 1992. “포인터 대 주소” ACM 저널, 39 (3), 617-648, 1992 년 7 월
- 1996-Amir Ben-Amram. “Pipenger의 순수와 불순 리스프 비교에 관한 메모” 덴마크 코펜하겐 대학교 DIKU 미공개 원고
- Bird, Richard, Jones, Geraint, De Moor, Oege 1997. “더 많은 서둘러, 더 적은 속도 : 게으른 대 열렬한 평가” Journal of Functional Programming 7, 5 pp. 541–547, 1997 년 9 월
- 오카 사키, 크리스 1996. “순수한 데이터 구조” 카네기 멜론 대학교 박사 학위 논문
- 오카 사키, Chris 1998. “순수한 기능적 데이터 구조” Cambridge University Press, Cambridge, 영국
- Pippenger, Nicholas 1996. 프로그래밍 언어의 원칙에 대한 “순수한 대 리스프” ACM 심포지엄, 페이지 104–109, 1996 년 1 월
답변
게으름에도 불구하고 무의식적으로 효율적인 순수 기능 솔루션 (순수 람다 미적분에서 구현 가능한 솔루션)이 알려지지 않은 몇 가지 알고리즘과 데이터 구조가 있습니다.
- 앞서 언급 한 노조 찾기
- 해시 테이블
- 배열
- 일부 그래프 알고리즘
- …
그러나, 우리는 “불완전한”언어에서 메모리에 대한 접근은 O (1) 인 반면 이론 상으로는 무의식적으로 (즉, 무한한 문제 크기에 대해) 불가능하고 거대한 데이터 세트 내의 메모리에 대한 접근은 항상 O (log n)라고 가정합니다. 기능 언어로 에뮬레이트 할 수 있습니다.
또한 실제로 모든 현대 기능 언어는 변경 가능한 데이터를 제공하며 Haskell은 순도 (ST 모나드)를 희생하지 않고 제공합니다.
답변
이 기사 는 노조 찾기 알고리즘 의 알려진 기능 구현은 모두 게시 한 것보다 더 복잡한 점증 적 복잡성을 가지며, 기능적으로 순수한 인터페이스를 가지고 있지만 내부적으로 변경 가능한 데이터를 사용 한다고 주장합니다 .
다른 답변에 차이가 없다고 주장한다는 사실과, 예를 들어 순수하게 기능적인 코드의 유일한 “단점”은 병렬화 될 수 있다는 것입니다. .
편집하다:
아래의 의견은 순수한 기능적 프로그래밍의 장단점에 대한 편견은“기능적 프로그래밍 커뮤니티”에서 나오지 않을 수 있다고 지적합니다. 좋은 지적. 아마도 내가 옹호하는 사람들은 단지“완화”라는 의견을 인용하는 것일뿐입니다.
예를 들어,이 블로그 게시물 은 함수형 프로그래밍 커뮤니티를 대표한다고 할 수있는 사람이 작성한 것으로 생각 되며 “게으른 평가를위한 포인트”목록이므로 다음과 같은 단점을 언급 할 수 있습니다. 게으르고 순전히 기능적인 프로그래밍이있을 수 있습니다. 좋은 장소는 다음과 같은 장소에 있었을 것입니다 (기술적으로는 맞지만 재미 있지 않은 지점으로 편향 됨).
엄격한 함수가 엄격한 언어에서 O (f (n)) 복잡도를 갖는 경우 게으른 언어에서도 복잡도 O (f (n))가 있습니다. 왜 걱정? 🙂
답변
메모리 사용에 대한 상한이 고정되어 있으면 차이가 없어야합니다.
프루프 스케치 : 메모리 사용에 대한 고정 된 상한이 주어지면 실제 머신에서 실제로 실행하는 것과 동일한 점근 적 복잡도로 명령형 명령 세트를 실행하는 가상 머신을 작성할 수 있어야합니다. 변경 가능한 메모리를 영구 데이터 구조로 관리하여 O (log (n))에 읽기 및 쓰기를 제공 할 수 있지만 메모리 사용에 대한 상한이 고정되어 있으면 고정 된 양의 메모리를 가질 수 있으므로 O (1)로 붕괴합니다. 따라서 기능 구현은 VM의 기능 구현에서 실행되는 명령 버전 일 수 있으므로 둘 다 동일한 점근 적 복잡성을 가져야합니다.
