Il y a une file D'attente à MATLAB?
je veux convertir une fonction récursive pour une itératif. Ce que je fais normalement, c'est d'initialiser une file d'attente, mettre le premier emploi dans la file d'attente. Puis dans une boucle de temps je consomme des emplois de la file d'attente et en ajoute de nouveaux à la file d'attente. Si ma fonction récursive s'appelle elle-même plusieurs fois (E. g marcher sur un arbre avec de nombreuses branches) plusieurs travaux sont ajoutés. Le Pseudo code:
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;
Je ne peux pas trouver de file d'attente comme structure dans MATLAB cependant. Je peux utiliser le vecteur pour simuler la file d'attente où ajouter 3 à la file d'attente est comme:
a = [a 3]
et la suppression de l'élément est
val = a(1);
a(1) = [];
si J'ai bien compris la méthode MATLAB, cette méthode sera un tueur de performance.
existe-t-il une façon saine d'utiliser une file D'attente dans MATLAB?
Qu'en est-il des autres structures de données?
6 réponses
si vous insistez pour utiliser des structures de données appropriées, vous pouvez utiliser Java à partir de MATLAB:
import java.util.LinkedList
q = LinkedList();
q.add('item1');
q.add(2);
q.add([3 3 3]);
item = q.remove();
q.add('item4');
Ok, voici une implémentation rapide et sale, à peine testée à L'aide d'une classe de poignée MATLAB. Si vous stockez uniquement des valeurs numériques scalaires, vous pouvez utiliser un double tableau pour "elements" plutôt qu'un tableau de cellules. Aucune idée sur les performances.
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
- une solution récursive est-elle si mauvaise? (examinez toujours votre dessin d'abord).
- Échange De Fichiersvotre ami. (voler avec fierté!)
- Pourquoi s'embêter avec les problèmes d'une bonne File d'attente ou une classe - faux un peu. Keep it simple:
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;
Si le rendement s'en ressent d'ajouter à la fin trop - ajouter en morceaux:
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;
Une classe est certainement plus élégant et réutilisable, mais adapter l'outil à la tâche.
Utilisez ce code, enregistrez le code en tant que Fichier m, et utilisez les fonctions telles que Q. pop () etc. c'est le code d'origine avec quelques modifications:
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
Référence: liste de, file, pile Structures dans Matlab
si vous pouvez faire avec une file D'attente FIFO de taille prédéfinie sans avoir besoin d'un accès direct simple, vous pouvez simplement utiliser le modulo opérateur et quelques contre-la variable:
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
cette approche est très simple, mais a l'inconvénient de ne pas être aussi facilement accessible que votre file d'attente typique. En d'autres termes, le nouvel élément sera toujours l'élément k, pas d'élément 1 etc.. Pour certaines applications, telles que le stockage de données FIFO pour les opérations statistiques, cette n'est pas nécessairement un problème.
j'avais aussi besoin d'une file d'attente comme structure de données.
Heureusement que j'avais un nombre limité d'éléments (n).
ils font tous la queue à un moment donné, mais une seule fois.
si votre situation est similaire, vous pouvez adapter l'algorithme simple en utilisant le tableau de taille fixe et 2 indices.
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;