Ottimizzazione matematica in C #
https://stackoverflow.com/questions/412019
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho profilato un'applicazione per tutto il giorno e, dopo aver ottimizzato un paio di bit di codice, me ne sono lasciato sulla mia lista di cose da fare. È la funzione di attivazione per una rete neurale, che viene chiamata oltre 100 milioni di volte. Secondo dotTrace, ammonta a circa il 60% del tempo complessivo della funzione.
Come lo ottimizzeresti?
public static float Sigmoid(double value) {
return (float) (1.0 / (1.0 + Math.Pow(Math.E, -value)));
}
Soluzione
Prova:
public static float Sigmoid(double value) {
return 1.0f / (1.0f + (float) Math.Exp(-value));
}
EDIT: ho fatto un rapido benchmark. Sulla mia macchina, il codice sopra è circa il 43% più veloce del tuo metodo, e questo codice matematicamente equivalente è il più adolescente un po 'più veloce (46% più veloce dell'originale):
public static float Sigmoid(double value) {
float k = Math.Exp(value);
return k / (1.0f + k);
}
MODIFICA 2: Non sono sicuro di quante funzioni generali C # abbiano, ma se #include <math.h> nel tuo codice sorgente dovresti essere in grado di usarlo, che usa un float-exp funzione. Potrebbe essere un po 'più veloce.
public static float Sigmoid(double value) {
float k = expf((float) value);
return k / (1.0f + k);
}
Inoltre, se stai effettuando milioni di chiamate, l'overhead di chiamata delle funzioni potrebbe essere un problema. Prova a creare una funzione inline e vedi se è di aiuto.
Altri suggerimenti
Se è per una funzione di attivazione, è molto importante se il calcolo di e ^ x è completamente accurato?
Ad esempio, se usi l'approssimazione (1 + x / 256) ^ 256, sul mio test Pentium in Java (suppongo che C # essenzialmente si compili con le stesse istruzioni del processore) questo è circa 7-8 volte più veloce di e ^ x (Math.exp ()), ed è preciso fino a 2 cifre decimali fino a circa x di +/- 1,5 e nell'ordine di grandezza corretto nell'intervallo specificato. (Ovviamente, per aumentare a 256, in realtà quadrate il numero 8 volte - non usare Math.Pow per questo!) In Java:
double eapprox = (1d + x / 256d);
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
Continua a raddoppiare o dimezzare 256 (e aggiungere / rimuovere una moltiplicazione) a seconda della precisione con cui desideri che l'approssimazione sia. Anche con n = 4, fornisce comunque circa 1,5 decimali di precisione per i valori di x tra -0,5 e 0,5 (e appare ben 15 volte più veloce di Math.exp ()).
P.S. Ho dimenticato di menzionare - ovviamente non dovresti davvero dividere per 256: moltiplicare per una costante 1/256. Il compilatore JIT di Java effettua automaticamente questa ottimizzazione (almeno, lo fa Hotspot), e stavo assumendo che anche C # dovesse fare.
Dai un'occhiata a questo post . ha un'approssimazione per e ^ x scritta in Java, questo dovrebbe essere il codice C # per esso (non testato):
public static double Exp(double val) {
long tmp = (long) (1512775 * val + 1072632447);
return BitConverter.Int64BitsToDouble(tmp << 32);
}
Nei miei benchmark questo è più di 5 volte più veloce di Math.exp () (in Java). L'approssimazione si basa sul documento & Quot; Un'approssimazione veloce e compatta della funzione esponenziale < ! / a> <> quot; che è stato sviluppato esattamente per essere utilizzato nelle reti neurali. È sostanzialmente lo stesso di una tabella di ricerca di 2048 voci e approssimazione lineare tra le voci, ma tutto questo con i trucchi in virgola mobile IEEE.
MODIFICA: Secondo Salsa speciale questo è ~ 3,25 volte più veloce del Implementazione CLR. Grazie!
- Ricorda che eventuali modifiche a questa funzione di attivazione comportano un costo per comportamenti diversi . Ciò include anche il passaggio al float (e quindi la riduzione della precisione) o l'utilizzo di sostituti di attivazione. Solo sperimentare con il tuo caso d'uso mostrerà la strada giusta.
- Oltre alle semplici ottimizzazioni del codice, consiglierei anche di prendere in considerazione parallelizzazione dei calcoli (vale a dire: sfruttare più core della tua macchina o persino macchine su Windows Azure Clouds) e migliorare il algoritmi di formazione.
AGGIORNAMENTO: Pubblica nelle tabelle di ricerca per le funzioni di attivazione ANN
AGGIORNAMENTO2: ho rimosso il punto su LUT poiché li ho confusi con l'hashing completo. Grazie a Henrik Gustafsson per avermi riportato in pista. Quindi la memoria non è un problema, sebbene lo spazio di ricerca sia ancora incasinato con extrema locale un po '.
A 100 milioni di chiamate, vorrei iniziare a chiedermi se il sovraccarico del profiler non distorca i risultati. Sostituisci il calcolo con un no-op e vedi se è ancora segnalato per consumare il 60% del tempo di esecuzione ...
O meglio ancora, crea alcuni dati di test e usa un cronometro per profilare circa un milione di chiamate.
Se sei in grado di interagire con C ++, potresti prendere in considerazione l'archiviazione di tutti i valori in un array e scorrere su di essi usando SSE in questo modo:
void sigmoid_sse(float *a_Values, float *a_Output, size_t a_Size){
__m128* l_Output = (__m128*)a_Output;
__m128* l_Start = (__m128*)a_Values;
__m128* l_End = (__m128*)(a_Values + a_Size);
const __m128 l_One = _mm_set_ps1(1.f);
const __m128 l_Half = _mm_set_ps1(1.f / 2.f);
const __m128 l_OneOver6 = _mm_set_ps1(1.f / 6.f);
const __m128 l_OneOver24 = _mm_set_ps1(1.f / 24.f);
const __m128 l_OneOver120 = _mm_set_ps1(1.f / 120.f);
const __m128 l_OneOver720 = _mm_set_ps1(1.f / 720.f);
const __m128 l_MinOne = _mm_set_ps1(-1.f);
for(__m128 *i = l_Start; i < l_End; i++){
// 1.0 / (1.0 + Math.Pow(Math.E, -value))
// 1.0 / (1.0 + Math.Exp(-value))
// value = *i so we need -value
__m128 value = _mm_mul_ps(l_MinOne, *i);
// exp expressed as inifite series 1 + x + (x ^ 2 / 2!) + (x ^ 3 / 3!) ...
__m128 x = value;
// result in l_Exp
__m128 l_Exp = l_One; // = 1
l_Exp = _mm_add_ps(l_Exp, x); // += x
x = _mm_mul_ps(x, x); // = x ^ 2
l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_Half, x)); // += (x ^ 2 * (1 / 2))
x = _mm_mul_ps(value, x); // = x ^ 3
l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver6, x)); // += (x ^ 3 * (1 / 6))
x = _mm_mul_ps(value, x); // = x ^ 4
l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver24, x)); // += (x ^ 4 * (1 / 24))
#ifdef MORE_ACCURATE
x = _mm_mul_ps(value, x); // = x ^ 5
l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver120, x)); // += (x ^ 5 * (1 / 120))
x = _mm_mul_ps(value, x); // = x ^ 6
l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver720, x)); // += (x ^ 6 * (1 / 720))
#endif
// we've calculated exp of -i
// now we only need to do the '1.0 / (1.0 + ...' part
*l_Output++ = _mm_rcp_ps(_mm_add_ps(l_One, l_Exp));
}
}
Tuttavia, ricorda che gli array che utilizzerai dovrebbero essere allocati usando _aligned_malloc (some_size * sizeof (float), 16) perché SSE richiede che la memoria sia allineata a un limite.
Utilizzando SSE, posso calcolare il risultato per tutti i 100 milioni di elementi in circa mezzo secondo. Tuttavia, allocare tanta memoria alla volta ti costerà quasi i due terzi di un gigabyte, quindi suggerirei di elaborare più ma più piccoli array alla volta. Potresti anche prendere in considerazione l'utilizzo di un doppio approccio di buffering con almeno 100.000 elementi.
Inoltre, se il numero di elementi inizia a crescere considerevolmente, potresti voler scegliere di elaborare queste cose sulla GPU (basta creare una texture float4 1D ed eseguire uno shader di frammenti molto banale).
FWIW, ecco i miei benchmark C # per le risposte già pubblicate. (Vuoto è una funzione che restituisce solo 0, per misurare l'overhead della chiamata di funzione)
Empty Function: 79ms 0 Original: 1576ms 0.7202294 Simplified: (soprano) 681ms 0.7202294 Approximate: (Neil) 441ms 0.7198783 Bit Manip: (martinus) 836ms 0.72318 Taylor: (Rex Logan) 261ms 0.7202305 Lookup: (Henrik) 182ms 0.7204863
public static object[] Time(Func<double, float> f) {
var testvalue = 0.9456;
var sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1e7; i++)
f(testvalue);
return new object[] { sw.ElapsedMilliseconds, f(testvalue) };
}
public static void Main(string[] args) {
Console.WriteLine("Empty: {0,10}ms {1}", Time(Empty));
Console.WriteLine("Original: {0,10}ms {1}", Time(Original));
Console.WriteLine("Simplified: {0,10}ms {1}", Time(Simplified));
Console.WriteLine("Approximate: {0,10}ms {1}", Time(ExpApproximation));
Console.WriteLine("Bit Manip: {0,10}ms {1}", Time(BitBashing));
Console.WriteLine("Taylor: {0,10}ms {1}", Time(TaylorExpansion));
Console.WriteLine("Lookup: {0,10}ms {1}", Time(LUT));
}
In cima alla mia testa, questo documento spiega un metodo di approssimazione l'esponenziale abusando di virgola mobile , (fai clic sul collegamento in alto a destra per PDF) ma non so se ti sarà molto utile in .NET.
Inoltre, un altro punto: allo scopo di addestrare rapidamente grandi reti, il sigmoid logistico che stai usando è piuttosto terribile. Vedere la sezione 4.4 di Backprop efficiente di LeCun et al e usare qualcosa centrato sullo zero (in realtà, leggi l'intero documento, è immensamente utile).
F # ha prestazioni migliori rispetto a C # negli algoritmi matematici .NET. Quindi riscrivere la rete neurale in F # potrebbe migliorare le prestazioni complessive.
Se implementiamo nuovamente Snippet di benchmarking LUT (sto usando una versione leggermente ottimizzata) in F #, quindi il codice risultante:
- esegue il benchmark sigmoid1 in 588,8ms anziché 3899,2ms
- esegue il benchmark sigmoid2 (LUT) in 156,6 ms anziché 411,4 ms
Ulteriori dettagli sono disponibili nella post di blog . Ecco il JIC dello snippet F #:
#light
let Scale = 320.0f;
let Resolution = 2047;
let Min = -single(Resolution)/Scale;
let Max = single(Resolution)/Scale;
let range step a b =
let count = int((b-a)/step);
seq { for i in 0 .. count -> single(i)*step + a };
let lut = [|
for x in 0 .. Resolution ->
single(1.0/(1.0 + exp(-double(x)/double(Scale))))
|]
let sigmoid1 value = 1.0f/(1.0f + exp(-value));
let sigmoid2 v =
if (v <= Min) then 0.0f;
elif (v>= Max) then 1.0f;
else
let f = v * Scale;
if (v>0.0f) then lut.[int (f + 0.5f)]
else 1.0f - lut.[int(0.5f - f)];
let getError f =
let test = range 0.00001f -10.0f 10.0f;
let errors = seq {
for v in test ->
abs(sigmoid1(single(v)) - f(single(v)))
}
Seq.max errors;
open System.Diagnostics;
let test f =
let sw = Stopwatch.StartNew();
let mutable m = 0.0f;
let result =
for t in 1 .. 10 do
for x in 1 .. 1000000 do
m <- f(single(x)/100000.0f-5.0f);
sw.Elapsed.TotalMilliseconds;
printf "Max deviation is %f\n" (getError sigmoid2)
printf "10^7 iterations using sigmoid1: %f ms\n" (test sigmoid1)
printf "10^7 iterations using sigmoid2: %f ms\n" (test sigmoid2)
let c = System.Console.ReadKey(true);
E l'output (rilascia la compilation contro F # 1.9.6.2 CTP senza debugger):
Max deviation is 0.001664
10^7 iterations using sigmoid1: 588.843700 ms
10^7 iterations using sigmoid2: 156.626700 ms
AGGIORNAMENTO: benchmarking aggiornato per utilizzare 10 ^ 7 iterazioni per rendere i risultati comparabili con C
AGGIORNAMENTO2: ecco i risultati delle prestazioni della implementazione C da la stessa macchina da confrontare con:
Max deviation is 0.001664
10^7 iterations using sigmoid1: 628 ms
10^7 iterations using sigmoid2: 157 ms
Nota: questo è il seguito di questo post.
Modifica: Aggiorna per calcolare la stessa cosa di this e < a href = "https://stackoverflow.com/questions/412019/code-optimizations#416180"> questo , prendendo spunto da questo .
Ora guarda cosa mi hai fatto fare! Mi hai fatto installare Mono!
$ gmcs -optimize test.cs && mono test.exe
Max deviation is 0.001663983
10^7 iterations using Sigmoid1() took 1646.613 ms
10^7 iterations using Sigmoid2() took 237.352 ms
C non vale più la pena, il mondo sta andando avanti :)
Quindi, poco più di un fattore 10 6 più veloce. Qualcuno con una finestra di Windows può investigare l'utilizzo della memoria e le prestazioni usando roba MS :)
L'uso di LUT per le funzioni di attivazione non è così raro, specialmente se implementato nell'hardware. Ci sono molte varianti ben collaudate del concetto là fuori se sei disposto a includere quei tipi di tabelle. Tuttavia, come è già stato sottolineato, l'aliasing potrebbe rivelarsi un problema, ma ci sono anche modi per aggirare questo. Qualche ulteriore lettura:
- NEURObjects di Giorgio Valentini (c'è anche un documento su questo)
- Reti neurali con funzioni di attivazione LUT digitale
- Potenziamento dell'estrazione delle funzionalità della rete neurale mediante funzioni di attivazione a precisione ridotta
- Un nuovo algoritmo di apprendimento per reti neurali con pesi interi e funzioni di attivazione non lineare quantizzate
- Gli effetti di quantizzazione su reti neurali con funzioni di alto ordine
Alcuni gotchas con questo:
- L'errore aumenta quando si raggiunge all'esterno della tabella (ma converge a 0 agli estremi); per x circa + -7,0. Ciò è dovuto al fattore di ridimensionamento scelto. Valori maggiori di SCALE danno errori più alti nella gamma media, ma più piccoli ai bordi.
- Questo è generalmente un test molto stupido, e non conosco C #, è solo una semplice conversione del mio codice C :)
- Rinat Abdullin è molto corretto che l'aliasing e la perdita di precisione potrebbero causare problemi, ma dal momento che ho Non ho visto le variabili per questo posso solo consigliarti di provare questo. In effetti, sono d'accordo con tutto ciò che dice ad eccezione del problema delle tabelle di ricerca.
Perdonate la codifica copia-incolla ...
using System;
using System.Diagnostics;
class LUTTest {
private const float SCALE = 320.0f;
private const int RESOLUTION = 2047;
private const float MIN = -RESOLUTION / SCALE;
private const float MAX = RESOLUTION / SCALE;
private static readonly float[] lut = InitLUT();
private static float[] InitLUT() {
var lut = new float[RESOLUTION + 1];
for (int i = 0; i < RESOLUTION + 1; i++) {
lut[i] = (float)(1.0 / (1.0 + Math.Exp(-i / SCALE)));
}
return lut;
}
public static float Sigmoid1(double value) {
return (float) (1.0 / (1.0 + Math.Exp(-value)));
}
public static float Sigmoid2(float value) {
if (value <= MIN) return 0.0f;
if (value >= MAX) return 1.0f;
if (value >= 0) return lut[(int)(value * SCALE + 0.5f)];
return 1.0f - lut[(int)(-value * SCALE + 0.5f)];
}
public static float error(float v0, float v1) {
return Math.Abs(v1 - v0);
}
public static float TestError() {
float emax = 0.0f;
for (float x = -10.0f; x < 10.0f; x+= 0.00001f) {
float v0 = Sigmoid1(x);
float v1 = Sigmoid2(x);
float e = error(v0, v1);
if (e > emax) emax = e;
}
return emax;
}
public static double TestPerformancePlain() {
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 10; i++) {
for (float x = -5.0f; x < 5.0f; x+= 0.00001f) {
Sigmoid1(x);
}
}
sw.Stop();
return sw.Elapsed.TotalMilliseconds;
}
public static double TestPerformanceLUT() {
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 10; i++) {
for (float x = -5.0f; x < 5.0f; x+= 0.00001f) {
Sigmoid2(x);
}
}
sw.Stop();
return sw.Elapsed.TotalMilliseconds;
}
static void Main() {
Console.WriteLine("Max deviation is {0}", TestError());
Console.WriteLine("10^7 iterations using Sigmoid1() took {0} ms", TestPerformancePlain());
Console.WriteLine("10^7 iterations using Sigmoid2() took {0} ms", TestPerformanceLUT());
}
}
Primo pensiero: che ne dici di alcune statistiche sulla variabile dei valori?
- Sono i valori di " valore " tipicamente piccolo -10 < = valore < = 10?
In caso contrario, probabilmente puoi ottenere un boost testando valori fuori limite
if(value < -10) return 0;
if(value > 10) return 1;
- I valori vengono ripetuti spesso?
In tal caso, puoi probabilmente trarre vantaggio da Memoization (probabilmente no, ma non fa male controllare ....)
if(sigmoidCache.containsKey(value)) return sigmoidCache.get(value);
Se nessuno di questi può essere applicato, allora come alcuni altri hanno suggerito, forse puoi cavartela riducendo la precisione del tuo sigmoide ...
Soprano ha avuto delle belle ottimizzazioni nella tua chiamata:
public static float Sigmoid(double value)
{
float k = Math.Exp(value);
return k / (1.0f + k);
}
Se provi una tabella di ricerca e scopri che utilizza troppa memoria, puoi sempre guardare il valore del tuo parametro per ogni chiamata successiva e utilizzare una tecnica di memorizzazione nella cache.
Ad esempio, prova a memorizzare nella cache l'ultimo valore e il risultato. Se la chiamata successiva ha lo stesso valore di quella precedente, non è necessario calcolarla poiché si sarebbe memorizzato nella cache l'ultimo risultato. Se la chiamata corrente era la stessa della precedente chiamata anche 1 su 100 volte, potresti potenzialmente salvare 1 milione di calcoli.
In alternativa, è possibile che entro 10 chiamate successive il parametro value sia in media le stesse 2 volte, quindi è possibile provare a memorizzare nella cache gli ultimi 10 valori / risposte.
Idea: forse puoi creare una (grande) tabella di ricerca con i valori pre-calcolati?
Questo è leggermente fuori tema, ma solo per curiosità, ho fatto la stessa implementazione di quello in C , C # e F # in Java. Lascio questo qui nel caso in cui qualcun altro sia curioso.
Risultato:
$ javac LUTTest.java && java LUTTest
Max deviation is 0.001664
10^7 iterations using sigmoid1() took 1398 ms
10^7 iterations using sigmoid2() took 177 ms
Suppongo che il miglioramento rispetto a C # nel mio caso sia dovuto alla migliore ottimizzazione di Java rispetto a Mono per OS X. Su un'implementazione MS .NET simile (rispetto a Java 6 se qualcuno vuole pubblicare numeri comparativi) suppongo che i risultati sarebbe diverso.
Codice:
public class LUTTest {
private static final float SCALE = 320.0f;
private static final int RESOLUTION = 2047;
private static final float MIN = -RESOLUTION / SCALE;
private static final float MAX = RESOLUTION / SCALE;
private static final float[] lut = initLUT();
private static float[] initLUT() {
float[] lut = new float[RESOLUTION + 1];
for (int i = 0; i < RESOLUTION + 1; i++) {
lut[i] = (float)(1.0 / (1.0 + Math.exp(-i / SCALE)));
}
return lut;
}
public static float sigmoid1(double value) {
return (float) (1.0 / (1.0 + Math.exp(-value)));
}
public static float sigmoid2(float value) {
if (value <= MIN) return 0.0f;
if (value >= MAX) return 1.0f;
if (value >= 0) return lut[(int)(value * SCALE + 0.5f)];
return 1.0f - lut[(int)(-value * SCALE + 0.5f)];
}
public static float error(float v0, float v1) {
return Math.abs(v1 - v0);
}
public static float testError() {
float emax = 0.0f;
for (float x = -10.0f; x < 10.0f; x+= 0.00001f) {
float v0 = sigmoid1(x);
float v1 = sigmoid2(x);
float e = error(v0, v1);
if (e > emax) emax = e;
}
return emax;
}
public static long sigmoid1Perf() {
float y = 0.0f;
long t0 = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
for (float x = -5.0f; x < 5.0f; x+= 0.00001f) {
y = sigmoid1(x);
}
}
long t1 = System.currentTimeMillis();
System.out.printf("",y);
return t1 - t0;
}
public static long sigmoid2Perf() {
float y = 0.0f;
long t0 = System.currentTimeMillis();
for (int i = 0; i < 10; i++) {
for (float x = -5.0f; x < 5.0f; x+= 0.00001f) {
y = sigmoid2(x);
}
}
long t1 = System.currentTimeMillis();
System.out.printf("",y);
return t1 - t0;
}
public static void main(String[] args) {
System.out.printf("Max deviation is %f\n", testError());
System.out.printf("10^7 iterations using sigmoid1() took %d ms\n", sigmoid1Perf());
System.out.printf("10^7 iterations using sigmoid2() took %d ms\n", sigmoid2Perf());
}
}
Mi rendo conto che è passato un anno da quando è emersa questa domanda, ma l'ho incontrata a causa della discussione sulle prestazioni di F # e C rispetto a C #. Ho giocato con alcuni dei campioni di altri responder e ho scoperto che i delegati sembrano eseguire più velocemente di una normale chiamata al metodo ma non vi è alcun vantaggio apparente sulle prestazioni di F # rispetto a C # .
- C: 166ms
- C # (delegato): 275ms
- C # (metodo): 431ms
- C # (metodo, contatore float): 2.656 ms
- F #: 404ms
Il C # con un contatore float era una porta diritta del codice C. È molto più veloce usare un int nel ciclo for.
Potresti anche considerare di sperimentare funzioni di attivazione alternative che sono più economiche da valutare. Ad esempio:
f(x) = (3x - x**3)/2
(che potrebbe essere considerato come
f(x) = x*(3 - x*x)/2
per una moltiplicazione in meno). Questa funzione ha una strana simmetria e la sua derivata è banale. Usarlo per una rete neurale richiede la normalizzazione della somma degli input dividendo per il numero totale di input (limitando il dominio a [-1..1], che è anche range).
Una leggera variazione sul tema del Soprano:
public static float Sigmoid(double value) {
float v = value;
float k = Math.Exp(v);
return k / (1.0f + k);
}
Dato che stai solo dopo un singolo risultato di precisione, perché fare in modo che la funzione Math.Exp calcoli un doppio? Qualsiasi calcolatore esponente che utilizza una somma iterativa (consultare l'espansione di e x ) richiederà più tempo per una maggiore precisione, ogni volta. E il doppio è il doppio del lavoro del singolo! In questo modo, converti prima in singolo, poi esegui il tuo esponenziale.
Ma la funzione expf dovrebbe essere ancora più veloce. Tuttavia, non vedo la necessità del cast di soprano (float) per passare a expf, a meno che C # non esegua implicitamente la conversione float-double.
Altrimenti, usa semplicemente una lingua reale , come FORTRAN ...
Ci sono molte buone risposte qui. Suggerirei di eseguirlo questa tecnica , solo per essere sicuri
- Non lo stai chiamando più volte del necessario.
(A volte le funzioni vengono chiamate più del necessario, solo perché sono così facili da chiamare.) - Non lo stai chiamando ripetutamente con gli stessi argomenti
(dove è possibile utilizzare la memoization)
A proposito, la funzione che hai è la funzione di log inverso,
o l'inverso della funzione log-odds ratio log(f/(1-f)).
(aggiornato con misurazioni delle prestazioni) (aggiornato di nuovo con risultati reali :)
Penso che una soluzione di tabella di ricerca ti porterebbe molto lontano quando si tratta di prestazioni, con una memoria trascurabile e costi di precisione.
Il seguente frammento è un'implementazione di esempio in C (non parlo abbastanza fluentemente c # per codificarlo a secco). Funziona e funziona abbastanza bene, ma sono sicuro che ci sia un bug :)
#include <math.h>
#include <stdio.h>
#include <time.h>
#define SCALE 320.0f
#define RESOLUTION 2047
#define MIN -RESOLUTION / SCALE
#define MAX RESOLUTION / SCALE
static float sigmoid_lut[RESOLUTION + 1];
void init_sigmoid_lut(void) {
int i;
for (i = 0; i < RESOLUTION + 1; i++) {
sigmoid_lut[i] = (1.0 / (1.0 + exp(-i / SCALE)));
}
}
static float sigmoid1(const float value) {
return (1.0f / (1.0f + expf(-value)));
}
static float sigmoid2(const float value) {
if (value <= MIN) return 0.0f;
if (value >= MAX) return 1.0f;
if (value >= 0) return sigmoid_lut[(int)(value * SCALE + 0.5f)];
return 1.0f-sigmoid_lut[(int)(-value * SCALE + 0.5f)];
}
float test_error() {
float x;
float emax = 0.0;
for (x = -10.0f; x < 10.0f; x+=0.00001f) {
float v0 = sigmoid1(x);
float v1 = sigmoid2(x);
float error = fabsf(v1 - v0);
if (error > emax) { emax = error; }
}
return emax;
}
int sigmoid1_perf() {
clock_t t0, t1;
int i;
float x, y = 0.0f;
t0 = clock();
for (i = 0; i < 10; i++) {
for (x = -5.0f; x <= 5.0f; x+=0.00001f) {
y = sigmoid1(x);
}
}
t1 = clock();
printf("", y); /* To avoid sigmoidX() calls being optimized away */
return (t1 - t0) / (CLOCKS_PER_SEC / 1000);
}
int sigmoid2_perf() {
clock_t t0, t1;
int i;
float x, y = 0.0f;
t0 = clock();
for (i = 0; i < 10; i++) {
for (x = -5.0f; x <= 5.0f; x+=0.00001f) {
y = sigmoid2(x);
}
}
t1 = clock();
printf("", y); /* To avoid sigmoidX() calls being optimized away */
return (t1 - t0) / (CLOCKS_PER_SEC / 1000);
}
int main(void) {
init_sigmoid_lut();
printf("Max deviation is %0.6f\n", test_error());
printf("10^7 iterations using sigmoid1: %d ms\n", sigmoid1_perf());
printf("10^7 iterations using sigmoid2: %d ms\n", sigmoid2_perf());
return 0;
}
I risultati precedenti erano dovuti all'ottimizzatore che faceva il suo lavoro e ottimizzava i calcoli. La sua effettiva esecuzione del codice produce risultati leggermente diversi e molto più interessanti (sulla mia strada MB Air lenta):
$ gcc -O2 test.c -o test && ./test
Max deviation is 0.001664
10^7 iterations using sigmoid1: 571 ms
10^7 iterations using sigmoid2: 113 ms
TODO:
Ci sono cose da migliorare e modi per rimuovere i punti deboli; come fare è lasciato come esercizio al lettore :)
- Ottimizza l'intervallo della funzione per evitare il salto in cui la tabella inizia e finisce.
- Aggiungi una leggera funzione noise per nascondere gli artefatti di aliasing.
- Come diceva Rex, l'interpolazione potrebbe renderti un po 'più preciso dal punto di vista della precisione pur essendo piuttosto economico dal punto di vista delle prestazioni.
Esistono funzioni molto più veloci che fanno cose molto simili:
x / (1 + abs(x)) & # 8211; sostituzione rapida per TAHN
E allo stesso modo:
x / (2 + 2 * abs(x)) + 0.5 - sostituzione rapida per SIGMOID
Facendo una ricerca su Google, ho trovato un'implementazione alternativa della funzione Sigmoid.
public double Sigmoid(double x)
{
return 2 / (1 + Math.Exp(-2 * x)) - 1;
}
È corretto per le tue esigenze? È più veloce?
http://dynamicnotions.blogspot.com/2008 /09/sigmoid-function-in-c.html
1) Lo chiami da un solo posto? In tal caso, è possibile ottenere una piccola quantità di prestazioni spostando il codice da quella funzione e posizionandolo esattamente dove normalmente si chiamerebbe la funzione Sigmoid. Questa idea non mi piace in termini di leggibilità del codice e organizzazione, ma quando è necessario ottenere l'ultimo guadagno in termini di prestazioni, questo potrebbe essere utile perché penso che le chiamate di funzione richiedano un push / pop di registri nello stack, che potrebbe essere evitato se il tuo il codice era tutto in linea.
2) Non ho idea se questo possa aiutare, ma prova a rendere il parametro della tua funzione un parametro ref. Vedi se è più veloce. Avrei suggerito di renderlo const (che sarebbe stata un'ottimizzazione se questo fosse in c ++) ma c # non supporta i parametri const.
Se hai bisogno di un gigantesco aumento di velocità, probabilmente potresti cercare di parallelizzare la funzione usando la forza (ge). IOW, usa DirectX per controllare la scheda grafica e farlo per te. Non ho idea di come farlo, ma ho visto persone usare le schede grafiche per tutti i tipi di calcoli.
Ho visto che molte persone qui stanno cercando di usare l'approssimazione per rendere Sigmoid più veloce. Tuttavia, è importante sapere che Sigmoid può anche essere espresso usando tanh, non solo exp. Il calcolo di Sigmoid in questo modo è circa 5 volte più veloce che con esponenziale, e usando questo metodo non si sta approssimando nulla, quindi il comportamento originale di Sigmoid viene mantenuto così com'è.
public static double Sigmoid(double value)
{
return 0.5d + 0.5d * Math.Tanh(value/2);
}
Naturalmente, la parellizzazione sarebbe il prossimo passo per il miglioramento delle prestazioni, ma per quanto riguarda il calcolo grezzo, l'utilizzo di Math.Tanh è più veloce di Math.Exp.
