O (1) 요소 제거의 동적 배열

Question

이 질문은 내가 생각한 데이터 구조에 관한 것입니다. 제거 알고리즘이 다르다는 점을 제외하면 C++의 std :: vector <>과 같은 동적 배열입니다.

일반 동적 배열에서 요소가 제거되면 나머지 요소는 O (1)이 아닌 마지막 요소 인 경우를 제외하고는 O (n)로 이동해야합니다.

어떤 요소가 제거되면 마지막 요소로 대체됩니다. 이것은 물론 요소들의 순서를 잃어 버린다. 그러나 이제 모든 요소의 제거는 일정한 시간입니다.

목록에는 제거 시간이 동일하지만이 구조에는 임의 액세스 권한이 있습니다. 그와 관련된 유일한주의 사항은 주문이 뒤죽박죽이 될 수 있으므로 액세스하는 내용을 알지 못하는 것이므로 어쨌든 임의 액세스가 사용됩니다. 게다가리스트는 요소에 대한 포인터/반복자를 망칠 수 없습니다.

그래서이 구조는 요소를 철저히 지키고 길을 따라 제거하는 매우 구체적인 작업을 제외하고는 오히려 쓸모없는 것처럼 보입니다. 목록에서도 동일한 작업을 수행 할 수 있지만 캐시 성능이 향상됩니다.

그래서이 이상한/쓸모없는 구조에는 이름이 있으며 용도가 있습니까? 아니면 좋은 작은 뇌 폭풍?

Answer 1

이 아이디어는 Knuth (Fisher–Yates) shuffle에서 사용됩니다. 무작위로 선택한 요소는 배열의 마지막 요소로 바뀝니다. 어쨌든 우리가 원하는 것은 무작위 순열이므로, 재정렬은 중요하지 않습니다.

Answer 2

흠, 알고리즘에 실제로 O (1) 제거 시간이 있습니까?

1. 제거 요소를 찾는 것을 의미는 (1) (삭제 된 요소를 대체) 마지막 요소 찾기
2. O (1)
3. 번째 찾는 O이고 마지막 요소 (새로운 "마지막"요소)는 O (1)

... 어떤 데이터 구조에서도 가능하지 않습니다. 더블 링크 된 목록은 이미 제거 할 요소에 대한 포인터를 가지고 있으므로 이러한 제약 조건을 채울 수 있습니다.

Answer 3

이전에는이 ​​방법을 많이 사용 했었습니다. 그러나 나는 그 이름을 모른다.

간단한 예 : 컴퓨터 게임에서 모든 "나쁜 녀석"을 반복하고 자신의 움직임 등을 계산합니다. 한 가지 일은 사라질 것입니다. (죽은 몸은 사라지고 이제는 99 % 투명 해집니다) . 그 시점에서 당신은리스트에서 제거하고, 반복 카운터를 증가시키지 않으면 서 반복자를 재개합니다.

항목을 삭제할 때 Binary Heap에서 이와 비슷한 작업이 수행되지만 다음 단계는 힙 규칙 - O (log n)을 유지 관리하는 것입니다.

Answer 4

그래서이 이상한/쓸모없는 구조에는 이름이 있으며 용도가 있습니까?

저는 다중 프로세스 시스템의 시뮬레이션에서 비슷한 것을 사용했습니다.

상태 시스템으로 구현 된 프로세스의 스케줄러에서 각 프로세스는 외부 이벤트 (활성 또는 완료)를 기다리고 있습니다. 스케줄러에는 프로세스에 대한 포인터의 배열이 있습니다.

처음에는 각 프로세스가 활성화되고 스케줄러는 마지막 대기 및 첫 번째 완료 프로세스의 색인을 갖습니다. 처음에는 0과 배열 길이입니다.

V-- waiting 
[ A-active, B-active, C-active, D-active ] 
          completed --^ 
^- run 

프로세스를 다음 상태로 전환하기 위해 스케줄러가 배열을 반복하고 차례로 각 프로세스를 실행합니다. 프로세스가 대기 중이라고보고하면 배열에서 마지막으로 대기중인 프로세스 이후의 프로세스로 바뀝니다.

  V-- waiting 
[ A-waiting, B-active, C-active, D-active ] 
           completed --^ 
      ^- run 

완료되었다고 신고하면 첫 번째 완성 된 배열보다 먼저 처리됩니다.

  V-- waiting 
[ A-waiting, D-active, C-active, B-completed ] 
        completed --^ 
      ^- run 

그래서 말 또는 완료 대기 활성에서 스케줄러 실행 및 프로세스 전환, 시작시 모든 대기 프로세스, 중간에 모든 활성 사람과 함께 주문하게 배열하고, 완성 된 것과 같은 . 더 활성 프로세스가있을 때

     V-- waiting 
[ A-waiting, C-waiting, D-active, B-completed ] 
        completed --^ 
         ^- run 

반복 특정 숫자 중 후에, 또는 상기 종료 프로세스 배열로부터 세정 외부 이벤트 처리 :

     V-- waiting 
[ A-waiting, C-waiting, D-completed, B-completed ] 
      completed --^ 
         ^- run == completed so stop 

이 유사 그것은 스와핑을 사용하여 컬렉션에서 항목을 제거하지만 양쪽 끝에서 항목을 제거하고 중간에 '컬렉션'을 남겨 두는 것입니다.

Answer 5

Set이라고합니다.

Answer 6

이름은 모르지만 어떤 경우에는 목록보다 좋습니다.

특히 매우 작은 데이터의 경우 단일 연결 목록 또는 이중 연결 목록보다 훨씬 우수합니다. 모든 것을 연속적으로 저장하기 때문에 요소 당 여분의 포인터 오버 헤드가 없습니다.