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

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?

edit: Не уверен, что, возможно, мой вопрос был неясным.Мне нужно иметь возможность доступа к возникшему уклону 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

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

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

edit

`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-й элемент позиции.

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

Answer 2

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

edit добавление данных вашего примера:

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

Answer 3

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

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 4

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

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>>();

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

---

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

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

затем:

var slopeCounts = new List<SlopeCount>();

// fill the list