Test di tutte le combinazioni

3

Ho bisogno di fare alcune misurazioni delle prestazioni all'interno della mia applicazione. Voglio misurare, modificare alcuni parametri, misurare di nuovo. Ci sono diversi algoritmi che voglio testare e ci sono vari parametri che interagiscono tra loro in quanto le prestazioni totali dipendono da tutti i parametri (ma i parametri stessi non si influenzano a vicenda, ad esempio se imposto da x a 5, rimarrà sempre 5 e la modifica di qualche altro parametro non cambierà x).

Penso che il numero totale di combinazioni sia piuttosto elevato, almeno abbastanza da non voler cambiare manualmente tutto e testare ogni possibilità a mano.

Sto cercando un pezzo di architettura software leggera (oserei dire un modello di progettazione) che mi permette di definire un tipo di parametro set rilevante per un algoritmo, i possibili valori di quei tipi e quel pezzo di il codice dovrebbe quindi essere eseguito attraverso tutte le combinazioni di questi tipi e dei loro valori, per ognuno dei quali viene eseguita la richiesta (chiamando alcune funzioni per modificare i valori, ecc.) e quindi eseguendo l'algoritmo.

Esempio: un algoritmo dipende dai valori x, y e z. x può essere 0 o 1, y può essere "ciao" o "ciao" e z può essere nell'intervallo [0,100]. La soluzione che sto cercando inizia con [0, "ciao", 0], chiama alcune funzioni per impostare i valori di tali variabili, consente la profilazione per un po 'di tempo, quindi passa a [0, "ciao", 1] , ripeti, [0, "ciao", 2] ... ecc.

Questo probabilmente è qualcosa che le persone hanno bisogno di risolvere prima. Come posso risolvere questo elegantemente?

    
posta heishe 11.02.2014 - 01:28
fonte

4 risposte

5

Puoi farlo in (almeno) due modi.

Uno è semplicemente quello di avere un vettore con le cardinalità dei parametri. Quindi dal momento che l'array di parametri è ( leggermente modificato per ottenere numeri univoci ):

[
    [ 0, 1, -1 ],
    [ 'hello', 'goodbye' ],
    [ 0 .. 100 ],
]

le cardinalità sono [3, 2, 101]. Questo dà un prodotto cartesiano di 3 * 2 * 101 = 606 combinazioni. Dato un qualsiasi numero compreso tra 0 e 605, il suo resto modulo 3 è l'indice del parametro nella prima matrice di opzioni, quindi di nuovo modulo 2 per il secondo e di modulo 101 per il terzo. Per esempio. 137:

137 modulo 3 è 2, quindi il primo parametro è -1.    137 intero diviso per 3 è 45, 45 modulo 2 è 1, quindi il secondo parametro è "addio".    45 i.d.b. 2 è 22, quindi il terzo parametro è 22.

Ciò consente di mappare l'intera configurazione su un singolo numero e viceversa. Quindi puoi avere una funzione o un metodo che imposterà la configurazione da un numero, dati gli array di possibili valori.

Ora puoi semplicemente provare tutti i valori in sequenza. Questo è solo un approccio a forza bruta.

Un'altra possibilità è quella di supporre che la funzione di performance f (x, y, z) sia ragionevolmente continua, cioè che il cambiamento nelle prestazioni sia proporzionale al cambiamento di ogni parametro dato dal suo i-th a i + j-th valore; più cambi, più le prestazioni variano.

Se ciò è vero, ci sono diverse opzioni per trovare le massime prestazioni in modo efficiente, senza esaminare tutti i valori possibili. Ad esempio, si genera un numero a caso da 0 a (qui) 605, ottenendo così una configurazione iniziale (x, y, z). Ora puoi aumentare o diminuire uno qualsiasi dei tre parametri, che ti dà al massimo ventisette set di valori da esaminare ( ogni parametro può aumentare di uno, diminuire di uno o rimanere lo stesso, ovvero tre possibilità; tre sono i parametri, quindi aumenti il numero di possibilità per il numero di parametri e ottieni 3 ^ 3 o 27 ). Esegui il test delle prestazioni per ciascuno di questi set. La migliore combinazione sarà il tuo nuovo punto di partenza. Ripeti (vorrai memorizzare nella cache i risultati per le ultime esecuzioni, poiché diversi set sarebbero stati esaminati più volte).

Quando si hanno molti valori possibili per ciascun parametro, questo metodo consente di esaminare relativamente pochi di essi. Se f () è "ragionevolmente" ben educato, questo metodo "camminerà" nello spazio dei parametri seguendo la linea di ascesa più ripida, convergendo rapidamente verso la migliore combinazione. Potresti voler utilizzare tecniche come annealing o riavviare da una posizione iniziale molto diversa per garantire che non tieni "bloccato" al massimo locale.

    
risposta data 11.02.2014 - 02:11
fonte
1

run through all combinations of those types and their values, for each one doing the required stuff (calling some functions to change values, etc.) and then executing the algorithm.

Mi sembra un prodotto cartesiano. Molte lingue dispongono di una libreria per calcolare il prodotto cartesiano di un elenco di elenchi, ad esempio python itertools.product ().

@Iserni ha avuto un ottimo punto, nella maggior parte dei casi, le prestazioni degli algoritmi non sono completamente casuali. Esistono spesso modi per evitare di effettuare ricerche esaurienti, magari a costo di non trovare la soluzione ottimale (ad esempio un'euristica).

    
risposta data 11.02.2014 - 03:02
fonte
1

Non è necessario reinventare la ruota: utilizzare la funzionalità del framework di test dell'unità preferito. Ad esempio, Nunit fornisce un attributo "combinatorio" (e alcuni altri utili attributi come "sequenziale" ) che fa esattamente quello che stai cercando. Per JUnit, trovi componenti aggiuntivi come "jcombinatorial" . Immagino ci siano funzionalità simili per altri framework xUnit.

    
risposta data 11.02.2014 - 08:18
fonte
0

This is probably something that people have needed to solve before.

Sì, davvero.

How do I solve this elegantly?

Vorrei usare Prolog, perché si adatta perfettamente in questo caso. I predicati Prolog sono composti da diverse clausole; definiamo il predicato x/1 ( x/1 significa functor x con arity 1, a.k.a. il numero di argomenti):

x(-1).
x(0).
x(1).

Abbiamo definito 3 clausole alternative per x/1 (l'ordine di dichiarazione è importante). Quindi, qualsiasi chiamata a x(V) con V una variabile libera lascerà i "punti di scelta" che vengono visitati su backtrack. Interattivo:

[eclipse]: x(V).

V = -1
Yes (0.00s cpu, solution 1, maybe more) ? ;

V = 0
Yes (0.00s cpu, solution 2, maybe more) ? ;

V = 1
Yes (0.00s cpu, solution 3)

Tuttavia, non abbiamo necessariamente bisogno di due clausole:

y(Y) :- Y = "hello"; Y = "goodbye".

Qui, l'operatore di disgiunzione ; separa due unificazioni alternative della variabile V con stringhe diverse *. Definiamo anche un predicato z/1 , usando tra / 4 predicato ausiliario incorporato:

z(Result) :- between(0,100,1,Result).

Ora, dovrai chiamare una funzione di test specifica, che dipende in larga misura dai tuoi requisiti precisi. Ma ecco uno schizzo di come chiamarlo:

run :-
     x(X),
     y(Y),
     z(Z),
     test(X,Y,Z),
     % failing here will backtrack over other values of X, Y, Z.
     fail.

% since the previous clause of the run predicate always fail, we
% add another one that will succeed. It will be tried after all values of
% X, Y and Z have been attempted. Since there is no need to have a body, we 
% simply write "run."
run.

Il flusso di controllo del programma è guidato da un meccanismo implicito di backtracking: fondamentalmente, per vedere se run/0 ha esito positivo, proviamo entrambe le clausole, una dopo l'altra. Affinché la prima clausola abbia successo, tutti gli obiettivi elencati devono avere successo. Obiettivi x(X) , y(Y) e z(Z) vincola uno dei possibili valori per liberare le variabili X, Y e Z. Quando raggiungiamo il predicato fail , che fallisce sempre, dobbiamo provare le valutazioni alternative delle variabili libere; prima vengono testati tutti i valori per Z, poi un altro per Y e ancora, tutti i valori di Z, finché non proviamo tutte le combinazioni di X, Y e Z. In effetti, la prima clausola di run/0 non può mai avere successo (ma proviamo comunque, e come effetto collaterale chiamiamo il test con tutte le combinazioni di valori). Alla fine, proviamo con l'altra clausola di run/0 , che riesce banalmente.

Il predicato test/3 è il punto in cui dovresti definire il test. Potresti voler concatenare tutti i tuoi termini e chiamare una shell esterna, ad esempio:

test(X,Y,Z) :-
    join_string(["./test",X,Y,Z]," ",Cmd),
    sh(Cmd).

Alernative, puoi parlare con un altro processo con socket o attraverso un flusso. Questo particolare esempio non gestisce gli spazi possibili negli argomenti, quindi fai attenzione.

@Iserni ha sottolineato che potresti voler evitare una ricerca esauriente. Se pensi di dover abbattere l'albero di ricerca in base a vincoli aggiuntivi, puoi codificare i vincoli e le funzioni di costo come predicati: questo è esattamente il tipo di problemi che le persone risolvono quotidianamente con Prolog.

Non è Python o qualsiasi altro linguaggio di scripting popolare, ma penso che valga la pena provarlo. Dopotutto, se fallisce, puoi semplicemente provare un'altra opzione: -)

(*) Anche se il codice risultante è breve, potrebbe essere più breve utilizzando solo il predicato member/2 per X e Y ( member(X,[-1,0,1]) , member(Y,["hello","goodbye"]) ).

    
risposta data 11.02.2014 - 10:35
fonte

Leggi altre domande sui tag