Algoritmo albero "if-else" ottimale per ridurre al minimo il codice duplicato

4

Ho problemi a formulare questo problema come un algoritmo:

Ho un set di condizioni (combinato con && ) e operazioni, ad esempio:

if (A && B)
    execute C
else if (D && A)
    execute E

Voglio che un algoritmo trovi l'albero "if-else" ottimale che minimizzi la quantità di codice duplicato. La ramificazione ottimale per l'esempio precedente sarebbe:

if (A){
    if (B)
        execute C
    else if (D)
        execute E
}

Il costo dei condizionali duplicati sarà diverso per ogni condizionale, ma è almeno 1 . Il costo per le operazioni duplicate (ad esempio execute C ) è 3 .

Questo mi sembra un problema con uno spanning minimo. O forse qualche altro problema noto di teoria dei grafi. Ma non riesco a capire come rappresentare il problema come un grafico per cominciare.

Ecco un confronto tra i due alberi "if-else" dell'esempio:

    
posta Azmisov 31.12.2013 - 01:22
fonte

3 risposte

4

Evita il più possibile la logica di annidamento nei blocchi interni. Rende il codice più difficile da leggere.

if (!A)
   return

if (B)
   execute C

if (D)
   execute E

Esci se non A. Altrimenti B o D, ma se sai che D è già vero quando B è falso. Puoi rilasciare if (D) e solo eseguire E.

In casi come questo è preferibile utilizzare un interruttore.

if (!A)
   return

switch R
    case B:
       execute C
       break
    case D:
       execute E
       breal
    
risposta data 31.12.2013 - 01:54
fonte
2

Supponendo di non ottimizzare i condizionali, puoi usare un grafico aciclico orientato alla proposizione. Può anche essere considerato come un diagramma di decisione binaria .

Esempio di PDAG:

Leaves are labeled with \top (true), \bot (false), or a Boolean variable.

Non-leaves are \bigtriangleup (logical and), \bigtriangledown (logical or) and \Diamond-nodes (logical not).

\bigtriangleup and \bigtriangledown-nodes have at least one child.

\Diamond-nodes have exactly one child.

Il PDAG consente di utilizzare tutti gli algoritmi standard del grafico su di esso in base alle esigenze. Tuttavia, è meglio che tu stia ottimizzando ogni condizionale che puoi.

    
risposta data 31.12.2013 - 02:13
fonte
1

In un commento hai scritto che si tratta di un problema di generazione di codice, in pratica un modello di fabbrica o costruttore.

Direi che è possibile ottimizzare i condizionali via in molti scenari pratici come nell'esempio qui sotto mostra. Inoltre vorrei dire che se il tempo di esecuzione per ottenere un'informazione booleana su A, B o C varia l'ottimizzazione non può essere fatta ottimizzando se le dichiarazioni / else. Questo risolve tutti gli scenari di cui sono a conoscenza.

Il modo più veloce per valutare sarebbe quello di presentare tutti i booleani in una variabile comune e valutare solo quella singola variabile. A seconda del sistema che si intende eseguire su questo potrebbe o potrebbe non essere possibile e potrebbe essere o non essere già il caso.

La soluzione dovrebbe scalare con un'esecuzione costante fino al punto in cui la quantità di informazioni bool eccedeva la quantità di bit in un intero.

Questo è inteso come una soluzione pragmatica con un insieme finito di booleani in cui è noto a tutti che insieme di booleani dovrebbe risultare in quale serie di esecuzioni.

Ecco alcuni pseudocodici:

func()
{
    unsigned currentSwitches = GetBooleanSet();
    executeable currentExEc = ExecFactory(currentSwitches);
    currentExEc();
}

executeable ExecFactory(unsigned allMySwitches)
{
    switch(allMySwitches)
    {
        case 0x....: return exeLib.HeaterOn; break;
        case 0x....: return exeLib.HeaterOff; break;
        case 0x....: return exeLib.BeepLikeCrazy; break;
        default : return exeLib.NotImplementedExecution; break;
    }
}

Modifica:

A seconda di come ti presenti con i tuoi booleani potresti o non dovresti fare nulla. Uno scenario è che leggete i vostri booleani da una qualche forma di flusso (TCP, File, ecc.) Dove potrebbero essere già stati contattati. Un'altra opzione potrebbe essere che ti trovi in un ambiente logico programmabile in cui le tue opzioni bool condividono già un registro.

Supponiamo che tu non sia in quella posizione e potresti finire con il bit-stringing personalizzato. Ecco un'opzione costosa per farlo in the of of pseudocode:

enum {
bit_A, bit_B, bit C
}

GetBooleanset()
{
return (bool_A << bit_A) | (bool_B << bit_B) | (bool_C << bit_C);
}

Questa espressione sarà ottimizzata dal processo di compilazione e puoi verificare se la velocità soddisfa i tuoi requisiti. A seconda dell'ammontare delle opzioni e della loro volatilità, ad esempio, puoi ottimizzare tracciando le opzioni modificate e ricostruendo solo le parti che sono cambiate.

Dipende molto dall'ambiente in cui lavori.

EDIT:

Ho scritto una piccola implementazione Ansi C dello pseudocodice sopra.

#include <stdio.h>

typedef int (*t_logf)(const char * format, ...);

#define opt_A ( 1U << 0U )
#define opt_B ( 1U << 1U )
#define opt_C ( 1U << 2U )

typedef struct {
    unsigned options;
    t_logf logf;
}System;

typedef void (*execDelegate) (System * system);
void DelegateOne (System * system);
void DelegateTwo (System * system);
void DelegateThree (System * system);
void DelegateDefault (System * system);


void buildOptions(System * system);
execDelegate ExecFactory(System * system);

void main()
{
    System system;
    execDelegate execute;
    system.logf = printf;

    buildOptions(&system);
    execute = ExecFactory(&system);
    execute(&system);

    getchar();
}

void buildOptions(System * system)
{
    //this would obviousely 
    system->options = opt_A | opt_C;
}

execDelegate ExecFactory(System * system)
{
    system->logf("options: 0x%X\n", system->options);
    switch(system->options)
    {
        case opt_A | opt_B | opt_C : return DelegateOne; break;
        case opt_B | opt_C : return DelegateTwo; break;
        case opt_A | opt_C : return DelegateThree; break;
        default : return DelegateDefault; break;
    }
}

void DelegateOne (System * system)
{
    system->logf("one\n");
}

void DelegateTwo (System * system)
{
    system->logf("two\n");
}

void DelegateThree (System * system)
{
    system->logf("three\n");
}

void DelegateDefault (System * system)
{
    system->logf("default\n");
}
    
risposta data 31.12.2013 - 03:38
fonte

Leggi altre domande sui tag