Data.Array는 얼마나 빠릅니까?

하스켈은 그 도메인 정수의 연속 하위 집합에 동형이다 함수로 생각 될 수있다 색인 배열을 제공합니다. 이 방법으로 제한된 기능은 효율적으로 구현할 수 있습니다. ; 특히, 프로그래머는 구성 요소에 대해 빠른 액세스를 기대할 수 있습니다 ( ).

(!)과 (//)이 얼마나 빠를 수 있는지 궁금합니다. O (1)의 복잡성을 예상 할 수 있습니까?

일반적으로 그렇습니다. O (1)을 !에서 기대할 수 있습니다. 표준에 의해 보장되는지 확실하지 않습니다.

(스트림 융합을 사용하여) 빠른 배열을 원한다면 벡터 패키지를보고 싶을 수도 있습니다. 그것은 또한 더 잘 설계되었습니다.

//은 아마도 명령형 프로그램처럼 목록을 탐색해야하기 때문에 아마도 O (n) 일 것입니다. 돌연변이가 많이 필요한 경우 MArray 또는 MVector을 사용할 수 있습니다.

2011-09-02 21:21:13 alternative

어레이의 새 복사본을 만들어야하기 때문에'(//)'는 실제로 배열 _ 크기의 선형입니다. 그러나 가변 배열을 사용하면 업데이트 수가 선형 일 것으로 예상됩니다. – hammar

@hammar 배열을 복사하고 목록을 반복해야하므로 양쪽 모두 선형입니다. // 대량 업데이트 기능이 필요 없기 때문에 MArray에서는 오히려 쓸모가 없습니다. – alternative

물론 가능합니다. 그러나 몇 가지 요소를 두 번 이상 업데이트하는 경우에만 문제가됩니다. – hammar

답변