가장 가까운 모든 작은 값

All nearest smaller values

컴퓨터 과학에서 가장 가까운 작은 값 문제는 모두 다음과 같은 작업이다: 각 위치의 숫자에 대해, 더 작은 값을 포함하는 마지막 위치를 찾기 위해 이전 위치들 사이를 검색하라. 이 문제는 효율적으로 평행하고은 알고리즘:버크먼, Schieber & 둘 다 우선 다른 병렬 프로그램에 대한 유용한 서브 루틴은 절차를 확인했다 Vishkin(1993년), 효율적인 알고리즘 병렬 임의 접근 기계 모델 문제를 해결하는 방법을 개발했다;그것은 선형적인 시간에non-par해야만 해결 될 것 해결될 수 있다.모든스택 기반 알고리즘을 사용하는 el 컴퓨터. 이후 연구자들은 병렬 컴퓨팅의 다른 모델에서 이를 해결하기 위한 알고리즘을 연구했다.

예

입력이 이진 반 데르 코퍼트 시퀀스라고 가정해 보십시오.

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

시퀀스의 첫 번째 요소(0)에는 이전 값이 없다. 8 이전의 가장 작은 값과 4 이전의 작은 값은 0이다. 12 이전 세 값은 모두 작지만 가장 가까운 값은 4이다. 동일한 방식으로 계속하면 이 시퀀스에 대해 이전의 가장 가까운 작은 값(대시에 의한 이전 작은 값의 비확실성을 나타냄)은

—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

대부분의 애플리케이션에서는 값 자체가 아니라 가장 가까운 작은 값의 위치를 계산해야 하며, 많은 애플리케이션에서는 시퀀스에서 가장 가까운 다음과 같은 작은 값을 찾기 위해 시퀀스의 역전에 대해 동일한 계산을 계산해야 한다.

적용들

버크만, 쉬버 & 비슈킨(1993)은 가장 가까운 작은 값 계산을 사용하여 병렬로 효율적으로 해결할 수 있는 많은 다른 문제들을 언급한다. 이 중 다음과 같은 내용을 포함한다.

  • 병합 알고리즘, 병합 정렬의 병합 단계 계산 이러한 알고리즘에 대한 입력은 두 개의 정렬된 숫자 배열로 구성된다. 원하는 출력은 단일 정렬 배열에서 동일한 숫자 집합이다. 한 개의 정렬된 배열, 즉 첫 번째 정렬된 배열과 두 번째 정렬된 배열과 두 번째 정렬된 배열과 내림차순으로 연결될 경우, 출력에서 각 값의 이전은 이전의 가장 가까운 작은 값 또는 다음의 가장 가까운 작은 값이다(둘 중 두 값 중 더 큰 값). 그리고 정렬된 출력 배열에서 각 값의 위치는 쉽게 ca일 수 있다.이 두 개의 가장 가까운 작은 값들의 위치에서 계산된 값.
  • 데카르트 나무의 건설. 까르테시안 트리는 뷔이유민(1980)이 도입하고 가보우, 벤틀리, 타르잔(1984)이 범위 검색 애플리케이션을 위해 추가 연구한 데이터 구조다. 또한 데카르트 트리는 이진 검색을 위한 treap과 임의의 바이너리 검색 트리 데이터 구조의 정의에서 발생한다. 일련의 값의 데카르트 트리는 각 값에 대한 노드를 가지고 있다. 트리의 루트는 시퀀스의 최소값이다. 다른 모든 노드에 대해, 노드의 모체는 이전의 가장 가까운 작은 값이거나 더 작은 값(둘 중 더 크고 존재하는 값)에 가장 가까운 값이다. 따라서 데카르트 나무는 가장 가까운 모든 작은 값 알고리즘에 기초하여 선형 시간 내에 생성될 수 있다.
  • 일치하는 괄호. 각 괄호의 내포 깊이와 함께 일련의 열린 괄호 문자 및 닫힌 괄호 문자가 입력으로 주어지는 경우, 각 열린 괄호와의 일치는 더 큰 내포 깊이가 없는 다음 가까운 괄호인 만큼 가까운 모든 작은 값 계산에 의해 가까운 괄호 안에 유리하게 묶여져 있는 것을 발견할 수 있다. 내포 깊이가 주어지지 않으면 접두사 합계 계산을 사용하여 계산할 수 있다.

또한 다각형 삼각측량, 볼록 선체 구조(순차 그래함 스캔 볼록 선체 알고리즘 평행), 나무의 횡단 순서 중 2개에서 나무 재구성, 쿼드트리 시공 등의 문제에도 유사한 기법이 적용될 수 있다.[1]

순차 알고리즘

순차적 컴퓨터에서는 스택 데이터 구조를 사용하여 가장 가까운 모든 작은 값을 찾을 수 있다. 즉, 지금까지 처리된 값들의 연속성을 유지하기 위해 스택을 사용하여 값을 순차적으로 처리한다. 유사코드에서는 알고리즘은 다음과 같다. 

S = 입력 시퀀스에서 x에 대한 새로운 빈 스택 데이터 구조는 S가 비어 있지 않고 S의 상단 요소가 x do pop S보다 크거나 같은 반면, S가 비어 있으면 x가 선행 작은 값을 가지지 않으면 x에 가장 가까운 작은 값이 S 푸시 x의 상단 요소다.

내포된 루프 구조를 가지고 있음에도 불구하고, 내측 루프의 모든 반복은 외부 루프의 일부 이전 반복에서 추가된 항목을 제거하기 때문에 이 알고리즘의 실행 시간은 선형이다. 스택으로 정렬하기 위한 크누스의 알고리즘(이러한 방법으로 정렬할 수 있는 입력의 경우)과 밀접하게 관련되어 있다.[2]

심지어 더 간단한 선형 시간 순차 알고리즘(Barbay, Fischer & Navarro(2012, Lema 1)은 스택이 필요하지 않으며, 입력 시퀀스가 배열 A[1,n]로 주어진다고 가정하고 선행 I'th 값 A[i]의 인덱스 j를 P[i]에 저장한다. 인위적인 전체 최소값은 A[0]로 가정한다. 

1 ~ n: j = i-1인 반면 A[j] >= A[i]: j = P[j] P[i] = j

병렬 알고리즘

Berkman, Schieber & Vishkin(1993)은 동시 읽기 동시 쓰기 병렬 랜덤 액세스 시스템에서 가장 가까운 모든 작은 값 문제를 효율적으로 해결하는 방법을 보여주었다. 배열로 저장되는 n개의 값 시퀀스의 경우, 총 작업의 선형 양을 사용하여 시간 O(log log n)로 문제를 해결할 수 있음을 보여준다. 모든 값이 구간[1,s]의 정수인 시퀀스의 경우, 버크만, 마티아스 & 라그드(1998)는 O(로그 로그 로그 s)로 바인딩을 개선했다. 또한 s의 충분한 큰 값에 대해서는 이전의 이중 로그 시간 바인딩이 문제에 대해 달성할 수 있는 최선의 값임을 보여주었다. 이 작업 이후, 하이퍼큐브 구조 통신망을 가진 병렬 컴퓨터와 [3]대량 동기식 병렬 모델을 포함한 병렬 컴퓨팅의 다른 모델에서도 가장 가까운 모든 작은 값 문제에 대한 병렬 알고리즘이 개발되었다.[4]

메모들

  1. ^ 베른, 엡스타인 & 텡 (1999년).
  2. ^ Knuth, Donald (1968), "Vol. 1: Fundamental Algorithms", The Art of Computer Programming, Reading, Mass.: Addison-Wesley.
  3. ^ 크래브츠 & 플랙스턴(1996년).
  4. ^ 헤&황(2001년).

참조