1. 홈
  2. 질의 응답
  3. 자기 조정 데이터 구조 란 무엇입니까?

자기 조정 데이터 구조 란 무엇입니까?

2009-05-20 4 views
2

"자체 조정"데이터 구조 란 무엇을 의미합니까? 다른 데이터 구조와 다른 점은 무엇입니까? 그들은 어디에 사용됩니까?자기 조정 데이터 구조 란 무엇입니까?

편집 : 삽입 및 삭제 이외의 작업을 수행하면 왜 데이터 구조가 조정됩니까?

출처

2009-05-20 unj2

+1

그들은 데이터를 위해 서스펜더와 같습니다. – Shog9

+0

여러분의 필요를 예상하기 위해 스스로를 재 작성하는 코드입니다. 또한 skynet. 감사합니다. –

답변

8

자체 조정 데이터 구조는 작업이 커밋 될 때 자체를 재정렬 할 수있는 구조입니다. 때때로 그들은 광범위하게 혹은 최소한으로 재 배열합니다.

예를 들어 AVL trees은 노드가 삽입되거나 제거 될 때마다 균형을 유지하여 삽입 및 삭제 비용으로 빠른 검색을 보장합니다.

비 자체 조정 구조의 예로는 순진한 이진 트리가 있습니다. 이진 트리는 노드가 트리에 어떤 영향을 미치더라도 처음 삽입 된 위치에 머무르게됩니다.

부록 : 다른 구조는 삽입이나 삭제가 아닌 읽기를 기준으로 조정됩니다. 이러한 구조는 진보되어 액세스에 관한 많은 양의 통계를 수집 할 수 있으며, 실제로는 더 경험적 일 수 있습니다. 이러한 구조의 목표는 과거에 읽은 내용을 토대로 더 빠르게 읽는 것입니다. 이러한 구조의 일반적인 예는 cache이며 최근 액세스 한 데이터는 아직 액세스하지 않은 데이터보다 빠르게 액세스 할 수 있습니다.

출처

2009-05-20 01:10:00 Welbog

+0

. 그러나 삽입이나 삭제 이외의 작업을 수행 할 때 데이터 구조가 조정해야하는 이유는 무엇입니까? – unj2

+1

@ kunjaan : 그것은 구조에 달려 있습니다. 구조가 액세스되는 방법에 대한 기록을 유지하고, 그러한 기록을 기반으로 통계를 계산하고, 액세스되는 가장 일반적인 방식으로 더 빠르게 액세스되도록 재 배열 할 수 있습니다. 간단한 예는 삽입 또는 삭제가 아닌 액세스에 따라 다른 데이터가 캐시에 저장되는 캐싱입니다. – Welbog

+0

또 다른 (다소 고안된) 예제는 링크 된 목록 일 수 있습니다. 여기에서 각 노드가 검색에서 발견되는 횟수가 추적되고 가장 자주 검색되는 노드를 목록 앞쪽으로 이동시키기 위해 목록이 재정렬됩니다. –

1

이 컨텍스트에서 다른 의미는 "자체 조정"입니다. 입력 데이터 세트가 주어지면 최소 요소와 같은 일부 출력 값을 제공하는 데이터 구조 (최소 힙)를 가질 수 있습니다. 입력 데이터를 약간 변경하고 힙을 업데이트하여 새로운 최소 요소를 전달하려는 경우가 일반적입니다. 이상적으로는 힙의 전체 크기가 아닌 변경 크기에 비례하여이 작업을 수행하고 싶을 것입니다.

자체 조정 데이터 구조는이 유형의 "입력 수정, 점진적으로 출력 다시 계산"동작을 지원합니다. this recent paper from PLDI '10을 참조하십시오.

이것은 몇 가지면에서 효과적인 종속성 추적 및 증분 계산의 목표를 공유하는 기능적 반응 형 프로그래밍과 관련이 있습니다.

출처

2010-07-28 21:13:48

관련 문제

 관련 문제