Come rendere stabile il max-heap con il contatore e l'account per l'overflow del contatore?

Question

Come rendere stabile il max-heap con il contatore e l'account per l'overflow del contatore?

#1 da (2 voti)

3

In generale, ho bisogno di una struttura dei dati efficiente in termini di dimensioni simile a std::priority_queue ma stabile (preservando l'ordine di inserimento).

Aggiungendo solo 4 byte all'oggetto potrei avere 1 byte che serve come priorità e 3 byte come contatore per mantenere l'ordine di inserimento. Il concorrente più vicino - std::forward_list - aggiungerebbe un overhead di 5 byte (in pratica 8 a causa dell'allineamento) - uno per priorità e 4 per collegamento (architettura a 32 bit). Sarebbe anche più lento di max-heap a causa di attraversamenti quando si aggiunge un nuovo elemento.

Il problema con il contatore è il comportamento del contenitore quando il contatore trabocca. In Boost il contatore ha una lunghezza di 64 bit e quando si rovescia, il contenitore genera un'eccezione ( link ).

Una soluzione a questo problema che viene in mente è il reset del contatore ogni volta che la coda si svuota, ma questa è solo una soluzione parziale al problema.

Esiste un generico (e ottimale - senza attraversare l'intero heap ogni volta) in cui questo potrebbe essere risolto? Ho pianificato di utilizzare std::push_heap() e std::pop_heap() da <algorithm> con una matrice di storage raw, quindi ho accesso a "internals" delle voci. Se possibile, preferirei attenermi a queste funzioni standard invece di implementare il mio heap (o qualsiasi altra struttura di dati) che sarebbe stabile.

EDIT:

Come richiesto in un commento, sto aggiungendo alcune ulteriori informazioni sul mio caso d'uso qui.

Ho bisogno di questa struttura dati per implementare una coda messaggi nel RTOS che sto sviluppando ( link ). Questa coda di messaggi deve seguire tutti i requisiti POSIX e uno di questi è "stabilità" - le nuove voci con la stessa priorità devono essere posizionate DOPO le voci precedenti:

Da link :

A message shall be inserted after other messages in the queue, if any, with equal msg_prio.

Questo è un RTOS per microcontrollori embedded, quindi non posso dare uno scenario di utilizzo specifico, perché ce ne saranno molti. Alcuni dispositivi funzioneranno per un secondo e spegneranno, altri dispositivi potrebbero funzionare per anni senza riavviare. Dato che sto puntando a un design senza limiti, sono principalmente interessato a una soluzione che funzioni in tutti i casi, senza limiti come quella imposta dal contatore semplice, che fallisce quando il contatore trabocca.

Dato che questo è per un microcontrollore, preferirei che la soluzione fosse di dimensioni compatte, quindi soluzioni come "use counter a 128 bit" non sono accettabili.

In generale, vedo due opzioni: utilizzare l'elenco collegato separatamente o utilizzare max-heap (come inizialmente inteso).

L'uso dell'elenco a link singolo aggiungerebbe 5 (in pratica 8 - a causa dell'allineamento) byte a ciascun oggetto archiviato: 1 per priorità, 4 per collegamento. Questa soluzione è stabile "in base alla progettazione", ma l'inserimento di oggetti può essere lento quando ci sono molti oggetti nella lista - perché molti nodi dovranno essere attraversati per trovare lo spot per l'inserimento.

Usando l'heap potrei provare a limitare l'overhead a 4 byte - 1 per priorità, 3 per contatore. Questa opzione potrebbe essere più veloce dell'elenco, ma richiede una soluzione per l'overflow del contatore. Vedo diverse opzioni qui (più possono essere utilizzati allo stesso tempo):

usa un contatore a 56 bit (l'overhead totale sarebbe di 8 byte per oggetto),
ripristina il contatore quando la lista diventa vuota (soluzione solo parziale),
quando si verifica l'overflow, il contatore deve essere resettato, l'intero heap deve essere attraversato e ogni contatore di voci visitate deve essere aggiornato al valore "basso".

Naturalmente so che potrei semplicemente ignorare l'overflow, ma se c'è una soluzione reale, mi piacerebbe implementarla.

Poiché non sembra esserci una soluzione semplice, robusta e deterministica al problema dell'overflow, sto iniziando a orientarmi verso l'uso di - mi aspetto che non ci siano molte voci nella coda dei messaggi (la maggior parte dei microcontrollori ha RAM veramente limitata), quindi il vantaggio di velocità dell'utilizzo dell'heap sarebbe probabilmente trascurabile. Soprattutto quando conto tutte queste copie durante l'inserimento / la cancellazione, mentre il contenuto dell'elenco linkato singolarmente sarebbe per lo più statico in questo senso. E c'è anche l'estrazione "istantanea" dalla testa della lista ...

c++ data-structures c++11 heap

posta Freddie Chopin 04.01.2015 - 17:45

fonte

1 risposta

Leggi altre domande sui tag c++ data-structures c++11 heap

Come implementare un'API RESTful che aggiorna un elenco che potrebbe contenere l'esclusione e l'aggiunta di risorse correlate? Utilizzo di Prolog per implementare le regole di autorizzazione

score 2 · Answer 1

Non penso che ci sia un buon modo per risolvere il tuo problema di overflow con i vincoli dati.

Rinumerare l'heap periodicamente significa un'operazione di housekeeping stop-the-world, che ritengo abbia bisogno di tempo O (n log n) senza allocazione aggiuntiva, o forse O (n) tempo con O (n) spazio temporaneo.

Si noti che se O (n log n) operazioni stop-the-world non sono accettabili - si è detto che è un RTOS - allora è necessario assicurarsi che ci sia sempre spazio per allocare lo spazio di lavoro temporaneo. Se lo riservi in ogni caso, potresti spendere il doppio di overhead dello spazio per oggetto su una struttura che non ha bisogno di operazioni di housekeeping stop-the-world in primo luogo.

La soluzione più semplice che riesco a pensare è quella di ammortizzare quell'overhead su più oggetti, piuttosto che aggiungere un puntatore a ciascuna istanza. Quindi, dividiamolo in due problemi:

Ordinamento FIFO di elementi con la stessa priorità

Puoi semplicemente usare un contenitore ordinato FIFO con pop_front costante e push_back : questo è un deque.

Potresti provare std::deque e scrivere un'implementazione personalizzata se, ad esempio, hai bisogno di un controllo più preciso sulla dimensione del blocco. L'overhead per blocco è ammortizzato su tutti gli oggetti in quel blocco, quindi puoi controllare il tradeoff tra allocazione del gioco e overhead per oggetto.
contenitore di livelli di priorità ordinati a chiave:
- Poiché 8 bit sono sufficienti per memorizzare la priorità, una serie di 256 livelli (deques) sarebbe la soluzione più semplice.
- Se ciò comporta uno spazio troppo lungo per te, una normale coda di priorità funzionerà ancora, ma pop_front / pop_heap dovrebbe apparire dall'oggetto a livello di priorità anteriore e solo spuntare quel livello dalla coda generale quando è vuota.
  
  Si noti che è possibile scrivere questa logica come un involucro sottile attorno al pop_heap esistente per riutilizzare la sua logica di heap, ma lo stesso non è vero per push_heap , e infatti in questo modo finirà più lentamente schema (dovrai cercare il punto di inserimento per vedere se esiste, quindi setacciarlo se non lo fa).

Questo dovrebbe avere un tempo nozionalmente costante, quindi è asintoticamente migliore di un heap; se in pratica è abbastanza veloce dipenderà dalla piattaforma, dal comportamento della cache e dalla capacità di ottimizzare gli allocatori, le dimensioni dei blocchi, ecc.

L'overhead dello spazio è di pochi byte (qualcosa come 2-4 puntatori) per livello di priorità distinto, più sperabilmente 1 byte o meno per elemento (a seconda della dimensione del blocco della deque e del numero di elementi per blocco). Quindi, ciò consentirà di risparmiare spazio solo se si dispone di un numero sufficientemente grande di elementi per livello di priorità. Tuttavia, non può mai incontrare il tuo problema di overflow, non richiede alcuna pulizia di stop-the-world e non si deteriora in modo significativo con il tempo o le dimensioni.