c++ - reorder - std:: vector sorting




std:: stable_sort: come scegliere l'algoritmo ottimizzato per la memoria rispetto all'algoritmo ottimizzato nel tempo? (2)

Vorrei usare std::stable_sort . La complessità dell'algoritmo è dichiarata come

O (N · log ^ 2 (N)), dove N = std :: distanza (primo, ultimo) applicazioni di cmp. Se è disponibile memoria aggiuntiva, la complessità è O (N · log (N)). http://en.cppreference.com/w/cpp/algorithm/stable_sort

Nella mia applicazione, la memoria è critica, quindi preferirei std::stable_sort per utilizzare l'algoritmo O (N · log ^ 2 (N)) ottimizzato per la memoria, piuttosto che l'O ottimizzato nel tempo (N · log (N) algoritmo). Capisco che la versione ottimizzata per il tempo verrà scelta solo se è sicuro farlo (memoria disponibile). Tuttavia, il mio obiettivo è quello di eseguire il benchmark della mia applicazione e, pertanto, poiché la memoria è fondamentale, si desidera eseguire un benchmark dell'algoritmo quando il consumo di memoria è minimo. Poiché il mio sistema ha attualmente abbastanza memoria per allocare il buffer, sceglierà automaticamente la versione O (N · log ^ 2 (N)) di std::stable_sort . Vorrei quindi affermare a std::stable_sort di prendere la versione ottimizzata per la memoria. È possibile?

La politica di esecuzione sembra essere un parametro che può modificare l'algoritmo, tuttavia sembra alterare solo l'estensione del parallelismo. http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

Sebbene la scelta della versione parallela o sequenziale possa effettivamente scegliere rispettivamente le versioni O (N · log (N)) o O (N · log ^ 2 (N)), ciò non è indicato in nessun punto della pagina web.

Mi chiedo se qualcuno abbia qualche esperienza nell'affermare questa scelta. In tal caso sarebbero in grado di fornire qualche consiglio?


Puoi esaminare le tue intestazioni e vedere quale funzione viene chiamata se il buffer extra non è disponibile. Per me su gcc lo è

    std::__inplace_stable_sort(__first, __last, __comp);

Questo naturalmente non è conforme agli standard. __inplace_stable_sort è una funzione di supporto e non è pensata per essere utilizzata direttamente.

La chiamata da std :: stable_sort a questa funzione è il risultato del seguente codice

typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
  _TmpBuf __buf(__first, __last);

  if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
  else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
                _DistanceType(__buf.size()), __comp);

Sfortunatamente non esiste un modo standard per dire a stable_sort di fare l'ordinamento sul posto. In C ++ 14 le uniche opzioni che abbiamo

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

C ++ 17 ha aggiunto versioni che consentono la politica di esecuzione come si fa notare, ma anche quelle non influenzeranno la decisione. Se consideriamo il requisito di complessità in [stable.sort] otteniamo

Complessità : fa al massimo N log²(N) (dove N == last - first ) confronti; se è disponibile memoria aggiuntiva sufficiente, è N log(N).

Quindi è obbligatorio utilizzare più memoria se è disponibile.

O devi scrivere il tuo e puoi vedere il peggior caso O ( n ln n ) O ( n ln⁡ n ) in ordine stabile? su questo o trovare una libreria che fornisce la funzione per voi.





stable-sort