Max sur les valeurs d'une colonne d'n tableau

chaps31 · janvier 2009

Bonjour à tous,

J'ai un tableau avec plusieurs colonnes et plusieurs lignes, je voudrais connaitre la valeur max contenue dans une colonne d'integer.

Je ne vois aucune méthode simple pour les NSArray... Donc je me demandais comment faire de manière économe en ressource... Pour éviter de voir tourner la roue multicolore si j'ai un tableau de plusieurs milliers de lignes...
Je ne peux pas créer un autre threat car cette valeur est vitale à la suite de l'exécution du programme...

Merci par avance pour vos lumières.

schlum · janvier 2009

Il faut maintenir cette valeur "max" en continu quelque part... et la mettre à jour quand il le faut.
Y a pas d'algorithmes en dessous de O(n) pour trouver une valeur maximale dans un tableau non trié.

Chacha · janvier 2009

dans 1231340620:

J'ai un tableau avec plusieurs colonnes et plusieurs lignes, je voudrais connaitre la valeur max contenue dans une colonne d'integer.

D'un point de vue du code, c'est une question triviale :
-parcourir toutes les cases, garder la valeur max.
-ou sinon, maintenir "en cache" la valeur max, mise à jour à chaque ajout dans le tableau (facile et peu coûteux), ainsi qu'à chaque suppression/modification (beaucoup moins pratique).
Il y a peu de chances que la 1ère méthode ne soit pas la meilleure dans tous les cas.

J'ai cependant l'impression que tu veux en fait te poser la question pour une NSTableView. Mais ça c'est côté interface, pas côté "modèle de données".
Quel est ton modèle de données ? Est-il adapté à une interrogation ligne par ligne dans une colonne ? As-tu accès à un gros tableau bi-dimensionnel sous-jacent ?
Pour l'instant on ne peut pas trop répondre.

Un détail toutefois : as-tu pensé à l'opérateur @max du key-value-coding ?

NSArray* array = [NSArray arrayWithObjects:
[NSNumber numberWithInt:1], [NSNumber numberWithInt:3], [NSNumber numberWithInt:2], nil];
NSLog(@max = %d, [[array valueForKeyPath:@"@max.self"] intValue]);

+
chacha

schlum · janvier 2009

dans 1231342386:

-ou sinon, maintenir "en cache" la valeur max, mise à jour à chaque ajout dans le tableau (facile et peu coûteux), ainsi qu'à chaque suppression/modification (beaucoup moins pratique).

Bah... c'est moins pratique que dans des cas précis :
- Quand on supprime une valeur égale au max
- Quand on réduit une valeur égale au max
Dans ce cas il faut recalculer en parcourant tout à nouveau.

chaps31 · janvier 2009

Vu que mon tableau à l'origine se remplie avec une base postgresql, oui je peux au moment du remplissage initial faire un MAX sur la base, voire à chaque mise à jour de la base (chaque modif du tableau est répercutée dans la base pour que mon tableau datasource et ma base de données soient bien sûr toujours identiques), c'est peut-être le moins couteux et le plus simple (je ne connais pas la vitesse du MAX de postgre sur des milliers d'enregistrements...).

sinon j'ai peur qu'un :

int i,idMax;<br />		int count;<br />		idMax=0;<br />		count = [clients count];<br />		for (i = 0; i &lt; count; i++) {<br />			if(idMax&lt;[[[maTable valueForKey:@&quot;id&quot;] objectAtIndex:i] intValue])<br />			{<br />				idMax =[[[maTable valueForKey:@&quot;id&quot;] objectAtIndex:i] intValue];<br />			}<br />		}

sur plusieurs milliers de ligne fasse mouliner un peu...

Je vais essayer ton

[[array valueForKeyPath:@&quot;@max.self&quot;] intValue]

que je ne connaissais pas, merci à vous 2.

Chacha · janvier 2009

dans 1231343471:

Bah... c'est moins pratique que dans des cas précis :
- Quand on supprime une valeur égale au max
- Quand on réduit une valeur égale au max
Dans ce cas il faut recalculer en parcourant tout à nouveau.

Non, il y a aussi le cas où les objets sont mutables : il faut détecter les modifications. S'il a une table view, la colonne des integers peut être une "vue" vers une propriété "int" d'un objet mutable sous-jacent.

Il y a aussi le cas "supprimer un ensemble de valeurs contenant le max". Dans ce cas, pour les performances, il ne faut pas décomposer en une "suite de suppressions avec calcul du nouveau max à chaque fois".

C'est vraiment une solution à risques.

+
Chacha

chaps31 · janvier 2009

Le

[[array valueForKeyPath:@&quot;@max.self&quot;] intValue]

Ne marche pas, il s'arrête à "9"... Alors qu'il devrait afficher 22...

Chacha · janvier 2009

dans 1231344358:
Le
[[array valueForKeyPath:@&quot;@max.self&quot;] intValue]
Ne marche pas, il s'arrête à "9"... Alors qu'il devrait afficher 22...

Alors c'est qu'il y a un problème dans ton code... As-tu compris comment fonctionne le @max ?

la doc : http://developer.apple.com/Documentation/Cocoa/Conceptual/KeyValueCoding/Concepts/ArrayOperators.html#//apple_ref/doc/uid/20002176

Dans ton cas (je pense : )

NSArray* maTable = [NSArray arrayWithObjects:
[NSDictionary dictionaryWithObjectsAndKeys:
[NSNumber numberWithInt:1], @id,nil],
[NSDictionary dictionaryWithObjectsAndKeys:
[NSNumber numberWithInt:3], @id,nil],
[NSDictionary dictionaryWithObjectsAndKeys:
[NSNumber numberWithInt:2], @id,nil],
nil];
NSLog(@max = %d, [[maTable valueForKeyPath:@"@max.id"] intValue]);

AliGator · janvier 2009

Heu question : si tu récupères ces données depuis ta base, ne serait-il pas moins coûteux en ressources de demander directement à ta base cette valeur (d'autant qu'ils ont sûrement des algos optimisés du côté de ta base SQL pour ça) ?
Certes ça te fait une requête SQL en plus (genre [tt]SELECT MAX(macolonne) FROM matable[/tt]) juste pour avoir le MAX, mais c'est peut-être moins coûteux que de calculer le max toi-même si tu as un gros tableau ?

Donc si la question est "comment optimiser le calcul de mon max", je crois pas que tu puisses faire bcp mieux que le parcours de toute ta liste, à part garder en mémoire le dernier max, le mettre à jour si tu modifies une valeur en >max, mais de toute façon tout recalculer si tu modifies le max pour le diminuer... et encore ça ne marche que si tu modifies tes données une par une, si tu refais une requête SQL à chaque fois et que donc toutes tes fiches sont potentiellement remises à jour, cette optimisation ne servira vraiment à rien (voire ne sera pas faisable) et tu retombes sur la solution de tout parcourir.

Je l'avais déjà cité dans ce forum, mais j'aime bien Cet article de ridiculousfish.com qui montre que les classes NSArray & co sont déjà bien optimisées automatiquement par Cocoa selon le nombre d'éléments qu'ils contiennent, etc. Donc de ce côté on a pas de soucis à se faire, le parcours d'un NSArray (pour calculer son max) sera optimisé en fonction du nombre d'éléments à priori. Encore plus si on utilise les fast-enumerators d'Objc-C 2.0.
Mais ça vaut le coup quand même de demander à SQL de calculer ce max pour toi, si tu risques d'avoir beaucoup beaucoup d'entrées.

Et puis bon au pire si vraiment c'est un peu long et que tu ne peux pas accélérer le calcul du max, ben c'est un fait, tu n'y peux rien, même si cette valeur est "vitale" : tu n'auras plus, pour éviter la roue multicolore, qu'à écrire "--" dans ton interface le temps de calculer, lancer le calcul dans un thread, et une fois le calcul fini mettre à jour l'interface.

chaps31 · janvier 2009

Merci à tous, Chacha, en effet... j'm'a gourré... :)beta: Je n'avais pas bien compris l'utilisation merci pour les détails.

Bon j'ai tout codé, tout marche reste plus qu'à choisir, au final vous pensez que la requête SQL sera le plus rapide ? Vu que j'ai tout codé je peux laisser le reste en commentaires au cas où :P

J'ai simplement créé une variable d'instance de ma classe "Base" (qui fait l'interface avec postgre) nommée idMax, j'y accède via mon instance de Base dans ma classe qui contrôle mon interface, dans "Base" j'ai créé une méthode pour extraire le max (4 lignes... :P) et je l'appel dans les méthodes de "Base" qui modifient la base de données pour mettre à jour mon idMax à chaque fois (cette variable ne peut qu'augmenter puisque c'est l'id de mes enregistrements postgre, un autoincrement).

Si l'unanimité va vers le fait de faire travailler SQL, parce-que quand même c'est fait pour ça je bouge plus et verrais dans la pratique.

Ali je vais aller voir ton lien, je me suis toujours demandé si Cocoa était rapide dans la manipulation des grands tableaux.

Merci à tous encore une fois.

schlum · janvier 2009

dans 1231343923:

dans 1231343471:

Bah... c'est moins pratique que dans des cas précis :
- Quand on supprime une valeur égale au max
- Quand on réduit une valeur égale au max
Dans ce cas il faut recalculer en parcourant tout à nouveau.

Non, il y a aussi le cas où les objets sont mutables : il faut détecter les modifications. S'il a une table view, la colonne des integers peut être une "vue" vers une propriété "int" d'un objet mutable sous-jacent.

Il y a aussi le cas "supprimer un ensemble de valeurs contenant le max". Dans ce cas, pour les performances, il ne faut pas décomposer en une "suite de suppressions avec calcul du nouveau max à chaque fois".

C'est vraiment une solution à risques.

+
Chacha

Ben... ça fait partie des 2 cas cités non ? :P

AliGator · janvier 2009

Heu attends, c'est pour récupérer ton ID max que tu veux ça ?? Qui est donc autoincrement ?Â ::)

Utilise plutôt [tt]LAST_ID()[/tt] (je crois que la fonction SQL s'appelle comme ça) alors, ça te retournera directement la valeur (que ta base SQL garde en mémoire pour ne pas avoir à la recalculer à chaque fois) , avec cette méthode SQL il ne va pas parcourir toute ta table pour trouver le max, il va se contenter de te retourner le dernier ID utilisé qu'il a en mémoire (et qu'il utilise pour l'incrémenter à chaque fois qu'il insère une nouvelle fiche)

Au pire si t'as pas d'équivalent à LAST_ID en postgreSql, un [tt]SELECT id FROM matable ORDER BY id DESCENDING LIMIT 1[/tt] sera peut-être plus rapide qu'un [tt]SELECT MAX(id) FROM matable[/tt], quoique ça se discute, mais de toute façon je suis sûr qu'il y a un LAST_ID ou truc du genre !!

Et ça t'évitera de parcourir tout ton tableau pour rien, surtout s'il est conséquent, puisque dans ce cas tu as une solution en O(1) (temps constant) au lieu de O(n) !

schlum · janvier 2009

"currval" en postgre...

http://archives.postgresql.org/pgsql-general/2003-08/msg01699.php

Max sur les valeurs d'une colonne d'n tableau

Réponses