Effectuer une rapide recherche dans une generic list of string

Version imprimable

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:

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

17/02/2014, 16h25
ebastien

Bonjour

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

Code:

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

Bonjour,
Avec Parallel.ForEach ?

Code:

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)

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:

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

18/02/2014, 11h51
shayw

Bonjour à tous

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

Citation:

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
18/02/2014, 13h03
dkmix

Citation:

à 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.

Merci dkmix :D

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

Code:

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

18/02/2014, 20h34
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.

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

Code:

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

19/02/2014, 09h36
DonQuiche

Citation:

Envoyé par shayw

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.
19/02/2014, 11h56
shayw

Citation:

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.

Citation:

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

Je n'ai pas compris de quel mot il s'agit :?
20/02/2014, 15h38
shayw

Ah j'ai compris :P après deux jours de recherche 8O

pour chaque mot du dictionnaire verifié s'il est formé des 10 Lettres distribuées
20/02/2014, 16h56
DonQuiche

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