Discussion :

[1tox]

Bonjour,

pour les besoins d'un comparateur d'offre pour un site web, je dois améliorer un algorithme. Voici le problème :
j'ai une liste A d'éléments numériques que nous appelerons Ai, i<N
et une liste B d'éléments numériques que nous appelerons Bj, j<N
On peut considérer que ces 2 listes sont triées par ordre croissant, i.e.
pour tout Ai, Ai<Ai+1
pour tout Bj, Bj<Bj+1
Je dois extraire une liste C constituée des 100 couples AiBj dont la somme Ai+Bj est la plus petite, i.e. telle que
Ck < Ck+1 ,k <= 100

La méthode la plus intuitive (et la moins efficace) consiste à constituer les N*N couples AiBj, à les trier et à en extraire les 100 premiers. Mais la complexité quadratique (O(n2)) de cette méthode pose un problème de performance. Est-il possible d'améliorer cet algorithme, et surtout existe-t-il un algorithme de complexité moindre qu'un algo en O(n2)?

Merci d'avance pour vos réponses futées

[Sylvain Togni]

J'ai en stock du O(100log(n)), quelqu'un a mieux ?

[1tox]

Je prends! Auriez-vous une solution gratuite à proposer ? Sinon on peut s'arranger

[pseudocode]

J'ai en stock du O(100log(n)), quelqu'un a mieux ?

En triant les 2 listes Ai et Bi et en maintenant un pointeur sur chaque liste on doit pouvoir faire mieux. Enfin je crois.

[Sylvain Togni]

En triant les 2 listes Ai et Bi et en maintenant un pointeur sur chaque liste on doit pouvoir faire mieux. Enfin je crois.

Tss, tss, tss, c'est pas si simple On ne peut pas se contenter d'avancer petit à petit l'un des deux pointeurs, il faut parfois reculer, voir repartir de zéro.


La solution que je propose est en fait en O(100log(100))

L'algorithme, qui à priori ne porte pas de nom vu que je viens de l'inventer , consiste à considérer les valeurs dans un repère, les Ai en abscisse, les Aj en ordonnées et les Ck sur la grille ainsi formée (voir figure ci-jointe).

Ensuite en raisonnant par récurrence :
- C0 = A0 + B0 (facile)
- Pour un k donné, supposons qu'on ai trouvé les C0, C1, ..., Ck (les cercles sur la figure), où chercher Ck+1 ? Réponse : sur la 4-frontière (frontière constituée des 4-voisins, i.e. les croix sur la figure), un raisonnement par l'absurde permet, par exemple, de s'en convaincre.

Cela permet donc de trouver les Ck dans l'ordre, et de s'arrêter quand on en a assez (100 par exemple).

Au niveau implémentation il suffit de maintenir deux listes ordonnées (ou arbres binaires, ...) : les Ck trouvés (cercles) et les candidats Ck+1 (croix). En effet, une liste ordonnée permet de récupérer le meilleur candidat (plus petite valeur) en O(1) et d'être mise à jour (insertion, suppression) en O(log n), n < 100 ici, d'où le O(100log(100)).

Je sais pas si j'ai été clair ?

[1tox]

L'explication est claire pour une solution qui n'est pas évidente à formuler . Il me semblait bien en effet que n ne devait pas dépasser 100 . Merci à vous et merci à Sylvain qui s'est donné la peine de faire un schéma

[pseudocode]

Tss, tss, tss, c'est pas si simple On ne peut pas se contenter d'avancer petit à petit l'un des deux pointeurs, il faut parfois reculer, voir repartir de zéro.

Of course. J'aurais du préciser qu'on ne peut pas construire la liste triée en une seule passe. Mais on doit pouvoir construire une liste de petite taille (entre 100 et N) qui contient, a coup sur, les 100 plus petites valeurs des sommes.

Reste a trier cette liste et prendre les 100 premiers.

Tout ca c'etait pour faire mieux que le log(N), mais si tu as du log(100), c'est tout bon.

[pseudocode]

Ensuite en raisonnant par récurrence :
- C0 = A0 + B0 (facile)
- Pour un k donné, supposons qu'on ai trouvé les C0, C1, ..., Ck (les cercles sur la figure), où chercher Ck+1 ? Réponse : sur la 4-frontière (frontière constituée des 4-voisins, i.e. les croix sur la figure), un raisonnement par l'absurde permet, par exemple, de s'en convaincre.

hum... ca implique que les Ai et les Bi soient triés non ?

[Zavonen]

hum... ca implique que les Ai et les Bi soient triés non ?

Cela fait partie de la donnée.

On peut considérer que ces 2 listes sont triées par ordre croissant, i.e.

[pseudocode]

Cela fait partie de la donnée.

Mince, faut que j'apprenne à lire.

[Zavonen]

Je précise tout de suite que je n'ai pas fait mieux que Sylvain Togni.
Voici la voie que j'ai essayé d'explorer sans pouvoir sortir de la complexité quadratique.
Quitte à faire une (ou deux) translations on peut supposer toutes les quantités positives.
En transformant par une exponentielle on peut transformer les sommes en produits.
Le problème est alors visuellement plus simple.
On a des points Mi(ai,bi) dans le quadrant supérieur droit du plan, à chaque point on associe l'aire du rectangle ayant O comme coin inférieur gauche et Mi comme coin supérieur droit, qui est justement aibi.
Maintenant toute hyperbole y=k/x divise le nuage en deux.
Les points qui sont dans la concavité de l'hyperbole.
Les points qui sont à l'extérieur (entre les axes et l'hyperbole).
Le problème est de trouver le plus petit paramètre k tel que les points de l'extérieur sont au nombre de 100.
Je précise qu'il s'agit juste d'une façon géométrique différente de visualiser le problème.
Cependant je ne sors pas de la complexité quadratique.
Si cette visualisation inspire quelqu'un ....

[pseudocode]

Je précise tout de suite que je n'ai pas fait mieux que Sylvain Togni.

Bah je ne pense pas qu'on puisse faire mieux que la programmation dynamique (ce que Sylvain Togni a proposé). Il faut trouver les 100 plus petites entrées dans le tableau des sommes Ai+Bj, ces 100 entrées sont forcément connexes. Donc faire mieux que 100.log(100) ca va etre dur, a moins de trouver une heuristique meilleure que l'exploration des voisins dans le tableau.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Cell implements Comparable<Cell> {		
	public int i,j,sum;
	public Cell(int i, int j, int sum) {
		this.i=i; this.j=j; this.sum=sum;
	}
	public int compareTo(Cell c) {
		return this.sum-c.sum;
	}
}
 
class CellList  {
	List<Cell> arraylist = new LinkedList<Cell>();
	public void add(Cell cell) {
		for(Cell c:arraylist)
			if (c.i==cell.i && c.j==cell.j) return;
		arraylist.add(cell);
	}
	public Cell popMin() {
		Cell cell = Collections.min(arraylist);
		arraylist.remove(cell);
		return cell;
	}		
}

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] A = new int[] { ... };
int[] B = new int[] { ... };
 
CellList tableau = new CellList();
tableau.add( new Cell(0,0,A[0]+B[0]) );
 
for(int k=0;k<100;k++) {
	// extrait la cellule avec la somme minimale
	Cell cell = tableau.popMin();
	System.out.println(cell.sum);
 
	// calcul des cellules voisines et ajout au tableau
	if (cell.i<A.length-1) 
		tableau.add( new Cell(cell.i+1,cell.j,A[cell.i+1]+B[cell.j]) );
	if (cell.j<B.length-1) 
		tableau.add( new Cell(cell.i,cell.j+1,A[cell.i]+B[cell.j+1]) );
}

[1tox]

Merci à tous pour votre participation