Есть ли в MATLAB «очередь»?

Question

Я хочу преобразовать рекурсивную функцию в итеративную.Обычно я инициализирую очередь, помещаю первое задание в очередь.Затем в цикле while я использую задания из очереди и добавляю новые в очередь.Если моя рекурсивная функция вызывает себя несколько раз (например, обход дерева с множеством веток), добавляется несколько заданий.Псевдокод:

queue = new Queue();
queue.put(param);
result = 0;

while (!queue.isEmpty()) {
    param = queue.remove();
    // process param and obtain new param(s)
    // change result
    queue.add(param1);
    queue.add(param2);
}

return result;

Я не могу найти ни одной очереди, подобной структуре, в MATLAB.Я могу использовать вектор для имитации очереди, где добавление 3 в очередь выглядит следующим образом:

a = [a 3]

, а удаление элемента -

val = a(1);
a(1) = [];

Если я правильно понял MATLAB, этот методубийца производительности.

Есть ли разумный способ использовать очередь в MATLAB?

А как насчет других структур данных?

Answer 1

Если вы настаиваете на использовании правильных структур данных, вы можете использовать Java из MATLAB:

import java.util.LinkedList
q = LinkedList();
q.add('item1');
q.add(2);
q.add([3 3 3]);
item = q.remove();
q.add('item4');

Answer 2

Хорошо, вот быстрая и грязная, едва протестированная реализация, использующая класс дескриптора MATLAB.Если вы храните только скалярные числовые значения, вы можете использовать двойной массив для «элементов», а не массив ячеек.Понятия не имею о производительности.

classdef Queue < handle
    properties ( Access = private )
        elements
        nextInsert
        nextRemove
    end

    properties ( Dependent = true )
        NumElements
    end

    methods
        function obj = Queue
            obj.elements = cell(1, 10);
            obj.nextInsert = 1;
            obj.nextRemove = 1;
        end
        function add( obj, el )
            if obj.nextInsert == length( obj.elements )
                obj.elements = [ obj.elements, cell( 1, length( obj.elements ) ) ];
            end
            obj.elements{obj.nextInsert} = el;
            obj.nextInsert = obj.nextInsert + 1;
        end
        function el = remove( obj )
            if obj.isEmpty()
                error( 'Queue is empty' );
            end
            el = obj.elements{ obj.nextRemove };
            obj.elements{ obj.nextRemove } = [];
            obj.nextRemove = obj.nextRemove + 1;
            % Trim "elements"
            if obj.nextRemove > ( length( obj.elements ) / 2 )
                ntrim = fix( length( obj.elements ) / 2 );
                obj.elements = obj.elements( (ntrim+1):end );
                obj.nextInsert = obj.nextInsert - ntrim;
                obj.nextRemove = obj.nextRemove - ntrim;
            end
        end
        function tf = isEmpty( obj )
            tf = ( obj.nextRemove >= obj.nextInsert );
        end
        function n = get.NumElements( obj )
            n = obj.nextInsert - obj.nextRemove;
        end
    end
end

Answer 3

1. Действительно ли рекурсивное решение так плохо?(всегда сначала проверяйте свой дизайн).
2. Обмен файлами - это ваш друг. (украсть с гордостью!)
3. Зачем беспокоиться о проблемеправильная Очередь или класс - подделайте это немного.Сделайте это просто:

<code>q = {};
head = 1;
q{head} = param;
result = 0;
while (head<=numel(q))<br>
    %process param{head} and obtain new param(s)
    head = head + 1;
    %change result
    q{end+1} = param1;
    q{end+1} = param2;
end %loop over q
return result;
 

Если производительность слишком сильно теряет в конце - добавьте куски:

chunkSize = 100;
chunk = cell(1, chunkSize);
q = chunk;
head = 1;
nextLoc = 2;
q{head} = param;
result = 0;
while (head<endLoc)        
    %process param{head} and obtain new param(s)
    head = head + 1;
    %change result
    if nextLoc > numel(q);
        q = [q chunk];
    end
    q{nextLoc} = param1;
    nextLoc = nextLoc + 1;
    q{end+1} = param2;
    nextLoc = nextLoc + 1;
end %loop over q
 return result;

Класс, безусловно, более элегантный и многократно используемый - но приспособьте инструмент к задаче.

Answer 4

У меня была потребность в очереди, подобной структуре данных.

К счастью, у меня было ограниченное количество элементов (n).

Все они попадают в очередь в какой-то момент, но только один раз.

Если ваша ситуация похожа, вы можете адаптировать простой алгоритм, используя массив фиксированного размера и 2 индекса.

queue  = zeros( n, 1 );
firstq = 1;
lastq  = 1;

while( lastq >= firstq && firstq <= n )
    i = queue( firstq );    % pull first element from the queue
                            % you do not physically remove it from an array,
                            % thus saving time on memory access
    firstq = firstq + 1;

    % % % % % % % % % % % % % WORKER PART HERE
    % do stuff

    %
    % % % % % % % % % % % % % % % % % % % % %

    queue( lastq ) = j;     % push element to the end of the queue
    lastq = lastq + 1;      % increment index

end;

Answer 5

Используйте этот код, сохраните код как файл am и используйте такие функции, как q.pop () и т. Д. Это оригинальный код с некоторыми изменениями:

properties (Access = private)
    buffer      % a cell, to maintain the data
    beg         % the start position of the queue
    rear        % the end position of the queue
                % the actually data is buffer(beg:rear-1)
end

properties (Access = public)
    capacity    % ص»µؤبفء؟£¬µ±بفء؟²»¹»ت±£¬بفء؟ہ©³نخھ2±¶،£
end

methods
    function obj = CQueue(c) % ³ُت¼»¯
        if nargin >= 1 && iscell(c)
            obj.buffer = [c(:); cell(numel(c), 1)];
            obj.beg = 1;
            obj.rear = numel(c) + 1;
            obj.capacity = 2*numel(c);
        elseif nargin >= 1
            obj.buffer = cell(100, 1);
            obj.buffer{1} = c;
            obj.beg = 1;
            obj.rear = 2;
            obj.capacity = 100;                
        else
            obj.buffer = cell(100, 1);
            obj.capacity = 100;
            obj.beg = 1;
            obj.rear = 1;
        end
    end

    function s = size(obj) % ¶سءذ³¤¶ب
        if obj.rear >= obj.beg
            s = obj.rear - obj.beg;
        else
            s = obj.rear - obj.beg + obj.capacity;
        end
    end

    function b = isempty(obj)   % return true when the queue is empty
        b = ~logical(obj.size());
    end

    function s = empty(obj) % clear all the data in the queue
        s = obj.size();
        obj.beg = 1;
        obj.rear = 1;
    end

    function push(obj, el) % ر¹بëذآشھثطµ½¶سخ²
        if obj.size >= obj.capacity - 1
            sz = obj.size();
            if obj.rear >= obj.beg 
                obj.buffer(1:sz) = obj.buffer(obj.beg:obj.rear-1);                    
            else
                obj.buffer(1:sz) = obj.buffer([obj.beg:obj.capacity 1:obj.rear-1]);
            end
            obj.buffer(sz+1:obj.capacity*2) = cell(obj.capacity*2-sz, 1);
            obj.capacity = numel(obj.buffer);
            obj.beg = 1;
            obj.rear = sz+1;
        end
        obj.buffer{obj.rear} = el;
        obj.rear = mod(obj.rear, obj.capacity) + 1;
    end

    function el = front(obj) % ·µ»ط¶ست×شھثط
        if obj.rear ~= obj.beg
            el = obj.buffer{obj.beg};
        else
            el = [];
            warning('CQueue:NO_DATA', 'try to get data from an empty queue');
        end
    end

    function el = back(obj) % ·µ»ط¶سخ²شھثط            

       if obj.rear == obj.beg
           el = [];
           warning('CQueue:NO_DATA', 'try to get data from an empty queue');
       else
           if obj.rear == 1
               el = obj.buffer{obj.capacity};
           else
               el = obj.buffer{obj.rear - 1};
           end
        end

    end

    function el = pop(obj) % µ¯³ِ¶ست×شھثط
        if obj.rear == obj.beg
            error('CQueue:NO_Data', 'Trying to pop an empty queue');
        else
            el = obj.buffer{obj.beg};
            obj.beg = obj.beg + 1;
            if obj.beg > obj.capacity, obj.beg = 1; end
        end             
    end

    function remove(obj) % اه؟ص¶سءذ
        obj.beg = 1;
        obj.rear = 1;
    end

    function display(obj) % دشت¾¶سءذ
        if obj.size()
            if obj.beg <= obj.rear 
                for i = obj.beg : obj.rear-1
                    disp([num2str(i - obj.beg + 1) '-th element of the stack:']);
                    disp(obj.buffer{i});
                end
            else
                for i = obj.beg : obj.capacity
                    disp([num2str(i - obj.beg + 1) '-th element of the stack:']);
                    disp(obj.buffer{i});
                end     
                for i = 1 : obj.rear-1
                    disp([num2str(i + obj.capacity - obj.beg + 1) '-th element of the stack:']);
                    disp(obj.buffer{i});
                end
            end
        else
            disp('The queue is empty');
        end
    end

    function c = content(obj) % ب،³ِ¶سءذشھثط
        if obj.rear >= obj.beg
            c = obj.buffer(obj.beg:obj.rear-1);                    
        else
            c = obj.buffer([obj.beg:obj.capacity 1:obj.rear-1]);
        end
    end
end end

Ссылка: список, очередь, стек Структуры в Matlab

Answer 6

Если вы можете делать с очередью FIFO предопределенного размера без необходимости простого прямого доступа, вы можете просто использовать оператор по модулю и некоторую переменную счетчика:

myQueueSize = 25;                  % Define queue size
myQueue = zeros(1,myQueueSize);    % Initialize queue

k = 1                              % Counter variable
while 1                            
    % Do something, and then
    % Store some number into the queue in a FIFO manner
    myQueue(mod(k, myQueueSize)+1) = someNumberToQueue;

    k= k+1;                       % Iterate counter
end

ЭтоПодход очень прост, но есть и обратная сторона: не так легко получить доступ, как в обычной очереди.Другими словами, самым новым элементом всегда будет элемент k , а не элемент 1 и т. Д. Для некоторых приложений, таких как хранение данных FIFO для статистических операций, это не обязательно является проблемой.

Answer 7

В случае, когда вам нужна очередь только для хранения векторов (или скаляров), тогда нетрудно использовать матрицу вместе с функцией circshift() для реализации базовой очереди с фиксированной длиной.

% Set the parameters of our queue
n = 4; % length of each vector in queue
max_length = 5;

% Initialize a queue of length of nx1 vectors 
queue = NaN*zeros(n, max_length);
queue_length = 0;

Для нажатия:

queue = circshift(queue, 1, 2); % Move each column to the right
queue(:,1) = rand(n, 1); % Add new vector to queue
queue_length = min(max_length, queue_length + 1); 

Для ввода:

result = queue(:,last)
queue(:, last) = NaN;
queue_length = max(1, queue_length - 1);