Programmation dynamique
Résolu
charline159
Messages postés
208
Date d'inscription
Statut
Membre
Dernière intervention
-
charline159 Messages postés 208 Date d'inscription Statut Membre Dernière intervention -
charline159 Messages postés 208 Date d'inscription Statut Membre Dernière intervention -
Bonjour, j'essaie de me pencher sur de la programmation dynamique en ce moment.
En regardant cette vidéo, j'ai pu voir que le programmeur ajoutait toujours un objet "memo" aux paramètres de sa méthode afin de mémoïser: https://www.youtube.com/watch?v=oBt53YbR9Kk&t=9333s
mais n'étant pas une spécialiste de Js, je me demandais quel devait être le type de l'objet en Java ? (dans le cas présent par exemple, en travaillant avec des String, est-ce que je devrais utiliser un objet de type String pour mémoïser, ou bien une ArrayList de String, ou autre?)
Merci pour votre aide
En regardant cette vidéo, j'ai pu voir que le programmeur ajoutait toujours un objet "memo" aux paramètres de sa méthode afin de mémoïser: https://www.youtube.com/watch?v=oBt53YbR9Kk&t=9333s
mais n'étant pas une spécialiste de Js, je me demandais quel devait être le type de l'objet en Java ? (dans le cas présent par exemple, en travaillant avec des String, est-ce que je devrais utiliser un objet de type String pour mémoïser, ou bien une ArrayList de String, ou autre?)
Merci pour votre aide
A voir également:
- Programmation dynamique
- Tableau croisé dynamique - Guide
- Exemple tableau croisé dynamique télécharger - Télécharger - Tableur
- Application de programmation - Guide
- Liste déroulante dynamique excel - Guide
- Sommaire dynamique word - Guide
3 réponses
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
bonjour,
afin de choisir le type d'objet, tu dois d'abord comprendre ce que tu feras avec l'objet.
qu'en feras-tu?
afin de choisir le type d'objet, tu dois d'abord comprendre ce que tu feras avec l'objet.
qu'en feras-tu?
Salut,
Pour reprendre l'exemple de la vidéo, je stocke dedans les combinaisons de String déjà explorées et qui n'ont pas ponctionnées, pour m'en servir aux explorations futures. Donc j'ai besoin de stocker des String.
Donc pour l'objet memo, je devrais utiliser une ArrayList de String ? Ou peut-être une hashmap de String ?
Pour reprendre l'exemple de la vidéo, je stocke dedans les combinaisons de String déjà explorées et qui n'ont pas ponctionnées, pour m'en servir aux explorations futures. Donc j'ai besoin de stocker des String.
Donc pour l'objet memo, je devrais utiliser une ArrayList de String ? Ou peut-être une hashmap de String ?
Bonjour,
Clairement ici c'est une Map dont tu as besoin.
La mémoïsation consiste à enregistrer le résultat d'une fonction à partir de ses paramètres.
Les paramètres doivent être la clé de Map, le résultat la fonction la valeur de la Map.
Pour une fonction à un argument genre
Pour une fonction à plusieurs arguments
Clairement ici c'est une Map dont tu as besoin.
La mémoïsation consiste à enregistrer le résultat d'une fonction à partir de ses paramètres.
Les paramètres doivent être la clé de Map, le résultat la fonction la valeur de la Map.
Pour une fonction à un argument genre
R fun(P param)tu devrais avoir une
Map<P, R>.
Pour une fonction à plusieurs arguments
R fun(P1 param1, P2 param2)tu devrais créer une
class Param { P1 param1; P2 param2; } pour revenir au cas d'une fonction à un paramètre avec une Map<Param, R>.
Salut et merci pour ta réponse.
J'ai essayé d'ajouter une fonction en paramètre à la Map, mais j'ai une erreur donc j'ai mis deux String à la place.
Est-ce que ça devrait ressembler à ça ?
J'ai essayé d'ajouter une fonction en paramètre à la Map, mais j'ai une erreur donc j'ai mis deux String à la place.
Est-ce que ça devrait ressembler à ça ?
package com.company;
import java.util.HashMap;
import java.util.Map;
public class Main {
static String[] listOfWords = {"bo","rd","ate","t","ska","sk","boar"};
public static void main(String[] args) {
Map<String, String> res = new HashMap<String, String>();
System.out.println(canConstruct("skateboard",res));
}
static boolean canConstruct(String word, Map<String, String> res){
// base cases
if (word.isEmpty()) return true;
if (res.containsValue(word)) return res.containsValue(word);
for (int i = 0; i < listOfWords.length; i++) {
// if the substring is contained at the beginning of the string
if (word.indexOf(listOfWords[i]) == 0 ){
// update of the word
int lengthSubString = listOfWords[i].length();
String exWord = word;
word = word.substring(0,lengthSubString);
if (canConstruct(word, res) == true){
res.put(exWord,word);
return true;
}
}
}
return false;
}
}
Je ne comprends pas pourquoi les valeurs dans ta Map sont des String alors que tu renvoies un booléen.
En plus tu ne stockes dans la map la valeur que lorsque c'est true, jamais quand c'est false... du coup tu ne tires profit de la Map qu'une fois sur deux alors que tu as déjà fait la calcul aussi quand c'est false...
Dans l'idée il faudrait plutôt avoir une structure comme ceci :
Après c'est le genre de chose qu'on peut généraliser dans une classe dédiée sans avoir à recopier le code pour chaque méthode qui pourrait avoir besoin de ça...
En plus tu ne stockes dans la map la valeur que lorsque c'est true, jamais quand c'est false... du coup tu ne tires profit de la Map qu'une fois sur deux alors que tu as déjà fait la calcul aussi quand c'est false...
Dans l'idée il faudrait plutôt avoir une structure comme ceci :
private static Map<String, Boolean> canConstructCache = new HashMap<>();
public static boolean canConstructWithCache(String word) {
if (canConstructCache.containsKey(word)) {
return canConstructCache.get(word);
} else {
boolean result = canConstructComputed(word);
canConstructCache.put(word, result);
return result;
}
}
private static boolean canConstructComputed(String word) {
return ... // calcul du résultat normal
}
Après c'est le genre de chose qu'on peut généraliser dans une classe dédiée sans avoir à recopier le code pour chaque méthode qui pourrait avoir besoin de ça...
J'ai essayé de reproduire ce que j'avais cru comprendre dans la vidéo. L'auteur de la vidéo s'était organisé de cette manière, enfin je crois.
J'ai fait deux String car je pensais passer par l'un pour avoir l'autre, et ainsi l'utiliser afin d'avoir un boolean.
La méthode canConstructComputed ça correspond aux lignes 28 à 31 de mon code ("update of the word") ?
J'ai fait deux String car je pensais passer par l'un pour avoir l'autre, et ainsi l'utiliser afin d'avoir un boolean.
La méthode canConstructComputed ça correspond aux lignes 28 à 31 de mon code ("update of the word") ?
Bonjour,
"J'ai essayé de reproduire ce que j'avais cru comprendre dans la vidéo. L'auteur de la vidéo s'était organisé de cette manière, enfin je crois."
Si on reprend la vidéo, à 2:36:42 il a son code final :
Ensuite il fait
"La méthode canConstructComputed ça correspond aux lignes 28 à 31 de mon code ("update of the word") ?"
La méthode canConstructComputed devrait correspondre à tout ce qui constituerait ta méthode si tu ne faisais pas de mémoïsation, c'est à dire toute ta boucle for des lignes 23 à 38. C'est tout ça que tu vas court-circuiter en passant par la Map lorsque le résultat a déjà été calculé avec le même paramètre.
"J'ai essayé de reproduire ce que j'avais cru comprendre dans la vidéo. L'auteur de la vidéo s'était organisé de cette manière, enfin je crois."
Si on reprend la vidéo, à 2:36:42 il a son code final :
if (target in memo)correspond à
if (canConstructCache.containsKey(word)) { dans mon code.
return memo[target]correspond à
return canConstructCache.get(word);.
Ensuite il fait
memo[target]=true; return true;et
memo[target]=false ; return false;que j'ai mutualisé avec
canConstructCache.put(word, result); return result;.
"La méthode canConstructComputed ça correspond aux lignes 28 à 31 de mon code ("update of the word") ?"
La méthode canConstructComputed devrait correspondre à tout ce qui constituerait ta méthode si tu ne faisais pas de mémoïsation, c'est à dire toute ta boucle for des lignes 23 à 38. C'est tout ça que tu vas court-circuiter en passant par la Map lorsque le résultat a déjà été calculé avec le même paramètre.