Discussion :

[shayw]

Bonjour

J'ai deux lists de string nommé perms et listdico et je obtenir la list de tous les string de perms se trouvant dans dico
J'ai écrit le code suivant mais ce n'est pas assez rapide

Code :

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

1
2
3
4
5
6
7
Dim listresult As New List(Of String)
    For Each item In permutation
             id = listdico.BinarySearch(item)
            If id >= 0 Then
                listresult.Add(item)
            End If
        Next

la list perms peut compter jusqu'à 10! soit 3628800 items et listdico 6000 items
le temps d'execution est de 15 sec

Si je divise la recherche en deux parties avec un thread cela peut améliorer la vitesse ?
merci d'avance

[ebastien]

Bonjour

Avec Linq, ce sera peut-être plus rapide :

Code VB.NET :

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

ListeResult = (From p In permutation Where listdico.BinarySearch(p)>=0 Select p).ToList

[dkmix]

Bonjour,
Avec Parallel.ForEach ?

Code :

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

1
2
3
4
5
6
7
8
 
 Parallel.ForEach(permutation, Sub(st)
                                          If listdico.Contains(st) Then
                                              SyncLock listresult
                                                  listresult.Add(st)
                                              End SyncLock
                                          End If
                                      End Sub)

[DonQuiche]

Bonjour.

Aujourd'hui tu utilises donc un algorithme en O(n.ln(m)). Je peux te proposer une solution en O(n.ln(n)+m), voire en O(n+m) si "permutations" est déjà triée. Le principe est de trier les listes en amont, puis de les parcourir conjointement de la façon suivante:

Code VB.NET :

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
' x et y doivent être triés en amont, je suggère de les renommer en "sortedList1" et "sortedList2".
Private Function Intersection(x As List(Of String), y As List(Of String)) As IEnumerable(Of String)
	Dim i As Integer = 0, j As Integer = 0
	While i < x.Count AndAlso j < y.Count
		Dim comparison As Integer = x(i).CompareTo(y(j))
		If comparison = 0 Then
			yield Return x(i)
			i += 1
			j += 1
		ElseIf comparison < 0 Then
			i += 1    ' x[i] < y[j]
		Else
			j += 1
		End If
	End While
End Function

[shayw]

Bonjour à tous

à ebastien le LINK un peu plus rapide
à dkmix cela n'a rien donné
à DonQuich

si "permutations" est déjà triée

justement non et pour trier cela demande aussi du temps


Le but est pour le jeu des chiffres et des lettres.
Comme il y a 10 lettres donc il y a en théorie 10! permutations
le mieux serait de retirer toutes les chaines qui ne peuvent pas etre un mot valable

je marque comme résolu

[dkmix]

à dkmix cela n'a rien donné

C'est à dire? le principe est d'utiliser Parallel.ForEach, pour une boucle multithread, le bout de code que j'ai donné, c'est juste pour montrer comment l'utiliser, il faut surement l'adapter à ton code.

[shayw]

Merci dkmix


j'ai modifié et c'est beaucoup plus rapide 9 sec au lieu de 16 avec le linq

Code :

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

1
2
3
4
5
Parallel.ForEach(permutation, Sub(st)
                                          If listdico.BinarySearch(st) > 0 Then
                                              listresult.Add(st)
                                          End If
                                      End Sub)

[DonQuiche]

Sauf que List.Add n'est pas thread-safe donc tu vas renocntrer aléatoirement des bogues. C'est pour ça que dkremix avait mis en place un mécanisme de synchronisation.
Et il serait peut-être plus rapide d'utiliser Parallel.For au lieu de ForEach.

[shayw]

ah merci DonQuich
je n'avais pas vu le SyncLock j'ai corrigé

Code :

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

1
2
3
4
5
6
7
Parallel.For(0, permutation.Count - 1, Sub(st)
                                                   If listdico(index).BinarySearch(permutation(st)) > 0 Then
                                                       SyncLock listresult
                                                           listresult.Add(permutation(st))
                                                       End SyncLock
                                                  End if
                                               End Sub)

Au point de vu vitesse parallel.for et parallel.foreach sont équivalent

Maintenant j'ai en fait plusieurs permutations string de 10 ,9,8 ......2 lettres et plusieurs listdico
Je verifie si on trouve un mot de 10 si oui j'arrete sinon je continue avec 9 lettres
Est ce qu'on peut effectuer les recherches en parallel multithread
Merci et bonne prog

[DonQuiche]

Maintenant j'ai en fait plusieurs permutations string de 10 ,9,8 ......2 lettres et plusieurs listdico
Je verifie si on trouve un mot de 10 si oui j'arrete sinon je continue avec 9 lettres
Est ce qu'on peut effectuer les recherches en parallel multithread
Merci et bonne prog

En fait, posé comme ça, je me rends que ton approche est mauvaise. J'aurais pu m'en rendre compte si j'avais fait attention aux tailles que tu nous donnais dans ton premier post.

Au lieu de calculer toutes les permutations possibles, mieux vaut tester tous les mots pour voir s'ils sont une permutation. C'est très simple et très rapide.

[shayw]

Au lieu de calculer toutes les permutations possibles, mieux vaut tester tous les mots pour voir s'ils sont une permutation. C'est très simple et très rapide.

mieux vaut tester tous les mots pour voir s'ils sont une permutation

Je n'ai pas compris de quel mot il s'agit

[shayw]

Ah j'ai compris après deux jours de recherche

pour chaque mot du dictionnaire verifié s'il est formé des 10 Lettres distribuées

[DonQuiche]

En effet, oui. Et désolé de t'avoir oublié.