4
작은/중간 크기의 슬라이딩 윈도우 (일반적인 크기는 600, 모든 요소는 정수)에 대해 최소/최대를 유지할 수있는 특정 알고리즘이 있습니까? 이 창은 실제로 스트림의 마지막 N 관측입니다. 그래서 새로운 관측치를 추가하고 각 시간 단위에서 가장 오래된 관측치를 제거합니다. 그래서 최후의 N obervations에 대해 최소값과 최대 값을 유지하고 싶습니다.슬라이딩 윈도우의 최소값
전체 데이터를 유지 관리하지 않기 때문에 Sliding window minimum algorithm에 나와있는 것과 다른 문제이므로 "인덱스 기반"솔루션은 여기에 적용되지 않습니다. 또한 입력 데이터 자체가 순환 배열로 나타납니다.
힙이 너무 잘 작동하지 않을 수 있습니다. 최소/최대 요소를 삭제/팝하지 않지만, 가장 먼저 힙을 가져 오는 목적을 무효화 할 가장 오래된 요소입니다.
로그와 같은 복잡성 기반 구조 (red - black trees)는 정상적으로 작동하며, 스플레이 트리는 내가 가지고있는 데이터 유형에 더 적합 할 수 있지만, 과도한 과도한 공격입니다. 내가 처리 할만한 크기?
나중에는 결코 도움이되지 않을 수도 있습니다. 실제로 알고리즘이 있습니다 : http://home.tiac.net/~cri/2001/slidingmin.html – Wam
위 링크는 작동하지 않지만 archive.org : http : //web.archive에서 버전을 발견했습니다. org/web/20120805114719/http : //home.tiac.net/~cri/2001/slidingmin.html – user674669
실제로 증가하는 색인을 추적 할 필요는 없으며이를 창 크기를 모듈로 추적하면됩니다. 따라서 귀하의 경우 인덱스는 0에서 599로 이동 한 다음 다시 0으로 이동합니다. –