Qual è una struttura dati efficiente per fare molte domande tra genitori / figli?

Naviga le tue risposte
4

Ho il seguente scenario per il quale ho riscontrato problemi di prestazioni:

Il contesto è un editor di livelli di un nuovo motore per un vecchio videogioco (la cui origine non è disponibile) in Unity . Fondamentalmente sto scrivendo un editor di livelli per Unity per modellare le vecchie strutture dati in quelle contemporanee, più utilizzabili, cioè parti / entità invece di un mucchio di modelli / poligoni non collegati.

Ecco un albero di come sono organizzate le cose nel vecchio gioco:

  • Container (dozzine)
    • Modelli (centinaia)
      • Poligoni (migliaia)

Ecco cosa mi piacerebbe realizzare:

  • Gruppo / i: per raggruppare oggetti correlati
    • Oggetto / i: un albero, una nave ecc ...
      • Parte / i: parti di un oggetto con materiale specifico ecc ...

A seconda di come appare l'oggetto finale sullo schermo, i dati iniziali (modelli / poligoni) sono un disastro, dove ci sono parti unite o non correlate in un modello e nei suoi poligoni.

Altri problemi emergono a causa di ciò, ad esempio, quello che era un semplice aggiornamento puntatore per aggiornare una texture o un colore non è semplicemente possibile all'interno di Unity.

Qui ho bisogno di cose e cosa ho fatto:

Devo essere in grado di tracciare riferimenti impliciti ed espliciti a modelli e poligoni. Questo per garantire che vengano creati oggetti validi e quindi prevenire contenuti non corretti.

Fondamentalmente l'utente può creare una parte dal modello o uno dei suoi poligoni, a differenza di ciò che è stato scelto prima.

Ecco un'immagine con spiegazioni:

  • Scene9 è di tipo Container
  • M123_456_ABC ... sono di tipo Model
  • P123_456_ABC ... sono di tipo Polygon
  • Un'icona verde è un riferimento esplicito
  • Un'icona gialla è un riferimento implicito
  • Un'icona rossa è un elemento senza riferimenti

Inoltre,l'interfacciautenteèaumentatadaglielementichevengonodisabilitatiognivoltachesonoappropriatiperaiutarel'utenteascegliereleazionigiustepercostruireillivello,ecc...

Qui,iproblemichestoriscontrando:

Laricercadiriferimentiespliciti/implicititracirca300modellie7000poligonidiventalentaneltempomanmanochelerelazionivengonocreate.

HoutilizzatounpaiodiList<T>efaccioqueryLINQtraloro:

  • tutto
  • tuttiimodelli
  • tuttiipoligoni
  • modelliimpliciti
  • poligoniimpliciti
  • modelliespliciti
  • poligoniespliciti

Menolalogicadeglispaghetti,funzionamaèlenta.Poihoeseguitol'upgradeaHashSet<T>conComparer<T>personalizzatochehanotevolmentemiglioratolavelocità,manonèancoraabbastanzaveloce.Tuttociòsibloccanell'interfacciautente.

Laconsiderazioneprincipaleècheall'internodiUnityiloopsonopiuttostostretti,le chiamate ad alta frequenza , l'interfaccia utente in modalità immediata e nessuna funzione di chiamata asincrona (Mono è approssimativamente .NET 3.5).

Sto iniziando a considerare che il mio approccio con le liste è errato e pensavo che una migliore struttura dei dati potesse essere utilizzata per query performanti.

Puoi suggerire una struttura dati più appropriata da utilizzare per tale scenario?

Modifica

Questo è un diagramma che mostra l'approccio nuovo che sto cercando dopo i tuoi suggerimenti:

Note:

  • IScenePrimitive è composto da 3% diint e Enum
  • ISceneReference.IsRef è semplicemente IsRefExplicit || IsRefImplicit
  • Le cose mancanti qui sono un dizionario in Scene per l'accesso rapido a un modello / poligono, quando l'utente seleziona qualcosa recupero questi usando gli hash senza dover enumerare, ecc ...

Parti interessanti nel codice:

SceneModel: 

    public override bool IsRefExplicit
    {
        get { return _isRefExplicit; }
        set
        {
            _isRefExplicit = value;

            if (value)
            {
                Debug.Assert(_polygons.None(s => s.IsRefExplicit));
                foreach (var polygon in _polygons)
                    polygon.IsRefImplicit = true;
            }
            else
            {
                Debug.Assert(_polygons.All(s => s.IsRefImplicit));
                foreach (var polygon in _polygons)
                    polygon.IsRefImplicit = false;
            }
        }
    }

    public override bool IsRefImplicit
    {
        get { return _isRefImplicit; }
        set
        {
            _isRefImplicit = value;
            if (value)
                Debug.Assert(_polygons.Any(s => s.IsRefExplicit));
        }
    }

ScenePolygon: 

    public override bool IsRefExplicit
    {
        get { return _isRefExplicit; }
        set
        {
            _isRefExplicit = value;
            if (value)
            {
                Debug.Assert(!Model.IsRefExplicit);
                Model.IsRefImplicit = true;
            }
            else
            {
                Debug.Assert(Model.IsRefImplicit);
                Model.IsRefImplicit = false;
            }
        }
    }

    public override bool IsRefImplicit
    {
        get { return _isRefImplicit; }
        set
        {
            _isRefImplicit = value;
            Debug.Assert(Model.IsRefExplicit);
        }
    }

Questo è tutto ciò che accade realmente, LINQ su una dozzina di elementi invece di molti altri (300 modelli che interrogano ogni 7000 poligoni X). Devo ancora provarlo per vedere come funziona, ma dovrebbe eseguire molto più velocemente, per continuare.

    
posta Aybe 12.10.2016 - 22:55
fonte

1 risposta

2

Diamo un'occhiata al SceneModel di IsRefExplicit . Ho aggiunto commenti:

SceneModel 

public override bool IsRefExplicit
{
    get { return _isRefExplicit; }
    set
    {
        _isRefExplicit = value;

        if (value)
        {
            // If the model has an explicit reference
            // then all its polygon have an implicit reference
            Debug.Assert(_polygons.None(s => s.IsRefExplicit));
            foreach (var polygon in _polygons)
                polygon.IsRefImplicit = true;
        }
        else
        {
            // If the model doesn't have an explicit reference
            // then all its polygon don't have an implicit reference
            Debug.Assert(_polygons.All(s => s.IsRefImplicit));
            foreach (var polygon in _polygons)
                polygon.IsRefImplicit = false;
        }
    }
}

Questo può essere fatto semplicemente cambiando l'implementazione di ScenePolygon per interrogare il Modello:

SceneModel 

public override bool IsRefExplicit
{
    get { return _isRefExplicit; }
    set { _isRefExplicit = value; }
}

ScenePolygon 

public override bool IsRefImplicit
{
    get { return Model.IsRefExplicit; }
    set { throw new NotSupportedException(); }
}

Nessun altro ciclo.

Ovviamente quanto sopra è supposto che IsRefImplicit su ScenePolygon sarà impostato solo da SceneModel . Se questa ipotesi non è vera, forse non dovresti fare polygon.IsRefImplicit = false; su SceneModel perché IsRefImplicit potrebbe essere stato impostato su true da un altro codice.

Ora, diamo un'occhiata al ScenePolygon di IsRefExplicit :

ScenePolygon 

public override bool IsRefExplicit
{
    get { return _isRefExplicit; }
    set
    {
        _isRefExplicit = value;
        if (value)
        {
            // If the polygon has an explicit reference
            // then the model has an implicit reference
            Debug.Assert(!Model.IsRefExplicit);
            Model.IsRefImplicit = true;
        }
        else
        {
            // If the polygon doens't have an explicit reference
            // then the model doens't have an implicit reference?
            // ...
            // Could there be another polygon of the model with an explicit reference?
            // If there is, then the model should remain with an implicit reference
            Debug.Assert(Model.IsRefImplicit);
            Model.IsRefImplicit = false;
        }
    }
}

In questo caso ciò di cui hai bisogno è il conteggio dei riferimenti. Mantieni nella SceneModel di quanti ScenePolygon ha con IsRefExplicit e lascia che ScenePolygon lo incrementi o lo decresci se necessario. 

public override bool IsRefExplicit
{
    get { return _isRefExplicit; }
    set
    {
        if (_isRefExplicit == value)
        {
            return;
        }
        _isRefExplicit = value;
        if (value)
        {
            Model.IncrementImplicitRefCount();
        }
        else
        {
            Model.DecrementImplicitRefCount();
        }
    }
}

Quindi il modello può implementare IsRefImplicit controllando se il conteggio dei riferimenti corrente è maggiore di 0.

Per astratti, potremmo scrivere le regole in questo modo: 

Model.IsRefImplicit = contains at least one polygon with IsRefExplicit.
    Have a counter, and check if it is greater than 0.
    There is no setter.

Model.IsRefExplicit = all the polygons have IsRefImplicit.
    Store a bool backing field.

Polygon.IsRefImplicit = belongs to an model with IsRefExplicit.
    Read Model.IsRefExplicit
    There is no setter.

Polygon.IsRefExplicit = should mark the model IsRefImplicit.
    Store a bool backing field.
    The setter will increment the counter of the Model when set to true,
                and decrement it when set to false,
                do nothing if the value didn't change.

Quindi la preoccupazione è di annotare IsRefExplicit e lasciare che IsRefImplicit venga popolata dal codice che hai. Quindi, leggerai i dati di origine e guarderai in un dizionario l'oggetto a cui fa riferimento e annotandoli. Se l'oggetto non è nel dizionario, lo si crea e lo si aggiunge.

Se modifichi il tuo codice per utilizzare Interlocked (usa Increment e Decrement per il conteggio dei riferimenti e usa CompareExchange e Exchange su int impostato su 0 o 1 invece che su bool backing fields) quindi il codice risultante sarà thread-safe, e sarete in grado di avere più thread scrivendo IsRefExplicit .

Se cambi i tuoi elenchi / dizionari in soluzioni thread-safe come ConcurrentDictionary , la struttura può anche essere popolata da più thread.

    
risposta data 15.10.2016 - 01:50
fonte

Leggi altre domande sui tag

Paradigmi di registrazione, DI / IoC, gerarchie di oggetti Organizzazione di moduli maven e profili a molla