+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [Javascript] Gérer les queues (files d'attente) ? (/showthread.php?tid=5650)
[Javascript] Gérer les queues (files d'attente) ? - Argorate - 20-08-2011
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.
RE: gérer les queue (file d'attente) en JS? - niahoo - 20-08-2011
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 ?
RE: gérer les queue (file d'attente) en JS? - Sephi-Chan - 20-08-2011
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.
RE: gérer les queue (file d'attente) en JS? - niahoo - 20-08-2011
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/zero/1.0/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);
}
}RE: gérer les queue (file d'attente) en JS? - Argorate - 20-08-2011
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?
RE: gérer les queue (file d'attente) en JS? - niahoo - 20-08-2011
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.
RE: gérer les queue (file d'attente) en JS? - Argorate - 21-08-2011
Et utiliser slice() au lieu de shift() mais sans offset?
RE: gérer les queue (file d'attente) en JS? - niahoo - 21-08-2011
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.
RE: gérer les queue (file d'attente) en JS? - Argorate - 21-08-2011
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;
}RE: gérer les queue (file d'attente) en JS? - niahoo - 21-08-2011
c'est ça :
(21-08-2011, 02:45 AM)niahoo a écrit : Ben ça revient au même je suppose. ça doit pas être beaucoup plus rapide. surement moins.
fais un test et dis nous