时间戳

首页 > 解决方案 > 从多个数组中查找 k 个最大值和最小值

algorithm - 从多个数组中查找 k 个最大值和最小值

问题描述

我有一个未来生成的数据数组，我有兴趣获得k个最小值和k个最大值。k可以是例如 10% 的数据。由于我的数据非常庞大，我无法一次将所有内容都放入内存中。

我在 MATLAB 中模拟我的想法，以找到最大值和最小值。

x=rand(1,100)*10; %Genearting Randam number

x_sorted= sort(x)'; %True sorting just for testing my code performance

 %Simulating the divided data arrays
divide=4;           
trim_persentage=10;   %Trim persentage to discard data
y = reshape(x, length(x)/divide, divide);
x_local_sorted = sort(y);

%Finding the minima's value array
x_local_trimed_high=x_local_sorted(1:round(size(x_local_sorted,1)*trim_persentage/100),:);
globalsort_lows= sort(x_local_trimed_high(:));

%Finding the maimas's value array
x_local_trimed_low=x_local_sorted(ceil(size(x_local_sorted,1)*trim_persentage/100):end,:);
globalsort_highs= sort(x_local_trimed_low(:));

%Comparing it with True sorting to check performance
sum(x_sorted(1:length(globalsort_lows))==globalsort_lows)/length(globalsort_lows)*100
sum(x_sorted(numel(x_sorted)- 
length(globalsort_highs)+1:end)==globalsort_highs)/length(globalsort_highs)*100

该算法的问题是我没有从数组中获得真正的 10% 最大值和 10% 最小值。有没有更好的方法来解决这个问题？

PS：简化代码并比较两种不同的方法来找到k最大值和最小值。第一种方法由@hadi 提出。

clear all
x=rand(10e3,1)*10;

kvalues=10;
%Simulating the divided data arrays
divide=8;
y = reshape(x, length(x)/divide, divide);
globalMins=[];
globalMaxs=[];

%Method 1
tic
for q=1:size(y,2)
    
    mi=find_k_min(y(:,q),kvalues);
    ma=find_k_max(y(:,q),kvalues);

    globalMins=[globalMins mi];
    globalMaxs=[globalMaxs ma];
    
end
Min_1st=sort(globalMins);
Max_1st=sort(globalMaxs);
toc

globalMins=[];
globalMaxs=[];

%Method 2
tic
for q=1:size(y,2)
    z=sort(y(:,q));
    mi=z(1:kvalues);
    ma=z(end-kvalues+1:end);
    globalMins=[globalMins; mi];
    globalMaxs=[globalMaxs; ma];
end

Min2nd=sort(globalMins);
Max2nd=sort(globalMaxs);
toc

function out=find_k_max(in,kvalue)
ma=zeros(1,kvalue);

for i=1:kvalue
    [ma(i),I]=max(in);
    in(I)=[];
end
out=ma;
end

function out=find_k_min(in,kvalue)
mi=zeros(1,kvalue);

for i=1:kvalue
    [mi(i),I]=min(in);
    in(I)=[];
end
out=mi;
end

多次运行的代码输出是

(1)
Elapsed time is 0.008850 seconds.
Elapsed time is 0.004439 seconds.
(2)
Elapsed time is 0.006718 seconds.
Elapsed time is 0.004550 seconds.
(3)
Elapsed time is 0.007108 seconds.
Elapsed time is 0.004618 seconds.

与 min 和 max 方法相比，排序和修剪方法（方法 2）更有效。

这个处理代码运行性能的效率；这很重要。但是，我正在寻找一种有效的方法来找到 k 个最小值或最大值。

标签： algorithmmatlabsortingmaxmin

解决方案

更详细地查看您的代码，我意识到您不是在寻找一些最小和最大值，而是大量。仅当k << n即值的总数 (AFAIK)时，有效地找到k个最小值的技术才有效。

您的技术涉及在每个子数组中查找 10% 的最小值，但不能保证 10% 的最小值总体上并不都在同一个子数组中。使这项工作正确的唯一方法是确定k，要找到的值的总数，然后在一个子数组中找到k个最小值，将这些值添加到第二个子数组，得到结果组合的k个最小值, 并对其他子数组重复此操作。最后，您将拥有k个最小值。当然，这不是有效的，并且它限制了子数组的大小。

要在数组中找到 10% 的最小值，我会首先找到第 10 个百分位，这比对整个数组进行排序更有效，然后找到小于或等于该百分位的所有值。

不幸的是，不可能通过单独计算每个数组中的百分位数来确定许多子数组的百分位数。您最终会遇到与我在第二段中描述的完全相同的问题。

但是您可以使用直方图找到近似值。如果您对数据中值的分布有所了解，则可以修复直方图参数。否则，您需要遍历数据并收集最小值和最大值。有了这些，您可以再次修复直方图参数。现在计算每个子数组的直方图并将它们加在一起。

从直方图中，您可以估计第 10 个百分位数。为其添加一个边距（使值大一点），然后收集数据集中低于此估计值的所有值。最后，从这个集合中删除最大值，直到你有合适的大小。

当然，你可以对 10% 的最大值做同样的事情。

推荐阅读