J'ai codé une structure de stockage de type tuple, mais je me demandais si j'aurais besoin d'optimiser les opérations de recherche, afin d'accélérer les opérations dans le cas où elle contiendrait beaucoup de données (je ne m'y connais pas trop en optimisation).
voici mon code :
package oc_cours_project.resources.types;
import java.util.Vector;
/**
* Un tuple simple, à deux entrées
* @author winterskill
* @since 1.0
*
*/
public class Tuple<I, V> {
protected Vector<I> m_index;
protected Vector<V> m_values;
public Tuple() {
this.m_index = new Vector<I>();
this.m_values = new Vector<V>();
}
/**
* Ajoute une entrée au tuple.
*
* @param index
* @param value
*
* @return void
*/
public void add(I index, V value) {
this.m_index.add(index);
this.m_values.add(value);
}
/**
* Retourne l'entrée qui correspond à l'index fourni. Si l'index n'existe pas, retourne null
*
* @param index
* @return V
* @throws ArrayIndexOutOfBoundsException
*/
public V get(I index) throws ArrayIndexOutOfBoundsException {
int askedIndex = -1;
// on parcour le tableau d'index
for (int i = 0; i < this.m_index.size(); i++) {
if (this.m_index.get(i).equals(index)) {
// si l'entrée i du tableau d'index est égale à l'index demandé
askedIndex = i;
}
}
if (askedIndex != -1) {
// si askedIndex à bien été changé (donc trouvé dans le tableau des index
if (askedIndex < this.m_values.size()) {
// si askedIndex est bien plus petit que la taille du tableau des valeurs
return this.m_values.get(askedIndex);
} else {
String _exc = new StringBuilder().append("").append(askedIndex).toString();
throw new ArrayIndexOutOfBoundsException("the index " + _exc + " does not exists.");
}
}
return null;
}
/**
* Retourne si l'index désigné existe dans le Tuple ou non.
*
* @param index
* @return boolean
*/
public boolean indexExists(I index) {
for (int i = 0; i < this.m_index.size(); i++) {
if (this.m_index.get(i).equals(index)) {
return true;
}
}
return false;
}
}
(l'optminisation concernerait surtout (je pense) la méthode get).
merci d'avance,
Winterskill
A soutenir absolument : https://www.kickstarter.com/projects/1264023666/bushido-the-way-of-men
ou faire une fonction "getIndexKey(I key)" avec un return dans la boucle et qui retourne "-1" si la clef n'est pas trouvée.
Je suis intrigué par ton choix d'utiliser des "Vector" de la java 1.1 comme collection. J'aimerais savoir pourquoi ce choix par rapport à d'autre collection qui ont pris la place.
Ce que tu cherches à faire n'est pas un Tuple mais une "Table de symboles". En java, ça s'appelle une Map et il en existe plusieurs sortes : HashMap, TreeMap, LinkedHashMap suivant tes besoins.
@ArgAur : si j'ai utilisé un vector, c'est parce qu'ils sont simples d'utilisation, et que pour les avoir déjà manipulés en C++, ils me sont assez familiers. De plus, je ne connais pas ses successeurs.
@brubru777 : ah? merci. dans ce cas-là, qu'est-ce qu'un tuple? (et puis recoder des structures déjà existantes, c'est un bon exercice )
A soutenir absolument : https://www.kickstarter.com/projects/1264023666/bushido-the-way-of-men
Un tuple, c'est une structure qui contient un nombre fixe d'éléments. Les types des éléments peuvent être différents.
Les exemples les plus courants sont la paire (tuple à 2 éléments) ou le triplet (tuple à 3 éléments).
En fait, je crois que je comprends ce que tu essayais de faire. Un "named" tuple est un tuple qui permet d'accéder à ses éléments par leur nom. Sauf que dans ton implémentation, le nombre d'éléments n'est pas fixe et tous les éléments ont le même type.
si j'ai utilisé un vector, c'est parce qu'ils sont simples d'utilisation, et que pour les avoir déjà manipulés en C++
Tu codes en Java. Oublie C++. ArrayList.
Concernant la question de base :
structure a-t-elle besoin d'optimisation?
La réponse est simple : mesure. On optimise pas au petit bonheur la chance. L'écriture d'une optimisation est toujours guidée par des mesures préalables.
@brubru777 : en gros, dans un tuple, la taille est définie à la création de la variable? je n'ai pas très bien compris ce qu'est un named tuple. Autant utiliser un enum dans ce cas, non?
@ksass`peuk : je vais essayer de remplacer Vector par ArrayList. Mais que dois-je mesurer?
A soutenir absolument : https://www.kickstarter.com/projects/1264023666/bushido-the-way-of-men
Les performances du programme que tu cherches à optimiser. Donc si tu es en train de développer une bibliothèque, tu construits une suite de benchs représentative de l'utilisation de la bibliothèque. Si tu es en train de concevoir un programme, tu vas utiliser ce programme.
Dans les deux cas, tu vas mesurer les performances de ton programme avec un profiler qui va notamment te donner les temps d'exécution de chacune des fonctions (voir beaucoup plus d'informations selon le profiler utilisé). Et c'est là que tu vas voir les tâches qui prennent vraiment du temps et qui sont intéressantes à optimiser. A quoi bon optimiser à mort une fonction si c'est pour s'apercevoir qu'elle est utilisée 2% du temps ?
Conseiller un break comme optimisation, moi ça me dérange
Sinon, le problème c'est que l'optimisation dépend énormément de l'utilisation que tu en fait. Au hasard, quelques optimisations possible que je vois...
Buffer (si tu accède souvent aux même données)
Trie (si tu privilégie l'extraction à l'insertion)
Hash (si tes clés sont lourdes)
Bitmap (Si tu as un nombre finit de possibilités pour une caractéristique donnée, exemple type de carburant pour des voitures)
B-Tree/Tas/Arbre Binaire/Truc-Tree (Si tu cherches selon une caractéristique en particulier)
Mais tous ça n'est utile que dans certains cas, donc c'est très dépendant de ce que tu sais sur les données. Ça peut te demander à changer ta structure, par exemple le trie serait probablement plus optimal avec une LinkedList qu'une ArrayList (enfin ton vector, vector c'est juste l'ancêtre de ArrayList, c'est outdaté depuis longtemps).
Les profileurs te permettront juste de savoir quelles opérations prennent du temps, tu pourras donc savoir ce qu'il faut optimiser. Dans le cadre d'un gros programme, ça t'évite de perdre des ressources à optimiser des méthodes jamais appelé. On l'utilise plutôt dans des cadres plus complexes.
Un buffer stocke en mémoire un objet, tout simplement... Ici tu peux intégrer un buffer basique en créant une sous liste d'index, avec une taille maximale de 10 par exemple, qui contiendra les 10 derniers éléments appelés... Lors de ta recherche tu fouillera d'abord ici.
Mais tu comprends que ça n'a de sens que si tu appel, à un moment donné, plusieurs fois le même éléments. Enfin on considère généralement qu'un Buffer c'est casimment la plus grosse optimisation que tu puisses apporter, au pire tu ne perds que 10 itérations, ce qui est ridicule si ta liste est constitués de milliers/millions d'éléments.
Ça n'a pas grand chose à avoir avec la discussion, mais j'ai un peu de mal avec l'appelle à equals, puisque tu n'as aucun moyen de savoir si ta classe I redéfinit la méthode. J'aurais plutôt utilisé compareTo et tu "obliges" la classe à hérité de l'interface Comparable.
Et sinon pour ton problème tu devrais regarder la complexité des opérations sur les collections de java et choisir celle qui te parait la plus adaptée
mais toutes les classes possèdent la méthode equals, non?
Oui, puisqu'elles héritent toutes de "Object" mais si elle n'est pas redéfinie la méthode "equals" de cette classe est assez restrictive elle ne renverra "true" que si les deux objets sont en faite le même. Et pas forcément si les deux objets possèdent les mêmes valeurs pour leurs attributs.
Comme dit, la méthode equals ne te permet pas de trier, implémenter CompareTo est obligatoire si tu veux des perfs. La plupart des types Java en possède une version. C'est une interface qui garantie la présence de la métode, il te suffit de restreindre l'objet (<T implements CompareTo>)
Sinon aucun intérêt si ta liste fait 10 éléments, je comprend que c'est pour t'entrainer mais si tu t'entraine sur des exemples aussi restreint ça va être frustrant pour toi. L'avantage d'avoir un buffer c'est quand tu as plusieurs milliers d'éléments au grand minimum.
Comme dit, la méthode equals ne te permet pas de trier, implémenter CompareTo est obligatoire si tu veux des perfs.
Ce n'est pas tant pour avoir des "perfs" que pour être sur que ta méthode fait bien ce qu'il faut. Et pour les type primitif, en java tous les type primitif possèdent une classe "wrapper" associée.
Et pour en revenir à l'optimisation, il existe plusieurs type d'optimisation (la complexité, taille en mémoire etc ..) à toi de voir ce que tu veux faire.
structure a-t-elle besoin d'optimisation?
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C