[Javascript] Gérer les queues (files d'attente) ?

[Argorate]

Bonsoir,

j'aimerais savoir si certains d'entre vous ont déjà eut a utiliser le système de file d'attente (FIFO) en Javascript? Si oui comment avez vous fait? avez vous un objet "queue"? Quelqu'un a le code d'un objet de ce genre a partager?

Je demande parceque ça me ferait gagner du temps plutôt que de m'en faire un maison, donc n'hésitez pas a me parler de toute vos expériences dans le domaine.

merci.

[niahoo]

ben FIFO ce n'est pas un algorithme, c'est simplement un type de pile.

utiliser simplement un array me semble un choix sympa, et sera facilement remplacé par un objet qui exporte les méthodes push/shift ou unshift/pop.

As-tu besoin de fonctionnalités plus spécifiques ?

[Sephi-Chan]

Il existe pas mal d'implémentations. Aussi incroyables que cela puisse paraîsse, on peut trouver la plupart d'entre elles dans Google grâce à la recherche "javascript queue".

Queue.js en est une très simple (85 LOC, commentaires et sauts de lignes compris) et fonctionnelle.

[niahoo]

Comparé a un array, leur benchmark indique que la méthode Array.shift est faible en performances.

Leur implémentation est interessante, je la mets ici en intégralité car elle est vraiment très simple à piger

/*



Queue.js



A function to represent a queue



Created by Stephen Morley - http://code.stephenmorley.org/ - and released under

the terms of the CC0 1.0 Universal legal code:



http://creativecommons.org/publicdomain/.../legalcode



*/



/* Creates a new queue. A queue is a first-in-first-out (FIFO) data structure -

 * items are added to the end of the queue and removed from the front.

 */

function Queue(){



  // initialise the queue and offset

  var queue  = [];

  var offset = 0;



  /* Returns the length of the queue.

   */

  this.getLength = function(){



    // return the length of the queue

    return (queue.length - offset);



  }



  /* Returns true if the queue is empty, and false otherwise.

   */

  this.isEmpty = function(){



    // return whether the queue is empty

    return (queue.length == 0);



  }



  /* Enqueues the specified item. The parameter is:

   *

   * item - the item to enqueue

   */

  this.enqueue = function(item){



    // enqueue the item

    queue.push(item);



  }



  /* Dequeues an item and returns it. If the queue is empty then undefined is

   * returned.

   */

  this.dequeue = function(){



    // if the queue is empty, return undefined

    if (queue.length == 0) return undefined;



    // store the item at the front of the queue

    var item = queue[offset];



    // increment the offset and remove the free space if necessary

    if (++ offset * 2 >= queue.length){

      queue  = queue.slice(offset);

      offset = 0;

    }



    // return the dequeued item

    return item;



  }



  /* Returns the item at the front of the queue (without dequeuing it). If the

   * queue is empty then undefined is returned.

   */

  this.peek = function(){



    // return the item at the front of the queue

    return (queue.length > 0 ? queue[offset] : undefined);



  }



}

[Argorate]

Pour répondre a ta question niahoo, dans la théorie: il faut un array, j'entends bien, mais FIFO => quand tu veux prendre un élément il te faut toujours prendre tab[0], et à la suite de quoi décaler tab[1] dans tab[0], tab[2] dans tab[1] etc... Ça c'est le principe de la queue, et c'est cette partie là que je souhaitais avoir un avis autre, pour savoir s'il y a avait plus optimisé qu'un algo maison...

D'après le code que tu donnes, il utilise le slice() ce qui est déjà mieux que de faire un truc à la main.
Cependant, pourquoi utiliser un "offset", si on prend toujours le premier comme le prochain "item" a traiter?

[niahoo]

Et bien parce que dans l'implémentation que je proposais, la function shift prends toujours le tab[0] puis décale les autres. C'était déjà fonctionnel.

Mais eux expliquent que cette fonction shift n'est pas rapide et donc accélèrent le processus en utilisant cet offset afin d'éviter de toujours prendre la première case pour gagner du temps.

[Argorate]

Et utiliser slice() au lieu de shift() mais sans offset?

[niahoo]

tu veux dire faire slice à chaque fois qu'on apellerait shift ?

Ben ça revient au même je suppose. ça doit pas être beaucoup plus rapide. surement moins.

[Argorate]

Je veux dire, es-ce que le code ci dessous ne serait pas le mieux?

Code :

this.dequeue = function()
    {
        var elt = this.queue[0];
        this.queue = this.queue.splice(1);
        return elt;
    }

[niahoo]

c'est ça :

Ben ça revient au même je suppose. ça doit pas être beaucoup plus rapide. surement moins.

fais un test et dis nous