Pouvoir utiliser une fonction à 2 arguments pour trier une liste avec "sort"

Bonjour ! :)

Je suis actuellement sur un projet pour mes études d'informatique. Le projet consiste de trier une liste de points (x, y) (avec les x et y positif et entier) et de les comparer pour garder un maximum de points qui possèdent une distance supérieur à un diamètre donné ("r").
J'ai donc trié la liste avec les x croissant puis en renversant une copie de la liste initial

Code:

---

1 2 3 4 5 6

l1.sort( key = operator.itemgetter(0) ) l2 = list(l1) l1 = traitementPoints(l1, r)   l2.reverse() l2 = traitementPoints(l2, r)

---

Puis j'ai fais la même chose mais cette fois pour les y en remplacant "operator.itemgetter(0)" par "operator.itemgetter(1)"
Jusque là tout va bien ^^

A présent je voulais trier la liste grâce au produit scalaire, j'ai créé cette fonction :

Code:

---

1 2	def produitScalaire(u, v): return u[0]*v[0] + u[1]*v[1]

---

Mais là où je n'arrive pas à trouver de réponse sur internet c'est pour le passage de la fonction sur la fonction "sort()"

J'ai donc essayer d'écrire (avec (3,2) un vecteur de référence) :

Code:

---

1 2	l.sort( key = lambda x: produitScalaire( (3, 2), x ) ) print(l)

---

Code:

---

1 2	l.sort( key = produitScalaire( (3, 2) ) ) print(l)

---

Mais j'ai toujours cette erreur :

Code:

---

1 2 3

"print(l) ^ SyntaxError: invalid syntax"

---

Je vous remercie d'avance pour votre aide !
Je suis nouveau sur ce forum (qui est mon premier forum ^^), j'espère ne pas avoir fais de faux pas sur la création du sujet ou autre :(, sinon j'essayerai de les corriger ^^

Salut,

En général, lorsqu'un SyntaxError arrive de nulle part, il faut s'assurer que l'instruction précédente se termine bien (en général on a oublié de compter le nombre de parenthèses ouvrantes/fermantes).

- W

Merci pour ta réponse ^^

Je dois admettre que je suis assez confus et désolé... Car effectivement je n'ai pas fais assez attention à une parenthèse oubliée :(

J'aurai juste une dernière question
Est-ce possible d'effectuer le calcul ci-dessous plus rapidement ? Car j'ai su hier qu'il fallait mieux utiliser "operator.itemgetter" que "lambda"

Code:

---

1 2	u = (3, 2) l.sort( key = lambda x: produitScalaire( u, x ) )

---

En m'excusant encore pour l'erreur que j'ai faite et pour l'embêtement occasionné...

Edit :

Car lorsque j'essaye comme ceci :

Code:

---

l.sort( key = produitScalaire( u, ( operator.itemgetter(0), operator.itemgetter(1) ) ) )

---

J'ai cette erreur :

Code:

---

1 2	return u[0]*v[0] + u[1]*v[1] TypeError: unsupported operand type(s) for *: 'int' and 'operator.itemgetter'

---

Citation:

---

Envoyé par RiivaG

Est-ce possible d'effectuer le calcul ci-dessous plus rapidement ? Car j'ai su hier qu'il fallait mieux utiliser "operator.itemgetter" que "lambda"

---

Il faut utiliser operator.itemgetter lorsque çà fait du sens... et c'est à voir au cas par cas.
D'abord, il faut comprendre qu'operator.itemgetter(n) retourne une fonction qui prendra une séquence en argument pour en retourner le n-ième élément:

Code:

---

1 2 3 4

>>> f = operator.itemgetter(3) >>> f('012345') '3' >>>

---

Ensuite, dans list.sort(key=...), l'argument passé à key sera une fonction qui recevra chaque élément de la liste pour retourner ce qui permettra de comparer.
Donc avec key = produitScalaire( u, ( operator.itemgetter(0), operator.itemgetter(1) ) ), on assigne à key le retour de la fonction produitScalaire. Et pour çà elle est appelée avant même de commencer à trier avec ( c(0), operator.itemgetter(1) ) en 2nd argument.

Et comme çà ne sait pas multiplier un entier par une fonction, çà plante.
=> pour appliquer la fonction produit_Scalaire aux différents éléments de la liste, il faudra toujours fabriquer une autre fonction appelée "fermeture" (avec ou sans lambda) qui dira comment appeler la fonction avec chaque élément.

Et si vous voulez ajouter des operator.itemgetter la dedans, çà devrait pouvoir s'écrire:

Code:

---

l.sort( key = lambda x: produitScalaire( u, ( operator.itemgetter(0)(x), operator.itemgetter(1)(x) ) ))

---

Et comparé à:

Code:

---

l.sort( key = lambda x: produitScalaire( u, x))

---

passer directement le "x" plutôt que d'en créer un autre avec deux appels de fonctions sera moins performant et inutile.

Quoique vous lisiez dans les forums, vous devez d'abord comprendre pour savoir si ce qu'on vous raconte s'applique ou pas à votre cas.

- W

Je vous remercie encore une fois pour votre réponse ! ^^

Je comprends beaucoup mieux l'utilisation de "operator.itemgetter()".

Donc si j'ai bien compris, dans le cas présent le mieux reste d'utiliser ce code ?

Code:

---

l.sort( key = lambda x: produitScalaire( u, x))

---

Il n'y a pas de moyen d'optimiser un peu plus le temps de traitement ?

(Je demande ça car j'ai une liste de 10 000 points à traiter, et je travaille dessus actuellement, ça peut prendre pas mal de temps :( Du coup je cherche à optimiser le plus de temps possible ^^)

Salut,

Citation:

---

Envoyé par RiivaG

Il n'y a pas de moyen d'optimiser un peu plus le temps de traitement ?

(Je demande ça car j'ai une liste de 10 000 points à traiter, et je travaille dessus actuellement, ça peut prendre pas mal de temps :( Du coup je cherche à optimiser le plus de temps possible ^^)

---

En l'état, vous pouvez juste supprimer l'appel à produitScalaire en incluant le calcul dans la définition du lambda.

Après vous pouvez décomposer l'opération en deux:

• calcul des produits scalaires,
• rangement des points,

et essayer d'utiliser numpy.dot pour les calculs (être plus efficace) ou les paralléliser (utiliser plus de ressources).

Après il faut vous poser des questions côté conception: avez vous vraiment besoin de calculer le produit scalaire avec les 10000 points?

- W

Citation:

---

Envoyé par RiivaG

Je vous remercie encore une fois pour votre réponse ! ^^

Je comprends beaucoup mieux l'utilisation de "operator.itemgetter()".

Donc si j'ai bien compris, dans le cas présent le mieux reste d'utiliser ce code ?

Code:

---

l.sort( key = lambda x: produitScalaire( u, x))

---

Il n'y a pas de moyen d'optimiser un peu plus le temps de traitement ?

(Je demande ça car j'ai une liste de 10 000 points à traiter, et je travaille dessus actuellement, ça peut prendre pas mal de temps :( Du coup je cherche à optimiser le plus de temps possible ^^)

---

1) Si vous voulez les points relativement à une certaine distance, je me demande pourquoi vous calculez le produit scalaire.... La distance entre 2 points A, et B de coordonnées respectives (xA,yA) et (xB, yB), c'est sqrt((xB-xA)²+(yB-yA)²).

2) Si vous voulez qqch de rapide, il y a numpy qui est parfaitement adapté pour cela. 10 000 points ce sera instantanné.

Citation:

---

Envoyé par wiztricks

et essayer d'utiliser numpy.dot pour les calculs (être plus efficace) ou les paralléliser (utiliser plus de ressources).

Après il faut vous poser des questions côté conception: avez vous vraiment besoin de calculer le produit scalaire avec les 10000 points?

---

Je regarderai ce soir l'utilisation de "numpy.dot" ^^ C'est vrai que je me suis posé la question mais c'est compliqué de s'arrêter dans une liste sans savoir si les points après ne sont peut-être pas à une distance r mais je vais me repencher dessus tête reposé ce soir !

Je vous remercie de nouveau pour votre aide et pour votre réponse !

Citation:

---

Envoyé par lg_53

1) Si vous voulez les points relativement à une certaine distance, je me demande pourquoi vous calculez le produit scalaire.... La distance entre 2 points A, et B de coordonnées respectives (xA,yA) et (xB, yB), c'est sqrt((xB-xA)²+(yB-yA)²).

2) Si vous voulez qqch de rapide, il y a numpy qui est parfaitement adapté pour cela. 10 000 points ce sera instantanné.

---

Pour reprendre le problème de base, je possède des fichiers de points en entrée (nombre de points, la distance r, et ensuite la série de x y des points par exemple :

2
10
0 1
10 20

que je récupère en input au début de mon programme et à l'aide de la commande python3 tp.py <(nom de fichier)).

Le but de mon programme est de trouver le maximum de points tout en respectant le fait que les points doivent avoir une distance entre eux supérieur à r. Du coup jusqu'à présent je prenais ma liste et je la triais soit grâce aux abscisses ou aux ordonnées qui ma permis de faire mon traitement de gauche à droite (et inversement) puis de bas en haut (et inversement). Le produit scalaire me permet de pouvoir trier la liste en "diagonale" avec un vecteur à un certain degré, pour essayer de trouver plus de points en résultat.

Je ne sais pas si mon raisonnement n'est pas trop pratique... ^^' Mais pour l'instant je ne voyais que cette solution. J'ai commencé à réfléchir ce matin pour essayer d’entamer le traitement "dans le tas" au milieu des extrémités mais pour l'instant je ne sais pas comment je vais procéder :?

Je ne sais pas si cela vous éclaire un peu plus ^^'

Voici mon traitement :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

def calcDistanceValide(a, b, r): return ((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])) < (r*r)   def traitementPoints(l, r):   i = 0 for x in l: j = i+1 while(j<len(l)): if( calcDistanceValide(x, l[j], r) ): del(l[j]) else: j+=1 i+=1   return l

---

et une image pour illustré pour un ensemble de 100points (bleu = valide, vert = "supprimé")
Pièce jointe 471512

Votre code semble fonctionner. Si c'est la maximalité (du nombre de points restants) qui vous pose problème alors là c'est plutot un problème algorithmique (et il y a une section sur le forum pour cela), qui est indépendant de python. Car en effet cette maximalité nécéssite des algos particulier pour la garantir. J'ai bien quelques idées en tête mais je n'ai pas vraiment le temps de les pousser pour voir si elles garantissent la maximalité (ce qui est loin d'être trivial), donc je préfère me taire pour ne pas vous envoyer dans une mauvaise direction. Quoi qu'il en soit sur le forum d'algorithmique vous trouverez surement de meilleur connaisseur des algorithmes de couverture spatiale maximal.

Bonsoir,

Excusez-moi du temps de réponse, j'ai un emploi du temps un peu chargé en ce moment ^^' En tout cas je vous remercie pour cette aide et ces informations précieuses !! J'ai vu rapidement pour la fonction, je verrai fin de week-end pour essayer de l'appliquer

Citation:

---

Envoyé par lg_53

Votre code semble fonctionner. Si c'est la maximalité (du nombre de points restants) qui vous pose problème alors là c'est plutot un problème algorithmique (et il y a une section sur le forum pour cela), qui est indépendant de python. Car en effet cette maximalité nécéssite des algos particulier pour la garantir. J'ai bien quelques idées en tête mais je n'ai pas vraiment le temps de les pousser pour voir si elles garantissent la maximalité (ce qui est loin d'être trivial), donc je préfère me taire pour ne pas vous envoyer dans une mauvaise direction. Quoi qu'il en soit sur le forum d'algorithmique vous trouverez surement de meilleur connaisseur des algorithmes de couverture spatiale maximal.

---

D'accord ! J'irai jeter un oeil plus tard, après avoir avancé d'autres projets ^^
En tout cas encore merci !

En attendant, je n'ai plus trop de question sur ce sujet pour l'instant ;) (Je recréerai un nouveau sujet si jamais j'en ai besoin ^^)
Je passe le sujet en résolu :)