사용자 도구

사이트 도구


ps:그래프

그래프

  • 이론적으로 엣지 리스트, 인접 행렬, 인접 리스트 등으로 표현 가능하지만, PS에서는 인접 리스트 형태로 돌리는 게 유리한 경우가 대부분.
  • 표현은 인접리스트 형태로 한다고 하고. 이것을 구현할때, list와 dict, list와 set 중에서 어떤 것을 사용해서 구현하는 것을 기본 형태로 둘지에 대해서 많이 고민을 했다.
    • 예를 들어 가중치 없는 그래프를 인접리스트로 구현할 때 아래의 네 가지 방식중 어느것으로 통일하느냐..
      • g1 = [[1, 2], [], [0]]
        g2 = {0: [1, 2], 1: [], 2: [0]}
        g3 = [{1, 2}, {}, {0}]
        g4 = {0: {1, 2}, 1: {}, 2: {0}}
  • 그러나, 문득 이것을 굳이 통일시킬 필요가 없음을 깨달았다.. 재사용을 위한 함수를 만들때, type annotation을 통해서 어떤 구현의 그래프를 인자로 받는지만 명시해준다면 된다.
  • non-weighted 그래프를 대상으로 하는 대부분의 알고리즘은 Sequence[Iterable[int]] 형태로 충분하지만, 어떤 알고리즘은 Sequence[AbstractSet[int]]가 필요할 때도 있다. 사용할 알고리즘이 전자면 list of list로, 후자면 list of set로 다르게 구현해도 아무 문제가 없다..
  • 바깥의 경우에는..
    • 노드가 0~N까지의 정수로 표현된다면 dict를 쓸 이유가 전혀 없다. list를 쓰는 것이 빠르다
    • 그러나 노드가 문자열이나 튜플 등으로 표현된다면 list를 사용하기 위해서는 노드이름-to-index 형태의 맵을 추가로 유지해야 한다.
    • 제네럴한 용법을 고려한다면 dict를 써야 하는게 맞긴 한데.. 그러기에는 ps의 대다수의 문제는 0~N으로 노드를 표현한다.
    • [정수노드 문제의 비율] * [정수노드일때 dict로 손해보는 속도] 와 (1-[정수노드 문제의 비율]) * ([추가 맵 유지에 드는 코딩의 지저분함] + [추가 맵 유지에 드는 속도 저하]) 를 비교해야 할텐데.. 이중에서 가장 궁금한 것은 [정수노드일때 dict로 손해보는 속도]이다.
  • 안쪽의 경우에는..
    • set을 쓸 경우, 특정 엣지의 존재 유무를 O(V)가 아닌 O(1)에 알 수 있다는 것이 장점.
      • 하지만 의외로 이 연산이 필요한 경우는 그다지 없다..
    • 단점은 list에 비해서 속도가 떨어지는 문제일텐데..
      • 근데 노드에 연결된 모든 엣지를 순회하는 것은 사실 속도 차이가 별로 없을 것 같다..
        • 테스트해보니 진짜 차이가 미미하다. set이 약간 느리다는 뜻이 아니라 오히려 빠를때도 있고 느릴때도 있다는 말..
      • set에 add할때 list에 append하는 것보다 좀 느릴것 같긴 한데. 이거는 그래프 초기화 할때만 필요한거니까 큰 문제는 아니지 않나?
    • set을 쓰자!
  • 바깥쪽의 경우에는..
    • list를 쓰자!
  • 결국 최종 형태는 list of set

토론

댓글을 입력하세요:
B᠎ R H J A
 
ps/그래프.txt · 마지막으로 수정됨: 2021/01/16 13:35 저자 teferi