arrays - ابحث عن كل عنصر أقل من عنصر إلى اليمين




performance matlab (4)

NKN لديها الحق. فرز.

x = some_vector_values;  

[Y,I]=sort(x);  %sort in order, get indices
dy=gradient(Y); %get difference vector same size as input vector
ind=find(dy~=0);%ignore places that are equal to the value of interest

for m = 1 : length(ind)
    do_such_and_such to Y(ind(m));
end

حظا سعيدا

أنا بحاجة إلى العثور على عناصر من ناقلات التي هي أقل من واحد من أكثر العناصر التي تأتي بعد ذلك. من السهل القيام به في حلقة:

x = some_vector_values;
for m = 1 : length(x)
  if( any( x(m+1:end) > x(m) )
    do_such_and_such;
  end
end

ولكن السرعة تقتلني. أنا خدش رأسي في محاولة التوصل إلى كفاءة العمل حول ولكن آم الخروج فارغة. طول الصفيف يمكن أن يكون على ترتيب الآلاف وأنا بحاجة للقيام بذلك لعدة صفائف مختلفة.


إذا كنت ترغب في العثور على عناصر أقل من بعض العناصر إلى اليمين، يمكنك القيام بذلك أيضا:

x = some_values'; % x should be a column vector to use this
h = hankel(x);
m = max(h,[],2);
f = find(x<m) %returns indices or f = (a<m) %returns true/false

سوف مصفوفة هانكيل تظهر العناصر إلى اليمين كما يذهب إلى أسفل الصفوف.

ثم يمكنك استخدام المؤشرات أو صحيح / خطأ لتكرار من خلال ل حلقة وتنفيذ بعض العمليات. هنا مثال:

x =

     9
     8
    16
    16
     4
    10
     9
    13
    15
     1

>> h = hankel(x)

h =

     9     8    16    16     4    10     9    13    15     1
     8    16    16     4    10     9    13    15     1     0
    16    16     4    10     9    13    15     1     0     0
    16     4    10     9    13    15     1     0     0     0
     4    10     9    13    15     1     0     0     0     0
    10     9    13    15     1     0     0     0     0     0
     9    13    15     1     0     0     0     0     0     0
    13    15     1     0     0     0     0     0     0     0
    15     1     0     0     0     0     0     0     0     0
     1     0     0     0     0     0     0     0     0     0

>> m = max(h,[],2)

m =

    16
    16
    16
    16
    15
    15
    15
    15
    15
     1

>> f = find(a<m)

f =

     1
     2
     5
     6
     7
     8

يجب أن تكون هذه خوارزمية تأخذ الذاكرة O (n) و O (n): تسمية العنصر الأخير في صفيف العنصر الأقصى. يتكرر إلى الوراء على المصفوفة. كلما كان لديك عنصر أصغر من الحد الأقصى، احفظه. وإلا يصبح الحد الأقصى الجديد. هذا يجب أن تحصل على كل العناصر التي تحتاج إليها مع تمريرة واحدة.


يستخدم هذا نهج تقسيم و قهر (على غرار البحث الثنائي):

  1. العثور على الحد الأقصى للمتجه.
  2. يتم قبول جميع العناصر إلى يسارها، في حين يتم رفض الحد الأقصى نفسه.
  3. بالنسبة لهذه العناصر إلى اليمين الأقصى، طبق الخطوة 1.

على الرغم من أنني لم تفعل تحليلا دقيقا، وأعتقد أن متوسط ​​التعقيد O ( n )، أو على الأكثر O ( n لوغ n ). الذاكرة هي O ( n ).

والنتيجة هي متجه منطقي ind يحتوي على true للعناصر المقبولة و false للعناصر المرفوضة. ستكون النتيجة النهائية x(ind) .

x = [3 4 3 5 6 3 4 1];
n = numel(x);
ind = false(1,n); %// intiallization
s = 1; %// starting index of the part of x that remains to be analyzed
while s <= n %// if s > n we have finished
    [~, m] = max(x(s:end)); %// index of maximum within remaining part of x
    ind(s:s-2+m) = true; %// elements to its left are accepted
    s = s+m; %// update start of remaining part
end

يمكن تقليل وقت التشغيل قليلا عن طريق تغيير الشرط while s < n في while s < n ، لأنه يتم رفض العنصر الأخير دائما.







vectorization