Discussion :

[petitours]

Bonjour

J'ai une liste de d'objets placés dans un espace mémoire de 100 000octets avec une adresse et une taille en mémoire (de 1 à 4 octets par objet)
Ces objets ne sont pas forcements continus dans l'espace mémoire.

Je dois regrouper ces objets par paquets
Il doit y avoir le moins de paquets possible
un paquet a une taille maximum de 250octets (prendre en compte la taille des objets)
un paquet doit être le plus petit possible (moins d'espaces vide possible)

exemple :
Adrr Taille
0 1

248 1
249 2
261 1
262 1

il me faut trouver
-1 paquet contenant 0
-1 paquet contenant 248 à 262

si le premier paquet englobait 0 à 248 on aurait le même nombre de paquets mais plus de "trous"...

Comment aborderiez vous un algorithme capable de déterminer la meilleure configuration ?

Merci par avance pour votre aide

PS : ce sera programmé en C#.

[anapurna]

salut
donc si je comprend bien tu veut te créer des paquet avec un intervalle d'adresse mémoire de max 255 octets

donc dans le meilleur des cas
1..255
256..512 ....
tu as un tas de 100 000 octet
donc dans les meilleur des cas si tout étais remplis tu aurais 393 paquet

dans l'exemple que tu nous fournit on vois très clairement un large trou dans tes adresses mémoire et tu aimerais ne pas avoir autant de trou
sans trop réfléchir je me dis qu'il faut que tu calcul l’écart type
en connaissant l’écart type il est donc aisé de définir tes groupe de façons homogène
ensuite il te faudra peut être épurer tes paquets pour ne prendre que les valeur contenue dans les intervalles

[petitours]

Bonjour

donc si je comprend bien tu veut te créer des paquet avec un intervalle d'adresse mémoire de max 255 octets

max 250 mais on s'en moque

donc dans les meilleur des cas si tout étais remplis tu aurais 393 paquet

Si tout était rempli oui mais ce sera jamais le cas, l'espace de 100 000octets peut contenir que 1 objet à n'importe qu'elle position (là l'algo est pas compliqué ) à quelques dizaines ou centaines d'objets répartis de manière totalement aléatoire dans l'espace mémoire. Du coup je peux très bien rechercher qu'un seul bloc s'il n'y a que 250 entre l'adresse de l'objet la plus grande et l'adresse la plus faible.

Pareil pour les vides : Le premier objet n'est pas forcement à 0 et il y aura un nombre totalement inconnu de vides avant le prochain objet et s'il y a 2 fois le même nombre de vide c'est pur hasard.

Je ne vois vraiment aucune trace de quoi que ce soit de prévisible ou statistique dans la position des objets et des vides dans les 100 000octets. A chaque fois des objets auront été positionnés arbitrairement par une "concepteur" et un "utilisateur" aura choisi encore une fois arbitrairement de garder ou pas tout ou partie des objets ; ça fait 2 choses aléatoires qui aboutissent au positionnement des objets qui m'intéressent.

dans l'exemple que tu nous fournit on vois très clairement un large trou dans tes adresses mémoire et tu aimerais ne pas avoir autant de trou

Dans l'exemple que je donne je compare le comportement recherché avec la recherche un peu mecanique qui consiste à partir de 0 puis quand on trouve un objet on commence un bloc et on met dedans les 250o qui suivent. Dans l'exemple on se retrouve alors avec un premier bloc avec un enorme trou, suivi d'un second bloc minus alors que la "bonne" solution consiste à avoir un premier bloc d'un seul objet (0) et un deuxième bloc pour le reste, sans trou

sans trop réfléchir je me dis qu'il faut que tu calcul l’écart type
en connaissant l’écart type il est donc aisé de définir tes groupe de façons homogène
ensuite il te faudra peut être épurer tes paquets pour ne prendre que les valeur contenue dans les intervalles

Je comprends vite mais il faut m'expliquer doucement, surtout pour les probabilités... serait il possible de m'illustrer l'idée ?

Je vois l’écart type comme une valeur unique qui caractériserait mon espace mémoire, j'ai bien du mal à voir comment il peut m'aider à positionner les blocs.

Merci beaucoup

[anapurna]

salut

l’écart type te donne la dispersion moyenne de tes éléments dans ton espace plus l’écart est grand plus tes éléments sont disparate et non homogène
dans notre cas cela donne environ 114
en sachant qu'avec 250 tu as 2 écart type soit environ 80% de la population
il ne te reste plus qu'a choisir la solution qui remplit au mieux cette affirmation
j'avais bien dis que c’était sans réfléchir ^^

[tbc92]

Etape n°1 : Tu calcules les longueurs des 'trous', et tu repères tous les trous qui font plus de 250 ( ... plus précisément les trous qui vérifient, si longueur trou + longueur_objet_avant+_longueur_objet_après >250 )

Cest trous sont des frontières intangibles.

Ainsi au lieu d'avoir un problème avec peut-être 20000 objets, tu as n problèmes plus simples à résoudre.

Dans chacun des 'pays' ainsi définis, le nombre de paquets est facile à calculer : Si un pays commence à l'adresse a et finit à l'adresse b, il faudra quoi que tu fasses faire exactement partieentiere(( b-a+1)/250) paquets ( ( a vérifier si b-a+1 est un multiple de 250...)

Et ensuite.. mais là je suis moins sûr, il faut repérer dans cet intervalle a,b le plus gros trou, et peut-être itérer en cherchant à chaque fois le plus gros trou.

[anapurna]

salut

l'histoire des pré-traitement que conseil tbc92 sont effectivement à mettre en place en premier lieu
ensuite je suis moins certain pour sa simple division par 250
imaginons le pire des cas tu as 1 et le suivant 248 ensuite tout se suis régulièrement tu risque de te retrouver avec un beau gruyère
je pense sincèrement que cela devrait être plus fin