2016-11-25 4 views
2

파이썬에는 groupby 함수가 있습니다.파이썬에서 analog of haskell

형식이 다음과 같이 haskell로 표현 될 수 있습니다. groupby :: a->b->[a]->[(b, [a])] 데이터를 정렬해야하기 때문에 실행 시간을 O(n*log(n))으로 생각할 수 있습니다.

나는 이것에 불만이있는 유일한 사람이 아니기 때문에 이 groupby 구현은 입력 시퀀스에 대해 두 번 통과해야합니다. 그래서 나는 그것의 실행 시간이 O(n)이라고 생각하지만, 문서에서 말하는 것처럼, 실제로 게으른 것은 아니다. 왜냐하면 만약 당신이 그것에 키를 전달하지 않으면, 아이템으로부터 모든 유일한 키를 수집하기 위해 시퀀스를 넘겨 줄 필요가 있기 때문이다.

그래서 나는 더 나은 방법이 있어야합니다

를 레이몬드 Hetttinger

를 인용, 생각!

그래서 난 당신이 파이썬에 익숙하지 않은 경우이

from collections import defaultdict, deque 


def groupby(sequence, key=lambda x: x): 
    buffers = defaultdict(deque) 
    kvs = ((key(item), item) for item in sequence) 
    seen_keys = set() 
    def subseq(k): 
     while True: 
      buffered = buffers[k] 
      if buffered: 
       yield buffered.popleft() 
      else: 
       next_key, value = next(kvs) 
       buffers[next_key].append(value) 
    while True: 
     try: 
      k, value = next(kvs) 
     except StopIteration: 
      for bk, group in buffers.items(): 
       if group and bk not in seen_keys: 
        yield (bk, group) 
      raise StopIteration() 
     else: 
      buffers[k].append(value) 
     if k not in seen_keys: 
      seen_keys.add(k) 
      yield k, subseq(k) 

이 아이디어는 매우 간단 썼다. key -> queue of elements의 변경 가능한 사전 만들기 시퀀스의 다음 요소와 해당 키 값을 가져가보십시오. 시퀀스가 ​​비어 있지 않으면이 값을 키에 따라 그룹 대기열에 추가합니다. 우리가이 키 수율을 보지 못했다면, 후자는 버퍼 또는 시퀀스로부터 키를 취할 것이다. 우리가 이미 이것을 본다면이 열쇠는 더 이상 아무것도하지 않고 반복합니다.

시퀀스가 ​​종료되면 모든 요소가 이미 버퍼에 저장되어 있거나 소비되었을 가능성이 있습니다. 버퍼가 비어 있지 않은 경우에 우리는 그것들을 반복하고 이름 바꾸기 (키, 반복 가능) 쌍을 산출합니다.

이미 단위 테스트를 마쳤습니다. 그리고 그것은 정말로 게으르다 (소비자가 그것을 요구하지 않을 때까지 시퀀스에서 어떤 가치도 취하지 않을 것이라는 의미이며) 실행 시간은 O(n)이어야한다.

나는이 함수의 유사점을 찾으려고했지만 아무 것도 찾지 못했다.

같은 것을 haskell에 쓸 수 있습니까? 그렇다면 해결책을 제시하고 그렇지 않다면 그 이유를 설명하십시오. 나는이 상황을 제대로 이해한다면

+1

http://hackage.haskell.org/package/discrimination-0.2.1/docs/Data-Discrimination.html#v:groupWith – leftaroundabout

+0

@leftaroundabout 예, 기본적으로 같지만 유형은'a-> b -> [[a]]'. 어떤 동등한 클래스가 어떤 것인지 어떻게 알 수 있습니까? 보시다시피, 저는 유형이 'a-> b-> [(b, [a])]'로 검색했습니다. – user1685095

+0

@leftaroundabout 두 번째 손에서 저는 소스를 읽고 그것을 어떻게 바꿀 수 있는지 생각할 수 있습니다. 그것은 동등한 클래스의 이름을 반환합니다. 소스를 통해 건너 뛴 적이 있는데, 수입으로 판단 할 때 가변 상태를 사용합니다. 맞습니까? 당신은 이것이 가변적 인 국가없이 가능하다고 생각합니까? – user1685095

답변

0

, 당신이 원하는 유형의 주요 기능 및 항목, 그룹 키에 의해 항목의 목록을 제공한다

(a -> k) -> [a] -> [(k, [a])] 

입니다.

하스켈에는 비슷한 기능을하는 groupBy 라이브러리 함수가 있습니다. 여기서는 정렬 된 목록이 있다고 가정하고 부울 조건을 만족하는 항목을 하위 목록으로 그룹화합니다. 우리는 당신이 원하는 일을하는 데 사용할 수 있습니다 :

import Data.List 
import Data.Ord 

groupByKey :: (a -> k) -> [a] -> [(k, [a])] 
groupByKey keyF xs = map getResult groups 
    where 
     keyPairs = map (\v -> (keyF v, v)) xs 
     groups = groupBy (\v1 v2 -> fst v1 == fst v2) 
        $ sortBy (comparing fst) keyPairs 
     getResult xs = (fst $ head xs, map snd xs) 

keyPairs 인수의 각 요소에 대한 쌍 (key, value)입니다. groups은 먼저 sortBy을 사용하여이를 키 순서로 정렬 한 다음 결과를 동일한 키를 공유하는 하위 목록으로 그룹화합니다. getResult은 하위 목록을 키 (head 요소에서 가져온 것)와 원래 값의 목록을 포함하는 쌍으로 변환합니다. groupBy은 결코 빈 하위 목록을 제공하지 않으므로 head을 사용하는 것이 안전합니다.

+0

글쎄, 그건 명백한 해결책이지만, 실행 시간은'O (n * log (n))'입니다. 아마도 충분히 명확하지 않을 수도 있지만, 나는 게으르고'O (n)'실행 시간을 갖는 솔루션을 원합니다. – user1685095

+1

요소를 주요 순서로 정렬해야 할 필요성을 어떻게 느끼는지 모르겠습니다. 어쩌면 내가 너가 원하는 걸 오해했을거야. 열쇠 표를 사용하면 어떻게 O (n log k)를 얻을 수 있는지 알 수 있습니다. 그게 다야? –

+0

글쎄, 내가 어떻게 파이썬에서 이미 그 것을 보았는가? 구현시에는 발행 될 키 순서가 지정되어 있지 않지만 특정 순서로 쌍을 출력하도록 수정할 수 있습니다. 열쇠는 요소의 버퍼링입니다. 또한 @leftaroundabout에서 유용한 링크가 있습니다. 차별 패키지를 작성한 사람이 이미 기본적으로 그렇게했습니다. 따라서 haskell에서도 가능합니다. – user1685095