Как я могу запустить обновление на нескольких счетчиках быстрее?

Question

У меня есть массив переменных счетчика (все инициализированы в 0). У меня есть k инструкций, которые мне нужно запустить в массиве. Инструкция состоит в увеличении всех значений массива между начальным и конечным индексами (оба включительно).
Например:

n = 5, k = 2
arr = [0,0,0,0,0]
0,2 - (arr = [1,1,1,0,0])
0,1 - (arr = [2,2,1,0,0])

Наконец, мне нужно отсортировать это по убыванию порядок значений счетчика, который легко.
Я сталкиваюсь с проблемой написания кода, чтобы сделать это во время менее чем за O (N ^ 2) сложность времени. Я должен использовать две петли.

Array counts = [0,0,0,0... n times]
for(Instruction instruction:instructions){
    int start = instruction.start;
    int end = instruction.end;
    for(i=start;i<=end;i++){
        counts.set(i,counts.get(i)+1);
    }
}

Есть ли способ сделать это быстрее? Я также согласен с очисткой массива count и принятием любой структуры данных, необходимой для достижения этой цели.

Answer 1

Пусть n будет длиной массива счетчиков. Мы можем думать о счетчике как о последовательности n символов; с n = 5 мы имеем

. . . . .

Мы можем интерпретировать каждую инструкцию (start, end) как директиву, чтобы заключить скобки вокруг некоторых элементов. Например,

1. (0, 2) => (. . .) . .
2. (0, 1) => ((. .) .) . .

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

Вот один из способов сделать это, обозначив ( на +1, ) на -1 и взяв кумулятивную сумму (в Python).

import numpy as np

# counter array with 5 elements
ctr = np.zeros(5+1)
instructions = [(0, 2), (0, 1)]
for s, e in instructions:
  ctr[s] += 1
  ctr[e+1] -= 1

result = ctr.cumsum()[:5]
print(result)
# [2. 2. 1. 0. 0.]

При условии доступа к массиву с постоянным временем, это O(N + M), где N - количество команд, а M - размер счетчика.

Кстати, сортировку можно также выполнять за линейное время с помощью сортировки по осям или сортировки по счетам, поскольку вы работаете с целыми числами.

Answer 2

Во-первых; преобразовать его в другую форму. В частности, преобразуйте оригинал «увеличить каждый элемент от начала до конца» в «добавить V к каждому элементу от начала до конца», найдя перекрывающиеся диапазоны в оригинале и объединяя их.

Например, «добавить 1» к пунктам с 1 по 5, затем добавьте 1 к пунктам с 3 по 8 «станет», добавьте 1 к пунктам с 1 по 2, затем добавьте 2 к пунктам с 3 по 5, затем добавьте 1 к пунктам с 6 по 8.

Это означает, что к каждому элементу в массиве происходит прикосновение только один раз (и никогда не увеличивается несколько раз).

Second; Вы можете получить небольшую скорость в сортировке, введя «добавить ноль к элементам от начала до конца» (чтобы каждый элемент в массиве включался в один диапазон), отсортировав элементы в каждом диапазоне, а затем объединяя финальный предварительно отсортированные диапазоны. Здесь я думаю, что, объединяя диапазоны в порядке добавленной к ним стоимости и отслеживая «наивысшее значение на данный момент», иногда вы обнаружите, что добавленная к диапазону величина больше, чем «наивысшее значение на данный момент», и вы можете просто объединить / скопировать вместо слияния (и избегать ветвей «если значение1 меньше значения2»).

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

Примечание: если массив всегда инициализируется заранее равным нулю (а не просто инициализируется нулем один раз и затем периодически обновляется после этого); тогда «сложение» становится «установкой»; сортировки не будет (так как все значения в диапазоне будут одинаковыми), и вы всегда сможете объединять, а не объединять. Другими словами, вы можете сгенерировать целый новый массив (и не потрудиться заранее инициализировать массив нулями).

Answer 3

Это не решение, извините, но, возможно, может помочь.

Вместо того, чтобы считать их, закажите Instructions на end, тогда, когда вам нужно данное число x, используйте двоичный поиск, чтобы найти x (если вы используете java, есть Array.binarySearch, который сделает это, или если он не может найти искомый номер, точку вставки), тогда go в обратном направлении и считать элемент до end == x и go вперед до x >= start

// instructions sorted by end
// need to find the "occurrence of x"
int occurence = 0;
int pos = instructions.binarySearch();
int i = pos;
while(instructions[i].end == x){
   count++ ;
   i++;
}
i = pos;
while(instructions[i].start <= x){
   if( x <= instructions[i].end)
       count++;
   i++;
}
// count now has the number of occurrence  of x (number of range [start, end] that contains x)

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