Эффективный способ поиска элемента по индексу в массиве с объединенным счетчиком

Question

У меня есть объект, который содержит два массива, первый массив массива:

double[] Slopes = new double[capacity];

Следующим является массив, содержащий количество различных наклонов:

int[] Counts = new int[capacity];

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

т.е. если у меня есть склоны 15 15 15 12 4 15 15, я получаю:

Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }

Есть ли лучший способ найти элемент i_th на склонах, чем перебирать Counts с индексом и найти соответствующий индекс в Slopes?

редактировать: не уверен, если, возможно, мой вопрос не был ясен. Мне нужно иметь возможность доступа к возникшему уклону i_th, поэтому в примере с нулевым индексированным уклоном i = 3, равным 12, вопрос заключается в том, существует ли более эффективное решение для нахождения соответствующего уклона в новой структуре.

Может быть, это поможет лучше понять вопрос: вот как я теперь получаю элемент i_th:

public double GetSlope(int index)
        int countIndex = 0;
        int countAccum = 0;
        foreach (int count in Counts)
        {
            countAccum += count;
            if (index - countAccum < 0)
            {
                return Slopes[countIndex];
            }
            else
            {
                countIndex++;
            }
        }
        return Slopes[Index];
}

Мне интересно, есть ли более эффективный способ?

Answer 1

Вы можете использовать третий массив для хранения первого индекса повторяющегося уклона

double[] Slopes = new double[capacity];
int[] Counts = new int[capacity]; 
int[] Indexes = new int[capacity]; 

С

Slopes  = { 15, 12, 4, 15 }
Counts  = {  3,  1, 1,  2 } 
Indexes = {  0,  3, 4,  5 } 

Теперь вы можете применить бинарный поиск в Indexes найти индекс, который меньше или равен тому, который вы ищете.

Вместо того, чтобы иметь O(n) производительность поиска, теперь у вас есть O(log(n)).

Answer 2

Вы всегда можете обернуть существующие массивы и другой массив (назовите его OriginalSlopes), в класс. Когда вы добавляете в SlopesВы также добавляете к OriginalSlopes как вы бы нормальный массив (т.е. всегда добавлять). Если вам нужно i_th наклон, посмотрите в OriginalSlopes, O(1) операции вокруг.

отредактируйте, добавив данные вашего примера:

Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }
OriginalSlopes = { 15, 15, 15, 12, 4, 15, 15 }

Answer 3

Если вы загружаете склоны одновременно и выполняете многие из этих поисков "i-го элемента", это может помочь иметь третий (или вместо счетчиков, в зависимости от того, для чего он используется) массив с итогами. Это было бы { 0, 3, 4, 5 } для вашего примера. Тогда вам не нужно складывать их при каждом поиске, это просто вопрос "есть ли между Итоги [x] и Итоги [x + 1]". Если вы ожидаете, что у вас будет мало сегментов наклона, или если уклоны будут добавлены во время обработки, или если вы не будете выполнять многие из этих поисков, это, вероятно, ничего не купит. По сути, это просто делает все эти дополнения одновременно.

Answer 4

В объекте count (или массиве в вашей базе) вы добавляете переменную, которая имеет cumulative count что вы нашли до сих пор.

Используя бинарный поиск с comparator метод сравнения cumulative count Вы сможете найти наклон за время O(log N).

редактировать

`Data = 15 15 15 12 4 15 15`
Slopes = { 15, 12, 4, 15 }
Counts = {  3,  1, 1,  2 }
Cumulative count = { 3, 4, 5, 7}

Например, если вы ищете элемент на 6-й позиции, когда вы ищете в Cumulative count Набор данных и найти значение 5, и знать следующее значение равно 7, вы можете быть уверены, что элемент с этим индексом будет также 6-й элемент позиции.

Используйте бинарный поиск, чтобы найти элемент в журнале (N) времени.

Answer 5

Почему не Dictionary<double, double> с key Склоны и тому value Быть рассчитывает?

Хм, дабл дабл? Теперь мне нужен кофе...

Answer 6

РЕДАКТИРОВАТЬ: Вы можете использовать словарь, где ключ является наклон, а значение каждого ключа является список соответствующих индексов и счетчиков. Что-то вроде:

class IndexCount
{
    public int Index { get; set; }
    public int Count { get; set; }
}

Ваша декларация коллекции будет выглядеть примерно так:

var slopes = new Dictionary<double, List<IndexCount>>();

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

---

Вы можете использовать один List<> типа, который связывает наклоны и счетчики, что-то вроде:

class SlopeCount
{
    public int Slope { get; set; }
    public int Count { get; set; }
}

затем:

var slopeCounts = new List<SlopeCount>();

// fill the list