Venir avec des facteurs pour un algorithme pondéré?

Question

Je suis en train de trouver un algorithme pondéré pour une application. Dans l'application, il y a une quantité limitée d'espace disponible pour différents éléments. Une fois que tout l'espace est occupé, l'algorithme doit choisir le meilleur élément (s) de retirer afin de faire de la place pour les nouveaux éléments.

Il existe différents attributs qui devraient influer sur cette décision. Par exemple:

• T: Temps écoulé depuis la dernière fois. (Il est préférable de remplacer quelque chose qui n'a pas été consulté en temps.)
• N: Nombre d'accès. (Il est préférable de remplacer quelque chose qui n'a pas été consulté à plusieurs reprises.)
• R: Nombre d'éléments qui doivent être enlevés pour faire de la place pour le nouvel élément. (Il est préférable de remplacer le moins d'éléments. Idéalement, cela devrait également prendre en considération les T et N attributs de chaque élément étant remplacé.)

J'ai 2 problèmes:

1. Déterminer combien de poids pour donner chacun de ces attributs.
2. Déterminer comment calculer le poids d'un élément.

(1) Je me rends compte que venir avec le poids pour quelque chose comme ceci est très subjectif, mais j'espérais qu'il ya une méthode standard ou quelque chose qui peut me aider à décider combien de poids pour donner chaque attribut. Par exemple, je pensais qu'une méthode pourrait être de trouver un ensemble de deux éléments échantillons puis comparer manuellement les deux et décider lequel devrait finalement être choisi. Voici un exemple:

L'élément A:. N = 5, T = il y a 2 heures
Élément B:. N = 4, il y a T = 10 minutes

Dans cet exemple, je voudrais probablement un être l'élément qui est choisi pour être remplacé car bien qu'il ait été consulté une fois de plus, il n'a pas été consultée dans beaucoup de temps par rapport à B. Cette méthode semble il faudrait beaucoup de temps et impliquerait de faire beaucoup de difficiles décisions subjectives. De plus, il ne peut pas être trivial de trouver les poids obtenus à la fin.

Une autre méthode que je suis venu avec était de choisir arbitrairement juste poids pour les différents attributs, puis utiliser l'application pendant un certain temps. Si je remarque quoi que ce soit de toute évidence mal à l'algorithme, je pourrais alors aller et modifier légèrement les poids. Ceci est essentiellement une méthode « deviner et vérifier ».

Ces deux méthodes ne semblent pas terrible et j'espère qu'il ya une meilleure solution.

(2) Une fois que je fais figure le poids, je ne suis pas sûr de quelle manière est préférable de calculer le poids. Dois-je ajouter que tout? (Dans ces exemples, je suppose que quel que soit l'élément a le plus replacementWeight devrait être celui qui va être remplacé.)

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

ou tout multiplier?

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

Qu'en est-il pas à l'aide de constantes pour les poids? Par exemple, bien sûr « Time » (T) peut être important, mais une fois une quantité spécifique de temps a passé, il commence à ne pas faire beaucoup de différence. Essentiellement, j'amalgamer tout dans un « beaucoup de temps a passé » bin. (Par exemple, même si 8 heures et 7 heures ont une différence d'heure entre les deux, cette différence pourrait ne pas être aussi importante que la différence entre 1 minute et 5 minutes puisque ces deux sont beaucoup plus récentes.) (Ou un autre exemple: remplacement (R ) 1 ou 2 éléments est très bien, mais quand je commence à devoir remplacer 5 ou 6, qui devrait être fortement lesté ... donc il ne devrait pas être linéaire.)

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

Il est évident que (1) et (2) sont étroitement liés, ce qui est la raison pour laquelle j'espère qu'il ya une meilleure façon de trouver ce genre d'algorithme.

Answer 1

Ce que vous décrivez est le problème classique de choisir un cache politique de remplacement . Quelle politique est le mieux pour vous, dépend de vos données, mais les suivantes fonctionne généralement bien:

Tout d'abord, toujours stocker un nouvel objet dans le cache, expulsant le R pire (s). Il n'y a aucun moyen de savoir a priori si un objet doit être stocké ou non. Si l'objet n'est pas utile, il va tomber du cache à nouveau bientôt.

Le cache populaire calmars outils le cache suivant algorithmes de remplacement:

• les moins récemment utilisés (MRU):
  • replacementKey = -T
• les moins fréquemment utilisés avec Dynamic vieillissement (LFUDA):
  • replacementKey = N + C
• Greedy-double Taille-fréquence (GDSF) :
  • replacementKey = (N/R) + C

C fait référence à un facteur d'âge de cache ici. C est essentiellement le replacementKey de l'élément qui a été expulsé dernier (ou nul).

Remarque: le replacementKey est calculé lorsqu'un objet est inséré ou accessible, et stocké à côté de l'objet. L'objet avec plus petit replacementKey est évincé.

est simple et LRU souvent assez bon. Plus votre cache, plus il exécute.

LFUDA et GDSF les deux sont compromis. LFUDA préfère garder les gros objets, même si elles sont moins populaires, en supposant que l'on a frappé un grand objet représente beaucoup de succès pour les petits objets. GDSF fait essentiellement le compromis opposé, en gardant beaucoup de petits objets sur des objets moins grandes. D'après ce que vous écrivez, ce dernier pourrait être un bon ajustement.

Si aucune de ces répondre à vos besoins, vous pouvez calculer les valeurs optimales pour T, N et R (et comparer les différentes formules pour les combiner) en minimisant regret , la différence de performance entre votre formule et optimale algorithme, en utilisant, par exemple, régression linéaire

Answer 2

Ce problème est tout à fait subjective - comme vous le soulignez. Et une possibilité est que si vos cas de test sont constitués de paires (A, B) où vous préférez A à B, alors vous trouverez peut-être que vous préférez A à B, B à C, mais aussi C sur A - dire son pas la commande.

Si vous ne faites pas attention, votre fonction peut ne pas exister!

Si vous pouvez définir une fonction scalaire de vos variables d'entrée, avec différents paramètres des coefficients et des exposants, vous pourriez être en mesure d'estimer lesdits paramètres en utilisant la régression, mais vous aurez besoin d'un très grand nombre de données si vous avez beaucoup de paramètres.

Ceci est l'approche classique de statisticienne du premier examen des données pour identifier un modèle, puis en utilisant ce modèle pour estimer une réalisation particulière du modèle. Il y a de grands livres sur ce sujet.