Ricevi i dati in ordine casuale, invia in ordine

Question

Ricevi i dati in ordine casuale, invia in ordine

#1 da (2 voti)
#2 da (1 voti)

2

Sto affrontando un problema in cui dispongo di un flusso di dati che invia dati non ordinati. Sto cercando di trovare un modo per ricevere i dati in ordine casuale, ma inviarlo in ordine.

Ad esempio, riceverò object4 e poi object3 e poi object1 . Avrò bisogno che il mio sistema memorizzi object4 e object3 quando arrivano e invii immediatamente object1 . In futuro, quando arriverà object2 , avrò bisogno che il sistema invii immediatamente object2 e quindi ricontrollo la matrice per inviare object3 e object4 e così via.

Altre informazioni:

I dati verranno sicuramente ricevuti, quindi non ci sono dati mancanti.
I dati sono numerati (ad esempio object1 , object20 ).

La mia soluzione attuale è:

Quando si riceve un nuovo oggetto ...
- se il nuovo oggetto è in ordine, invialo immediatamente.
- Se il nuovo oggetto non è in ordine
  - Memorizzalo in un elenco
  - Controlla l'elenco se contiene l'oggetto successivo da inviare
Dopo aver inviato un oggetto ...
- Controlla l'elenco se contiene l'oggetto successivo da inviare

Quindi questo sistema sta ricontrollando l'elenco degli elementi da inviare su due eventi:

Quando viene aggiunto un nuovo oggetto non in ordine.
Dopo l'invio riuscito

Come per l'invio

Dopo l'invio riuscito, l'oggetto inviato verrà rimosso dall'elenco

Come per la concorrenza

Per ragioni di discussione, si assuma una relazione produttore-consumatore in cui l'elenco è contemporaneamente accessibile da entrambi i giocatori:

Il thread del produttore sta trasferendo nuovi dati nell'elenco.
Il thread del consumatore sta controllando l'elenco, inviando ed eliminando i dati inviati.

La mia domanda è questa, è un buon meccanismo? C'è una struttura dati migliore per aiutarmi con questo problema?

data-structures algorithms sorting stream-processing

posta Solidak 12.02.2018 - 15:47

fonte

2 risposte

1

Se gli elementi da ricevere sono numerati 1..N, senza valori mancanti, è possibile utilizzare una serie di puntatori diretti agli elementi ricevuti. Inizializza gli elementi dell'array su tutto vuoto e inizializza una variabile next_to_transmit all'inizio della matrice.

Quando si riceve un elemento, se il suo indice è uguale a next_to_transmit, lo si trasmette e quindi si sposta l'array in avanti da next_to_transmit, inviando e rilasciando elementi completi e aggiornando next_to_transmit finché non si incontra uno vuoto o si esaurisce di matrice.

Quando ricevi un elemento e il suo indice non è uguale a next_to_transmit, lo inserisci nella tabella.

Il vantaggio di questo su una lista ordinata è che la scrittura in uno slot matrice noto è O (1), invece di O (N) per l'inserimento in una lista ordinata. Se la dimensione dell'oggetto dati è grande rispetto alla dimensione di un puntatore, il requisito di archiviazione medio non sarà peggiore. (Il requisito del caso peggiore è lo stesso: N-1 per gli elementi 2..N, quindi ricevere l'elemento 1 per attivare la trasmissione in blocco dell'intero set di dati.)

Non ho fatto un'analisi sufficientemente accurata per dire quali problemi di concorrenza potresti incontrare con questo approccio. Il mio istinto è che avrai problemi minimi.

risposta data 13.02.2018 - 02:06

fonte

Leggi altre domande sui tag data-structures algorithms sorting stream-processing

Quando dovrebbero essere usati metodi pubblici concreti se si implementa un'interfaccia? Dove devo fare i test di integrazione in un progetto multi-pacchetto

score 2 · Accepted Answer

Penso che il tuo approccio sia abbastanza preciso, anche se ti consiglierei di mantenere gli articoli ricevuti fino a quel momento in un elenco ordinato usando l'ordinamento per inserimento.

L'ordinamento di inserimento funziona meglio quando l'elemento viene inserito in un elenco che è già stato ordinato. Avendo un elenco ordinato, hai il vantaggio aggiunto che dopo aver inviato un oggetto, puoi immediatamente controllare il primo elemento nell'elenco per vedere se è il prossimo, senza dover controllare ogni oggetto ogni volta.

In altre parole, dedica O (n) tempo a mantenere la lista ordinata, e quindi ogni altra operazione è O (1).

@Telastyn è un buon punto nei commenti. Ricordati di tenerlo thread-safe se potenzialmente questo array è accessibile da più thread e richieste multiple!