Haskell의 비 모 놀리 식 배열

Question

아래 질문에 대한 대답을 수락했지만 haskell의 배열이 어떻게 작동하는지 오해 한 것 같습니다. 나는 그들이 단지리스트를 강화했다고 생각했다. 아래 질문을 읽을 때 명심하십시오.

---

큰 배열에 사용할 때 haskell의 모 놀리 식 배열이 매우 비효율적이라는 사실을 발견했습니다.

나는 haskell에서 배열의 비 모 놀리 식 구현을 찾을 수 없었습니다. 내가 필요한 것은 O (1) 시간을 다차원 배열에서 찾아 보는 것입니다.

이것을 지원하는 배열 구현이 있습니까?

편집 : 용어 모 놀리식이 잘못 이해 된 것 같습니다. 문제는 haskell의 배열이리스트처럼 배열을 처리하는 것처럼 보입니다. 나는 틀린 것일지도 모른다.

EDIT2 : 비효율적 인 코드 단편 예 :

fibArray n = a where 
    bnds = (0,n) 
    a = array bnds [ (i, f i) | i <- range bnds ] 
    f 0 = 0 
    f 1 = 1 
    f i = a!(i-1) + a!(i-2) 

이 i 번째 필드는 i 번째 피보나치 수를 보유 길이 n+1 배열이다. 그러나 haskell의 배열에는 O (n) 시간 조회가 있으므로 계산에 O (n²) 시간이 걸립니다.

Answer 1

배열에는 O (1) 색인이 있습니다. 문제는 각 요소가 느리게 계산된다는 것입니다. 그래서 이것은 당신이 ghci에서이 프로그램을 실행할 때 발생하는 것입니다 : 그 조회가 매우 빠르고

*Main> :set +s 
*Main> let t = 100000 
(0.00 secs, 556576 bytes) 
*Main> let a = fibArray t 
Loading package array-0.4.0.0 ... linking ... done. 
(0.01 secs, 1033640 bytes) 
*Main> a!t -- result omitted 
(1.51 secs, 570473504 bytes) 
*Main> a!t -- result omitted 
(0.17 secs, 17954296 bytes) 
*Main> 

주, 는 후 이미 한 번 고개 됐어요. array 함수는 썽크 (thunks)에 대한 포인터의 배열을 생성하며 결국에는 값을 산출하기 위해 계산됩니다. 처음으로 가치를 평가할 때이 비용을 지불하게됩니다.여기에 a!t을 평가하는 썽크의 처음 몇 확장은 다음과 같습니다

a!t -> a!(t-1)+a!(t-2)-> a!(t-2)+a!(t-3)+a!(t-2) -> a!(t-3)+a!(t-4)+a!(t-3)+a!(t-2) 

그것은 비싼 계산 자체의 비용이 아니다, 오히려이 매우 큰 썽크를 작성하고 통과 할 필요가있다.

나는 array에 전달 된 목록의 값을 엄격하게하려고했지만 끝없는 반복이 발생하는 것으로 보였다.

이 문제를 해결하는 일반적인 방법 중 하나는 STArray와 같은 변경 가능한 배열을 사용하는 것입니다. 요소는 배열을 만드는 동안 사용할 수있을 때 업데이트 할 수 있으며 최종 결과는 고정되어 반환됩니다. 벡터 패키지에서는 create 및 constructN 함수를 사용하여 쉽게이 작업을 수행 할 수 있습니다.

-- constructN :: Unbox a => Int -> (Vector a -> a) -> Vector a 


import qualified Data.Vector.Unboxed as V 
import Data.Int 

fibVec :: Int -> V.Vector Int64 
fibVec n = V.constructN (n+1) c 
where 
    c v | V.length v == 0 = 0 
    c v | V.length v == 1 = 1 
    c v | V.length v == 2 = 1 
    c v = let len = V.length v 
     in v V.! (len-1) + v V.! (len-2) 

하지만의 fibVec 기능은 언 박싱 벡터와 함께 작동합니다. 정규 벡터 (및 배열)는 충분히 엄격하지 않으므로 이미 발견 한 동일한 문제로 다시 안내됩니다. 그리고 안타깝게도 Integer에 대한 Unboxed 인스턴스가 없으므로 제한없는 정수 유형 (이 테스트에서는 이미 fibVec이 오버플로되어 있음)이 필요하면 IO 또는 ST에 변경 가능한 배열을 만들어야 만 고정밀 성을 유지할 수 있습니다. 당신의 fibArray 예에 특별히 참조

Answer 2

당신은 하스켈의 연결리스트를 배열과 혼동하고 있습니다.

[1,2,3,5] 

같이 정의 :

연결리스트는 다음과 같은 구문을 사용하는 데이터 유형

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

이것들은 O (N) 인덱싱 및 O (1지지 고전 재귀 데이터 형식이다) 앞자리.

O (1) 조회를 사용하여 다차원 데이터를 찾으려면 대신 실제 배열 또는 행렬 데이터 구조를 사용해야합니다. 좋은 후보는 다음과 같습니다

• Repa - 빠르고 병렬, 다차원 배열 - (Tutorial)
• Vector - (가변 및 불변 모두) Int 인 인덱스 배열의 효율적인 구현, 강력한 루프 최적화 프레임 워크. (Tutorial)
• HMatrix - GSL, BLAS 및 LAPACK을 사용하여 내부적으로 구현 된 기본 선형 대수 및 기타 수치 계산에 대한 순수 기능 인터페이스.

Answer 3

, 이것을 시도하고 물건을 조금 속도 있는지 : 나를 위해

-- gradually calculate m-th item in steps of k 
--  to prevent STACK OVERFLOW , etc 
gradualth m k arr       
    | m <= v = pre `seq` arr!m 
    where         
    pre = foldl1 (\a b-> a `seq` arr!b) [u,u+k..m] 
    (u,v) = bounds arr 

, let a=fibArray 50000를 들어, gradualth 50000 10 a은 바로 a!50000를 호출 0.65 런타임에 달렸다.