스팬에 대한 빠른 분

Question

배열 목록과 많은 설정 시간이 있으면 각 배열의 일부 하위 범위에서 가장 작은 값을 빨리 찾아야합니다. 개념 :

class SpanThing 
{ 
    int Data; 
    SpanThing(int[][] data) /// must be rectangulare 
    { 
     Data = data; 
     //// process, can take a while 
    } 

    int[] MinsBruteForce(int from, int to) 
    { 
     int[] result = new int[data.length]; 
     foreach(int index, int[] dat; Data) 
     { 
      result[i] = int.max; 
      foreach(int v; dat[from .. to]); 
       result[i] = min(result[i], v); 
     } 
     return result; 
    } 
    int[] MinsSmart(int from, int to) 
    { 
      // same as MinsBruteForce but faster 
    } 
} 

각 노드는 관련 기간에 최소가 들어있는 데이터에 이진 트리를 구축하는 것이 작업을 수행하는 방법에 대한 나의 현재의 생각. 그런 식으로 하나의 행에 대한 스팬의 최소값을 구하는 것은 그것을 구성하는 트리 노드 만의 최소값을 찾는 것으로 구성됩니다. 이 집합은 각 행에 대해 동일하므로 한 번 계산할 수 있습니다.

누구나이 아이디어에 대해 문제점을 보거나 더 나은 방법을 알고 있습니까?

---

내가 이야기하고있는 트리 루트 노드가 전체 행에 대해 각 노드에 대한 최소 값을 포함 것이라고 sutch를 설정됩니다, 명확히하기 위해, 그것은을위한 최소 값을 가질 것이다 아이를 남아 부모의 스팬의 왼쪽 절반, 오른쪽의 스팬.

0 5 6 2 7 9 4 1 7 2 8 4 2 
------------------------------------------------ 
    | 5 | 6| | 7 | 9 | | 1 | 7 | 2 | 8 | 4 | 2 
0 | 5 | 2 | 7 | 4 | 1 | 2 | 2 
    0  | 2  | 1  |  2 
      0   |   1 
         0 

이 트리

배열에 매핑 세그먼트 경계를 신속 룩업의 결과로 산출 될 수있는 방식으로 정의 될 수있다.

내가 최적화하려는 경우 고정 된 입력 집합과 많은 프론트 시간이 있지만 그 다음에 여러 가지 빠른 테스트를 수행해야합니다.

Answer 1

귀하의 제안 솔루션은 일정한 공간 오버 헤드, 일정 시간 설정 및 쿼리에 대한 로그 시간을 사용하여 대답을 줄 것으로 보인다. 이차 공간 (예 : 모든 간격을 미리 계산)을 지불하려는 경우 일정한 시간 내에 답변을 얻을 수 있습니다. 귀하의 로그 계획은 거의 확실합니다.

더 잘할 수 있다면 놀라지 않을 것이지만, 간단한 데이터 구조가 있다면 충격을받을 것입니다. 실제로는 로그 시간이 거의 항상 충분합니다. 충분히 빠르다. 그것을 위해 가라.

Answer 2

설명한 접근 방식은 사용자가 memoization 일종의 캐싱을 시도하는 것처럼 들리지만 동일한 범위 또는 중첩 된 범위를 반복적으로 확인하는 경우에만 도움이됩니다.

분에 대한 일반적인 경우 ([0..N]) 당신이 이미 가지고 무엇을 O (n)이을 될 것입니다.

코드는 배열의 실제 숫자보다 배열의 순서가 더 중요합니다. 이 기간을 반복해서 확인하려면 데이터를 먼저 정렬하는 것이 가능합니까? O (n log n) 작업 다음에 O (1) ops의 묶음이 올 수 있습니다. 대부분의 언어는 표준 라이브러리에 sorting algorithm에 내장되어 있습니다.

Answer 3

설명 된 트리 접근 방식을 사용하여 간격의 계층 구조를 효과적으로 표현할 수있는 방법은 명확하지 않습니다. 간격을 나누는 방법은 여러 가지가 있습니다. 모든 가능성을 고려해야합니까?

이렇게 간단한 방법으로 충분합니까? data이 N x M 배열 인 것으로 가정합니다. 엔트리 (i,j,k)이 data(k,i:j)의 "최소값"을 제공하는 M x M x N 배열을 만들 것입니다. 배열 항목은 수요에 채워집니다 :

int[] getMins(int from, int to) 
{ 
    assert to >= from; 

    if (mins[from][to] == null) 
    { 
     mins[from][to] = new int[N]; 

     // populate all entries (from,:,:) 
     for (int k = 0; k < N; k++) 
     { 
      int t = array[k][from]; 

      for (int j = from; j < M; j++) 
      { 
       if (array[k][j] < t) 
        t = array[k][j]; 

       mins[from][j][k] = t; 
      } 
     } 
    } 

    return mins[from][to]; 
}