Struttura dei dati da utilizzare per ricerche complesse in un motore degli eventi?

Question

Struttura dei dati da utilizzare per ricerche complesse in un motore degli eventi?

#1 da (1 voti)

0

Quale sarebbe un modo ottimale per organizzare tipi di dati arbitrari in una struttura che consente ricerche complesse (non basate su indici) nei dati senza eseguire il loop-through completo?

Per un po 'di background, non sto cercando una risposta su come progettare un motore Event, piuttosto sto cercando metodi per migliorare un'implementazione corrente.

Con il tour di 5 secondi, ho un'architettura in atto con i seguenti componenti,

Segnali - Segnala quali gesti eseguire
Gestisce - Esegue quando viene ricevuto un segnale
Coda - Gestisce gli handle
Engine - Gestisce le code e elabora i segnali, i nuovi handle ecc.

La mia attuale implementazione ha alcune insidie,

I segnali sono attualmente accoppiati in una coda, in questo modo il motore può identificare le code in memoria e i segnali che rappresentano.
Esistono due distinti archivi di code, indicizzati e non indicizzati, esiste l'indice per le ricerche su stringhe / int's, non-index esiste per segnali complessi come regex, confronti di array ecc.

Penso che potrei avere una soluzione ma vorrei i pensieri di altri che hanno sviluppato sistemi simili.

Con la nuova architettura che ho pensato, sarebbe costituito da quanto segue,

Le code memorizzerebbero solo una proprietà "data" piuttosto che un segnale che sarebbe passato al motore per il confronto dei segnali.
Il motore non avrebbe più spazio di archiviazione non indice e indice, piuttosto sarebbe utilizzato un singolo spazio di archiviazione che richiederebbe ricerche loop-through.

La libreria è scritta in PHP (se questo è importante), se vuoi vedere la fonte è a link .

performance

posta Nick 06.03.2012 - 21:20

fonte

1 risposta

Leggi altre domande sui tag performance

Ricerca di posizioni appropriate per le coordinate aggiunte a un elenco di coordinate Automazione della gestione dei rilasci e degli elementi della configurazione su progetti python sotto VCS mercuriale

score 1 · Accepted Answer

Dopo aver fatto molte ricerche su questo argomento, una ricerca binaria fornirà il massimo guadagno senza molta complessità.

La funzione di ricerca stessa è ignara dei dati effettivi per consentire la ricerca di qualsiasi dato arbitrario, dato che ha la capacità di essere ordinato e confrontato.

Il codice seguente è il mio risultato finale, si noti che questo appartiene a un'estensione SplFixedArray.

public function binsearch($node, $compare)
{
    $low = 0;
    $high = $this->getSize() - 1;

    while ($low <= $high) {
        $mid = ($low + $high) >> 1;
        $nval = $this->offsetGet($mid);
        $cmp = $compare($nval, $node);
        switch (true) {
            case $cmp === true:
                return $mid;
                break;
            case $cmp === 0:
                $low = $mid + 1;
                break;
            case $cmp === 1:
                $high = $mid - 1;
                break;
            default:
                return null;
                break;
        }
    }

    return null;
}

Test delle prestazioni utilizzando un array con 1,000,000 nodi

Binary
0.0001220703125
Linear Search
0.0046999454498291

Codice di prova

$array = new FixedArray();
for ($i=0;$i!=1000000;$i++ ){
    $array->push($i);
}
echo "Binary".PHP_EOL;
$t = microtime(true);
$array->binsearch(6570, function($node, $needle){
    if ($node > $needle) {
        return 0;
    }
    if ($node < $needle) {
        return 1;
    }
    if ($node === $needle) {
        return true;
    }
});
echo microtime(true) - $t.PHP_EOL;
echo "Linear Search".PHP_EOL;
while($array->valid()) {
    if ($array->current() == 6570) break;
    $array->next();
}
echo microtime(true) - $t.PHP_EOL;