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?

18
demandé sur nimcap 2010-11-10 10:37:33

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');
30
répondu Amro 2010-11-10 09:43:28

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
8
répondu Edric 2010-11-10 09:42:19
  1. une solution récursive est-elle si mauvaise? (examinez toujours votre dessin d'abord).
  2. Échange De Fichiersvotre ami. (voler avec fierté!)
  3. 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.

4
répondu Marc 2010-11-10 14:20:38

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

1
répondu moksef 2014-08-23 18:07:15

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.

0
répondu Tormod Haugene 2014-04-22 14:53:22

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;
0
répondu Antonm 2014-09-08 11:50:52