¿Cómo puedo optimizar este Mergesort? -- ++ campo con optimization campo con performance campo con mergesort camp codereview Relacionados El problema

How can I optimize this mergesort?


4
vote

problema

Español

en la principal:

  for(int i = 1; i < upto; i *= 2)     {  for(int j = 0; j < (upto - i); j += (2*i))        {  int end2 = (2*i < (upto - j)) ? 2*i : upto - j;           mymerge(&(array[j]), i, end2); }  }   

Fusión:

  void mymerge(people  *arr, int end1, int end2){   int i = 0;   int j = end1;   int k = 0;   people * temp = new people[end2];    while(i < end1 && j < end2){     if(arr[i].lname < arr[j].lname){         temp[k] = arr[i];         i += 1;     }else if(arr[i].lname > arr[j].lname){         temp[k] = arr[j];         j += 1;     }else if(arr[i].fname < arr[j].fname){         temp[k] = arr[i];         i += 1;     }else if(arr[i].fname > arr[j].fname){         temp[k] = arr[j];         j += 1;     }else if(arr[i].dob < arr[j].dob){         temp[k] = arr[i];         i += 1;     }else if(arr[i].dob >= arr[j].dob){         temp[k] = arr[j];         j += 1; }     k += 1;  }    while( i < end1){     temp[k] = arr[i];     i +=1; k +=1; }    while(j < end2){     temp[k] = arr[j];     j += 1; k += 1; }    for(int c = 0; c < end2; c += 1)     arr[c] = temp[c];    delete [] temp; }   

¿Un enfoque recursivo o iterativo mejoró el tiempo de ejecución? ¿Hay una mejor manera de usar los punteros? Esto sería para una matriz que no es probable que esté en ningún orden parcialmente ordenado.

Original en ingles

In main:

for(int i = 1; i < upto; i *= 2)     {  for(int j = 0; j < (upto - i); j += (2*i))        {  int end2 = (2*i < (upto - j)) ? 2*i : upto - j;           mymerge(&(array[j]), i, end2); }  } 

Merge:

void mymerge(people  *arr, int end1, int end2){   int i = 0;   int j = end1;   int k = 0;   people * temp = new people[end2];    while(i < end1 && j < end2){     if(arr[i].lname < arr[j].lname){         temp[k] = arr[i];         i += 1;     }else if(arr[i].lname > arr[j].lname){         temp[k] = arr[j];         j += 1;     }else if(arr[i].fname < arr[j].fname){         temp[k] = arr[i];         i += 1;     }else if(arr[i].fname > arr[j].fname){         temp[k] = arr[j];         j += 1;     }else if(arr[i].dob < arr[j].dob){         temp[k] = arr[i];         i += 1;     }else if(arr[i].dob >= arr[j].dob){         temp[k] = arr[j];         j += 1; }     k += 1;  }    while( i < end1){     temp[k] = arr[i];     i +=1; k +=1; }    while(j < end2){     temp[k] = arr[j];     j += 1; k += 1; }    for(int c = 0; c < end2; c += 1)     arr[c] = temp[c];    delete [] temp; } 

Would a recursive or iterative approach improve run time? Is there a better way to use pointers? This would be for an array that is not likely to be in any partially sorted order.

           

Lista de respuestas

4
 
vote

Primero debe definir su pedido por separado de su fusión:

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 0  

Incrementando por uno se puede hacer con el var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 1

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 2  

o puede hacerlo en el lugar con:

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 3  

usando nuevo / Eliminar es una mala idea. Te hace hacer toda la gestión de la memoria. Es mejor usar clases que lo hagan todo para usted. En su caso Std :: Vector es una mejor opción para la gestión de la memoria de las matrices

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 4  

Prefiero usar algoritmos estándar en lugar de bucles manuales.

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 5  

Si está copiando algo y no va a usar el original nuevamente. Luego, intente mover el objeto al destino en lugar de copiarlo.

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 6  

Ahora su combinación se vuelve más legible:

  var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 7  

Ahora que he limpiado la función 99887776655443318 var seqList = [[Int]](count: numOfSequences, repeatedValue: []) 9 logra esto.

 

First you should define your ordering separately from your merge:

bool operator<(people const& lhs, people const& rhs) {     if (lhs.lname < rhs.lname)  {return true;}     if (lhs.lname > rhs.lname)  {return false;}      // lhs.lname == rhs.lname      if (lhs.fname < rhs.fname)  {return true;}     if (lhs.fname > rhs.fname)  {return false;}      // lhs.lname == rhs.lname  && lhs.fname == rhs.fname     if (lhs.dob < rhs.dob)      {return true;}      // Optimize away the last test.     //if (lhs.dob > rhs.dob)      {return false;}      return false; } 

Incrementing by one can be done with the operator++

j += 1; // Easier to write as: ++j; 

Or you can do it in-place with:

temp[k] = arr[i]; i += 1; // Easier to write as temp[k] = arr[i++]; 

Using new/delete is a bad idea. It makes you do all the memory management. It is better to use classes that do it all for you. In your case std::vector is a better choice for memory management of arrays

people * temp = new people[end2]; .... delete [] temp; // Better to use std::vector std::vector<people>  temp(end2); .... 

Prefer to use standard algorithms rather than manual loops.

  for(int c = 0; c < end2; c += 1) {     arr[c] = temp[c];   }   // Use std::copy   std::copy(temp.begin(), temp.end(), arr); 

If you are copying something and not going to use the original again. Then try and move the object to the destination rather than copying it.

  temp[k] = arr[i];   // Prefer to move rather than copy   // if you are not going to use the value at arr[i] again.   temp[k] = std::move(arr[i]);    // Note this assumes you have defined move constructor and move assignment operator   // for the class people. If you have not defined these operations then it will   // default to use the normal copy versions. 

Now your merge becomes more readable:

void mymerge(people  *arr, int end1, int end2) {   int i = 0;   int j = end1;   std::vector<people>  temp;   temp.reserve(end2);    while(i < end1 && j < end2)   {       people&  src =  (arr[i] < arr[j])                          ? arr[i++]                          : arr[j++];       temp.emplace_back(std::move(src));   }    std::move(&arr[i], &arr[end1], std::back_inserter(temp));   std::move(&arr[j], &arr[end2], std::back_inserter(temp));    std::move(temp.begin(), temp.end(), arr); } 

Now that I have cleaned up the mymerge() function I can understand what you are doing and it looks like it should work. But it requires the input sections to be already pre-sorted. I am not sure how your double loop in main() achieves this.

 
 
3
 
vote
  for(int i = 1; i < upto; i *= 2)     {  for(int j = 0; j < (upto - i); j += (2*i))        {  int end2 = (2*i < (upto - j)) ? 2*i : upto - j;           mymerge(&(array[j]), i, end2); }  }   

Me gustaría saber cómo upto se define aquí. ¿Es el tamaño de array ? Llamarlo size o count podría hacer que esto sea más claro.

Este es un formato extraño. Aquí siempre coloca su 9988776665544335 en una nueva línea y luego coloque el código después de la misma línea. En otros lugares, usted pone su { en la misma línea y coloque el código después de una nueva línea.

  }else if(arr[i].dob >= arr[j].dob){     temp[k] = arr[j];     j += 1; }   

de nuevo, tengo problemas para seguir las reglas alrededor de su formato. En una línea, inicia su } en una nueva línea y luego, más tarde lo coloca al final de una línea. Al hacer esto, le dificulta escanear el código rápidamente. La lectura tiene que verificar cada línea para ver si hay alguna 99887766655443339 o upto0 en él. Es mucho más fácil si están constantemente en el mismo lugar para que el lector pueda seguir la estructura rápidamente.

Hay tres formatos principales:

siempre una nueva línea (estilo BSD)

  upto1  

siempre cierre solo en una nueva línea (medio acurrucado)

  upto2  

siempre comparta si puede (k & amp; r)

  upto3  

La mayor parte del código que estará leyendo seguirá una de estas reglas. Si su código también lo hace, entonces será mucho más fácil que las personas sigan. Ya sabremos las reglas. Prefiero la última versión, pero hay argumentos para y en contra de cada uno.

También prefiero tener espacios entre casi todos los tokens. Tenga en cuenta que escribo upto4 en lugar de upto5 . Esto ayuda a separar cosas como un upto6 de las llamadas de la función. También hace que sea más fácil ver el upto7 , ya que está separado del paréntesis de apertura y el primer token de la expresión. Su formato tiene cosas como upto8 que uno tiene que leer moderadamente a fondo para ver qué pasa con qué.

  upto9  

Rehacer esto para cada llamada a su función de ayuda. Mejor sería hacer esto fuera de la función y reutilizar la matriz para cada llamada. Es posible que solo esté utilizando la memoria $ O (N) $ en cualquier momento, pero está haciendo $ O (n log n) asignaciones de memoria. Podrías hacerlo solo uno (y tienes que hacerlo de todos modos para hacer la última fusión).

Tenga en cuenta que utilizando un tipo de datos estándar (por ejemplo, array0 ) y dejar que C ++ administre la memoria para usted debe hacer la misma cosa. Un compilador lo suficientemente inteligente podría asignar la memoria antes de tiempo y simplemente hacer uno. Si lo está haciendo manualmente, trate de ser al menos tan inteligente como sea que el compilador pueda ser.

Preguntas sobre soluciones iterativas y recursivas. Una solución puramente iterativa sin llamadas de función es potencialmente más rápida, pero un buen compilador debe optimizar la mayor parte de eso. Si la velocidad es importante para usted, perfile ambas soluciones y vea si hay una diferencia significativa.

A menos que el compilador pueda optimizar la recursión, una solución recursiva generalmente será la más lenta. Cada llamada de función requiere el programa para guardar el estado actual del mundo en la pila. Hacerlo recursivamente significa que tendría que mantener las llamadas de $ O ( log n) $ en una vez. El punto de recursión es generalmente para mejorar la elegancia y la legibilidad en lugar de rendimiento.

No volveré a cubrirlo, pero estoy de acuerdo con la respuesta de Loki Astari en el uso del array1 y array2 OPERADORES. Eso también facilitaría ejecutar este mismo tipo con array3 < / a> que está probado correcto (menos posibilidades de errores) y podría ser más eficiente. Al menos es una posibilidad que vale la pena perfilar.

Como problema lateral, generalmente hago clasificación así en la base de datos. Este es un índice de tres columnas relativamente sencillo en una base de datos. Luego, las clasificaciones se realizan a través de una especificación de inserción a la hora de escritura en lugar de ordenar todos los datos al tiempo de lectura. No publicas el resto del código, por lo que no está claro por qué no está haciendo esto en la base de datos.

 
for(int i = 1; i < upto; i *= 2)     {  for(int j = 0; j < (upto - i); j += (2*i))        {  int end2 = (2*i < (upto - j)) ? 2*i : upto - j;           mymerge(&(array[j]), i, end2); }  } 

I'd like to know how upto is defined here. Is it the size of array? Calling it size or count might make this clearer.

This is a weird format. Here you always put your { on a new line and then put the code after it on the same line. Elsewhere you put your { on the same line and put the code after it on a new line.

}else if(arr[i].dob >= arr[j].dob){     temp[k] = arr[j];     j += 1; } 

Again, I have trouble following the rules around your formatting. On one line, you start your } on a new line and then later you put it at the end of a line. By doing this you make it hard to scan the code quickly. The read has to check each line to see if there are any { or } on it. It's much easier if they are consistently in the same place so that the reader can follow the structure quickly.

There are three main formats:

Always a new line (BSD style)

if ( true ) {     // code here } else {     // more code } 

Always close alone on a new line (half cuddled)

if ( true ) {     // code here } else {     // more code } 

Always share if you can (K&R)

if ( true ) {     // code here } else {     // more code } 

Most of the code that you'll be reading will follow one of these rules. If your code does as well, then it's going to be much easier for people to follow. We'll already know the rules. I prefer the last version, but there are arguments for and against each.

I also prefer to have spaces between almost all tokens. Note that I write if ( rather than if(. This helps separate things like an if from function calls. It also makes it easier to see the if as it is separate from the opening parenthesis and the first token of the expression. Your format has things like if(arr[i].dob which one has to read moderately thoroughly to see what goes with what.

people * temp = new people[end2]; 

You redo this for each call to your helper function. Better would be to do this outside the function and reuse the array for each call. You may only be using \$O(n)\$ memory at any time, but you are doing \$O(n \log n)\$ memory allocations. You could do just one (and you have to do that one anyway to do the last merge).

Note that using a standard data type (e.g. std::vector) and letting C++ manage the memory for you should do much the same thing. A smart enough compiler could allocate the memory ahead of time and just do one. If you're doing it manually, try to be at least as smart as the compiler might be.

You ask about iterative and recursive solutions. A purely iterative solution with no function calls is potentially faster, but a good compiler should optimize most of that away. If speed is that important to you, profile both solutions and see if there is a significant difference.

Unless the compiler can optimize out the recursion, a recursive solution will generally be the slowest. Each function call requires the program to save the current state of the world on the stack. Doing so recursively means that you would have to maintain up to \$O(\log n)\$ function calls at any one time. The point of recursion is generally to improve elegance and readability rather than performance.

I won't cover it again, but I agree with Loki Astari's answer on using the < and ++ operators. That would also make it easier to run this same sort with std:sort which is proven correct (less chance of bugs) and might be more efficient. At least it's a possibility worth profiling.

As a side issue, I usually do sorting like this in the database. This is a relatively straightforward three column index in a database. Then sorts are done via insertion sort at write time rather than sorting all the data at read time. You don't post the rest of the code, so it's not clear to me why you are not doing this in the database.

 
 
 
 
0
 
vote

DOBLE POR LO TIENE A LO QUE ALGUIEN ES TRATANDO DE SER MUY LEVANTE Y PACTOR. No hay necesidad de eso:

  for(int subArrayLength = 1; subArrayLength < count; subArrayLength *= 2) {     for(int j = 0; j < (count- subArrayLength); j += (2*subArrayLength)) {         int remainingLength = 2*subArrayLength;         if(remainingLength > count - j)              remainingLength = count- j;           mymerge(&(array[j]), subArrayLength, remainingLength);      }   }   

Esto inmediatamente lo hace mucho más claro cómo funciona el doble para el bucle.

 

That double for looks like someone is trying to be very clever and compact. no need for that:

for(int subArrayLength = 1; subArrayLength < count; subArrayLength *= 2) {     for(int j = 0; j < (count- subArrayLength); j += (2*subArrayLength)) {         int remainingLength = 2*subArrayLength;         if(remainingLength > count - j)              remainingLength = count- j;           mymerge(&(array[j]), subArrayLength, remainingLength);      }   } 

This immediately makes it much clearer how the double for loop works.

 
 
 
 

Relacionados problema

12  Fusionar una especie de una matriz entera  ( Merge sort an integer array ) 
He implementado fusionar una matriz entera. ¿Está bien usar I, J, k como nombre de variable para bucle? ¿Debo cambiarlos a nombres más significativos? En gene...

6  Algoritmo para encontrar inversiones en tipo MERGE  ( Algorithm for finding inversions in merge sort ) 
Ayuda en las revisiones de código para la legibilidad, optimizándola, funcionalidad, etc. import java.io.BufferedReader; import java.io.FileNotFoundExcepti...

7  Merge Sort en JavaScript  ( Merge sort in javascript ) 
Implementé este tipo de fusión en JS y noté que para los números de enteros aleatorios es mucho más rápido que la construcción en funciones de tipo de todos l...

2  Fusionar la implementación de Sort Java  ( Merge sort java implementation ) 
¿Puede alguien revisar mi implementación de tipo de fusión en Java? ¿Es bueno / malo y puede mejorarse más? public class MyMergeSort { private int [] d...

2  Merge rápido en JavaScript  ( Fast merge sort in javascript ) 
Al desarrollar una interfaz de usuario que permite la clasificación por varios campos diferentes, noté que Array.prototype.sort() es extremadamente lento pa...

2  Algoritmo de Mergesort en C  ( Mergesort algorithm in c ) 
Tengo esta implementación de Mergesort que tiene exactamente la misma API que qsort : : Mergesort.h : #ifndef MERGESORT_H #define MERGESORT_H #inclu...

2  Fusión natural Sort En C  ( Natural merge sort in c ) 
Tengo esta implementación C del tipo de combinación natural: #include "stable_sort.h" #include <stdbool.h> #include <stdlib.h> #include <stdio.h> #include ...

6  Fusionar la implementación de ordenación en Java  ( Merge sort implementation in java ) 
¿Puedes revisar mi implementación de tipo de fusión? De todas mis pruebas, parece que funciona, pero solo quería asegurarme de que lo estoy haciendo lo mejor ...

5  Memoria / Performance of Merge Sort Code  ( Memory performance of merge sort code ) 
Escribí un código de tipo de combinación para un poco de bocadillo nocturno. Lo he puesto trabajando, pero solo estaba mirando a aprender si me faltaba algo e...

1  Merge Sort in PHP - Mi primera exposición algorítmica a PHP 5  ( Merge sort in php my first algorithmic exposure to php 5 ) 
Tengo este pequeño programa en PHP implementando una especie de combinación. Utilicé una optimización de tiempo de ejecución bastante simple mediante el uso d...




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