현실 세계에서 데이터 구조를 다시 구현

Question

알고리즘 클래스의 주제는 데이터 구조, 특히 Java의 ArrayList를 다시 구현하는 것이 었습니다. 여러 가지 방법으로 구조를 사용자 정의 할 수 있다는 사실은 특히 add() & iterator.remove() 메소드의 변형에 관심이 많습니다.

그러나 실제 프로그래머보다 학계에 중요한 데이터 구조를 다시 구현하고 사용자 지정하는 중입니까? 누구나 상업용 응용 프로그램/프로그램에서 데이터 구조의 자체 버전을 다시 구현했으며 특정 언어 구현에 대한 그 경로를 선택한 이유는 무엇입니까?

Answer 1

데이터 구조가 구현되고 구현 될 수있는 방법을 아는 것은 학계뿐 아니라 모든 사람에게 중요한 관심사입니다. 언어가 이미 적절한 기능과 성능 특성을 갖춘 구현을 제공하는 경우 데이터 구조를 다시 구현하지 않을 가능성이 있지만 다른 데이터 구조를 구성하여 고유 한 데이터 구조를 만들어야 할 가능성이 매우 높습니다. 잘 알려진 데이터 구조와는 약간 다른 동작으로 데이터 구조를 구현하십시오. 이 경우 원본 데이터 구조가 어떻게 구현되는지 확실히 알 필요가 있습니다. 또는 존재하지 않거나 기존 데이터 구조에 유사한 동작을 제공하는 데이터 구조가 필요할지 모르지만 사용되는 방식에 따라 다른 기능 집합에 맞게 최적화해야합니다. 다시 말하지만, 이러한 상황에서는 데이터 구조를 구현 (및 변경)하는 방법을 알아야하므로 관심의 대상입니다.

편집
나는 는 기존 데이터 구조체을 구현할 것을 옹호하지 않다! 그러지 마. 제가 말하고자하는 것은 지식에는 실제 적용이 있다는 것입니다. 예를 들어 양방향지도 데이터 구조 (단방향지도 데이터 구조 두 개를 구성하여 구현할 수 있음)를 만들거나 다양한 통계 (예 : min, max, 평균값)을 사용하여 값을 포함하는 요소 유형과 이러한 다양한 통계를 포함하는 기존 스택 데이터 구조를 사용합니다. 이것들은 현실 세계에서 구현해야 할 일들의 간단한 예입니다.

Answer 2

나는 언어의 기본 제공 데이터 구조, 함수 및 클래스 중 일부를 여러 번 다시 구현했습니다. 임베디드 개발자로서 내가 할 수있는 주된 이유는 속도 나 효율성 때문입니다. 표준 라이브러리 및 유형은 다양한 상황에서 유용하도록 설계되었지만 현재 플랫폼의 기능 및 제한 사항을 활용하도록 사용자 정의 된보다 특수화 된 버전을 만들 수있는 경우가 많이 있습니다. 언어가 기존 클래스를 열고 수정할 수있는 방법을 제공하지 않는다면 (예를 들어 Ruby 에서처럼) 클래스/함수/구조를 다시 구현하는 것이 유일한 방법 일 수 있습니다.

예를 들어, 제가 연구 한 한 시스템은 32 비트 숫자로 작업 할 때 빠르지 만 작은 것들로 작업 할 때는 느린 MIPS CPU를 사용했습니다. 필자는 16 비트 정수 대신 32 비트 정수를 사용하는 몇 가지 데이터 구조와 함수를 다시 작성하고 필드를 32 비트 경계에 맞춰 정렬하도록 지정했습니다. 그 결과는 소프트웨어의 다른 부분에 병목을 일으키는 코드 부분에서 눈에 띄는 속도 향상이었습니다.

그것은 말하자면, 그것은 사소한 과정이 아니 었습니다. 그 구조를 사용하는 모든 함수를 수정해야하고 결국 몇 가지 표준 라이브러리 함수도 다시 작성해야했습니다. 이 특별한 경우에는 그 이점이 작업을 능가했습니다. 그러나 일반적인 경우에는 일반적으로 문제가되지 않습니다. 디버그하기 어려운 문제에 대한 큰 잠재력이 있으며, 항상 보이는 것보다 더 많은 작업이 있습니다. 기존 구조/클래스가 충족시키지 못하는 특정 요구 사항이나 제한 사항이없는 경우이를 다시 구현하지 말 것을 권장합니다.

Michael이 언급했듯이 결코 그렇게하지 않더라도 구조를 다시 구현하는 방법은 실제로 을 알아두면 유용합니다. 앞으로도 기존 데이터 구조에 사용 된 원칙과 기술을 적용하여 해결할 수있는 문제점을 발견 할 수 있습니다.