Ответ 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');
Есть ли "очередь" в MATLAB?
Я хочу преобразовать рекурсивную функцию в итеративную. То, что я обычно делаю, я инициализирую очередь, поставил первое задание в очередь. Затем в цикле 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?
Как насчет других структур данных?
Ответы
Ответ 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
Ответ 3
- Рекурсивное решение действительно так плохо? (сначала проверьте свой дизайн).
- Файловый обмен ваш друг (украсть с гордость!)
- Зачем беспокоиться о проблемах с надлежащей очередью или классом - подделывать ее немного. Держите это просто:
q = {};
head = 1;
q{head} = param;
result = 0;
while (head<=numel(q))
%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;
Класс, безусловно, более изящный и многоразовый, но подходит для задачи.
Ответ 4
Используйте этот код, сохраните код как файл m и используйте такие функции, как 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
Ответ 5
Если вы можете сделать с FIFO-очередью предопределенного размера без необходимости простого прямого доступа, вы можете просто использовать оператор modulo и некоторую переменную счетчика:
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 для статистических операций, это не обязательно проблема.
Ответ 6
Мне также нужна структура данных, подобная очереди.
К счастью, у меня было ограниченное количество элементов (n).
Все они попадают в очередь в какой-то момент, но только один раз.
Если ситуация аналогична, вы можете адаптировать простой алгоритм с использованием массива фиксированного размера и двух индексов.
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;