하스켈. 어레이가리스트보다 빠른 이유는 무엇입니까?

하스켈을 공부하고 있습니다. 다음 질문이 있습니다.하스켈. 어레이가리스트보다 빠른 이유는 무엇입니까?

목록 유형은 하스켈의 기본 유형입니다. Haskell의 배열은 목록을 기반으로합니다. 이것은 인덱스 [Ix a]의리스트이고 함수는 테이블 [(Ix a, Value)]의 테이블리스트에 의해 제공됩니다. 배열이 목록을 사용하는 경우 왜 Array가 목록보다 빠릅니까?

출처

2009-10-15 Anton

더 빠른 작업을 원하십니까? 그게 더 빠름을 어떻게 알 수 있니? –

예를 들어 (array/list)의 끝에 추가하거나 i 요소를 가져옵니다. – Anton

'Data.Array'와'Data.List'는 둘 다 (array/list)의 끝에 추가하기 위해 "모두 복사"를 요구합니다. – ephemient

내가 틀렸을 까봐 두렵다.

하스켈에는 several implementations 개의 배열이 있지만, 이해하는 한 모든 배열은 인접한 메모리 배열 위에 구현됩니다. 이 때문에 O (1) 요소를 읽을 수있는 가능성이 있습니다.

어레이와 목록 간의 유사성은 작동 설정 수준에서만 존재합니다.

출처

2009-10-15 13:20:30

따라서, haskell에서보다 빠른 데이터 구조를 설계하지 마십시오. 좋은 "데이터 구조"가 다른 언어로 작성되었습니다. С \ С ++ 일 수 있습니다. 맞습니까? – Anton

@Anton : 아니요, 핑거 트리와 같은 멋진 데이터 구조는 순수한 하스켈에서 구현 될 수 있습니다. – ephemient

추천 도서 : http://books.google.com/books?id=SxPzSTcTalAC&dq=purely+functional+data+structures&printsec=frontcover&source=bn&hl=ko&ei=rNDaSprINsmo8AaAkry3BQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CBwQ6AEwAw#v=onepage&q= & f = false – jrockway

배열은 목록을 기준으로 이 아니고이고 다른 프로그래밍 언어와 마찬가지로 연속적인 메모리 영역으로 구현됩니다.

배열 함수는 인덱스, 값 쌍의 목록을 인수로 취해서 인쇄 할 때 이러한 목록과 마찬가지로 표시됩니다. 하스켈의 배열은 정수뿐만 아니라 (Int, Int) - 쌍, 불린 (boolean), Char 및 많은 다른 버전과 같은 1x 유형을 구현하는 모든 항목으로 인덱싱 될 수 있기 때문입니다. 그래서 [(index, value)] 표현은 배열을 Haskell에서와 같이 일반적으로 표시하는 유일하고 합리적인 방식입니다.

출처

2009-10-15 13:35:03 Tirpen

haskell에 연속 메모리 영역이있는 언어가 있습니까? – Anton

@Anton : Haskell'98 언어 사양은 'Array' 모듈 (및 연관된 클래스, 유형 및 함수)의 존재를 요구합니다. "프로그래머가 컴포넌트에 신속하게 액세스 할 것을 합리적으로 기대할 수있다"는 것을 제외하고 구현에 대해서는 아무 것도 말하지 않지만, 일반적으로 연속 랜덤 액세스 메모리에 대한 인터페이스로 사용됩니다. – ephemient

배열은 목록을 기반으로하지 않습니다. 이러한 uvector, 배열 벡터 carray, hmatrix 같은 다양한 배열 라이브러리, 판독 로우 레벨을 사용하여 어레이에 대한 인터페이스를 제공하기 위해 기록 동작 동안

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

: 나열 일반 재귀 데이터 형식이다. 서로 다른 복잡성을 가지고 있지만 두 데이터 구조가 시퀀스를 나타낼 수 있다는 것 외에 다른 유사성은 없습니다.

출처

2009-10-15 15:36:53

하스켈. 어레이가리스트보다 빠른 이유는 무엇입니까?

답변

관련 문제