Stl __merge_without_buffer algoritmo? -- ++ campo con algorithm campo con sorting campo con stl campo con d camp Relacionados El problema

STL __merge_without_buffer algorithm?


3
vote

problema

Español

¿Dónde puedo obtener una descripción de alto nivel decente del algoritmo utilizado en __merge_without_buffer() en el STL de C ++? Estoy tratando de reembolsar este código en el lenguaje de programación D, con algunas mejoras. Parece que no puedo generar lo que está haciendo a nivel algorítmico de solo leer el código fuente de STL porque hay demasiados detalles de bajo nivel lo ocultan. Además, no quiero simplemente traducir ciegamente el código porque entonces, si no funcionaba, no sabría por qué, y no podrían agregar mis mejoras.

Original en ingles

Where can I get a decent high-level description of the algorithm used in __merge_without_buffer() in the C++ STL? I'm trying to reimplement this code in the D programming language, with some enhancements. I can't seem to grok what it's doing at the algorithmic level from just reading the STL source code because there are too many low-level details obscuring it. Also, I don't want to just blindly translate the code because then, if it didn't work I wouldn't know why, and I wouldn't be able to add my enhancements.

</div
              

Lista de respuestas

11
 
vote
vote
La mejor respuesta
 

__merge_without_buffer() está realizando una fusión en el lugar , como el paso de fusión de un tipo de fusión en el lugar. Se necesita como entrada Dos rangos de datos [first, middle) y [middle, last) que se supone que ya se han ordenado. El len1 y len2 Los parámetros son iguales a las longitudes de los dos rangos de entrada, a saber, (middle - first) y (last - middle) respectivamente.

Primero, elige un elemento PIVOT . Luego, reorganiza los datos en el orden A1 B1 A2 B2 , donde A1 es el conjunto de elementos en [first, middle) que son menores que el pivote, [first, middle)0 es el conjunto de elementos en [first, middle)11111111/segancia o igual al pivote, [first, middle)2 es el conjunto de elementos en [first, middle)3 Menos que el pivote, y [first, middle)4 es el conjunto de elementos en [first, middle)5 mayor que o igual al pivote. Tenga en cuenta que los datos están originalmente en el orden [first, middle)6 , por lo que todo lo que debemos hacer es girar [first, middle)7 en [first, middle)8 . Esto es con una llamada a [first, middle)9 , que hace precisamente eso.

Ahora hemos separado los elementos que son menores que el pivote ( [middle, last)0 y [middle, last)1 ) de aquellos que son mayores o iguales al pivote ( [middle, last)2 y [middle, last)3 ), por lo que ahora podemos fusionar recursivamente los dos subranges [middle, last)4 y [middle, last)5 .

¿Cómo elegimos un pivote? En la implementación que estoy mirando, elige el elemento mediano de la subrange más grande (es decir, si [middle, last)6 tiene más elementos que (last - middle)27 , elige la mediana de [middle, last)8 ; De lo contrario, elige la mediana de [middle, last)9 ). Dado que los subranges ya están clasificados, la elección de la mediana es trivial. Esta opción de pivote garantiza que cuando se fusione recursivamente los dos subranges, cada subproblema no sea más de 3/4 del tamaño del problema actual, porque en el peor de los casos, al menos 1/4 de los elementos son más grandes o más pequeños que el pivote .

¿Cuál es el tiempo de ejecución de esto? El len10 Llama requiere o (n) tiempo, y hacemos dos llamadas recursivas a nosotros mismos. Esto equivale a un tiempo de ejecución de O (n log n). Sin embargo, tenga en cuenta que esto es solo un paso en Mergesort: recuerde que en Mergesor, primero resuelvo las dos mezas y luego se fusionó. Por lo tanto, la relación de recurrencia para el tiempo de ejecución de Mergesort es ahora:

len11

Enchufe esto a la Master Theorem , y obtienes que Mergesort ahora se ejecuta en O (n ¡Tiempo de registro 2 n)!

Como un punto final interesante, considere las siguientes tres cualidades de un algoritmo de clasificación basado en comparación:

  1. en el lugar
  2. estable
  3. se ejecuta en O (n log n) tiempo

Por lo general, solo puede obtener 2 de estos a la vez: Quicksort lo obtiene (1) y (3), Mergesort lo consigue (2) y (3), y un Mergesort en el lugar lo consigue (1) y (2 ). Las clasificaciones basadas en no comparación, como el tipo de conteo, pueden lograr los 3, pero esos tipos solo pueden ordenar ciertos tipos de datos. Es posible que exista un tipo basado en comparación que logre los 3, pero si lo existe, no estoy al tanto de su existencia, y es casi seguro que es mucho más complicado.

 

__merge_without_buffer() is performing an in-place merge, as the merge step of an in-place merge sort. It takes as input two ranges of data [first, middle) and [middle, last) which are assumed to already be sorted. The len1 and len2 parameters are equal to the lengths of the two input ranges, namely (middle - first) and (last - middle) respectively.

First, it picks a pivot element. Then, it rearranges the data into the order A1 B1 A2 B2, where A1 is the set of elements in [first, middle) that are less than the pivot, A2 is the set of elements in [first, middle) greater than or equal to the pivot, B1 is the set of elements in [middle, last) less than the pivot, and B2 is the set of elements in [middle, last) greater than or equal to the pivot. Note that the data is originally in the order A1 A2 B1 B2, so all we need to do is to turn A2 B1 into B1 A2. This is with a call to std::rotate(), which does just that.

Now we've separated out the elements which are less than the pivot (A1 and B1) from those that are greater than or equal to the pivot (A2 and B2), so now we can recursively merge the two subranges A1 A2 and B1 B2.

How do we choose a pivot? In the implementation I'm looking at, it chooses the median element from the larger subrange (i.e. if [first, middle) has more elements than [middle, last), it chooses the median of [first, middle); otherwise, it chooses the median of [middle, last)). Since the subranges are already sorted, choosing the median is trivial. This pivot choice ensures that when recursively merging the two subranges, each subproblem is no more than 3/4 the size of the current problem, because in the worst case, at least 1/4 of the elements are larger than or smaller than the pivot.

What is the running time of this? The std::rotate() call takes O(N) time, and we make two recursive calls to ourselves. This equates to a running time of O(N log N). However, note that this is only one step in mergesort: remember that in mergesort you first recursively sort both halves and then merge. Thus, the recurrence relation for the running time of mergesort is now:

T(N) = 2T(N/2) + O(N log N)

Plug this into the Master theorem, and you get that mergesort now runs in O(N log2 N) time!

As an interesting final point, consider the following three qualities of a comparison-based sorting algorithm:

  1. In-place
  2. Stable
  3. Runs in O(N log N) time

You can usually only get 2 of these at once - quicksort gets you (1) and (3), mergesort gets you (2) and (3), and an in-place mergesort gets you (1) and (2). Non-comparison-based sorts such as count sort can achieve all 3, but those sorts can only sort certain data types. It's possible there exists a comparison-based sort which achieves all 3, but if there is, I'm not aware of its existence, and it's almost certainly much more complicated.

</div
 
 
         
         

Relacionados problema

1  ¿Cómo intersectar a la matriz en D?  ( How to intersect to array in d ) 
Necesito encontrar la diferencia entre dos matrices de cadenas en D. El problema, que no puedo entender cómo usar SetDifference de std.algorithm . a...

1  Reemplazo de Cruntimeclass de MFC en D  ( Mfcs cruntimeclass replacement in d ) 
StackOverflow. Mi primer post aquí. He venido a D de C ++ y MFC, que estoy usando en mi trabajo, no solo con cosas de GUI, sino también la macro de MFC ( DEC...

2  Compiladores maduros basados ​​en antlr v3  ( Mature compilers based on antlr v3 ) 
¿Hay maduro (y de código abierto, ya que quiero leer el código) implementaciones de idioma basadas en antlr? Realmente no quiero leer el código para un DSL, o...

1  Cómo eliminar elementos de la matriz en D  ( How to remove elements from array in d ) 
Tengo una matriz de int 's en tracksList_filtered variable: [10422, 10681, 10421, 10392, 10616, 10589, 10581, 10423, 10743, 10213, 10613, 10609, 10427, ...

8  Usando `Void Main` en D  ( Using void main in d ) 
He visto el código D que usa void main . ¿Es esto legal? En caso afirmativo, está devolviendo lo que no es void ( int6 ) ¡También legal? ¿Por qué se permit...

3  Stl __merge_without_buffer algoritmo?  ( Stl merge without buffer algorithm ) 
¿Dónde puedo obtener una descripción de alto nivel decente del algoritmo utilizado en __merge_without_buffer() en el STL de C ++? Estoy tratando de reembols...

4  Restricción de la firma para los tipos genéricos  ( Signature constraint for generic types ) 
struct S(int a, int b) { } void fun(T)(T t) { } Quiero fun Para trabajar con S solo. ¿Cómo se vería la restricción de la firma? No puedo hacer fu...

1  Antlr D Target - ¿Alguna implementación madura por ahí?  ( Antlr d target any mature implementations out there ) 
¿Hay un objetivo antlr d que sea maduro (o al menos no clasificado como alfa)? ¿Quizás haya buenos ejemplos de trabajo del objetivo alojado de SourceForge exi...

2  Enumeración Tipo de seguridad en D  ( Enumeration type safety in d ) 
¿Cuál es el estado y los planes sobre la seguridad tipo de enumias en D? esperaba import std.stdio: writeln; void main(string args[]) { enum E {x, y...

163  ¿Es una alternativa creíble a Java y C ++? [cerrado]  ( Is d a credible alternative to java and c ) 
Según lo que actualmente representa, esta pregunta no es un buen ajuste para nuestro Q & Amp; un formato. Esperamos que las...




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