Salut !
A mes heures perdu, je suis en train de reflechir à la création d'un petit soft de peer to peer (juste pour le plaisir de coder, mais en essayant malgrès tout de trouver des idées novatrices vu qu'il existe bcp d'existant dans ce domaine).
J'aurai besoin de quelqu'un de motivé, qui pourrait se charger de l'interface graphique, et pis bien sûr de m'aider dans la recherche d'idée.
Bref, si ça branche quelqu'un d'essayer de monter un projet, me contacter ...
Ah oui, j'oubliais, j'ai commencée la partie serveur en C++, mais pour l'IHM, pas de contraintes ...
Journal Soft de peer to perr
19
juin
2003
# Re: Soft de peer to perr
Posté par Yannick Beynet (site web personnel) . Évalué à 0.
peer to peer et pas peer to perr
j'ai commencé et non pas j'ai commencée ...
j'en passe et des meilleures, sans doute la fatigue ...
[^] # Re: Soft de peer to perr
Posté par Christophe GRAND (site web personnel) . Évalué à 9.
[^] # Bonjour la France!
Posté par Nicolas (site web personnel) . Évalué à 2.
s/reflechir/réfléchir/
s/malgrès/malgré/
s/ortographe/d'orthographe/
c'est sans doute la fatigue....
# Re: Soft de peer to perr
Posté par Tutur . Évalué à 4.
Afin de resoudre ce pbs, plusieurs solutions:
- le fichier est decouper en packets, le serveur s'arrange que les packets soit repartie de maniére harmonieuse. c'est ce qui est fait pour bittorent
- L'autre solution c'est d'avoir 2 groupes de telechargeurs, ceux qui commence par le debut et ceux qui commence par la fin. Au debut du telechargement, tu prend les donnes à ceux de ton groupe. Puis apres, tu prend les donnees à ceux qui sont dans le groupe opposé. Du coup, plus de probléme pour recuperer les derniers octets du fichier.
[^] # Re: Soft de peer to perr
Posté par Christophe GRAND (site web personnel) . Évalué à 1.
Riche idée ! Une référence ?
En fait on peut diviser la population en N classes et pas eulement 2 ni de cette façon. Il suffit que N soit constant et de quelques contraintes sur la distribution.
Hmm ça me rappelle l'art de coder un tri en O(n), si vous êtes sages, un jour je vous raconterai. ;-)
[^] # Re: Soft de peer to perr
Posté par Larry Cow . Évalué à 1.
[^] # Re: Soft de peer to perr
Posté par Larry Cow . Évalué à 1.
Pour ceux qui ne suivent vraiment pas: Un tri en O(n) signifie que la complexité du tri est linéaire selon la taille de l'entrée (n). Ce qui, aux constantes près, équivaudrait en temps à un simple parcours des n éléments de l'entrée, ce qui est très bon (les tris courants ne descendent pas au dessous de O(n.log(n)) si j'ai bonne mémoire).
Cependant, il me semble que les fameux tris en O(n), même s'ils restent très supérieurs aux algorithmes classiques quand ils sont applicables, sont en fait en O(n.m) avec m une "très grosse" constante. Mais comme les notations asymptotiques ne tiennent pas compte des constantes, ça ne se voit pas.
Quelqu'un pour infirmer/confirmer/completer/me faire interner?
[^] # Re: Soft de peer to perr
Posté par Stephane Marchesin (site web personnel) . Évalué à 1.
Si tu utilises une table de hachage, tu peux effectivement trier en o(n). Mais bon, ca implique d'avoir une bonne clef de hachage et de créer une structure annexe (la table de hachage) au moins aussi grande que le tableau à trier. Après, pour trier, c'est simple : dans une première passe tu insères tous les éléments dans la table de hash, et dans une deuxième passe tu parcours la table pour relire les éléments dans l'ordre (pour cette deuxième étape, il faut avoir pensé à utiliser une fonction de hachage qui permette de déduire l'index de l'élément suivant à partir de l'élément courant).
Bref tu crées une structure en mémoire plus grande que ton tableau (pour éviter trop de collisions dans ta table de hachage) ce qui utilise plus du double de mémoire dans le cas qui nous intéresse le plus si on cherche un algo de tri en o(n) : pour n très grand !
Voila, ca demande effectivement de bonnes connaissance à priori sur les données à trier (pour faire une bonne clef de hachage).
[^] # Re: Soft de peer to perr
Posté par Christophe GRAND (site web personnel) . Évalué à 1.
Celui que j'ai détaillé ne nécessite que n/m en plus de tes n données.
[^] # Re: Soft de peer to perr
Posté par Jerome Herman . Évalué à 1.
Je suis contre la tres grosse constante.
Si on prend deux hypothese assez courantes :
1) je connais l'intervalle de mes valeurs qui sont des entiers (par exemple 0 <valeur <k) et leur nombre et fixee (j'ai n valeurs a trier)
2) Je m'en fout de la quantite de memoire que je grille je veux de la vitesse.
voici le tri le plus rapide du monde :
initialiser a 0 tableau[k] //je cree un tableau pour le tri
valeur[n] // la structure qui contient mes valeurs
pour i entre 0 et n exclu faire
incrementer tableau[valeur[i]]
fin pour
Amusant non ? et hop une structure qui contient dans chaque case le nombre d'elements egaux a la place de la case. cout : O(n).
Ensuite pour sortir les zeros du tableau (si le besoin s'en fait sentir )c'est O(k), mais c'est rarement obligatoire. En fait ca n'est utile que si k est tres superieur a n(ce qui est souvent tres rare).
Maintenant si ce n'est pas des entiers (c'est la que ca bouffe de la memoire) ben on va les transformer en entiers en les multipliant par ce qui va bien (preicision a six chiffres = *1000 0000). Vous avez bien entendu le droit de hurler a l'anonce de cette ennormite, neamoins il y a pas mal de cas ou ca marche. Bien sur il risque d'y avoir plus de chances que k soit superieur a n, donc le traitement pour purger les 0 du tableau peut sembler long.
Kha
[^] # Re: Soft de peer to perr
Posté par Christophe GRAND (site web personnel) . Évalué à 1.
Celui que j'ai détaillé ne nécessite que n/m en plus de tes n données.
Il ne nécessite pas non plus de vilaines bidouilles comme ta fonction injective sur les entiers (c'est ta "multiplication" qui tient ce rôle)
[^] # Re: Soft de peer to perr
Posté par Christophe GRAND (site web personnel) . Évalué à 2.
Cependant, il me semble que les fameux tris en O(n), même s'ils restent très supérieurs aux algorithmes classiques quand ils sont applicables, sont en fait en O(n.m) avec m une "très grosse" constante.
Pas forcément si grosse que ça la constante (puisqu'elle dépend grandement de la distribuion des données) mais, oui, elle est là et personne ne veut en parler.
Par exemple dans l'algo suivant :
soit une entrée de n nombres (dont la distribution est F)
soit m une constante (de préférence plus petite que n)
soient q_i = F^(-1)(i*m/n) pour i entier entre 1 et r-1=E(n/m) (E la partie entière)
et q_0 = -inf et q_r = +inf
soit c la fonction telle que :
c(x)=i si et seulement si q_i <= x < q_(i+1)
c peut être vue comme une équivalence. On a donc r classes d'équivalences. Or on peut classer n nombres en O(n) (avec une complexité mémoire en O(r), donc en O(n/m)... en O(n)).
(classer les nombres consiste à mettre en premeir ceux de la classe 0, en deuxième ceux de la classe 1 etc.)(NB : quicksort est un classement en deux classes qui s'appelle récursivement sur chaque classe)
Une fois classés, il suffit d'appeler sur chaque classe un algo de tri classique. Chaque classe ayant un effectif espéré de m nombres, le tri d'une classe se fait en O(m ln m).
Or il y a r (c'est à dire à peu près n/m) classes donc le tri de toutes les classes coûte :
O(n ln m)
il y a aussi le coût du classement : O(n)
Le tout est en O(n ln m) + O(n), c'est à dire O(n) CQFD et 10 de der.
Et puis ln m c'est pas gros comme constante.
Ok, je mens : la vraie vilaine constante est dans le classement : l'évaluation de F^(-1) pour tout nombre en entrée. Dans la plupart des cas pratiques, cette fonction est dégueulasse. (rien qu'une petite gaussienne est déjà méchante) (Par contre si vos données sont équiréparties, c'est trivial)
Et voilà, je suis un encore plus gros vendeur de mèche.
[^] # Re: Soft de peer to perr
Posté par Larry Cow . Évalué à 2.
On peut s'associer: on monterait MicroMèche, on aurait le monopole de la mèche dans le monde, et on deviendrait milliardaires.
Bien sur, une bande de fanatiques barbus et intaigristes clameraient la supériorité incontestable des Mèches Libres, mais qui donnerait foi à de tels tissus d'absurdité? Je vous le demande, ma bonne dame...
(il est tard, je sors direction mon lit)
[^] # Re: Soft de peer to perr
Posté par Erwan . Évalué à 1.
La deuxieme me semble plutot un retour en arriere ; les donnees du milieu seront difficiles a trouver.
# Re: Soft de peer to perr
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
L'idée est de pouvoir créer des radio a partant d'une bète ligne ADSL.
Cela ressemble à bit torrent et je voulais empécher l'exploration des IP de ceux qui écoute le stream et empécher le snif de la connexion (avec une distribution de clef pas triste).
"La première sécurité est la liberté"
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.