C-Convertion chaine - Algo liste chaînée ordonnée -Fonction qui enlève

Recherche :

Dernière réponse

Sujet : C-Convertion chaine - Algo liste chaînée ordonnée -Fonction qui enlève

LeGreg

merou91 a écrit a écrit :

Je ne dispose pas de liste de départ, c'est moi qui la crée et comme il peut y avoir plus de 50000 éléments à l'intérieur ce serait préférable que lorque j'ajoute un nouvel élément je la trie parce que le parcours de 50000 éléments 2 millions de fois ca peut être long (à l'heure actuelle c comme ca, c'est une pile).(si un élément est en double j'incrémente un compteur)

Si tu dois faire beaucoup de "lookup" dans ta liste,
il vaut certainement mieux passer a un b-tree
qui te permettra de passer d'un lookup en N
a un lookup en Log2(N)
M'enfin c'est juste un conseil.

Ou un arbre d'index.. enfin tu dois avoir
vu tout ca dans tes cours de prog, non?

LEGREG

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

LeGreg

merou91

Je ne dispose pas de liste de départ, c'est moi qui la crée et comme il peut y avoir plus de 50000 éléments à l'intérieur ce serait préférable que lorque j'ajoute un nouvel élément je la trie parce que le parcours de 50000 éléments 2 millions de fois ca peut être long (à l'heure actuelle c comme ca, c'est une pile).(si un élément est en double j'incrémente un compteur)
C'est une liste chaînée de structure et pour ca l'algorithme de shell ne m'aide pas bcp. Je cherche l'algo pour les listes chaînées parcequ'il y a pleins de cas chiants à gérer liste nulle, ajout avant le premier élément, ajout après, garder la le pointeur précédent pour faire une chaînage entre deux éléments, cas des éléments identiques etc.

Pour le coup de espaces je vais regarder ce que tu propose thx :).

kvl	Ta premiere idée me semble pas mal en utilisant un sscanf(ip,%[0-9]...,&a...) puis aprés complément à gauche %3d ... [jfdsdjhfuetppo]--Message édité par kvl--[/jfdsdjhfuetppo]

LeGreg

merou91 a écrit a écrit :

Oui c'est forcément une liste chaînée et je cherche l'algo qui ajoute un élément dans un liste selon 1 critère. Pas le tri à bulles qui trie après mais l'ago qui trie pendant l'ajout.
Sinon ouai je vois comment le faire à la main pour enlever les espaces de début mais bon comme ca va s'exécuter 2 fois pour les 2 millions de lignes du fichier que je lis si y a une fonction optimisée qui le fait c'est mieux quand même.

on n'optimise jamais un truc hors contexte.
Si ce sont des chaines statiques, tu peux
te contenter de deplacer le pointeur de debut
de chaine sur le premier caractere non espace.
Si tu dois operer une copie de ta chaine
a un moment (pour la mettre dans ta structure par ex),
et bien tu peux copier qu'a partir du premier
caractere non espace. etc.. etc..

Si tu as acces au C++, tu peux utiliser les structures
de la STL:

Citation :

void sort(); Sorts *this according to operator<. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N, where N is the list's size.

N*LogN c'est le temps d'execution moyen de la plupart des algorithmes de tri par comparaison.

Parfois c'est aussi rapide de conserver la liste en ordre
au fur et a mesure que tu rajoutes des elements.
Cela s'appelle le tri par insertion.
Tu prends une liste vide tu mets le premier element,
tu mets le deuxieme element en conservant l'ordre avec le premier.
Quand tu as une liste de n elements tries. Pour ajouter
ton n+1eme nombre, il suffit de parcourir ta liste a la recherche du plus petit element superieur a ton nombre
et d'inserer ce nombre a sa place. etc..
Si tu disposes d'une liste au depart quasiment triee,
le cout de construction de la liste triee est faible.
(tu peux faire le tri sur place mais pour une liste
chainee, la difference entre le tri sur place et la creation d'une nouvelle liste est totalement anecdotique).

Une variante plus efficace est le tri shell, qui consiste
a utiliser un pas variable pour rechercher le plus petit element superieur. Le principe de comment marche le tri shell est plus complique a comprendre mais il est efficace en pratique.

Il y a plein d'implantations disponibles sur internet:
http://www.google.fr/search?q=shell+sort

A+
LEGREG

merou91

Oui c'est forcément une liste chaînée et je cherche l'algo qui ajoute un élément dans un liste selon 1 critère. Pas le tri à bulles qui trie après mais l'ago qui trie pendant l'ajout.

Sinon ouai je vois comment le faire à la main pour enlever les espaces de début mais bon comme ca va s'exécuter 2 fois pour les 2 millions de lignes du fichier que je lis si y a une fonction optimisée qui le fait c'est mieux quand même.

LeGreg

Pour enlever les espaces
tu parcours ta chaine, tu reperes la position
du premier chiffre et tu decales simplement ta chaine
sur la gauche.. rien de sorcier.

pour le tri..
ca depend, du nombre d'elements a trier,
de leur ordre de depart.
Es-tu oblige d'utiliser une liste chainee?
si tu pouvais mettre tes valeurs dans un tableau
la fonction qsort ca marche pas mal.

A+
LEGREG

merou91

:bounce: up

merou91

Personne pour la fonction qui enlève les caractères espaces de début de chaîne et/ou un lien vers l'algorithme d'ajout trié d'un élément dans une liste chaînée selon 1 critère ?

merou91

Ok merci tout le monde pour les réponses :).

Je cherche encore un truc, un lien vers l'algorithme de trie d'une liste chaînée selon 1 critère en c (j'en ai pondu 1 mais bon je pense qu'il y a mieux :sarcastic: ).

HelloWorld

tu fais un tableau de 4 octets et tu mets chaque nombre dans les octets :

Code :

unsigned char Tab[4];

et tu initialise chaque caractere avec un nombre de l'ip ...
par exemple, 193.168.168.10 te donne :
Tab[0] = 193
Tab[1] = 168
Tab[2] = 168
Tab[3] = 10

pour avoir ensuite un long sous la forme "193168168010", tu fais juste :

Code :

if((unsigned long)(*Tab) < ...)

Cela dit, il va peut etre falloir inverser les nombres (Tab[0] = 10, ..., Tab[3] = 193)
Il serait peut etre mieux alors d'utiliser une structure voire une union ...

Code :

typedef union
{
unsigned char Tab[4];
unsigned long val;
}ip_t;

et le code devient

Code :

ip_t ip;
ip.Tab[0] = 193
ip.Tab[1] = 168
ip.Tab[2] = 168
ip.Tab[3] = 10
if(ip.val < ...)

à voir ...

merou91

Ok merci.

Sinon je cherche encore un truc, une fonction qui enlève les espaces de début de chaîne (toujours en c/c++).

Procat

merou91 a écrit a écrit :

Y a qqn qui peut m'expliquer le résultat de inet_addr pour "192.168.0.1" donnant 16820416 ?

Sinon à votre avis c'est plus rapide en temps d'exécution :

if(inet_addr(ip1)<inet_addr(ip2)) {etc etc }
ou
if (strcmp(ip1,ip2)<0) {etc etc }

Tu prends 1 comme octet de poid fort et 192 comme octet de poid faible
Donc a partir de là tu as en realité 1.0.168.192

Metjode 1 (methode de bourrin)

1.0.168.192 en decimal =>
0000 0001.0000 0000.1010 1000.1100 0000 en binaire =>
tu les mets cote a cote :
00000001000000001010100011000000 => 16820416 en decimal
compris ??

Autre methode moins barbare

1.0.168.192=>

1*(256*256*256) // octet de poid fort sur un groupe de 4
// octet donc il y aura 3 octets apres
// d'ou *(256*256*256)
+0*(256*256) // pareil avec 2 octect apres => *(256*256)
+168*(256) // encore un octet apres *(256)
+192 // octet de poid faible donc
= 16820416

merou91

Y a qqn qui peut m'expliquer le résultat de inet_addr pour "192.168.0.1" donnant 16820416 ?

Sinon à votre avis c'est plus rapide en temps d'exécution :

if(inet_addr(ip1)<inet_addr(ip2)) {etc etc }
ou
if (strcmp(ip1,ip2)<0) {etc etc }

merou91

Je voudrais la triller par ordre croissant ou décroissant d'@IP. Faut que je regarde quelles sont les @ les plus fréquentes pour savoir si elles sont plutôt grande ou petite ce qui me permettra de choisir l'ordre.

Sinon j'ai toujours pas capté tes puissances désolé :D
Y a pas de puissance 24 dans les @IP on s'arrête à 7 car elles sont découpées en octets et on prend les octets séparément. Transformer en binaire je sais faire mais je crois pas que c'est ce dont j'ai besoin là.
Et je capte donc toujours pas le résultat de inet_addr pour 192.168.0.1.
Désolé y en a être lent mais comprendre vite quand même :pt1cable: .

HappyHarry

c des decalages ... 'fin bref ...
tu sais compter en base 2 ?

les adresses ip c des long, jusque la on est d'accord ?
la représentation sous forme de chaine, c la valeur de chacun des 4 octets qui composent le long, séparées par des points

si tu veux la valeur 'numérique' d'une adresse ip, en la calculant toi meme comme un grand, pour ta culture personnelle tu fais

premier octer * 2 puissance 24
+ deuxieme octet * 2 puissance 16
+ troisieme octet * 2 puissance 8
+ quatrieme octet

m'enfin c clair que inet_addr ca va plus vite :)

reste juste a voir selon quels criteres tu veux les classer tes adresses

merou91

happyharry j'ai rien capté à ta comparaison de chiffres ?

HappyHarry

ben tu l'as dit toi meme .. une ip c un nombre sur 4 octets ...
donc 192.168.0.1 =
192<<24 + 168<<16 + 0<<8 + 1 ...

la conclusion tu la tireras toi meme ...

Tentacle

merou91 a écrit a écrit :

Tentacle : tu peux m'en dire un peu plus svp.

Sinon je viens de voir que inet_addr() transforme normalement une chaine de caractère contenant une @IP en un long mais je n'arrive pas à l'utiliser :
unsigned long l;
char *ip="192.168.0.1";
l=inet_addr(ip);

donne l = 16820416 ?

printf permet de formatter une chaîne en lui disant par exemple d'afficher un nombre sur 3 chiffres. sprintf fait la même chose mais on peut en récupérer le résultat dans une string.
Regarde dans de la doc pour la syntaxe exacte parce que je ne me rappelle plus des détails... au fait c'est bien du C ? spécifie ton language dans le nom du post stp :)

merou91

Tentacle : tu peux m'en dire un peu plus svp.

Sinon je viens de voir que inet_addr() transforme normalement une chaine de caractère contenant une @IP en un long mais je n'arrive pas à l'utiliser :
unsigned long l;
char *ip="192.168.0.1";
l=inet_addr(ip);

donne l = 16820416 ?

Tentacle

merou91 a écrit a écrit :

Je viens de penser à un truc, y aurai moyen de faire ca :
"192.168.0.1" -> 192168000001 ?
Je peux récupérer les 4 digits avec sscanf(ip,"%ld.%ld.%ld.%ld",&a,&b,&c,&d)

Mais alors comment forcer ces nombres à avoir 3 chiffres cad transformer 3 en 003, 12 en 012 ?
Et finalement comment obtenir le nombre final concatenation des 4 nombres ?

sprintf ?

merou91

Je viens de penser à un truc, y aurai moyen de faire ca :
"192.168.0.1" -> 192168000001 ?
Je peux récupérer les 4 digits avec sscanf(ip,"%ld.%ld.%ld.%ld",&a,&b,&c,&d)

Mais alors comment forcer ces nombres à avoir 3 chiffres cad transformer 3 en 003, 12 en 012 ?
Et finalement comment obtenir le nombre final concatenation des 4 nombres ?

merou91

J'aurai besoin de convertir un chaîne qui contient des chiffres et plusieurs caractères '.' de ce type : "192.135.1.1"

Si je fais :

sscanf(ip,"%f",&a) -> a=192.135 (a float)
a=strtod(ip,NULL) -> a=192.13500000000 (a double)

Le but est d'obtenir un chiffre unique pour une adresse IP donnée afin de ranger ces adresses par ordre dans une liste. Parce que je me vois mal faire l'algo de rangement sur les 4 octets de l'adresse IP.

[jfdsdjhfuetppo]--Message édité par merou91--[/jfdsdjhfuetppo]