▲

GN⁺: 사라진 데이터 타입을 찾는 추적

 (hillelwayne.com)
2P by neo 9달전 | favorite | 댓글 1개

누락된 데이터 유형을 찾아서

  • 그래프는 노드의 집합으로, 화살표(간선)로 연결됨.
  • 노드와 간선에 데이터를 포함할 수 있음.
  • 소프트웨어 엔지니어링에서 그래프는 패키지 의존성, 인터넷 링크, 소프트웨어의 상태 공간, 관계형 데이터베이스, 연결 리스트, 이진 트리, 해시 테이블 등 다양한 형태로 존재함.
  • 비즈니스 로직에서도 그래프는 인용문의 참조, 교통 네트워크, 소셜 네트워크 등으로 활용됨.
  • 소프트웨어 개발을 오래하면 어디서든 그래프를 마주칠 가능성이 높음.

그래프 사용에 대한 고민

  • 그래프는 유용하지만, 실제 코드에서 그래프를 사용하는 것은 부담스러움.
  • 대부분의 주류 언어에서 그래프를 내장 타입으로 지원하지 않고, 표준 라이브러리에서도 드물며, 견고한 서드파티 라이브러리도 많지 않음.
  • 그래프를 직접 구현해야 하는 경우가 많음.
  • 소프트웨어 엔지니어가 그래프를 사용할 수 있는 빈도와 프로그래밍 생태계에서의 지원 사이에 격차가 존재함.

그래프 타입이 없는 이유

디자인 선택이 너무 많음

  • 방향성이 있는 그래프와 없는 그래프, 단순 그래프와 다중 그래프, 하이퍼그래프, 우버그래프 등 다양한 그래프 유형이 존재함.
  • 각 유형에 대해 노드와 간선에 ID를 부여할지, 어떤 데이터를 저장할지 등의 결정이 필요함.
  • 모든 가능성을 지원하는 완벽한 그래프 라이브러리는 많은 시간을 필요로 함.
  • 그래프 알고리즘의 성능이 중요하며, 특수한 경우가 중요함.
  • 그래프 알고리즘은 올바르게 구현하기 어려움.

구현 선택이 너무 많음

  • 간단한 방향성 그래프만을 지원한다고 가정해도, 그래프를 내부적으로 표현하는 방법에는 여러 가지가 있음.
  • 간선 리스트, 인접 리스트, 인접 행렬, 구조체의 집합 등 다양한 저장 방식이 존재함.
  • 다른 그래프 연산은 다른 표현 방식에서 다른 성능 특성을 가짐.
  • 그래프의 희소성과 밀집성에 따라 최적의 내부 그래프 표현 방식이 달라짐.
  • 노드 데이터, 간선 데이터, 다양한 유형의 노드와 간선을 구현하는 것은 더 복잡함.

성능이 너무 중요함

  • 많은 그래프 알고리즘은 NP-완전 문제이거나 더 어려움.
  • 그래프는 매우 큰 문제가 될 수 있으며, 표현 방식과 알고리즘 구현 세부 사항에 따라 성능이 크게 달라짐.
  • 데이터 표현과 알고리즘에 대한 많은 제어가 필요함.

일치된 의견

  • 다양한 그래프 유형, 표현, 알고리즘, 성능에 민감함, 큰 그래프에서 비싼 알고리즘 실행 등이 그래프 지원이 널리 퍼지지 않은 이유임.
  • 언어가 표준 라이브러리에서 그래프를 지원하지 않는 이유를 설명함.
  • 프로그래머가 서드파티 그래프 라이브러리를 피하는 이유를 설명함.
  • 그래프를 사용하는 것이 어렵기 때문에 극단적인 상황이 아니면 그래프로 생각하고 싶지 않은 이유를 설명함.

GN⁺의 의견

  • 이 기사는 그래프가 프로그래밍 언어와 라이브러리에서 왜 기본적인 데이터 유형으로 자리 잡지 못했는지에 대한 통찰을 제공함.
  • 그래프 이론은 컴퓨터 과학의 중요한 분야이며, 알고리즘, 네트워크 분석, 데이터베이스 등 다양한 영역에서 응용됨.
  • 그래프를 효과적으로 사용하기 위해서는 성능 최적화와 적절한 데이터 구조 선택이 중요함.
  • 서드파티 라이브러리로는 NetworkX, Boost Graph Library, Graph-tool 등이 있으며, 이들은 다양한 그래프 문제를 해결하는 데 사용될 수 있음.
  • 그래프를 사용할 때는 문제의 특성에 맞는 그래프 유형과 알고리즘을 선택하는 것이 중요하며, 이는 시스템의 성능과 직결됨.
▲
neo 9달전  [-]
Hacker News 의견

  • Graphviz는 독자적인 그래프 라이브러리를 가지고 있으며, 이는 다른 프로젝트에서 사용되지 않는다. 이 라이브러리는 장단점이 있다.

    • 이 경험을 바탕으로, 그들은 자신들만의 '두 번째 시스템 증후군'을 겪었다.
    • 그래프 라이브러리는 모듈식이며, 타입 안전하고, 효율적이어야 한다고 결정했다. 이는 "좋고, 빠르고, 저렴하게 - 둘 중 하나를 선택하라"는 말의 변형일 수 있다.
    • 모듈식이란 독립적으로 개발되고 컴파일되는 그래프 알고리즘 라이브러리 모음을 작성하고자 함을 의미한다.
    • 타입 안전이란 컴파일 시 또는 늦어도 링크 시 프로그래밍 오류를 감지하고자 함을 의미한다. 실행 시간 오류는 원치 않는다.
    • 효율성이란 그래프의 속성에 접근하는 것이 C 구조체의 필드처럼 저렴해야 함을 의미한다.
    • 이러한 목표가 가치가 있는지 논란의 여지가 있지만, 그들이 원하는 바였다. 유명한 C++ 창시자들이 그들의 연구실에 있었기 때문에 도움을 받을 수 있을 것으로 기대했고, C++에 다시 한 번 기회를 주기로 했다.
    • 인턴 출신인 Gordon Woodhull은 뛰어난 프로그래머로, 템플릿 C++에서 이러한 종류의 그래프 라이브러리를 구현했다. 이는 sourceforge를 통해 https://www.dynagraph.org/에서 공개되었다.
    • 다른 사람들은 코드가 어떻게 작동하는지 이해할 수 있을지 확신하지 못했기 때문에, 유명한 C++ 발명가들과 코드 리뷰를 진행했다. 복잡성의 벼랑을 넘어섰을 수도 있다는 것을 알았다.
    • 이는 Gordon의 잘못이 아니었고, 그는 계속해서 플러그를 꽂고 마이크로소프트 OLE에서도 동적 그래프 레이아웃 작업을 성공적으로 수행했다. 회고해보면, 이는 그들만의 프로젝트 자나두였을 수 있다.
    • 그들이 이에 몰두하는 동안, Gephi(Java)와 NetworkX 및 NetworKit(Python)과 같은 많은 것들이 등장했다.
    • John Ellson은 Graphviz의 일부를 작성한 매우 재능 있는 소프트웨어 엔지니어로, 주요 노력을 되살렸다.

  • .NET에서 코딩하는 경우, 작고 기능이 풍부하지 않은 그래프 라이브러리 Arborescence를 시도해보길 바란다.

    • 이 라이브러리는 추상화, 알고리즘, 데이터 구조 사이의 좋은 분리를 제공한다고 믿는다.
    • 사용자는 자체 ID가 있는 엣지를 사용할 수도 있고, 즉석에서 펼쳐지는 암시적 그래프를 사용할 수도 있다.
    • 인접성(밖으로 향하는 이웃)과 인접성(밖으로 향하는 엣지 + 머리) 인터페이스를 모두 사용할 수 있다.
    • 라이브러리는 엣지 타입을 강제하지 않지만, 기본적인 꼬리-머리 쌍 구조를 유틸리티로 제공한다.

  • 그래프는 데이터 구조나 데이터 타입이 아니라 추상화이다.

    • 기본적으로 그래프를 정의하는 데 필요한 것은 정점 집합과 이웃 함수뿐이다.
    • 모든 다른 것들은 사례별 제약 조건이다.
    • 하이퍼그래프를 고려하면, 그래프는 단순히 특별한 경우에 불과하다.
    • 데이터베이스 관점에서 생각하면, 그래프는 쿼리 최적화 및 인덱싱 문제이다.

  • 프로그래밍 언어에 내장된 그래프 데이터 타입이 없는 이유에 대한 질문을 많이 받았다.

    • 이제 이 글과 같은 더 심도 있는 분석을 가리킬 수 있어 기쁘다.

  • 중앙 장애물은 다음과 같다:

    • 간단하고 작은 그래프 문제의 경우, 벡터의 벡터 인접 리스트를 코딩하는 것이 충분히 쉽다.
    • 복잡하고 거대한 그래프 문제의 경우, 문제에 맞는 그래프 구현을 맞춤화하는 것 외에는 성능을 얻을 수 있는 방법이 없다.
    • 어떤 종류의 언어 지원이 도움이 될지 명확하지 않다.

  • 이 글은 프로그래밍 언어에서 그래프 _알고리즘_이 더 잘 지원되지 않는 이유에 대한 질문에 대부분 답한다.

    • 그래프 지원을 일반적으로 살펴보면, OGM이 ORM만큼 인기가 없는 이유, JSON이 RDF보다 널리 사용되는 이유 등 더 넓은 질문을 볼 수 있다.
    • 결국 역사적인 이유와 그래프의 복잡성 때문에 개발자들 사이에서 잘 확장되지 않는다.

  • 그래프 그리기 도구도 매우 실망스럽다.

    • 500개 이상의 노드가 있는 그래프에서는 출력물이 이해하기 어렵거나 복잡해진다.
    • 그래프를 계층적 구조로 자동으로 구성하고 탐색하기 좋은 인터페이스를 제공하는 기능이 부족하다.

  • 이 글은 정말 멋지다.

    • "구현 선택지가 너무 많다"는 핵심 관찰에 대해, 실제로는 그렇지 않다.
    • 실제로 라이브러리는 모든 적합한 그래프 표현을 구현할 수 있다.
    • 알고리즘을 표현에 맞게 맞춤화하고, 하나의 표현에서 다른 표현으로 변환할 수 있다.

  • Electric Clojure는 Clojure 자체(s-표현식)를 그래프 저작 구문으로 사용한다.

    • 그래프 저작 DSL은 범위, 제어 흐름, 추상화를 표현해야 하며, 이는 본질적으로 프로그래밍 언어와 동일하다.

  • 테이블(데이터베이스 내의 테이블과 같은)과 같은 또 다른 유용한 데이터 타입이 있다.

    • 컴파일러가 데이터 구조의 구현을 선택하게 하면 프로그래밍 언어에서 진전이 있을 것이다.
    • 추상 구조(시퀀스, 맵, 세트, 테이블, 그래프 등)를 사용하고 프로그램 프로필에 기반하여 컴파일러가 구체적인 구현을 선택한다.
답변달기