'dominio di attività di una funzione'
Buongiorno, spero che qualcuno di voi può essermi di aiuto.
Sto cercando un algoritmo efficiente per trovare il 'periodo di attività' di una funzione...
mi spiego meglio, ho dei dati in tabella che graficati sono rappresentati dall'immagine uploadata, cerco una funzione efficiente che mi ritorni il range delle x dove l'attività è maggiore, in questo caso il fronte di salita (per esempio [75000:200000])
Tenendo in considerazione che sto lavorando con valori discreti in x.
Qualche consiglio? Thanks in advance...
Sto cercando un algoritmo efficiente per trovare il 'periodo di attività' di una funzione...
mi spiego meglio, ho dei dati in tabella che graficati sono rappresentati dall'immagine uploadata, cerco una funzione efficiente che mi ritorni il range delle x dove l'attività è maggiore, in questo caso il fronte di salita (per esempio [75000:200000])
Tenendo in considerazione che sto lavorando con valori discreti in x.
Qualche consiglio? Thanks in advance...
Risposte
grazie davvero per la spiegazione. Vedo ciò che posso fare!
ok. proviamo...
Penso che i tuoi dati siano salvati secondo il modello punto-valore.
Sia $D={|x in RR,v in RR}$ l'insieme dei dati discreti e $N$ la sua cardinalità. Un elemento qualsiasi lo denotiamo come una coppia $$ dove $x$ è il punto analizzato e $v$ il valore della funzione.
Ordiniamo $D$ secondo i valori di $x$ crescenti perciò diamo una relazione d'ordine $<=$ su $D$.
sia $S$ l'insieme delle distanze tra i punti (essendo tutto bello bello del mondo discreto utilizziamo il rapporto incrementale), allora:
$\forall i, in D$ con $x_{i-1} <= x_{i} $ perciò $S(i) = (v_i - v_{i-1}) / (x_{i} - x_{i-1})$ dove $i=2...N$
Notando che in $S$ ci sono sia valori positivi che negativi, tutto questo è servito per poter ridursi al problema di sottosequenza di somma massima o Maximum subarray problem. In letteratura son descritti i più vari algoritmi da $O(n^3)$ a $O(n)$.
Forse bisogna considerare di mettere un $\epsilon$ fissato, per filtrare dati che si son stabilizzai su un certo valore, ma secondo me con la riduzione del problema e modificandolo un attimo si ha sicuramente il range che cerchi.
Perciò quello che devi fare in algoritmo: ordinare, calcolare le distanze e poi basta che cerchi una versione dell'algoritmo nel tuo linguaggio preferito e hai finito.
penso che così risolvi (sincaso scrivi qui che rivediamo).
EDIT:
alcune note:
- sull'insieme $S$ c'è una relazione di ordine dato da $i$ nel momento dell'inserimento dei vari dati (le distanze). E' semplicemente una generalizzazione di un vettore $S$
- se l'algoritmo di MSS ti da un intervallo su $S[]$ e ti da degli indici di ritorno mettiamo $s_k$ e $s_m$ con $k>m$ questi sono delle distanze e non è il dato che cerchi. Devi convertirlo nell'insieme originale cioè in $D$. In pratica $k = {i,i-1} in D$ con la relativia implicazione di calcolo inverso (banale). Uguale con $m$.
- la complessità dell'algoritmo con ordinamento $O(nlogn) +$ calcolo distanze $O(n) +$ MSS mettiamo $O(n)$ $in O(nlogn)$ cioè è sovrastato dall'ordinamento (se scegli la versione più efficiente del problema della sottosequenza di somma massima, sempre se corretta).
Penso che i tuoi dati siano salvati secondo il modello punto-valore.
Sia $D={
Ordiniamo $D$ secondo i valori di $x$ crescenti perciò diamo una relazione d'ordine $<=$ su $D$.
sia $S$ l'insieme delle distanze tra i punti (essendo tutto bello bello del mondo discreto utilizziamo il rapporto incrementale), allora:
$\forall i
Notando che in $S$ ci sono sia valori positivi che negativi, tutto questo è servito per poter ridursi al problema di sottosequenza di somma massima o Maximum subarray problem. In letteratura son descritti i più vari algoritmi da $O(n^3)$ a $O(n)$.
Forse bisogna considerare di mettere un $\epsilon$ fissato, per filtrare dati che si son stabilizzai su un certo valore, ma secondo me con la riduzione del problema e modificandolo un attimo si ha sicuramente il range che cerchi.
Perciò quello che devi fare in algoritmo: ordinare, calcolare le distanze e poi basta che cerchi una versione dell'algoritmo nel tuo linguaggio preferito e hai finito.
penso che così risolvi (sincaso scrivi qui che rivediamo).
EDIT:
alcune note:
- sull'insieme $S$ c'è una relazione di ordine dato da $i$ nel momento dell'inserimento dei vari dati (le distanze). E' semplicemente una generalizzazione di un vettore $S$
- se l'algoritmo di MSS ti da un intervallo su $S[]$ e ti da degli indici di ritorno mettiamo $s_k$ e $s_m$ con $k>m$ questi sono delle distanze e non è il dato che cerchi. Devi convertirlo nell'insieme originale cioè in $D$. In pratica $k = {i,i-1} in D$ con la relativia implicazione di calcolo inverso (banale). Uguale con $m$.
- la complessità dell'algoritmo con ordinamento $O(nlogn) +$ calcolo distanze $O(n) +$ MSS mettiamo $O(n)$ $in O(nlogn)$ cioè è sovrastato dall'ordinamento (se scegli la versione più efficiente del problema della sottosequenza di somma massima, sempre se corretta).
i dati sono monotoni crescenti, anche se la derivata è molto variabile (vedi figura). Cerco un algoritmo che mi dica quando la derivata si stabilizza sotto una certa soglia e ci rimane per sempre...
per ora ho risolto cosi: prendo il grafico della derivata nel range delle x che mi interessa, trovo il massimo e stabilisco una soglia minore di esso, dopo di che definisco dominio di attività il range delle x che va dalla prima all'ultima intersezione con la soglia. sembra funzionare ma a "occhio" naturalmente esce meglio, e poi dipende molto dalla soglia che scelgo...
grazie
per ora ho risolto cosi: prendo il grafico della derivata nel range delle x che mi interessa, trovo il massimo e stabilisco una soglia minore di esso, dopo di che definisco dominio di attività il range delle x che va dalla prima all'ultima intersezione con la soglia. sembra funzionare ma a "occhio" naturalmente esce meglio, e poi dipende molto dalla soglia che scelgo...
grazie
Ciao,
ha un andamento sempre regolare nell'input la funzione dei dati?
Es:
c'è sempre un fronte in salita. Perciò l'analisi si riduce ad istanziale un tipo di algoritmo per un tipo particolare di funzione.
Oppure può capitare anche una funzione che è sempre crescente perciò il massimo intervallo di attività sono il max e min dei dati discreti.
Per capirci i dati hanno un andamento stabile e regolare?
"silviusbob":
ritorni il range delle x dove l'attività è maggiore,
ha un andamento sempre regolare nell'input la funzione dei dati?
Es:
c'è sempre un fronte in salita. Perciò l'analisi si riduce ad istanziale un tipo di algoritmo per un tipo particolare di funzione.
Oppure può capitare anche una funzione che è sempre crescente perciò il massimo intervallo di attività sono il max e min dei dati discreti.
Per capirci i dati hanno un andamento stabile e regolare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo