일련의 역변환을 사용하여 배열을 정렬하는 가장 효율적인 방법은 무엇입니까?

Question

나는 이미 내림차순으로 정렬 된 정수 목록을 가지고 있지만 첫 번째 요소의 값을 취하는 함수 (x이라고 부름)와 subtract 1을 x (나머지 첫 번째 요소)가 적용됩니다. (나는 a graphic sequence를 확인하기 위해 재귀 알고리즘을 구현하려합니다.)

list1 = [4,4,3,2,2,2,2,1] --an example of a nonincreasing list 
newList = (/s -> map (subtract 1) (fst s) ++ snd s) $ splitAt (head list1) (tail list1) 
         --newList == [3,2,1,1,2,2,1] 
--only these four need to be swapped  | | | |    
sortedList = sortFunction newList --[3,2,2,2,1,1,1] 

새로운 목록은 재귀의 다음 단계에 대한 내림차순으로 다시 정렬 할 필요가있다. 나는 Data.List.sort을 사용해 보았지만, 큰 목록에서는 상당히 느려지므로 모든 수준의 재귀에 적용됩니다.

숫자가 증가하지 않는 정수 목록의 시작 부분에 매핑 subtract 1의 성격은 실제로 반전이있는 지점에 단 하나의 지점이 있음을 의미합니다. 예를 들어 이전 코드에서 처음 두 개는 1의 경우에만 필요합니다. 목록을 정렬하려면 다음 두 개의 2과 교환하십시오.

이 정렬을 수행하는 가장 효율적인 (즉, 가장 빠른) 방법은 무엇입니까? 또한,이 작업에 대한 목록 대신에 사용할 효율적인 데이터 구조가 있습니까?

Answer 1

런레트 인코딩을하는 것이 더 나을 것 같습니다. 그렇다면 목록을 정렬 된 상태로 유지하기 위해 멀리 파고 들지 않아도됩니다.

(경고 :. 안된 하스켈 코드) 함수

rlEncode xs = [(length xs', head xs') | xs' <- reverse $ group $ sort xs] 

는 [(2,4),(1,3),(4,2),(1,1)]에 [4,4,3,2,2,2,2,1]집니다. 그리고 우리는 "생성자"

rlCons (n, x) [] = [(n, x)] 
rlCons (n, x) rle@((n', x') : rle') 
    | x == x' = (n + n', x) : rle' 
    | otherwise = (n, x) : rle 

및 실행 길이 인코딩 목록에 대한 "소멸자"

rlUncons [] = Nothing 
rlUncons ((1, x) : rle) = Just (x, rle) 
rlUncons ((n, x) : rle) = Just (x, (n - 1, x) : rle) 

를 작성할 수 있습니다. 그렇다면 isGraphic은 가장 간단하고 효율적인 형태로 다음과 같이 보입니다. 때문에,

isGraphic [] = True 
isGraphic rle = fromMaybe False $ do 
    (d, rle') <- rlUncons rle 
    rle'' <- deflate d rle' 
    return $ isGraphic rle'' 

deflate 0 rle = Just rle 
deflate _d [] = Nothing 
deflate _d [(_,0)] = Nothing 
deflate d ((n, d') : rle) 
    | d < n = Just $ rlCons (n - d, d') $ rlCons (d, d' - 1) rle 
    | otherwise = liftM (rlCons (n, d' - 1)) $ deflate (d - n) rle