관리 언어를위한 Judy 배열

StackOverflow https://stackoverflow.com/questions/550204

문제

주디 어레이 희소 배열 또는 값 세트를 나타낼 수있는 빠른 데이터 구조입니다. C#과 같은 관리 언어에 대한 구현이 있습니까? 감사

도움이 되었습니까?

해결책

이것들을 종종 Judy Trees 또는 Judy Triss라고 불렀다는 점은 주목할 가치가 있습니다.

또한 .NET 구현을 찾았지만 아무것도 찾지 못했습니다. 또한 주목할 가치가 있습니다.

구현은 효율적인 캐시 사용을 중심으로 크게 설계되었으며, 이러한 구현 세부 사항은 하위 구조 내에서 사용되는 특정 구성의 크기에 크게 의존 할 수 있으므로. .NET 관리 구현은 이와 관련하여 다소 다를 수 있습니다.

내가 볼 수있는 몇 가지 중요한 장애물이 있습니다 (그리고 아마도 내 간단한 스캔을 놓친 것들이 더있을 것입니다)

  • API에는 상당히 반 OO 측면 (예 : 널 포인터가 빈 트리로 간주 됨)이 단순하기 때문에 상태 포인터를 LHS로 이동시키고 기능 인스턴스 메소드를 C ++로 변환하는 기능이 작동하지 않습니다.
  • 내가 본 서브 구조의 구현은 포인터를 많이 사용했습니다. 이들이 관리되는 언어로 된 참조로 효율적으로 번역되는 것을 볼 수 없습니다.
  • 구현은 공개 API의 단순성에 따른 매우 복잡한 아이디어의 증류입니다.
  • 코드베이스는 약 20k 라인 (대부분 복잡한)이며, 이는 쉬운 포트로 나를 공격하지 않습니다.

라이브러리를 가져 와서 C 코드를 C ++/CLI로 랩핑 할 수 있습니다 (아마도 C API 트리 인 포인터를 내부적으로 보관하고 모든 C 호출 이이 제품을 가리킬 수 있습니다). 이는 단순한 구현을 제공하지만 기본 구현을위한 링크 된 라이브러리는 문제가 될 수 있습니다 (메모리 할당 가능성). 또한 .NET 문자열을 전환에서 일반적인 바이트*로 변환해야 할 수도 있습니다 (또는 바이트와 직접 작업).

다른 팁

Judy는 실제로 관리 언어에 잘 맞지 않습니다. Swig와 같은 것을 사용하고 첫 번째 레이어를 자동으로 수행 할 수 있다고 생각하지 않습니다.

나는 Pyjudy를 썼고 결국 파이썬에 잘 맞지 않도록 사소한 API를 변경해야했습니다. 예를 들어, 나는 문서에 다음을 썼습니다.

유틸 어레이는 기계 단어를 기계 단어에지도에지도에 맵핑합니다. 실제로 단어는 서명되지 않은 정수 또는 포인터를 저장합니다. Pyjudy는 네 가지 매핑을 모두 뚜렷한 클래스로 지원합니다.

  • pyjudy.judylintint- 서명되지 않은 정수 값에 대한 서명되지 않은 정수 키 맵
  • pyjudy.judylintobj- Python 객체 값에 대한 서명되지 않은 정수 키 맵
  • pyjudy.judylobjint- 서명되지 않은 정수 값에 대한지도 파이썬 객체 키 맵
  • pyjudy.judylobjobj- Python 객체 값에 대한 Python 객체 키 맵

나는 몇 년 동안 코드를 보지 못했기 때문에 그것에 대한 나의 추억은 꽤 흐릿합니다. 그것은 나의 첫 번째 Python Extension 라이브러리였으며, 나는 코드 생성을위한 일종의 템플릿 시스템을 해킹 한 것을 기억합니다. 요즘 나는 Genshi와 같은 것을 사용할 것입니다.

Judy의 대안을 지적 할 수 없습니다. 그것이 내가 StackoverFlow를 검색하는 이유 중 하나입니다.

편집 : Judy가 64 비트 캐시 라인을 위해 개발되었고 파워북이 32 비트에 불과했기 때문에 문서의 내 타이밍 번호가 Judy의 문서가 제안한 것에서 꺼져 있다고 들었습니다.

다른 링크 :

마지막에는 다른 고성능 트리 구현에 대한 비교 숫자가 있습니다.

이것은 내가 생각했던 것보다 까다로운 것을 증명합니다. Pyjudy 살펴볼 가치가있을 수 있습니다 넥타이 :: 주디. 뭔가가 있습니다 소프트 페디아, 그리고 뭔가 루비-어. 문제는, 이들 중 어느 것도 구체적으로 .net이 아닙니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top