從多個陣列中找出最大和最小的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。

 %模擬分割資料陣列
divide=4。          
trim_persentage=10; %Trim persentage以丟棄資料。
y = reshape(x, length（x）/divide, divide);
x_local_sorted = sort（y）。

%尋找最小值的陣列。
x_local_trimed_high=x_local_sorted(1: round(size(x_local_sorted,1)*trim_persentage/100)，：)。
globalsort_lows= sort(x_local_trimed_high(:) )。

%尋找maimas的值陣列。
x_local_trimed_low=x_local_sorted(ceil（size(x_local_sorted,1）*trim_persentage/100）。 end,:)。
globalsort_highs= sort(x_local_trimed_low(:) )。

%與True排序比較以檢查性能。
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%最小的值。有什么更好的方法來解決這個問題嗎？

P.S: 簡化代碼并比較兩種不同的方法來尋找k最大和最小值。第一種方法是由@hadi提出的。

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

kvalues=10。
%Simulating the divided data arrays8;
y = reshape(x, length（x）/divide, divide);
globalMins=[];
globalMaxs=[]。

%Method 1[/span
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[/span]。
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; in(I)=[]; in(I)=[].
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)=[]。
結束結束。

多次運行的代碼輸出是

(1)
消耗的時間是0.008850秒。
經過的時間是0.004439秒。
(2)
經過的時間是0.006718秒。
經過的時間是0.004550秒。
(3)
經過的時間是0.007108秒。
經過的時間是0.004618秒。

與最小和最大方法相比，排序和修剪的方法作業（方法2）很有效率。

這就處理了代碼運行性能的效率；這很重要。然而，我正在尋找一種有效的方法來找到最小或最大的k值。

uj5u.com熱心網友回復：

更詳細地看你的代碼，我意識到你不是在尋找幾個最小和最大的值，而是大量的。只有當k <<n，即值的總數時，有效地找到k最小值的技術才是有效的（AFAIK）。

你的技術涉及到在每個子陣列中找到 10% 的最小值，但是不能保證總體上 10% 的最小值不都在同一個子陣列中。唯一能使其正常作業的方法是確定k，即要找到的值的總數，然后在一個子陣列中找到k最小的值，將這些值添加到第二個子陣列中，得到所得組合中k最小的值，并在其他子陣列中重復這一程序。最后，你將得到k最小的數值。當然，這并不高效，而且它限制了子陣列的大小。

為了找到陣列中 10% 的最小值，我首先會找到第 10 個百分位數，這比對整個陣列進行排序要有效得多，然后找到所有小于或等于這個百分位數的數值。

不幸的是，通過分別計算每個陣列的百分位數來確定許多子陣列的百分位數值是不可能的。你最終會遇到與你遇到的和我在第二段中描述的完全相同的問題。

但是你可以使用直方圖找到一個近似值。如果你對資料中的數值分布有一定的了解，那么你可以固定你的直方圖引數。否則，你需要對資料進行回圈，收集最小和最大值。 有了這些，你可以再次固定直方圖引數。現在計算每個子陣列的直方圖，并將它們全部加在一起。

從直方圖中你可以估計出第10個百分點。給它添加一個余量（讓數值大一點），然后收集資料集中低于這個估計值的所有數值。最后，從這個集合中移除最大的值，直到你有合適的大小。

當然，你也可以對10%的最大值采取同樣的做法。

uj5u.com熱心網友回復：

試試這個：

x=rand（1,100）*10。%Genearting Randam number[/span]。
x_max = x(1)。
x_min = x(1)。
%%比較陣列的每個位置。
for i = 2:length（x）。
  if x(i) > x_max
    x_max = x(i); % 更新最大值。
  結束。
  if x(i) < x_min
    x_min = x(i); %更新最小值。
  結束。
end
%% 列印輸出
disp(['Maximum Value = ',num2str(x_max)] )。
disp(['Minimum Value = ',num2str(x_min)])。

請讓我知道它是如何進行的！

uj5u.com熱心網友回復：

根據評論，你可以用min(array), max(array)來找到min和max 然后從陣列中洗掉該值，再做同樣的事情，直到你找到6個最小值和6個最大值。 sort函式非常昂貴。

x=rand(100,1)*10。
for i=1: 6 
    [mi(i),I]=min（x）。
    x(I)=[]。
    [ma(i),I]=max(x)。
    x(I)=[]。
結束。

如果x非常大，你可以使用高大的陣列，或者你可以將x切成片狀 :

x=rand(4e6,1) 。
mi=[]。
ma=[];
for s=1: 4
    mi=[mi;find_6_min(x((s-1)*1e6 1:s*1e6）]。
    ma=[ma;find_6_max(x((s-1)*1e6 1:s*1e6)]。
結束。
mi=find_6_min(mi)。
ma=find_6_max(ma)。

function out=find_6_min（in）
    for i=1: 6 
        [mi(i),I]=min（x）。
        x(I)=[]。
    結束。
結束。
function out=find_6_max（in）
    for i=1: 6 
        [ma(i),I]=max（x）。
        x(I)=[]。
    結束。
結束。

uj5u.com熱心網友回復：

你可以將同樣的概念擴展到更大的陣列上

標籤：

上一篇：數獨消除策略

下一篇：為一個有最大偏移量上限的日期范圍api請求查找所有子范圍