2

我有一个包含两个数组的对象，第一个是斜率数组：

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 }

Counts有没有比用索引遍历 并在 中找到相应索引更好的方法来找到斜坡中的第 i 个项目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];
}

我想知道是否有更有效的方法？

4

6 回答 6

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 }

现在，您可以在 serach 中应用二进制搜索Indexes来查找小于或等于您要查找的索引的索引。

现在的搜索性能不是 O(n)，而是 O(log(n))。

于 2012-02-02T16:54:25.700 回答
1

您始终可以将现有数组和另一个数组（称为它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 }
于 2012-02-02T16:54:56.993 回答
1

在 counts 对象（或您的基础中的数组）中，您添加一个具有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 位元素。

使用二进制搜索在 log(N) 时间内查找元素。

于 2012-02-02T16:56:47.650 回答
1

如果您一次加载斜率并执行许多这些“第 i 项”查找，则使用总数的第三个（或代替 Counts，取决于其用途）数组可能会有所帮助。这将是{ 0, 3, 4, 5 }你的例子。然后你不需要为每次查找添加它们，这只是“我在 Totals[x] 和 Totals[x + 1] 之间”的问题。但是，如果您希望有很少的坡度桶，或者如果在整个处理过程中添加了坡度，或者如果您不进行很多此类查找，那么它可能不会给您带来任何收益。本质上，这只是预先一次性完成所有这些添加。

于 2012-02-02T16:52:26.250 回答
0

编辑：您可以使用字典，其中键是斜率，每个键的值是相应索引和计数的列表。就像是：

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
于 2012-02-02T16:29:27.887 回答
0

为什么不Dictionary<double, double>使用key存在斜坡和value存在计数？

嗯，双双？现在我需要一杯咖啡...

于 2012-02-02T16:32:34.247 回答