3

I have an Array with 1 and 0 spread over the array randomly.

int arr[N] = {1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1....................N}

Now I want to retrive all the 1's in the array as fast as possible, but the condition is I should not loose the exact position(based on index) of the array , so sorting option not valid. So the only option left is linear searching ie O(n) , is there anything better than this.

The main problem behind linear scan is , I need to run the scan even for X times. So I feel I need to have some kind of other datastructure which maintains this list once the first linear scan happens, so that I need not to run the linear scan again and again.

Let me be clear about final expectations-

I just need to find the number of 1's in a certain range of array , precisely I need to find numbers of 1's in the array within range of 40-100. So this can be random range and I need to find the counts of 1 within that range. I can't do sum and all as I need to iterate over the array over and over again because of different range requirements

4

6 回答 6

8

我很惊讶您将排序视为线性搜索的更快替代方案。

如果您不知道它们出现在哪里，那么没有比线性搜索更好的方法了。也许如果你使用位或char数据类型，你可以做一些优化，但这取决于你想如何使用它。

您可以对此进行的最佳优化是克服分支预测。因为每个值都是零或一，所以您可以使用它来提升用于存储一索引的数组的索引。

简单的方法：

int end = 0;
int indices[N];

for( int i = 0; i < N; i++ )
{
    if( arr[i] ) indices[end++] = i;  // Slow due to branch prediction
}

无分支：

int end = 0;
int indices[N];

for( int i = 0; i < N; i++ )
{
    indices[end] = i;
    end += arr[i];
}

[编辑]我测试了上述内容，发现没有分支的版本快了近 3 倍（在随机填充的 1 亿个元素数组上重复 20 次时为 4.36 秒与 11.88 秒）。

回到这里发布结果，我看到你已经更新了你的要求。使用动态编程方法，你想要的真的很容易......

您所做的只是创建一个元素大一个的新数组，该数组存储从数组开头到（但不包括）当前索引的个数。

arr   :   1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1
count : 0 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 5 6 6 6 6 7

（我已经在arr上面偏移了，所以它排列得更好）

现在您可以在 O(1) 时间内计算任意范围内 1 的数量。要计算 indexA和之间的 1 的数量B，您只需执行以下操作：

int num = count[B+1] - count[A];

显然，您仍然可以使用非分支预测版本来生成最初的计数。所有这些都应该给你一个很好的加速比对每个查询求和的天真的方法：

int *count = new int[N+1];
int total = 0;

count[0] = 0;

for( int i = 0; i < N; i++ )
{
    total += arr[i];
    count[i+1] = total;
}


// to compute the ranged sum:
int range_sum( int *count, int a, int b )
{
    if( b < a ) return range_sum(b,a);
    return count[b+1] - count[a];
}
于 2013-05-15T05:12:16.027 回答
3

好吧，一次线性扫描就可以了。由于您正在寻找跨阵列范围的多次扫描，我认为这可以在恒定时间内完成。干得好：

  1. 扫描数组并创建一个位图，其中键 = 数组的键 = 序列 (1,2,3,4,5,6....)。存储在位图中的值将是一个tuple<IsOne,cumulativeSum>where isOne 是你是否有一个累积总和是你遇到它们时加 1

    数组 = 1 1 0 0 1 0 1 1 1 0 1 0

    元组： (1,1) (1,2) (0,2) (0,2) (1,3) (0,3) (1,4) (1,5) (1,6) (0, 6) (1,7) (0,7)

  2. 案例 1：当累积和的下限为 0 时。1 的数量 [6,11] = 第 11 位的累积和 - 第 6 位的累积和 = 7 - 3 = 4

    案例 2：当累积和的下限为 1 时。1 的数量 [2,11] = 第 11 位的累积和 - 第 2 位的累积和 + 1 = 7-2+1 = 6

第 1 步是 O(n)

第 2 步是 0(1)

毫无疑问，总复杂度是线性的，但是对于您必须处理范围数倍的任务，如果您有足够的内存，上述算法似乎会更好:)

于 2013-05-15T06:21:24.060 回答
1

它必须是一个简单的线性数组数据结构吗？或者您是否可以创建自己的数据结构，该结构恰好具有所需的属性，您可以为其提供所需的 API，但可以隐藏（封装）其实现细节？

如果您可以实现自己的并且有一定的稀疏性保证（到 1 或 0），那么您可能能够提供比线性性能更好的性能。我看到您想要保留（或能够重新生成）确切的流，因此您必须为此存储一个数组或位图或运行长度编码。（如果流实际上是随机的而不是任意的，则 RLE 将毫无用处，但如果存在显着的稀疏性或带有长字符串的模式，则可能非常有用。例如，位图图像的黑白光栅通常是一个很好的候选者RLE)。

假设您保证流将是稀疏的 --- 例如，不超过 10% 的位将为 1（或者相反，超过 90% 的位将是）。如果是这种情况，那么您可以在 RLE 上为您的解决方案建模并维护所有 1 的计数（只需在设置位时递增，在清除它们时递减）。如果可能需要快速获取这些元素的任意范围的设置位数，那么您可以使用大小方便的计数器数组来代替单个计数器，以用于流的分区。（在这种情况下，大小方便意味着可以轻松放入内存、缓存或寄存器集，但在计算总和（所有分区完全在范围内）和线性扫描之间提供了合理的折衷。

对于一个非常非常大的流，您甚至可以拥有分区总和的多层“索引”——从最大（最粗略）的粒度向下遍历到任一端的“片段”（使用下一层分区sums) 并仅对小片段进行线性搜索。

显然，这样的结构代表了构建和维护结构的复杂性（插入需要额外的操作，并且对于 RLE，除了追加/前置之外的任何东西都可能非常昂贵）与执行任意长的线性搜索/增量的费用之间的权衡扫描。

于 2013-05-15T06:29:23.590 回答
0

为什么排序无效？您可以克隆原始数组，对克隆进行排序，并1根据需要计算和/或标记 s 的位置。

于 2013-05-15T06:11:41.127 回答
0

您使用的是 C（或派生语言）吗？如果是这样，您可以控制数组的编码吗？例如，如果您可以使用位图进行计数。位图的好处是您可以使用查找表来汇总计数，但如果您的子范围末端不能被 8 整除，您将不得不专门处理末端部分字节，但加速将是显着的.

如果不是这样，您至少可以将它们编码为单个字节吗？在这种情况下，如果存在稀疏性，您也许可以利用它（更具体地说，希望经常有多个零索引条带）。

因此对于：

u8 input = {1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1....................N};

您可以编写类似（未经测试）的内容：

uint countBytesBy1FromTo(u8 *input, uint start, uint stop)
{ // function for counting one byte at a time, use with range of less than 4,
  // use functions below for longer ranges
  // assume it's just one's and zeros, otherwise we have to test/branch
    uint sum;
    u8 *end = input + stop;
    for (u8 *each = input + start; each < end; each++)
        sum += *each; 
    return sum;
}

countBytesBy8FromTo(u8 *input, uint start, uint stop)
{
    u64 *chunks = (u64*)(input+start);
    u64 *end = chunks + ((start - stop) >> 3);
    uint sum = countBytesBy1FromTo((u8*)end, 0, stop - (u8*)end);
    for (; chunks < end; chunks++)
    {
        if (*chunks)
        {
            sum += countBytesBy1FromTo((u8*)chunks, 0, 8);
        }
    }
}

基本技巧是利用将目标数组的切片转换为语言可以一口气查看的单个实体的能力，并通过推理测试它的任何值是否为零，然后跳过整个块。零越多，效果就越好。在您的大整数总是至少有一个的情况下，这种方法只会增加开销。您可能会发现使用 u32 更适合您的数据。或者在 1 和 8 之间添加一个 u32 测试会有所帮助。对于零比零更常见的数据集，我已经使用了这种技术。

于 2013-05-15T06:06:17.360 回答
0

如果：

  1. 目的是能够随时找到数组中1的个数，
  2. 鉴于数组中相对较少的值可能会在您想知道数字的时刻和另一时刻之间发生变化，并且
  3. 如果您必须在不断变化的n值数组中找到 1 的数量m，

...您当然可以比m使用缓存策略检查数组中的每个单元格做得更好。

正如其他人指出的那样，第一次需要 1 的数量时，您当然必须检查每个单元格。但是，如果您随后将 1 的数量存储在一个变量（sum例如，该函数可以添加到，并且每次在数组中用 a 替换 a时，该函数都可以从中减去。update()01update()1sum10update()1sum

因此，sum在第一次计算数组中 1 的数量后，它始终是最新的，无需进一步计数。

（编辑考虑更新的问题）

如果需要返回数组给定范围内的 1 的数量，可以使用比我刚刚描述的更复杂的缓存策略来完成。

您可以在数组的每个子集中保留 1 的计数，并在该子集中将 0 更改为 1 时更新相关子集计数，反之亦然。查找数组中给定范围内 1 的总数将是添加完全包含在该范围内的每个子集中 1 的数量，然后计算该范围内但不在该范围内的 1 的数量。已经计算过的子集。

根据情况，可能值得进行分层排列，其中（例如）整个数组中 1 的数量位于层次结构的顶部，每个1/q th数组中 1 的数量位于第二层层次结构，每个1/(q^2) th数组中 1 的数量在层次结构的第三级，等等。例如，对于q = 4，您将在顶部有 1 的总数，在第二个数组的每个四分之一中的 1 的数量级别，第三级数组中每十六分之一的 1 的数量等。

于 2013-05-15T05:27:46.917 回答