Tabella di ricerca lineare a tratti lineare

Question

Sto cercando un oggetto di ricerca ottimizzato generico che abbia una funzione f (x) e crei un'approssimazione a tratti lineare con parametri configurabili per l'intervallo di x e gli intervalli di popolazione.

Ovviamente questo non è difficile da scrivere, ma dato che è utile per molte funzioni costose (trig, yield, distance), ho pensato che uno generico potrebbe già esistere. Per favore mi faccia sapere.

Un'altra funzione utile sarebbe quella di serializzare/deserializzare la tabella di ricerca come una tabella di 100.000 punti + piuttosto precisa può richiedere diversi minuti per la costruzione.

Answer 1

Non credo che qualcosa esista direttamente nelle librerie di classi .NET. Qualcosa potrebbe esistere in una libreria di terze parti (like C5 perhaps).

La creazione di una versione generica di una funzione che può accettare intervalli è un po 'complicata in C#, poiché non esiste un tipo o un'interfaccia unificante che fornisce operatori aritmetici. Tuttavia, con un po 'di creatività, è possibile mestiere qualcosa:

// generic linear lookup class, supports any comparable type T 
public class LinearLookup<T> where T : IComparable<T> 
{ 
    private readonly List<T> m_DomainValues = new List<T>(); 

    public LinearLookup(Func<T,T> domainFunc, Func<T,T> rangeFunc, 
      T lowerBound, T upperBound) 
    { 
     m_DomainValues = Range(domainFunc, rangeFunc, 
           lowerBound, upperBound) 
          .ToList(); 
    } 

    public T Lookup(T rangeValue) 
    { 
     // this could be improved for numeric types 
     var index = m_DomainValues.BinarySearch(rangeValue); 
     if(index < 0) 
      index = (-index)-1; 
     return m_DomainValues[index]; 
    } 

    private static IEnumerable<T> Range(Func<T,T> domainFunc, 
     Func<T,T> rangeFunc, T lower, T upper) 
    { 
     var rangeVal = lower; 
     do 
     { 
      yield return domainFunc(rangeVal); 

      rangeVal = rangeFunc(rangeVal); 

     } while(rangeVal.CompareTo(upper) < 0); 
    } 
} 

Questa classe precompute un insieme di valori di dominio per la funzione domainFunc nel range [inferiore, superiore>. Utilizza la ricerca binaria per la ricerca, un compromesso che consente di utilizzare qualsiasi tipo comparabile, non solo i tipi numerici incorporati. La funzione rangeFunc consente di controllare l'incremento tramite codice esterno. Quindi, ecco una ricerca lineare per Math.Sin nel range [0, PI/2> con un incremento di 0,01:

var sinLookup = new LinearLookup(Math.Sin, x => x + 0.01d, 0, Math.PI/2); 
var lookupPI4 = sinLookup[Math.PI/4]; // fetch the value sin(π/4)