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.