Καλησπέρα .NetZoners ;)

General Information

Δεν είμαι σίγουρος αν θα βοηθούσε περισσότερο να βάλω τον actual κώδικα ή αν θα ήταν καλύτερα (και γρηγορότερο στην κατανόηση) να περιγράψω απλώς την ιδέα του τι θέλω, οπότε θα διαλέξω το δεύτερο προς το παρόν, αλλά ευχαρίστως να γράψω και ακριβώς τον κώδικα εάν κάποιος νομίζει ότι χρειάζεται.

Θέλω να κάνω υπολογισμούς πάνω σε όλους τους δυνατούς συνδυασμούς ν-άδων για ένα σύνολο πινάκων Integers

Αυτό εκρήγνυται σε κάτι εξαιρετικά CPU-Intensive, χρονοβόρο και Memory hungry πολύ γρήγορα! (Ουσιαστικά αυτά είναι 2 προβλήματα, μόνο για το 1 εκ των οποίων ζητάω λύση σε αυτό το thread - αλλά αν κατά τύχη έχει κάποιος ιδέα και για το άλλο, don't hesitate to disclose the insight).

Algorithmic Information

Έχουμε 2 standards:

1) Υπάρχουν 80 διαφορετικοί αριθμοί από το 1 ως το 80 που μπορεί να περιέχονται μέσα στο κάθε array

2) Το κάθε Array περιέχει πάντα ένα συνδυασμό 20 integers από τους προαναφερθείς

Έχουμε 2 πράγματα που μπορούν να αλλάξουν:

1) Το πόσοι συνδυασμοί nChoosek υπάρχουν (από 80choose2 ως 80choose20)

2) Το πόσα Arrays περιέχει το κάθε σύνολο (από 1 ως μερικά εκατομμύρια)

Για την απλή περίπτωση: 80choose2= 3,160 συνδυασμοί και ένα σύνολο με 1 array των 20 integers

Άρα μιλάμε για 3,160 * 1 * 2 = 6,320 φορές να γίνουν υπολογισμοί

Αν μεγαλώσουμε το "ν" στις ν-άδες κατά 1 μόνο και κρατώντας το σύνολο σε μόνο 1, τότε έχουμε 80choose3= 82,160 συνδυασμούς * 1 * 20 = 246,480 φορές οι υπολογισμοί.

Αν το μεγαλώσουμε κατά 1 ακόμα φτάσαμε 1,581,580 4άδες και 6,326,320 φορές

1 ακόμα και έχουμε 24,040,016 5άδες και 120,200,080 φορές

1 ακόμα και 300,500,200 6άδες και 1,502,501,000 φορές, κτλ, κτλ.

Η πολυπλοκότητα δεν είναι ακριβώς O(n^2) διότι έχουμε ουσιαστικά τον άνω τριγωνικό πίνακα (combinations όχι permutations) και μάλιστα χωρίς τη διαγώνιο, αλλά και πάλι πάει προς εκθετική.

Το να κάνω υπολογισμούς για 12άδες π.χ. είναι επιστημονική φαντασία έτσι, διότι ο αλγόριθμος δεν κλιμακώνεται και θα πάρει μήνες να τελειώσουν οι υπολογισμοί (βέβαια με 32GB RAM και από 6άδες και πάνω χτυπάει out of memory, αλλά αυτό είναι ξεχωριστό πρόβλημα).

Algorithm

 Ο αρχικός κώδικας μου ήταν κάπως έτσι:

Dim ΑπόIndexΤάδε As Integer
Dim ΩςIndexΤάδε As Integer
Dim k As Integer = CInt(nudFindNGrams.Value)
Dim Συνδυασμοί As New List(Of List(Of Integer))
Συνδυασμοί = nChooseK(Από1Ως80, k)
				...
Await Task.Run(
	Sub()
		For i = 0 To Συνδυασμοί.Count - 1
			For j = ΑπόIndexΤάδε To ΩςIndexΤάδε
				For f As Integer = 0 To k - 1
					'Κάνε κάτι
				Next
			Next
		Next
		End Sub)

Δυστυχώς αυτό το μόνο που κάνει είναι αφήνει στο κύριο thread το User Interface και όλοι οι υπολογισμοί να γίνονται σε ΕΝΑ ξεχωριστό thread, σειριακά.

Προσπαθώντας να το κάνω να γίνονται όλα παράλληλα και σε τόσα threads όσα είναι και τα threads της CPU το μετέτρεψα έτσι (αλλά δεν κάνει αυτό που νόμιζα):

Public Class clsNGram
    Public nGramCombination As List(Of Integer)
    Public Occurrences As Integer
End Class

Dim ΑπόIndexΤάδε As Integer
Dim ΩςIndexΤάδε As Integer
Dim k As Integer = CInt(nudFindNGrams.Value)
Dim Συνδυασμοί As New List(Of List(Of Integer))
Συνδυασμοί = nChooseK(Από1Ως80, k)
				...
Await Task.Run(
Async Function()
	Dim ComputeQuery As New List(Of Task(Of List(Of clsNGram)))
	If Συνδυασμοί.Count > CoresCount Then
		Dim intCombinationsPerIteration As Integer = CInt(Math.Floor(Συνδυασμοί.Count / CoresCount))
		For i As Integer = 1 To CoresCount
			If i = 1 Then
				ComputeQuery.Add(Compute(0, intCombinationsPerIteration, k, Συνδυασμοί, ΑπόΤάδεIndexΣυνόλου, ΩςΤάδεIndexΣυνόλου))
			ElseIf i < CoresCount Then
				ComputeQuery.Add(Compute((intCombinationsPerIteration * i) - intCombinationsPerIteration + 1, intCombinationsPerIteration * i, k, Συνδυασμοί, ΑπόΤάδεIndexΣυνόλου, ΩςΤάδεIndexΣυνόλου))
			Else
				ComputeQuery.Add(Compute((intCombinationsPerIteration * i) - intCombinationsPerIteration + 1, Συνδυασμοί.Count - 1, k, Συνδυασμοί, ΑπόΤάδεIndexΣυνόλου, ΩςΤάδεIndexΣυνόλου))
			End If
		Next
	Else
		ComputeQuery.Add(Compute(0, Συνδυασμοί.Count - 1, k, Συνδυασμοί, ΑπόΤάδεIndexΣυνόλου, ΩςΤάδεIndexΣυνόλου))
	End If
	Dim CountSwarmsTasks As Task(Of List(Of clsNGram))() = ComputeQuery.ToArray
	Dim CountSwarmsLstClsNGram() As List(Of clsNGram) = Await Task.WhenAll(CountSwarmsTasks)
End Function)

Private Async Function Compute(ByVal ΑπόΤάδεIndexΣυνδυασμού As Integer, ByVal ΩςΤάδεIndexΣυνδυασμού As Integer, ByVal k As Integer, ByVal Συνδυασμοί As List(Of List(Of Integer)), ΑπόΤάδεIndexΣυνόλου As Integer, ΩςΤάδεIndexΣυνόλου As Integer) As Task(Of List(Of clsNGram))
    Dim CombinationsOccurences As New List(Of clsNGram)
    For i = ΑπόΤάδεIndexΣυνδυασμού To ΩςΤάδεIndexΣυνδυασμού
        CombinationsOccurences.Add(New clsNGram With {.nGramCombination = Συνδυασμοί(i), .Occurrences = 0})
		For j = ΑπόΤάδεIndexΣυνόλου To ΩςΤάδεIndexΣυνόλου
			For f As Integer = 0 To k - 1
				'Κάνε κάτι
			Next
		Next
    Next
    Return CombinationsOccurences
End Function