Быстрая мин на пролете

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
     }
}

В настоящее время я думаю о том, как это сделать, чтобы построить двоичное дерево данных, где каждый узел содержит минимум в соответствующем интервале. Таким образом, нахождение минимума в промежутке для одной строки будет состоять из нахождения минимума только тех узлов дерева, которые его составляют. Этот набор будет одинаковым для каждой строки, поэтому может быть вычислен один раз.

Кто-нибудь видит какие-либо проблемы с этой идеей или знает лучшие способы?

---

Для пояснения, дерево, о котором я говорю, будет создано таким образом, чтобы корневой узел содержал значение min для всей строки, а для каждого узла его левый потомок имел значение min для левой половины родительский промежуток и то же самое для права.

 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

Ваш описанный подход звучит так, как будто вы пытаетесь выполнить какое-то запоминание или кэширование, но это поможет вам, только если вы неоднократно проверяете одни и те же или вложенные участки.

Общий случай для min ([0..n]) будет O (n) , что у вас уже есть.

Ваш код, похоже, больше заботится о реальных числах в массиве, чем об их порядке в массиве. Если вы собираетесь многократно проверять эти промежутки, возможно ли сначала просто отсортировать данные, что может быть одна операция O (n log n) , за которой следует набор O ( 1) опс? Большинство языков имеют своего рода встроенный алгоритм сортировки в своих стандартных библиотеках.

Answer 3

Не ясно, как мы можем эффективно представить иерархию интервалов, используя описанный вами древовидный подход. Есть много способов разделить интервал - мы должны рассмотреть каждую возможность?

Достаточно ли простого подхода, подобного этому: предположим, data - это массив N x M. Я хотел бы создать массив M x M x N, где запись (i,j,k) дает "мин" data(k,i:j). Записи массива будут заполняться по требованию:

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];
}