Structure de données

Version imprimable

Bonjour à toutes et à tous ! :)

J'ai besoin de manipuler une structure de données qui a cette forme :
Chaque ligne représente un individu récolté à une coordonnée pas forcément unique dans le jeu de données. Pour chaque individu on a une valeur associée à l'allèle A1 (ou A2) d'un locus ( = un point du génome) auquel est attribué un joli nom (locus DJRD456 par exemple). Taille actuelle : 300 ind x 20 locus x 2 alleles
Code:

1 2 3 4 5 6 7 8 ------------------------------------------------------------------------------ ____| coords | nom locus 1 || nom locus 2 || ... ____|___________| A1 A2 || A1 A2 || ... ------------------------------------------------------------------------------- 1 | (44 ; 1.5) | 123 154 || 211 456 || ... 2 | (44 ; 1.5) | 211 456 || 123 211 || ... 3 | (39 ; 3.5) | 434 111 || 434 154 || ...
J'ai bien fait un truc qui marche (mais crado, trop compliqué, très certainement pas du tout efficace, un peu comme mon tableau ci-dessus :mouarf:) et évidemment je galère à lui filer une interface sympatoche.
Je suis très mauvais dans la manipulation des structures de données. Quels réflexes vous viennent ici spontanément à l'esprit ?
En vous remerciant,

04/06/2016, 17h46
Abacar94

Citation:

Envoyé par Seabirds

Bonjour à toutes et à tous ! :)
Taille actuelle : 300 ind x 20 locus x 2 alleles

Avant de commencer un travail tu doit te fixer certains principes.....tu veux faire une allocation statique ou dynamique ?
04/06/2016, 18h02
Seabirds

Merci de ta réponse :)
Donc ça c'est la première question qu'on doit se poser. C'est noté.

Pour l'instant le chemin d'accès au fichier est connu à la compilation et l'objet est créé sur la pile. Mais je ne sais pas si c'est la meilleure alternative.

Cette donnée est une variable du programme, j'imagine que c'est synonyme de "non-connue à la compilation" :question:
Cela dit le temps de compilation est très faible devant le temps d'exécution, alors je ne sais pas à quel point il serait idiot de recompiler le programme pour chaque jeu de donnée à traiter. :question:

A quel point ça ne répond pas à ta question ? :?
04/06/2016, 18h17
Abacar94
Ce que je voulait de demander quel allocation veut tu faire ?
1. Pour l'allocation statique: C'est la plus facile, on doit connaitre au préalable le nombre d’individu,de locus et d’allèle....mais elle a des inconvénient une fois qu'on fixe le nombre on ne peut plus changer
2. Pour l'allocation dynamique: c'est la plus difficile par ce qu'on doit utiliser des pointeur dans nôtres structure mais son avantage est qu'on ne fixe pas le nombres le nombre d’individu,de locus et d’allèle on insert seulement les donnée.....on peut a chaque fois ajouter d'autres données ou même en supprimer
04/06/2016, 18h40
Seabirds

D'accord. Alors si je comprends bien l'allocation statique est suffisante, parce que le nombre d'individus, de loci et d'allèles sont fixés par le fichier, et que le programme n'a pas vocation à rajouter/enlever des individus ou des allèles.
Par contre on doit pouvoir dupliquer le jeu de données et modifier les valeurs des allèles du jeu dupliqué, c'est faisable avec l'allocation statique ?

Je réponds encore à côté ?
04/06/2016, 19h00
foetus

C'est la différence entre Ma_Struct tab[XXX]; et Ma_Struct* tab = NULL;.

Mais si tu veux dupliquer bien tu fais ... 2 variables locales - statiques ou pas :whistle: tab_ori et tab
04/06/2016, 19h55
jo_link_noir

Allocation dynamique ou non n'est que le résultat d'une contrainte. Je trouve le raisonnement taille variable = allocation, taille fixe = allocation statique plutôt très restrictive.

Avant toutes choses, il faut déterminer quelles seront les contraintes d'entrée et de sortie.

- La manière d'utiliser les données (grossièrement les algorithmes en jeux. Cette partie influence énormément l'interface)
- la plage de valeur ou valeur possible des données
- leur nombre: pré-définit, calculé/déduit, variable, limité
- les contraintes de temps et de mémoire.
- etc

Sinon, de façon naïve, les données sont des structures (locus, coord, ligne) et les données multiples des tableaux (vector ou array). En essayant toutefois de linéariser les vectors de vectors pour une question de vitesse d'accès. Mais ce n'est pas cela qui devrait changer l'interface.
04/06/2016, 22h13
Abacar94

Citation:

Envoyé par Seabirds

Par contre on doit pouvoir dupliquer le jeu de données et modifier les valeurs des allèles du jeu dupliqué, c'est faisable avec l'allocation statique ?
Je réponds encore à côté ?

Ta parfaitement compris ce que je veut dire......et aussi tu peut dupliquer le jeu de données et modifier les valeurs des allèles du jeu dupliqué, c'est faisable avec l'allocation statique
05/06/2016, 13h45
Seabirds

Merci à tous pour vos réponses :D

Citation:

Avant toutes choses, il faut déterminer quelles seront les contraintes d'entrée et de sortie.

- La manière d'utiliser les données (grossièrement les algorithmes en jeux. Cette partie influence énormément l'interface)
- la plage de valeur ou valeur possible des données
- leur nombre: pré-définit, calculé/déduit, variable, limité
- les contraintes de temps et de mémoire.
- etc

- Plage des valeurs : pour le moment des nombres entier naturels inférieurs à 1000
- Nombre de données : définit par le fichier à traiter, mais variable entre fichiers. En pratique, le nombre d'individu est de l'ordre de la centaine (100 - 500), le nombre d'allèles de 1 ou 2, le nombre de locus peut devenir important mais pour l'instant il est de l'ordre de la dizaine (20 - 50)
- contraintes de temps et de mémoire : durant un temps d'exécution le jeu de données va être dupliqué plusieurs millions de fois, chaque valeur du jeu de donnée pour chaque [individu][locus][allele] va être modifiée par simulation, et les millions de jeu de données résultants vont être redirigés vers des fichiers pour être stockés en mémoire. Contrainte de temps : faudrait que le programme total tourne en quelques jours.
- La manière d'utiliser la donnée :
1) Je clone le jeu de données initial
2) Pour chaque locus, pour tous les allèles de tous les individus correspondant je crée un objet N contenant un pointeur/référence sur la donnée clonée data[locus][individu][allele]. L'idée c'est que pour chaque case du jeu de donnée un objet N soit créé.
3) On fait les simulations avec le vecteur des N à un locus donné,
4) Après simulation on demande à tous les N de rebalancer leurs nouvelles données simulées dans le jeu de données.
5) On exporte le jeu de donné simulé dans un fichier texte.

Citation:

Sinon, de façon naïve, les données sont des structures (locus, coord, ligne) et les données multiples des tableaux (vector ou array)

Pas compris :calim2: Veux-tu dire que fabriquer une grosse matrice contenant tous les nombres serait une mauvaise idée et qu'il vaudrait mieux structurer tout ça en faisant une structure "individu" qui contient des structures locus qui contiennent des allèles ? :?
05/06/2016, 22h01
jo_link_noir
Citation:

Envoyé par Seabirds

durant un temps d'exécution le jeu de données va être dupliqué plusieurs millions de fois

Mais il n'y aura qu'un jeu de donnée dupliqué à la fois ? (ou un par thread).

Citation:

Envoyé par Seabirds

Pour chaque locus, pour tous les allèles de tous les individus correspondant je crée un objet N contenant un pointeur/référence sur la donnée clonée data[locus][individu][allele].

Je ne comprends pas ce que contient l'objet N. La référence sur un allèle... Et quoi d'autres ?

Citation:

Envoyé par Seabirds

Pas compris :calim2: Veux-tu dire que fabriquer une grosse matrice contenant tous les nombres serait une mauvaise idée et qu'il vaudrait mieux structurer tout ça en faisant une structure "individu" qui contient des structures locus qui contiennent des allèles ? :?

C'est surtout plus simple de manipuler des sous éléments si ce sont des structures. Cela reste toutefois une représentation matricielle.

Mais je n'ai pas lu dans quel ordre les données sont manipulées. Par exemple, si les algorithmes travaillent d'abord sur tous les allèles du locus, puis du locus 2, et ainsi de suite, il est préférable de regrouper les allèles par locus plutôt que par individu.
Code:

1 2 3 4 5 6 7 { locus 1 {{A1, A2}, {A1, A2}, ...} locus 2 {{A1, A2}, {A1, A2}, ...} ... } coords{...}
Le but étant de parcourir linéairement les données pour profiter d'optimisation comme la vectorisation et de réduire les caches miss.
06/06/2016, 10h33
bacelar

Plutôt que de se focaliser sur les données et l'optimisation, moi je vous conseille de découper le problème en sous problème et de faire des classes qui fournissent des services et pas des conteneurs de données.
Les classes seront donc fonction des algorithmes envisagés.
06/06/2016, 12h27
Seabirds
Citation:

Envoyé par jo_link_noir

Mais il n'y aura qu'un jeu de donnée dupliqué à la fois ? (ou un par thread).

Heu bonne question j'en sais rien, je sais à peine ce qu'est un thread :weird: Dans un premier temps chaque duplication/traitement aura lieu dans une boucle for. Cela dit, chaque itération duplication/traitement est indépendante de la suivante, et à un moment va falloir se poser la question de comment optimiser ça sur le cluster de mon labo. Toutes les itérations utilisent des données communes constantes.

Citation:

Envoyé par jo_link_noir

Je ne comprends pas ce que contient l'objet N. La référence sur un allèle... Et quoi d'autres ?

N pour Node, un truc au coeur de la théorie permettant la simulation d'un échantillon génétique. On construit les feuilles d'un arbre à partir du jeu de données, puis on simule la généalogie de toutes les feuilles/allèles en gardant dans chaque node nouvellement créé la date et le lieu de l'apparition de l'allèle, sa valeur, et un pointeur sur la case du jeu de donnée associée à cet allèle.
Citation:
Envoyé par jo_link_noir

Mais je n'ai pas lu dans quel ordre les données sont manipulées. Par exemple, si les algorithmes travaillent d'abord sur tous les allèles du locus, puis du locus 2, et ainsi de suite, il est préférable de regrouper les allèles par locus plutôt que par individu.

Code:

1 2 3 4 5 6 7 { locus 1 {{A1, A2}, {A1, A2}, ...} locus 2 {{A1, A2}, {A1, A2}, ...} ... } coords{...}

Le but étant de parcourir linéairement les données pour profiter d'optimisation comme la vectorisation et de réduire les caches miss.
Pour l'instant on commence par les locus. Pour un locus, on veut créer un N pour chaque allèle (que ce soit A1 ou A2) de tous les individus et le ranger dans un dictionnaire avec la coordonnée associée :)
En gros, on se place à la colonne "Locus1" et on chope toutes les adresses de tous les allèles (indifféreemment A1 ou A2) de tous les individus.

Citation:

Plutôt que de se focaliser sur les données et l'optimisation, moi je vous conseille de découper le problème en sous problème et de faire des classes qui fournissent des services et pas des conteneurs de données.

Merci pour ta réponse :)
A vrai dire, les services fournis par ce jeu de données sont pour l'instant très limités (juste des itération/accès). :)
06/06/2016, 13h18
ternel
J'ai l'impression que tu as un problème de formulation. Ton code ne sera jamais plus simple à écrire que ta solution à être décrite.

Ton problème est une simulation (numérique).
C'est à dire que tu calcule des étapes entre une situation initiale et une situation finale.

Il y en a deux grands genres: celles dont le résultat est la situation finale, et celle dont c'est l'ensemble des résultats partiels.
Pour ce que j'en sais, tu es dans ce second cas.

C'est une précision utile à garder en tête, mais je ne pense pas qu'elle influence vraiment la question de cette discussion.

Dans une telle simulation, on a en général plusieurs types de données:
- un ou plusieurs états de simulation (notamment l'état actuel)
- des données complémentaires permettant de repérer un état dans la simulation complète (le temps, en général)
- des paramètres constants dans la simulation (comme une taille de grille)
- une fonction de transition.
Ceci n'est que la liste des besoins généraux.
En pratique, un état est complexe, et la seule fonction de transition qu'on sache écrire concerne des sous parties de l'état. On parle de situation locale
Par exemple, dans un "jeu de la vie", l'état d'une case en T+1 est fonction des états en T d'elle-même et de ses voisines.

Du coup, il faut écrire une structure (ou classe, on n'est pas obtus :) ) pour représenter ces situations locales, pour pouvoir écrire une fonction s'occupant d'elle seulement.
par exemple: evolution (emplacement & cible, contexte const&) ou emplacement::evolution(contexte const&).

Cela veut dire qu'il faut que tu prennes le temps de lire comment se décompose ta situation globale en sous-parties

Si j'ai bien compris, les locus sont des unités de lieux, chacun étant en contact avec tous les autres (haute dispersion).
Cela signifie qu'en interne dans ton environnement, tu disposes d'un vecteur ou d'une map de locus.

Ce que j'ai perdu de vue, c'est ce qu'est ton arbre.
J'ai l'impression que tu n'étudies pas une seule propagation, mais la coévolution de plusieurs choses, qui sont les alleles.
Si c'est le cas, chaque locus doit fournir un moyen de savoir la quantité présente de chaque allele (donc une map<allele, quantité>).

Pour aller plus loin, tes locus sont des données géographiques, et un contexte (météo, par exemple) non simulé, même si variable dans le temps. Ce contexte est soit paramétré soit pré-échantillonné.
A coté de cela, dans chaque locus, il y a une situation locale, qui elle est intégralement simulée: la quantité de chaque allele.

Je pense que cela mérite plusieurs classes: une situation locale, un contexte, et le locus lui-même.
Tu as déjà une classe Environnement qui fournit l'ensemble des informations de contextes de l'ensemble des locus. Tu n'as pas forcément besoin d'autre classe de contexte.
Dans ce cas, la classe locus n'est qu'un moyen d'identifier le locus, ça peut être ton type d'identifiant spatial.

Dans ce fonctionnement, tu as donc: Environnement, Etat (état global), et SituationLocale.
Etat ne contiendrait finalement qu'une map<identifiant_spatial, situation_local>, ainsi qu'éventuellement une position temporelle (une date, donc :aie:).

Du point de vue des fonctions, ta simulation contiendrais une fonction permettant de passer d'un état global au suivant.
Pour une simulation classique, ca serait une simple boucle du type:
```
pour chaque position:
    la faire évoluer en fonction de l'état actuel global et de l'environnement.
```
Il me semble que dans ton problème, l'évolution locale se fait en deux temps: évolution interne puis transmission.
L'évolution interne est une autre simulation (dont on ne veut que le résultat), qui pourrait requérir son propre découpage.

Normalement, et c'est le même conseil que bacelar, ton évolution locale est une fonction membre de SituationLocale.
Avec les noms que j'ai utilisé, ca serait void SituationLocale::evolution_interne(Etat const&, Environnement const&) (la date de départ étant accessible dans l'Etat)

Une des subtilités de ton problème est d'avoir une fonction presque arbitraire pour faire cette évolution.
Qu'a cela ne tienne, fais en une propriété de l'environnement (en retournant une std::function<...>).

Le multithread viendra plus tard, et permettra de faire toutes les évolutions des SituationLocales simultanément.

De même, les transmissions se font à partir des situations locales ayant fait leurs évolutions internes.
Cela signifie que tu as deux fonctions d'évolutions distinctes: evolution_interne et transmission, tant pour Etat que pour SituationLocale.
06/06/2016, 13h57
Seabirds

Wooh merci pour la réponse :)

Citation:

Envoyé par leternel

Si j'ai bien compris, les locus sont des unités de lieux, chacun étant en contact avec tous les autres (haute dispersion).

Mhhh pas tout à fait. Les locus sont des emplacement chromosomiques, sur lesquels on trouve un allèle ou un autre. Chez l'homme le génome est un ensemble de paires de chromosomes {{X1, X2}, {Y1, Y2}, {Z1,Z2}}. Le long de chaque paire de chromosome, on trouve des locus (autrement une "simple" position le long du génome). Pour la paire {X1, X2} on aurait par ex. les loci {A, B,C ...}. L'information à chaque locus peut être différente sur les deux exemplaire de chaque chromosome, et c'est ce qu'on nomme allèle : X1 = {A1, B1, C1 ... } et X2 = {A2, B2, C2 ...}.
Par contre tu as mis derrière le mot locus ce qui est en fait le mot "localité", c'est à dire l'endroit de l'espace géographique où a été échantillonné chaque individu (et donc chaque chromosome de cet individu et donc chaque allèle de chaque locus cet individu).

Citation:

Envoyé par leternel

Ce que j'ai perdu de vue, c'est ce qu'est ton arbre.

Dans le cadre de ce modèle, chaque allèle devient une entité physique dont on cherche à reconstituer l'histoire (tel allèle s'est déplacé de ce point à ce point, a été dupliqué et transmis aux enfants, a subi une mutation)... Un des points originaux c'est que l'histoire est simulée backward-in-time. On part de l'échantillon au temps présent (= tous les allèles "frères" provenant forcément d'un même allèle-ancêtre commun), on simule la généalogie jusqu'à cet ancêtre (c'est ce que représente l'arbre). Une fois la généalogie simulée, elle représente en fait la structure de dépendance entre tous les allèles de l'échantillon, et on peut notamment opérer le processus mutationnel, répandre les mutations dans la généalogie et reconstituer le jeu de données génétique.

Le plus gros morceau du processus simulatoire est implémenté et testé. Je cherche maintenant à interfacer le jeu de données génétique avec la généalogie. En effet, on a besoin d'itérer sur le jeu de donnée pour créer les feuilles (= allèles échantillonnés au temps présent) de l'arbre avant simulation, et après simulation on a besoin de dire aux feuilles "simulation terminée, vous pouvez rebalancer votre état allélique simulé dans le jeu de donnée.

C'est plus clair ?:mrgreen:

Salut ! C'est bon j'ai construit le schmilblik et ça marche :)
Merci à tous pour vos propositions, vos idées et votre patience ! :D

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
template<typename Marker>
class Locus
{
public:
	using marker_type = Marker;
	std::vector<typename marker_type::value_type> alleles;
 
	void print(std::ostream &flux) const{
		for(auto const& it : alleles){
			flux << it << " ";
		}
	}
};
 
template<typename Localisation, typename Genetics>
class Individual
{
public:
	using coord_type = Localisation;
	using locus_type = Genetics;
 
	coord_type position;
	std::vector<locus_type> loci;
 
	void print(std::ostream &flux) const{
		flux << position << " ";
		for(auto const& it : loci){it.print(flux);}
	}
};
 
 
template<typename Individual>
class GeneticSample
{
public:
	std::vector<Individual> individuals;
	std::vector<std::string> loci_names;
	unsigned int get_nb_of_loci(){return loci_names.size();}
 
	void print(std::ostream &flux) const{
		print_headers(flux);
		flux << "\n";
		print_individuals(flux);
 
	}
 
	void print_headers(std::ostream &flux) const{
		flux << "lon lat";
		for(auto const& it : loci_names){ flux << " " << it; }
	}
 
	void print_individuals(std::ostream &flux) const{
		for(auto const& it : individuals) {	
			it.print(flux);
			flux << "\n";
		}
	}
 
};
 
template<typename Individual>
std::ostream &operator<<( std::ostream &flux, GeneticSample<Individual> const& sample)
{
    sample.print(flux) ;
    return flux;
}