c - 从数据流 : 中选择前 k 个(百分比)项目的有效算法

Question

我必须重复对包含 300 个随机元素的数组进行排序。但我必须做一种特殊的排序:我需要数组子集中 5% 的最小值，然后计算一些值并增加子集。现在再次计算该值并且子集也增加了。依此类推，直到子集包含整个数组。

子集从前 10 个元素开始，每一步增加 10 个元素。 即:

子集大小 k=ceil(5%*subset)
10 1(所以只是最小的元素)
20 1(所以也是最小的)
30 2(最小和次小)

...

计算的值基本上是所有小于k的元素和特别加权的k最小元素的总和。 在代码中:

k = ceil(0.05 * subset) -1; // -1 because array index starts with 0...  
temp = 0.0; 
for( int i=0  i<k; i++)
    temp += smallestElements[i];
temp += b *  smallestElements[i];

我自己实现了一个基于选择排序的算法(代码在本文末尾)。我使用 MAX(k) 指针来跟踪 k 个最小的元素。因此，我不必要地对所有小于 k 的元素进行排序:/ 此外，我知道选择排序对性能不利，不幸的是，这对我来说至关重要。

我试着想出一种方法来使用一些基于快速排序或堆排序的算法。我知道如果 k 和子集是固定的，quickselect 或 heapselect 非常适合查找 k 最小元素。 但是因为我的子集更像是一个输入数据流，所以我认为基于快速排序的算法会被淘汰。 我知道如果 k 是固定的，heapselect 将非常适合数据流。但是我没有设法在不大幅降低性能的情况下为动态 k 调整堆选择，因此它不如我基于选择排序的版本有效:( 谁能帮我修改动态 k 的堆选择？

如果没有更好的算法，您可能会为我的选择排序实现找到不同/更快的方法。这是我实现的一个最小示例，此示例中未使用计算变量，因此请不要担心。 (在我的真实程序中，我只是手动展开了一些循环以获得更好的性能)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ARRAY_SIZE 300
#define STEP_SIZE 10

float sortStream( float*  array, float**  pointerToSmallest, int k_max){    
    int  i,j,k,last = k_max-1;
    float temp=0.0;

// init first two pointers  
    if( array[0] < array[1] ){  
        pointerToSmallest[0] = &array[0];
        pointerToSmallest[1] = &array[1];
    }else{
        pointerToSmallest[0] = &array[1];
        pointerToSmallest[1] = &array[0];
    }
// Init remaining pointers until i= k_max
    for(i=2; i< k_max;++i){
        if( *pointerToSmallest[i-1] < array[i] ){   
            pointerToSmallest[i] = &array[i];
        }else{  
            pointerToSmallest[i] = pointerToSmallest[i-1];
            for(j=0; j<i-1 && *pointerToSmallest[i-2-j] > array[i];++j)
                pointerToSmallest[i-1-j] = pointerToSmallest[i-2-j];            
            pointerToSmallest[i-1-j]=&array[i];         
        }   
        if((i+1)%STEP_SIZE==0){
            k = ceil(0.05 * i)-1;       
            for(j=0; j<k; j++)
                temp += *pointerToSmallest[j];
            temp += 2 * (*pointerToSmallest[k]);
        }
    }
// Selection sort remaining elements    
    for( ; i< ARRAY_SIZE; ++i){     
        if( *pointerToSmallest[ last ] > array[i] ) {       
            for(j=0; j != last && *pointerToSmallest[ last-1-j] > array[i];++j)
                pointerToSmallest[last-j] = pointerToSmallest[last-1-j];            
            pointerToSmallest[last-j] = &array[i];      
        }       
        if( (i+1)%STEP_SIZE==0){
            k = ceil(0.05 * i)-1;       
            for(j=0; j<k; j++)
                temp += *pointerToSmallest[j];  
            temp += 2 * (*pointerToSmallest[k]);        
        }
    }   
    return temp;

}

int main(void){
    int     i,k_max = ceil( 0.05 * ARRAY_SIZE );
    float*  array = (float*)malloc ( ARRAY_SIZE * sizeof(float));
    float** pointerToSmallest = (float**)malloc( k_max * sizeof(float*));
    for( i=0; i<ARRAY_SIZE; i++)
            array[i]= rand() / (float)RAND_MAX*100-50;

    // just return a, so that the compiler doens't drop the function call
    float a = sortStream(array,pointerToSmallest, k_max);
    return (int)a;
}

非常感谢

Answer 1

通过使用两个堆来存储流中的所有项目，您可以:

1. 在 O(1) 中找到前 p% 的元素
2. 在 O(log N) 中更新数据结构(两个堆)

假设，现在我们有N个元素，k = p% *N,

1. 用于存储前 k 个项目的最小堆 (LargerPartHeap)
2. 用于存储其他 (N - k) 项的最大堆 (SmallerPartHeap)。

SmallerPartHeap 中的所有项都小于或等于 LargerPartHeap 的最小项(top item @LargerPartHeap)。

1. 对于查询“top p% 元素是什么？”，简单地返回 LargerPartHeap

2. 用于更新“来自流的新元素 x”，

   2.a 检查新的 k' = (N + 1) * p%，如果 k' = k + 1，则将 SmallerPartHeap 的顶部移动到 LargerPartHeap。 - O(logN)

   2.b 如果x大于LargerPartHeap的栈顶元素(min element)，则将x插入LargerPartHeap，将LargerPartHeap的栈顶移动到SmallerPartHeap；否则，将 x 插入 SmallerPartHeap - O(logN)