Implementación de la cola C ++ -- ++ campo con performance campo con queue camp codereview Relacionados El problema

C++ Queue Implementation


3
vote

problema

Español

Entonces escribí una implementación de colas en C ++ y, aunque sé que el código probablemente no sea tan sólido como debería ser y probablemente no realice todos los cheques que debería, me gustaría saber principalmente si hay Cualquier diferencia de funcionalidad entre mi implementación y la de STL.

Mi idea de implementación es usar una cola circular, cuando llegue al final de la cola, comienzo a usar los elementos al principio del rango (que se eliminaron a través del método POP).

Cuando no tengo más espacio para asignar un nuevo elemento que realizo un nuevo búfer y mueva todo al nuevo búfer en orden (esto probablemente podría hacerse más rápido usando 2 memmoves).

La razón por la que publico esto aquí se debe a que esta implementación de la cola parece ser aproximadamente un 50% más rápido que la de STD. Aquí está mi código:

  template<typename T> class Queue { private:     int m_capacity;     int m_size;     int m_startIndex;     int m_endIndex;     T* m_buffer;      void expand_queue() {         int newCapacity = m_capacity * 2;         T* newBuffer = new T[newCapacity];         if (m_endIndex <= m_startIndex) {             int cnt = 0;             for (int i = m_startIndex; i < m_capacity; i++) {                 newBuffer[cnt++] = m_buffer[i];             }              for (int i = 0; i < m_endIndex; i++) {                 newBuffer[cnt++] = m_buffer[i];             }         } else {             int cnt = 0;             for (int i = m_startIndex; i < m_endIndex; i++) {                 newBuffer[cnt++] = m_buffer[i];             }                     }          delete[] m_buffer;         m_buffer = newBuffer;         m_startIndex = 0;         m_endIndex = m_size;         m_capacity = newCapacity;     }      void init_queue(int capacity) {         m_capacity = capacity;         m_size = 0;         m_startIndex = 0;         m_endIndex = 0;          m_buffer = new T[capacity];     }  public:     Queue() {         init_queue(32);     }      Queue(int capacity) {         init_queue(capacity);     }      void push(T element) {         if (m_endIndex == m_startIndex && m_size > 0) {             // expand queue             expand_queue();         }          m_buffer[m_endIndex] = element;         m_endIndex = (m_endIndex + 1) % m_capacity;         m_size++;     }      void pop() {         if (m_size == 0) {             return;         }          m_startIndex = (m_startIndex + 1) % m_capacity;         m_size--;     }      T front() {         if (m_size == 0) {             throw;         }          return m_buffer[m_startIndex];     }      T back() {         if (m_size == 0) {             throw;         }          if (m_endIndex == 0) {             return m_buffer[m_capacity - 1];         } else {             return m_buffer[m_endIndex - 1];         }     }      int size() {         return m_size;     } };   

y aquí está el código que solía probar esto:

  #include <queue> #include "queue.h" #include <iostream> #include <list> #include <cstdlib> #include <ctime>  using namespace std;  Queue<int> q; // queue<int> q;  int main() {     srand(time(0));     for (int i = 0; i < 100000000; i++) {         if (q.size() > 10000000) {             q.pop();         } else if (q.size() == 0) {             q.push(i);         } else if (random() % 2 == 0) {             q.push(i);         } else {             q.pop();         }     }      while (q.size() > 0) {         q.pop();     }      return 0; }   

Puede ver que en el código de prueba tengo ambos tipos de colas allí (solo comenta una línea y el des comentario). Este programa realiza un funcionamiento de 100 miliones de empuje / pop en la cola mientras se asegura de que la cola no cumpla con más de 10 millones de personas.

Usando la implementación de la cola anterior, obtén esta vez:

  real    0m3.859s user    0m3.827s sys     0m0.015s   

y estos son tiempos usando la cola STD:

  real    0m6.077s user    0m6.055s sys     0m0.011s   

(puntos de referencia realizados en un MacBook Air de mediados de 2012).

Después de estudiar la implementación de la cola de STD, logré notar estas diferencias:

  • std :: cola usa std :: deques como un contenedor de forma predeterminada (usando STD :: LISTE da resultados aún peores). La STD :: la cola solo llama al pop_front y los métodos Push_Back del Deque. Toda la lógica está en el deque.
  • STD :: Deque crea trozos de tamaño fijo que utiliza para asignar los datos y los administra en consecuencia (primer trozo se expande a la inversa y el último trozo se expande normalmente).
  • Dado que Std :: Deque crea estos trozos de fragmentación de memoria también podría convertirse en un problema.
  • std :: la cola no hace ningún movimiento de memoria, solo asignaciones de nuevos trozos, mientras que mi cola moverá la memoria cuando necesita expandir la cola (log (n) veces donde n es el tamaño máximo de la cola).
Original en ingles

so I wrote a queue implementation in c++ and even though I know the code probably isn't as robust as it should be and probably doesn't perform all the checks it should, I'd like to know mostly if there is any functionality difference between my implementation and the one in STL.

My implementation idea is to use a circular queue, when I reach the end of the queue I start using the elements at the beginning of the range (that were removed through the pop method).

When I don't have any more space to allocate a new element I reallocate a new buffer and move everything to the new buffer in order (this could probably be done faster using 2 memmoves).

The reason I post this here is because this queue implementation seems to be aproximately 50% faster than the one in std. Here is my code:

template<typename T> class Queue { private:     int m_capacity;     int m_size;     int m_startIndex;     int m_endIndex;     T* m_buffer;      void expand_queue() {         int newCapacity = m_capacity * 2;         T* newBuffer = new T[newCapacity];         if (m_endIndex <= m_startIndex) {             int cnt = 0;             for (int i = m_startIndex; i < m_capacity; i++) {                 newBuffer[cnt++] = m_buffer[i];             }              for (int i = 0; i < m_endIndex; i++) {                 newBuffer[cnt++] = m_buffer[i];             }         } else {             int cnt = 0;             for (int i = m_startIndex; i < m_endIndex; i++) {                 newBuffer[cnt++] = m_buffer[i];             }                     }          delete[] m_buffer;         m_buffer = newBuffer;         m_startIndex = 0;         m_endIndex = m_size;         m_capacity = newCapacity;     }      void init_queue(int capacity) {         m_capacity = capacity;         m_size = 0;         m_startIndex = 0;         m_endIndex = 0;          m_buffer = new T[capacity];     }  public:     Queue() {         init_queue(32);     }      Queue(int capacity) {         init_queue(capacity);     }      void push(T element) {         if (m_endIndex == m_startIndex && m_size > 0) {             // expand queue             expand_queue();         }          m_buffer[m_endIndex] = element;         m_endIndex = (m_endIndex + 1) % m_capacity;         m_size++;     }      void pop() {         if (m_size == 0) {             return;         }          m_startIndex = (m_startIndex + 1) % m_capacity;         m_size--;     }      T front() {         if (m_size == 0) {             throw;         }          return m_buffer[m_startIndex];     }      T back() {         if (m_size == 0) {             throw;         }          if (m_endIndex == 0) {             return m_buffer[m_capacity - 1];         } else {             return m_buffer[m_endIndex - 1];         }     }      int size() {         return m_size;     } }; 

And here is the code I used to test this:

#include <queue> #include "queue.h" #include <iostream> #include <list> #include <cstdlib> #include <ctime>  using namespace std;  Queue<int> q; // queue<int> q;  int main() {     srand(time(0));     for (int i = 0; i < 100000000; i++) {         if (q.size() > 10000000) {             q.pop();         } else if (q.size() == 0) {             q.push(i);         } else if (random() % 2 == 0) {             q.push(i);         } else {             q.pop();         }     }      while (q.size() > 0) {         q.pop();     }      return 0; } 

You can see that in the test code I have both queue types in there (just comment one line and uncomment the other). This program perform 100 milion operation of push/pop on the queue while making sure the queue doesn't go over 10 million in size.

Using the queue implementation above I get this time:

real    0m3.859s user    0m3.827s sys     0m0.015s 

And these are times using the std queue:

real    0m6.077s user    0m6.055s sys     0m0.011s 

(Benchmarks done on a mid-2012 Macbook Air).

After studying the std queue implementation I managed to note these differences:

  • std::queue uses std::deque as a container by default (using std::list gives even worse results). The std::queue only calls the pop_front and the push_back methods of the deque. All the logic is in the deque.
  • std::deque creates chunks of fixed size which he uses to allocate the data and manages them accordingly (first chunk expands in reverse and the last chunk expands normally).
  • Given that std::deque creates these chunks memory fragmentation could also become an issue.
  • std::queue doesn't do any memory movements, just allocations of new chunks, while my queue will move the memory around when it needs to expand the queue (log(N) times where N is the maximum size of the queue).
        

Lista de respuestas

2
 
vote

Utilice std::vector en lugar de T* porque claramente no sabe lo que está haciendo (falta operator= , copy-constructor, etc. ). Mejor, haga que el contenedor subyacente sea un parámetro de plantilla.

El std::queue es probablemente más lento porque puede liberar un poco de memoria al hacer todo este pop() mientras que el tuyo lanza cualquier cosa.

sobre esto:

      if (m_size == 0) {         throw;     }   

¿Qué crees que estás lanzando? Lanzar una excepción adecuada (consulte http://en.cppreference.com/w/cpp/ encabezado / stdexcept por ejemplo).

 

Please use std::vector instead of T* because you clearly don't know what you are doing (missing operator=, copy-constructor, etc). Better, make the underlying container a template parameter.

The std::queue is probably slower because it may free some memory when doing all these pop() while yours doest release anything.

About this:

    if (m_size == 0) {         throw;     } 

what do you think you are throwing ? Please throw a proper exception (see http://en.cppreference.com/w/cpp/header/stdexcept for example).

 
 
   
   
0
 
vote

Sí, su clase es funcionalmente diferente de la cola proporcionada por el STL. Esta línea:

  m_buffer = new T[capacity];   

significa que el tipo T tiene que proporcionar un constructor predeterminado. Esta limitación no se le impone a usted si usa la cola STL.

Como aparte, cuando está comparando el rendimiento de dos sistemas diferentes y desea usar los números aleatorios como parte de ella, es mejor que no se siembra el generador de números aleatorios. Esto:

  srand(time(0));   

Semillas El generador de números aleatorios usando la hora actual. En muchos casos, esto es lo que quieres. Sin embargo, cuando está comparando el rendimiento de las dos colas que desea pseudo números aleatorios, pero no quiere que sean diferentes cada vez. De esa manera, sabes que estás comparando como con como. No desea terminar la prueba de su cola con una longitud máxima de 100 y la cola de STL con una longitud máxima de 10000.

 

Yes, your class is functionally different from the queue provided by the stl. This line:

m_buffer = new T[capacity]; 

Means that the type T has to provide a default constructor. This limitation is not imposed on you if you use the STL queue.

As an aside, when you're comparing performance of two different systems and you want to use random numbers as part of it, you're better off not seeding the random number generator. This:

srand(time(0)); 

seeds the random number generator using the current time. In a lot of cases this is what you want. However when you're comparing the performance of the two queues you want pseudo random numbers, but you don't want them to be different every time. That way you know you're comparing like with like. You don't want to end up testing your queue with a maximum length of 100 and the stl queue with a maximum length of 10000.

 
 
 
 
0
 
vote

Solo tengo un par de comentarios menores:

1

  void push(T element) {     if (m_endIndex == m_startIndex && m_size > 0) {         // expand queue         expand_queue();     }      m_buffer[m_endIndex] = element;     m_endIndex = (m_endIndex + 1) % m_capacity;     m_size++; }   

¿Por qué no escribir simplemente T*0 ?

2

  T*1  

}

Lo anterior podría ser escrito más sucintly como

  T*2  

3

Finalmente, si podría garantizar que la matriz de almacenamiento interno tenga capacidad que siempre es una potencia de dos, podría sustituir:

  T*3  

donde T*4 .

espero que ayude.

 

I have only a couple of minor comments:

1

void push(T element) {     if (m_endIndex == m_startIndex && m_size > 0) {         // expand queue         expand_queue();     }      m_buffer[m_endIndex] = element;     m_endIndex = (m_endIndex + 1) % m_capacity;     m_size++; } 

Why not write simply if (m_size == m_capacity) ... ?

2

if (m_endIndex <= m_startIndex) {     int cnt = 0;     for (int i = m_startIndex; i < m_capacity; i++) {         newBuffer[cnt++] = m_buffer[i];     }      for (int i = 0; i < m_endIndex; i++) {         newBuffer[cnt++] = m_buffer[i];     } } else {     int cnt = 0;     for (int i = m_startIndex; i < m_endIndex; i++) {         newBuffer[cnt++] = m_buffer[i];     }             

}

The above could be written more succintly as

for (int i = m_startIndex, cnt = 0; cnt < m_size; ++i, ++cnt) {     newBuffer[cnt] = m_buffer[i % m_capacity]; } 

3

Finally, if you could guarantee that the internal storage array has capacity that is always a power of two, you could substitute:

index % m_capacity --> index & m_mask,  

where m_mask == m_capacity - 1.

Hope that helps.

 
 
   
   

Relacionados problema

2  Montón Binomial en Java  ( Binomial heap in java ) 
Tengo esta implementación de un montón de binomio que proporciona inserto, disminución de la tecla y el extracto en el tiempo logarítmico. minpriorityqueue...

3  Cola de JavaScript para las funciones de ASYNC  ( Javascript queue for async functions ) 
Basado en la respuesta a Mi pregunta anterior sobre el desbordamiento de pila , armé la siguiente clase de cola. Me doy cuenta de que ya hay bibliotecas para...

3  Cola MultiPhread Generic Simple  ( Simple generic multithreaded queue ) 
Esta es una cola de hilo simple que se usa en un modelo de consumidor productor. public class ThreadedQueue<TType> { private Queue<TType> _queue; p...

1  DEQUEUE () en la implementación de la cola que utiliza una lista circular vinculada  ( Dequeue in queue implememtation that uses a circular linked list ) 
Utilizo una lista de enlaces circulares para implementar un queue , y solo sostiene un 99887776665544332 (Tenga en cuenta que 99887776655443333 enlaces a...

2  Implementación de la lista de la cola prioritaria  ( Priority queue linked list implementation ) 
Soy nuevo en Python y quería asegurarme de que mi código responde a la pregunta de mi tarea debido. Mi tarea: Una cola de prioridad es una cola en la que...

5  Cola de bloqueo con la exactitud de la lista doblemente vinculada  ( Lock free queue with doubly linked list correctness ) 
Necesito una cola de bloqueo que se implementa mediante la lista doblemente vinculada. es mi código correcto? ¿Hay algún error? ¿Hay alguna mejoras a realiz...

4  Linkedlist para ser utilizado en una pila o cola  ( Linkedlist to be used in a stack or queue ) 
Todo esto funciona. Solo quería asegurarse de que no me perdí nada. Viniendo de C ++ y trabajando en mi camino a través de algoritmos, 4ta ed. Aquí está mi cl...

19  Una clase de hilo-piscina / cola personalizada  ( A custom thread pool queue class ) 
Quería una clase que ejecuta cualquier cantidad de tareas, pero solo cierta cantidad al mismo tiempo (por ejemplo, para descargar varios contenidos de Interne...

2  Cola de bloqueo delimitada  ( Bounded blocking queue ) 
¿Puede alguien por favor revise este código para mí? No he implementado todos los métodos para la simplicidad. NSUSerDefaults1 Preguntas abiertas: l...

8  Reader de cola sin bloqueo Seclador de Singler-Writer en C ++  ( Lockless queue multiple reader singler writer in c ) 
Escribí una cola sin encimera para enviar objetos pequeños desde un solo hilo a un hilo de trabajador aleatorio. suposiciones: x86 / x86_64 compilado con...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos