Haskell :리스트, 배열, 벡터, 시퀀스

Haskell :리스트, 배열, 벡터, 시퀀스

---

Haskell을 배우고 있으며 Haskell 목록과 (언어 삽입) 배열의 성능 차이에 관한 기사를 읽습니다.

학습자이므로 분명히 성능 차이에 대해 생각하지 않고 목록을 사용합니다. 저는 최근 조사를 시작하여 Haskell에서 사용할 수있는 수많은 데이터 구조 라이브러리를 발견했습니다.

데이터 구조에 대한 컴퓨터 과학 이론에 깊이 들어 가지 않고 목록, 배열, 벡터, 시퀀스의 차이점을 설명해 주시겠습니까?

또한 하나의 데이터 구조를 다른 데이터 구조 대신 사용하는 일반적인 패턴이 있습니까?

누락되어 유용 할 수있는 다른 형태의 데이터 구조가 있습니까?

---

락 목록

하스켈에서 순차적 데이터에 대한 가장 친숙한 데이터 구조는

 data [a] = a:[a] | []

목록은 ϴ (1) 단점과 패턴 일치를 제공합니다. 그 서막을 문제에 대한 표준 라이브러리, 그리고 유용한 목록 기능의 전체입니다해야 쓰레기 코드 ( foldr, map, filter). 목록은 지속적 이며, 순전히 기능적이며 매우 좋습니다. 하스켈 목록은 실제로 "목록"이 아닙니다. 왜냐하면 그것들은 서로 일치하기 때문에 (다른 언어들은이 스트림이라고 부릅니다)

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

훌륭하게 작동합니다. 무한한 데이터 구조

Haskell의 목록은 게으름 때문에 명령형 언어의 반복자와 매우 유사한 인터페이스를 제공합니다. 따라서 널리 사용되는 것이 좋습니다.

반면에

목록의 첫 번째 문제는 색인을 생성하는 (!!)데 ϴ (k) 시간이 걸리므로 성가신 것입니다. 또한 더하기는 느릴 수 ++있지만 Haskell의 게으른 평가 모델은 전혀 발생하지 않으면 완전히 상각되는 것으로 간주 될 수 있음을 의미합니다.

목록의 두 번째 문제는 데이터 지역성이 좋지 않다는 것입니다. 실제 프로세서는 메모리의 객체가 나란히 배치되지 않을 때 높은 상수를 발생시킵니다. 따라서 C ++ std::vector에서는 내가 알고있는 순수한 링크 된 목록 데이터 구조보다 "snoc"(끝에 객체를 넣는) 속도가 빠르지 만 Haskell의 목록보다 덜 친근한 데이터 구조는 아닙니다.

목록의 세 번째 문제는 공간 효율성이 떨어진다는 것입니다. 추가 포인터 묶음으로 인해 스토리지가 계속 증가합니다.

시퀀스가 작동 함

Data.Sequence내부적으로 손가락 나무를 기반으로합니다 (알고 싶지 않습니다).

1. 순전히 기능적입니다. Data.Sequence완전히 지속되는 데이터 구조입니다.
2. 나무의 시작과 끝에 빠르게 접근 할 수 있습니다. 첫 번째 또는 마지막 요소를 가져 오거나 나무를 추가하려면 ϴ (1) (오목). 목록이 가장 빠른 것에서, Data.Sequence최대는 일정하게 느려집니다.
3. ϴ (log n) 시퀀스 중간에 액세스합니다. 여기에는 새로운 시퀀스를 만들기 위해 값을 삽입하는 것이 포함됩니다
4. 고품질 API

반면 Data.Sequence에, 데이터 지역성 문제에 대해서는 많은 일을 하지 않으며 유한 수집에 대해서만 작동합니다 (목록보다 게으르지 않음)

배열은 희미한 마음을위한 것이 아닙니다

배열은 CS에서 가장 중요한 데이터 구조 중 하나이지만 게으른 순수 기능 세계에는 적합하지 않습니다. 배열은 컬렉션 중간에 ϴ (1) 액세스를 제공하고 매우 우수한 데이터 위치 / 일정한 요소를 제공합니다. 그러나 하스켈에 잘 맞지 않기 때문에 사용하기가 쉽지 않습니다. 현재 표준 라이브러리에는 실제로 다양한 배열 유형이 있습니다. 여기에는 완전 지속 형 배열, IO 모나드 용 가변 배열, ST 모나드 용 가변 배열 및 위의 박스가없는 버전이 포함됩니다. 더 많은 haskell 위키를 확인하십시오

벡터는 "더 나은"배열입니다

이 Data.Vector패키지는 높은 수준의 깔끔한 API로 모든 어레이 우수성을 제공합니다. 실제로 수행중인 작업을 알지 못하면 성능과 같은 배열이 필요한 경우이를 사용해야합니다. 물론, 일부 경고는 여전히 적용됩니다. 데이터 구조와 같은 가변 배열은 순수한 게으른 언어에서는 잘 작동하지 않습니다. 여전히, 때로는 O (1) 성능 Data.Vector을 원하고 사용 가능한 패키지로 제공합니다.

다른 옵션이 있습니다

마지막에 효율적으로 삽입 할 수있는 목록 만 원하는 경우 차이점 목록을 사용할 수 있습니다 . 성능을 강화하는 목록의 가장 좋은 예 [Char]는 전주곡이로 별칭이 지정된 경향이 있습니다 String. Char목록은 확실하지만 C 문자열보다 20 배 느리게 실행되는 경향이 있으므로 자유롭게 사용 Data.Text하십시오 Data.ByteString. 나는 지금 생각하지 않는 다른 시퀀스 지향 라이브러리가 있다고 확신합니다.

결론

Haskell 목록에서 순차 수집이 필요한 시간의 90 % 이상이 올바른 데이터 구조입니다. 리스트는 반복자와 같습니다.리스트를 소비하는 toList함수는 함께 제공 되는 함수를 사용하여 이러한 다른 데이터 구조와 쉽게 사용할 수 있습니다 . 더 나은 세상에서 prelude는 어떤 컨테이너 유형을 사용하는지에 대해 완전히 매개 변수가되지만 현재 []표준 라이브러리를 어지럽 힙니다. 따라서 거의 모든 곳에서 목록을 사용하는 것이 좋습니다.
대부분의 목록 함수를 완전히 파라 메트릭 버전으로 사용할 수 있으며 사용하기가 어렵습니다.

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

실제로, Data.Traversable"list like"에 대해 어느 정도 보편적 인 API를 정의합니다.

그럼에도 불구하고, 당신은 훌륭하고 완전 파라 메트릭 코드 만 작성할 수 있지만, 우리 대부분은 여기저기서 목록을 사용하지 않습니다. 당신이 배우고 있다면, 당신도 그렇게 할 것을 강력히 권합니다.

---

편집 : 의견을 기반으로 Data.Vectorvs를 언제 사용 해야하는지 결코 알지 못합니다 Data.Sequence. 배열 및 벡터는 매우 빠른 인덱싱 및 슬라이싱 작업을 제공하지만 근본적으로 일시적인 (비 제한적인) 데이터 구조입니다. 순수 기능 데이터 구조 등 Data.Sequence과 []효율적으로 생산할 수 있도록 새로운 당신이 이전 값을 수정 한 것처럼 이전 값에서 값을.

  newList oldList = 7 : drop 5 oldList

이전 목록을 수정하지 않으며 복사 할 필요가 없습니다. 따라서 oldList엄청나게 길더라도이 "수정"은 매우 빠릅니다. 비슷하게

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

newValue3000 요소 대신에 for를 사용하여 새로운 시퀀스를 생성합니다 . 다시 말하지만 이전 시퀀스를 파괴하지 않고 새로운 시퀀스를 만듭니다. 그러나 O (log (min (k, kn))를 취하면 매우 효율적으로 수행됩니다. 여기서 n은 시퀀스의 길이이고 k는 수정하는 인덱스입니다.

Vectors및 로이 작업을 쉽게 수행 할 수 없습니다 Arrays. 그것들은 수정 될 수 있지만 그것은 반드시 필요한 수정이므로, 일반적인 Haskell 코드에서는 수행 될 수 없습니다. 의 수단 작업 그건 Vector패키지는 같은 메이크업 수정하는 것이 snoc및 cons포획 때문에 전체 벡터 복사해야 할 O(n)시간. 이에 대한 유일한 예외 Vector.Mutable는 ST모나드 (또는 IO) 내 에서 가변 버전 ( )을 사용하고 명령형 언어에서와 마찬가지로 모든 수정을 수행 할 수 있다는 것입니다. 완료되면 벡터를 "고정"하여 순수한 코드와 함께 사용할 불변 구조로 변환합니다.

내 느낌은 Data.Sequence목록이 적절하지 않으면 기본값을 사용해야한다는 것 입니다. 사용 Data.Vector패턴에 많은 수정이 필요하지 않거나 ST / IO 모나드 내에서 매우 높은 성능이 필요한 경우에만 사용하십시오 .

이 ST모나드 에 대한이 모든 이야기가 혼란스러워 진다면 순수한 빠르고 아름답게 고집해야 할 더 많은 이유 Data.Sequence입니다.

참고 URL : https://stackoverflow.com/questions/9611904/haskell-lists-arrays-vectors-sequences