Venendo fuori fattori per un algoritmo ponderato?

Question

Sto cercando di trovare un algoritmo ponderato per un'applicazione. Nell'applicazione, è disponibile una quantità limitata di spazio per diversi elementi. Una volta occupato tutto lo spazio, l'algoritmo dovrebbe scegliere gli elementi migliori da rimuovere per fare spazio per nuovi elementi.

Esistono diversi attributi che dovrebbero influenzare questa decisione. Per esempio:

• T: tempo dall'ultimo accesso. (È meglio sostituire qualcosa a cui non è stato possibile accedere da un po '.)
• N: numero di volte accessibile. (È meglio sostituire qualcosa a cui non è stato accesso molte volte.)
• R: numero di elementi che devono essere rimossi per fare spazio per il nuovo elemento. (È meglio sostituire la minima quantità di elementi. Idealmente questo dovrebbe anche prendere in considerazione gli attributi T e N di ciascun elemento sostituito.)

Ho 2 problemi:

1. Capire quanto peso dare ciascuno di questi attributi.
2. Capire come calcolare il peso per un elemento.

(1) Mi rendo conto che emergere il peso per qualcosa del genere è molto soggettivo, ma speravo che ci fosse un metodo standard o qualcosa che può aiutarmi a decidere quanto peso dare ogni attributo. Ad esempio, pensavo che un metodo potesse essere quello di elaborare una serie di due elementi di esempio e quindi confrontare manualmente i due e decidere quale alla fine si dovrebbe essere scelti. Ecco un esempio:

Elemento A: n = 5, t = 2 ore fa.
Elemento B: n = 4, t = 10 minuti fa.

In questo esempio, probabilmente vorrei che fosse l'elemento che viene scelto per essere sostituito poiché sebbene fosse accessibile ancora una volta, non è stato accessibile in un sacco di tempo rispetto a B. Questo metodo sembra che ci vorrebbe Un sacco di tempo e implicherebbero prendere molte decisioni difficili e soggettive. Inoltre, potrebbe non essere banale trovare i pesi risultanti alla fine.

Un altro metodo che mi è venuto in mente è stato quello di scegliere arbitrariamente pesi per i diversi attributi e quindi utilizzare l'applicazione per un po '. Se noto qualcosa di ovviamente sbagliato nell'algoritmo, potrei quindi entrare e modificare leggermente i pesi. Questo è fondamentalmente un metodo "indovina e controllo".

Entrambi questi metodi non sembrano così grandi e spero che ci sia una soluzione migliore.

(2) Una volta che ho capito il peso, non sono sicuro di quale modo sia meglio calcolare il peso. Dovrei solo aggiungere tutto? (In questi esempi, presumo che qualunque elemento abbia il massimo replacementWeight dovrebbe essere quello che verrà sostituito.)

replacementWeight = .4*T - .1*N - 2*R

o moltiplicare tutto?

replacementWeight = (T) * (.5*N) * (.1*R)

Che ne dici di non usare costanti per i pesi? Ad esempio, certo che "tempo" (t) può essere importante, ma una volta passata una quantità di tempo specifica, inizia a non fare molta differenza. Essenzialmente vorrei mettere tutto in un cestino "molto tempo è passato". (EG anche se 8 ore e 7 ore hanno una differenza di un'ora tra i due, questa differenza potrebbe non essere così significativa come la differenza tra 1 minuto e 5 minuti poiché questi due sono molto più recenti.) (O un altro esempio: sostituire (R ) 1 o 2 elementi vanno bene, ma quando inizio a sostituire 5 o 6, questo dovrebbe essere pesantemente ponderato ... quindi non dovrebbe essere lineare.)

replacementWeight = 1/T + sqrt(N) - R*R

Ovviamente (1) e (2) sono strettamente correlati, motivo per cui spero che ci sia un modo migliore per trovare questo tipo di algoritmo.

Answer 1

Quello che stai descrivendo è il classico problema della scelta a Politica di sostituzione della cache. Quale politica è la migliore per te, dipende dai tuoi dati, ma di solito funziona bene:

Innanzitutto, memorizza sempre un nuovo oggetto nella cache, sfrattando il R Il peggiore (s). Non c'è modo di conoscere un priori se un oggetto deve essere archiviato o meno. Se l'oggetto non è utile, cadrà presto di nuovo dalla cache.

La popolare cache di calamari strumenti I seguenti algoritmi di sostituzione della cache:

• Meno recentemente usato (LRU):
  • replacementKey = -T
• Meno frequentemente usato con invecchiamento dinamico (LFUDA):
  • replacementKey = N + C
• Frequenza golosa a dual-dimensione (GDSF):
  • replacementKey = (N/R) + C

C si riferisce a a Fattore di età della cache qui. C è fondamentalmente il replacementKey dell'oggetto che è stato sfrattato per ultimo (o zero).

Nota: la sostituzione viene calcolata quando un oggetto viene inserito o accessibile e conservato accanto all'oggetto. L'oggetto con il più piccolo La sostituzione è sfrattata.

LRU è semplice e spesso abbastanza bravo. Più grande è la cache, meglio funziona.

LFUDA e GDSF sono entrambi compromessi. Lfuda preferisce mantenere oggetti di grandi dimensioni anche se sono meno popolari, nel presupposto che uno colpito a un oggetto di grandi dimensioni costituisce molti colpi per oggetti più piccoli. GDSF fondamentalmente fa il compromesso opposto, mantenendo molti oggetti più piccoli su un minor numero di oggetti di grandi dimensioni. Da quello che scrivi, quest'ultimo potrebbe essere adatto.

Se nessuno di questi soddisfa le tue esigenze, puoi calcolare valori ottimali per T, N e R (e confronta formule diverse per combinarle) minimizzando rimpiangere, la differenza nelle prestazioni tra la tua formula e il ottimale algoritmo, usando, ad esempio, Regressione lineare.

Answer 2

Questo è un problema completamente soggettivo, come fai tu stesso. E una possibilità distinta è che se i tuoi casi di test sono costituiti da coppie (a, b) dove preferisci da A a b, allora potresti scoprire che preferisci da A a B, B a C ma anche su A - cioè non è un ordinamento.

Se non stai attento, la tua funzione potrebbe non esistere!

Se puoi definire una funzione scalare delle tue variabili di input, con vari parametri per coefficienti ed esponenti, potresti essere in grado di stimare tali parametri usando la regressione, ma avrai bisogno di molti dati se hai molti parametri.

Questo è l'approccio dello statistico classico di esaminare prima i dati per identificare un modello e quindi utilizzare quel modello per stimare una particolare realizzazione del modello. Ci sono grandi libri su questo argomento.