Καλησπέρα .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

Καλύτερα να περιγράψεις τί θέλεις να κάνεις, όχι πως προσπαθείς να το κάνεις. Αν ο αλγόριθμος έχει και όνομα, ακόμα καλύτερα. Όπως είναι τα πράγματα, κρύβεται εντελώς το τι θέλεις να κάνεις.

Όσον αφορά τα Tasks, δεν κερδίζεις πολλά φτιάχνοντας tasks με το χέρι. Δεν φτιάχτηκαν για επεξεργασία μεγάλου όγκου δεδομένων και η λάθος χρήση θα οδηγήσει σε σπατάλη μνήμης πολύ γρήγορα.
Το βασικό στην παράλληλη επεξεργασία είναι να σπάσεις τα δεδομένα σε partitions και μετά κάθε επεξεργαστής να δουλέψει όσο γρηγορότερα γίνεται με τα *δικά του* δεδομένα.
Αν χρησιμοποιήσεις άπειρα tasks, απλά θα χάνεις το χρόνο σου καθώς οι επεξεργαστές θα γυρίζουν από το ένα μικρό task στο άλλο.

Αντίθετα, αν χρησιμοποιήσεις PLINQ ή τις μεθόδους της κλάσης Parallel μπορείς να χρησιμοποιήσεις όλα τα διαθέσιμα cores για να επεξεργαστείς τα data.
Όταν καλείς ένα Parallel.ForEach ή ένα Parallel.For, το PLINQ σπάει τα δεδομένα σε τόσα partitions όσα και cores και μετά χρησιμοποιεί *ένα* task ανά επεξεργαστή για να επεξεργαστεί το κάθε partition.

 Αν τα αρχικά σου δεδομένα είναι οι συνδυασμοί ανά χ από 80 αριθμούς, προφανώς δεν μπορείς να υπολογίσεις *όλους* τους συνδυασμούς από την αρχή, ούτε χρειάζεται.
Φτιάξε ένα iterator ο οποίος θα επιστρέφει κάθε συνδυασμό. Αρκεί να φτιάξεις ένα function το οποίο θα επιστρέφει ένα IEnumerable<T> και μέσα στο function να καλείς την Yield myCombination κάθε φορά που φτιάχνεις ένα συνδυασμό.

Ένας iterator επιστρέφει αποτελέσματα μόνο όταν του τα ζητάνε παρακάτω. Το αποτέλεσμα είναι ότι αντί να υπολογιστούν μερικά εκατομμύρια συνδυασμοί από την αρχή, ένας συνδυασμός θα δημιουργείται μόνο όταν το ζητάει όποιος
έχει ξεκινήσει το iteration του IEnumerable. 

Καλύτερα να περιγράψεις τί θέλεις να κάνεις, όχι πως προσπαθείς να το κάνεις.

WOW! Εξαιρετική επίθεση από μέρους σου! Δεν καταλαβαίνω γιατί να μου φερθείς έτσι... :S

Τέτοια ειρωνεία και χλευασμός, κυριολεκτικά από την πρώτη πρόταση είναι αξιοπερίεργο, αλλά για να συνεχίσει ο διάλογος θα το κάνω disregard.

Όχι, δεν έχει κάποιο συγκεκριμένο όνομα αυτό που θέλω να κάνω.

Όχι, δεν κρύβω το τι θέλω να κάνω - προσπαθώ να εξηγήσω αναλυτικότατα τι θέλω να κάνω.. αυτό είναι και το όλο νόημα άλλωστε - να καταλάβετε τι θέλω να πετύχω ώστε να μπορέσετε να με βοηθήσετε.

Όπως εξήγησα παραπάνω, για να μην έχω κατεβατά κώδικα είπα να γράψω μόνο τα βασικά - δηλαδή το ότι θέλω να χωρίσω ένα task που βασίζεται σε ένα τεράστιο list σε κομμάτια και να γίνονται πράξεις Multithreaded και concurrently και έδωσα ένα code snippet του τι είχα κάνει και πώς το άλλαξα για να πετύχω αυτό που θέλω (και δυστυχώς δεν πέτυχα το σκοπό μου τελικά).

Αλλά όπως προανέφερα, εάν χρειάζεται να δώσω ολόκληρο τον κώδικα, ευχαρίστως να το κάνω.

Όσον αφορά τα Tasks, δεν κερδίζεις πολλά φτιάχνοντας tasks με το χέρι. Δεν φτιάχτηκαν για επεξεργασία μεγάλου όγκου δεδομένων και η λάθος χρήση θα οδηγήσει σε σπατάλη μνήμης πολύ γρήγορα.

Δεν είμαι σίγουρος τι εννοείς με το "φτιάχνοντας tasks με το χέρι". Θα μπορούσες να το εξηγήσεις και να μου δώσεις ένα παράδειγμα ως προς το που θα φαινόταν χρήσιμο?

Το βασικό στην παράλληλη επεξεργασία είναι να σπάσεις τα δεδομένα σε partitions και μετά κάθε επεξεργαστής να δουλέψει όσο γρηγορότερα γίνεται με τα *δικά του* δεδομένα.

Αν χρησιμοποιήσεις άπειρα tasks, απλά θα χάνεις το χρόνο σου καθώς οι επεξεργαστές θα γυρίζουν από το ένα μικρό task στο άλλο.

Συμφωνώ - ακριβώς αυτό προσπάθησα να κάνω (και δυστυχώς απέτυχα παταγωδώς).

Πιο συγκεκριμένα, όπως το σκεφτόμουν στο μυαλό μου, αυτό που θα έκανε αυτή ακριβώς τη λειτουργία ήταν το:

	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
 

 Εδώ νόμιζα ότι έλεγα το εξής:

Αν η λίστα που είναι να γίνουν οι υπολογισμοί περιέχει περισσότερα elements απ'ότι το πλήθος των thread μας,. τότε κάνε το εξής:

Στον πρώτο επεξεργαστή δώσε να κάνει πράξεις από το πρώτο element της λίστας μέχρι και το ΠλήθοςΛίστας/ΠλήθοςThread

Στον δεύτερο επεξεργαστή δώσε να κάνει πράξεις από το element που είχε ο πρώτος + 1, μέχρι 2*ΠλήθοςΛίστας/ΠλήθοςThread

Στον τρίτο από το element που είχε να κάνει πράξεις ο δεύτερος + 1 μέχρι 3*ΠλήθοςΛίστας/ΠλήθοςThread

......

Στον τελευταίο δώσε από το element που είχε να κάνει πράξεις ο προηγούμενος μέχρι και το τέλος

Και στο μυαλό μου, καλώντας μετά το "Await Task.WhenAll(CountSwarmsTasks)" θα τα έκανε παράλληλα και θα γυρνούσαν με τη σειρά που τα έβαλα (διότι και αυτό παίζει ρόλο - πρέπει τα permutations να είναι με τη σωστή σειρά)

Τα γυρνάει με τη σωστή σειρά, αλλά δεν γίνονται σε multithreaded manner.

Αντίθετα, αν χρησιμοποιήσεις PLINQ ή τις μεθόδους της κλάσης Parallel μπορείς να χρησιμοποιήσεις όλα τα διαθέσιμα cores για να επεξεργαστείς τα data.

Όταν καλείς ένα Parallel.ForEach ή ένα Parallel.For, το PLINQ σπάει τα δεδομένα σε τόσα partitions όσα και cores και μετά χρησιμοποιεί *ένα* task ανά επεξεργαστή για να επεξεργαστεί το κάθε partition.

Αυτό μάλλον ακούγεται σαν αυτό που θέλω να κάνω - θα το ψάξω. Δεν ήξερα ότι υπάρχει "Parallel." πράγμα. Πολύ ενδιαφέρον!

Αν τα αρχικά σου δεδομένα είναι οι συνδυασμοί ανά χ από 80 αριθμούς, προφανώς δεν μπορείς να υπολογίσεις *όλους* τους συνδυασμούς από την αρχή, ούτε χρειάζεται. 

Φτιάξε ένα iterator ο οποίος θα επιστρέφει κάθε συνδυασμό. Αρκεί να φτιάξεις ένα function το οποίο θα επιστρέφει ένα IEnumerable<T> και μέσα στο function να καλείς την Yield myCombination κάθε φορά που φτιάχνεις ένα συνδυασμό.

Εδώ αποβιβάστηκα από το τρένο της σκέψης σου και πάλι... Δεν είμαι σίγουρος τι εννοείς.

Πάντως σίγουρα πρέπει να υπολογιστούν *όλοι* οι συνδυασμοί γιατί πρέπει να βρούμε πόσες φορές έχει τύχει/συμβεί ο καθένας

Με το IEnumerable<T> εννοείς να αλλάξω το "Dim ListOfEikosades As New List(Of clsEikosada)" (που αναφέρω παρακάτω και έχω στο αρχείο του project) σε "Dim ListOfEikosades As New IEnumerable(Of clsEikosada)" ??

Ένας iterator επιστρέφει αποτελέσματα μόνο όταν του τα ζητάνε παρακάτω. Το αποτέλεσμα είναι ότι αντί να υπολογιστούν μερικά εκατομμύρια συνδυασμοί από την αρχή, ένας συνδυασμός θα δημιουργείται μόνο όταν το ζητάει όποιος
έχει ξεκινήσει το iteration του IEnumerable.

Δυστυχώς δεν είμαι σίγουρος ότι σε καταλαβαίνω - Θα μπορούσες να κάνεις ένα code snipper με μια αντιπαράθεση του *λάθος τρόπου* και πώς αυτό γίνεται καλύτερο με αυτό που προτείνεις?

Νομίζω θα με βοηθούσε πολύ να αντιληφθώ το νόημα.

Ευχαριστώ πολύ για τη βοήθεια και τα tips 

Ο πηγαίος κώδικας (με ολόκληρο το φάκελο του Project) βρίσκεται σε αυτό το συμπιεσμένο αρχείο:  https://dl.dropboxusercontent.com/u/18135227/TempLinks/WindowsApplication1.zip

        Dim k As Integer = CInt(nudFindNGrams.Value)
        Dim sbKinoCombinations As New StringBuilder
        Try
            btnFindNGrams.Enabled = False
            Dim Combinations As New List(Of List(Of Integer))
            Dim CombinationsFrequencyIndexes As New List(Of clsNGram)
            Dim KinoNumbers As New List(Of Integer)
            For i = 1 To nOfNumbers
                KinoNumbers.Add(i)
            Next
            Await Task.Run(
                Async Function()
                    Combinations = nChooseK(KinoNumbers, k)
                    Dim CountOccurrencesTasksQuery As New List(Of Task(Of List(Of clsNGram)))
                    If Combinations.Count > CoresCount Then
                        Dim intCombinationsPerIteration As Integer = CInt(Math.Floor(Combinations.Count / CoresCount))
                        For i As Integer = 1 To CoresCount
                            If i = 1 Then
                                CountOccurrencesTasksQuery.Add(CalcCombinations(0, intCombinationsPerIteration, k, Combinations))
                            ElseIf i < CoresCount Then
                                CountOccurrencesTasksQuery.Add(CalcCombinations((intCombinationsPerIteration * i) - intCombinationsPerIteration + 1, intCombinationsPerIteration * i, k, Combinations))
                            Else
                                CountOccurrencesTasksQuery.Add(CalcCombinations((intCombinationsPerIteration * i) - intCombinationsPerIteration + 1, Combinations.Count - 1, k, Combinations))
                            End If
                        Next
                    Else
                        CountOccurrencesTasksQuery.Add(CalcCombinations(0, Combinations.Count - 1, k, Combinations))
                    End If
                    Dim CountOccurrencesTasks As Task(Of List(Of clsNGram))() = CountOccurrencesTasksQuery.ToArray
                    Dim CountOccurrencesLstClsNGram() As List(Of clsNGram) = Await Task.WhenAll(CountOccurrencesTasks)
                    For Each item In CountOccurrencesLstClsNGram
                        CombinationsFrequencyIndexes.AddRange(item)
                    Next
                    If chkSaveNGramsToFile.Checked Then
                        sbKinoCombinations.AppendLine("Eikosades: " & (ListOfEikosades.Count.ToString("n0")))
                        sbKinoCombinations.AppendLine(k.ToString & "-grams") 'k-grams
                        sbKinoCombinations.AppendLine("--------------------------------")
                        For i = 0 To Combinations.Count - 1
                            sbKinoCombinations.AppendLine(ArrayBox(doNumeriseItems:=False, DelimitationStr:="-", SplitOnNum:=0, IgnoreNullValues:=True, listTVar:=Combinations(i), IgnoreDelimitSpace:=True) & ": " & CombinationsFrequencyIndexes(i).Occurrences)
                        Next
                    End If
                    Dim tmp = CombinationsFrequencyIndexes.OrderByDescending(Function(clsNGram) clsNGram.Occurrences)
                    GroupedNGramResults = tmp.GroupBy(Function(clsNGram) clsNGram.Occurrences)
                    lstStrGroupedNGramResults.Clear()
                    For Each item In GroupedNGramResults
                        lstStrGroupedNGramResults.Add(item.Key.ToString("n0") & " times (" & item.Count.ToString("n0") & " " & k.ToString & "-grams)") 'n times (k-grams)
                    Next
                End Function)
            If chkSaveNGramsToFile.Checked Then
                Dim FilePath As String = strDesktop & Now.ToLocalTime.ToString.Replace("/", "-").Replace(":", "_") & ".txt"
                WriteText(FilePath, sbKinoCombinations.ToString, Encoding.UTF8)
                exeProcesses.StartInfo.FileName = FilePath
                exeProcesses.StartInfo.Arguments = ""
                exeProcesses.Start()
            End If
            Dim NGramResultsForm As New frmNGramResultsList
            NGramResultsForm.k = k
            NGramResultsForm.EikosadesCount = ListOfEikosades.Count
            NGramResultsForm.lstNGramsText = lstStrGroupedNGramResults.ToArray
            NGramResultsForm.GroupedNGramResults = GroupedNGramResults.ToList
            NGramResultsForm.Show() 

Πρέπει να διευκρινισεις τι πράξη θα κάνεις με τον κάθε συνδυασμό του ΚΙΝΟ :) .Ισως γινεται πιο συγκεντρωτικα, χωρις να τους αναπαραγάγεις ολους.

Φαίνεται στον κώδικα στο αρχείο - Μετράω το πόσες φορές έχει συμβεί η κάθε ν-αδα μέσα από ένα σύνολο από εικοσάδες.

Αλλά αυτό δεν παίζει ρόλο - ό,τι πράξη και να έκανα, η ερώτηση στην οποία θέλω απάντηση είναι πώς μπορώ να το χωρίσω σε κομμάτια που να γίνονται multi-threaded και concurrently και να ενώνονται με τη σωστή σειρά στο τέλος.

Αν βρεθεί η λύση για αυτό, μετά  θα το χρησιμοποιήσω για 1002 άλλα πράγματα. Το ότι γράφω τη συγκεκριμένη πράξη δεν σημαίνει ότι θα το χρησιμοποιήσω μόνο εκεί... απλώς βλέποντας πως δουλεύει εκεί θα μπορώ να το προσαρμόσω και σε άλλα πράγματα που θέλω.

Το θέμα είναι, πώς το κάνουμε αυτό? 

Δηλαδή αν το array σου εχει π.χ. τους  αριθμους [1,2,3,...20] εσυ θα παραξεις όλες τις v-αδες του συνολου [1,2,..80] για να μετρήσεις πόσες εμπεριέχονται στο array;

Αυτο υπολογίζεται με μολυβι.

Κολλάμε αρκετά στο που πάω να το χρησιμοποιήσω αυτή τη στιγμή.
Ένα άλλο που θέλω να κάνω πάλι Multithreaded + Concurrently είναι να διαβάζει πολλαπλά αρχεία και να να φορτώνει τα περιεχόμενα αυτών σε λίστα κλάσεων. Αντί να τα διαβάζει 1-1 και να χρησιμοποιεί το 12.5% της CPU, ας τα διαβάζει 8-8 να χρησιμοποιεί το 100%. Δεν έχει νόημα να γράψω ένα-ένα όλα όσα θέλω να γίνονται έτσι. Μόλις δω πώς γίνεται ένα, θα καταλάβω πώς να κάνω διάφορα άλλα με αυτόν τον τρόπο μόνος μου.

Αφού το πιάσαμε που το πιάσαμε τόσο συγκεκριμένα συγκεκριμένα αυτό με τις εικοσάδες, ας περιγράψω με λόγια τι ακριβώς κάνω:

Έχω ένα σύνολο από εικοσάδες - ας πούμε 2 εικοσάδες:

1 3 5 7 10 11 12 13 14 15 16 17 18 20 30 40 50 60 70 80

1 2 3 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 78 80

Θεωρούμε ότι θέλουμε να υπολογίσουμε τις 2-άδες

Έχουμε 1-2, 1-3, 1-4, 1-5, 1-6, 1-7, ..... 79-80 (όλες οι 2-άδες)

Το αποτέλεσμα που θέλω είναι:

η 2-άδα "1-2" έχει συμβεί 1 φορά στο σύνολο (στην πρώτη εικοσάδα)

η 2-άδα "1-3" έχει συμβεί 2 φορές στο σύνολο (και στην πρώτη και στην δεύτερη εικοσάδα)

η 2-άδα "1-4" έχει συμ........

η 2-άδα "79-80" έχει συμβεί 0 φορές στο σύνολο (ούτε στην πρώτη ούτε στην δεύτερη εικοσάδα)

Για να πάρω αυτή την πληροφορία πρέπει να βγουν όλα τα combinations και για την κάθε γραμμή του συνόλου δεδομένων να σαρωθούν όλα τα combinations. 

Εκτός κι αν εγώ σκέφτομαι κάτι λάθος, νομίζω μπορούμε να σταματήσουμε να διαφωνούμε στο premise και να δούμε πως θα μπορούσε να γίνει αυτό.

Αυτό που είχα σκεφτεί και έκανα στον κώδικα εγώ είναι να βάλω 2 Integers "Από" και "Μέχρι" στην συνάρτηση έτσι ώστε να μπορεί να σπάσει σε κομμάτια.

Οπότε κοιτάω πόσους πυρήνες (threads ουσιαστικά) έχει ο υπολογιστής?

8

Άρα λέω, θα κάνω 8 διαφορετικά tasks που με το "Από" και "Μέχρι" θα παίρνουν για ανάλυση το καθένα το 1/8 των combinations και στο τέλος θα γίνει RowBind (αφού είναι λίστα, ουσιαστικά απλώς θα προστεθούν τα αποτελέσματα του 2ου task κάτω από του 1ου, του 3ου κάτω από του 2ου κ.ο.κ.).

Αυτό που σκέφτηκα έτσι όπως το υλοποίησα δεν πέτυχε. Δυστυχώς απέτυχα παταγωδώς σε αυτό που ήθελα να κάνω.

Μήπως έχεις καμία ιδέα πώς θα μπορούσε να γίνει?

Υπενθυμίζω - Αυτό που θέλω είναι μία λογική, ένα πλαίσιο, μία ιδέα του πώς μπορούμε να πάρουμε ένα task και να το χωρίσουμε σε κομμάτια, μιλώντας για πράξεις που γίνονται σε μία λίστα (List (Of Κάτι))

Αν τυχαίνει να μπορεί να το σκεφτεί κάποιος πάνω στον δικό μου κώδικα, ακόμα καλύτερα - το παίρνω όπως είναι.

Αλλά και η γενική ιδέα του πώς μπορεί να γίνει κάτι τέτοιο θα βοηθούσε - και την προσαρμόζω μετά. 

Συνήθως σε τέτοια προβλήματα η λύση(εαν υπάρχει) δεν είναι συνήθως να πας με την πεπατημένη...δηλαδή Loop μεσα σε Loop μέσα σε Loop....και πάει λέγοντας...

Υποθέτω ότι θέλεις να κάνεις κάποια στατιστική κατανομή ώστε να παράγεις τους 20 πιο πιθανούς αριθμούς να εμφανιστούν με βάση τη συχνότητα εμφάνισης αλλά πέρα απο την συχνότητα εμφάνισης είναι και άλλοι παράγοντες που θα μπορούσαν να επηρεάσουν...(π.χ εμφανίστηκαν στις τελευταίες 20 κληρώσεις...πόσες μέρες απο την τελευταία εμφάνιση και πάει και λέγοντας)

Εν πρώτοις θα φόρτωνα όλα τα δεδομένα σε 1 SQL server και πιθανόν επειδή θα χρειαστείς αναδρομή να χρησιμοποιήσεις Ms SQL server Λόγω CTE...

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

Kathe 20-ada exei sxetika liges 12-ades (125970) h alles n-ades.  Ara apo tis 10^13 12-ades tou 80 mono liges tha periexontai stis 20-des. Oi pio polles tha exoun sumbei 0 fores sto synolo (an mporeis na tis agnoiseis). 

Sorry gia ta greeklish.

tsgiannis:

Συνήθως σε τέτοια προβλήματα η λύση(εαν υπάρχει) δεν είναι συνήθως να πας με την πεπατημένη...δηλαδή Loop μεσα σε Loop μέσα σε Loop....και πάει λέγοντας...

Υποθέτω ότι θέλεις να κάνεις κάποια στατιστική κατανομή ώστε να παράγεις τους 20 πιο πιθανούς αριθμούς να εμφανιστούν με βάση τη συχνότητα εμφάνισης αλλά πέρα απο την συχνότητα εμφάνισης είναι και άλλοι παράγοντες που θα μπορούσαν να επηρεάσουν...(π.χ εμφανίστηκαν στις τελευταίες 20 κληρώσεις...πόσες μέρες απο την τελευταία εμφάνιση και πάει και λέγοντας)

Εν πρώτοις θα φόρτωνα όλα τα δεδομένα σε 1 SQL server και πιθανόν επειδή θα χρειαστείς αναδρομή να χρησιμοποιήσεις Ms SQL server Λόγω CTE...

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

Όχι - αλήθεια δεν το πάω πουθενά παραπέρα. Ο τελικός σκοπός μου είναι απλώς και μόνο να να έχω έναν-έναν τους συνδυασμούς και δίπλα τις πόσες φορές έχουν τύχει

και μετά από αυτόν τον τεράστιο κατάλογο κάνω aggregate και βγάζω σε μία φόρμα με DESC σειρά τα occurrences:

"5 φορές έτυχαν 32 4-άδες"

"4 φορές έτυχαν 56 4-άδες"

"1 φορά έτυχαν 28 4-άδες"

"0 φορές έτυχαν 1700 4-άδες"

που όταν πατάω στο κάθε item του listbox θα μου δείχνει αυτές τις 32 4-άδες, 56 4-άδες, 28 4-άδες ή 1700 4-άδες

[Τα νούμερα είναι εντελώς τυχαία και δεν προσθέτονται σε ένα λογικό νούμερο] 

[P.S. Ωστόσο, ΠΡΕΠΕΙ επειγόντως να περάσω σε SQL απλώς αυτός ο χρόνος είναι πάντα πολύ μεγάλο πρόβλημα... Το πρόγραμμα το έκανα όταν ήμουν έφηβος, οπότε έχει ότι να'ναι κώδικα, αλλά τρέχω σαν τρελός με το μεταπτυχιακό και όλα - με έχουν τεντώσει τα τελευταία 5 χρόνια οπότε με τι να πρωτο-ασχοληθώ?]

nikos123:

 

Kathe 20-ada exei sxetika liges 12-ades (125970) h alles n-ades.  Ara apo tis 10^13 12-ades tou 80 mono liges tha periexontai stis 20-des. Oi pio polles tha exoun sumbei 0 fores sto synolo (an mporeis na tis agnoiseis). 

Sorry gia ta greeklish. 

Ναι, σίγουρα θα είναι πολύ περισσότερα τα μηδενικά - το θέμα είναι ότι θέλουμε να εμφανίζονται και τα μηδενικά.

[P.S. Προσωπικά δεν με ενοχλούν καθόλου τα greeklish. Το ανθρώπινο μυαλό είναι equipped να καταλαβαίνει το ίδιο εύκολα όπως και να τα γράψεις. Εξού και τα τόσα posts "Αν μπορείς να διαβάσεις αυτό είσαι awesome" - γραμμένα πάντα σε εξαιρετικά περίεργες γραμματοσειρές, όπως αυτή με τα Unknowns από τα Pokemon. That said, αυτή είναι η προσωπική μου άποψη και δεν αντικατοπτρίζει την άποψη του forum as a whole.] 

Λογικά η λύση είναι αυτό που ανέφερε ο Παναγιώτης Καναβός απλώς δεν είχα χρόνο μέχρι στιγμής να το ψάξω

Μέχρι το βράδυ φαντάζομαι ότι θα το έχω δοκιμάσει και θα απαντήσω αν ήταν η λύση ή όχι. 

Pantos an ginontai 1000 kloiroseis tin imera kai kathe fora diafoterikos syndyasmos se 100 xronia tha exoume 1000*365*100=36500000 syndyasmous apo tous 10^13 pithanous !!!.

To ena ekatomiriosto dld.

Epoisis otan parageis syndyasmous den xreiazetai na einai apothikeymenoi oloi. Mia GetNextCombination(previous) arkei.

 An sou elega kane tin tade praxi me tous zygous arithmous 1 eos 10000000000 tha xreiazosoun pinaka 10000000000/2 na tous apothikeyseis prota?!!

AlKiS:

tsgiannis:

Συνήθως σε τέτοια προβλήματα η λύση(εαν υπάρχει) δεν είναι συνήθως να πας με την πεπατημένη...δηλαδή Loop μεσα σε Loop μέσα σε Loop....και πάει λέγοντας...

 

Όχι - αλήθεια δεν το πάω πουθενά παραπέρα. Ο τελικός σκοπός μου είναι απλώς και μόνο να να έχω έναν-έναν τους συνδυασμούς και δίπλα τις πόσες φορές έχουν τύχει

Να σου πω την αλήθεια δεν πρόλαβα να δω ακριβώς τον συλλογισμό σου αλλά ισως πρέπει να το δεις και απο άλλη οπτική γωνία....τις προάλλες έλυσα 1 challenge CodeEval μόνο με παρατήρηση...Πες οτι δεν έχεις Η/Υ....και πάρε χαρτί και μολύβι...

Αυτό που ζητούσα φαίνεται πράγματι να το πετυχαίνει το PLINQ και το Parallel.ForEach που είπες.

Δυστυχώς όμως, επειδή στην loop δεν γίνονται πράξεις αλλά το μόνο που γίνεται είναι να μετράει το πόσες φορές έτυχε ο κάθε συνδυασμός ανανεώνοντας το element της μεταβλητής που κρατάει τα occurrences, αυτού του είδος ο παραλληλισμός δεν μου χρησιμεύει λόγω του Lock/SyncLock που πρέπει να γίνει στη μεταβλητή για να μην ενημερώνουν ταυτόχρονα όλα τα Threads και χαθούν εγγραφές.

Με άλλα λόγια, επειδή το μόνο που γίνεται στη loop είναι ανανέωση της μεταβλητής και όλα τα threads παν να κάνουν αυτό αλλά κάθε φορά πρέπει να κλειδώνει η μεταβλητή για να παραμείνουν σωστά τα δεδομένα, χάνεται το νόημα του παραλληλισμού λόγω SyncLock και πάει το ίδιο αργά όσο και το Single Thread (για την ακρίβεια λίγο πιο αργά - φαντάζομαι επειδή περιμένουν τα threads να ξεκλειδώσει η μεταβλητή).

Το καλό είναι ότι κάθισα και παιδεύτηκα με την Parallel και είδα διάφορα πράγματα για παραλληλισμό, κάτι με το οποίο δεν είχα ξανασχοληθεί

Για το συγκεκριμένο πράγμα δεν νομίζω ότι υπάρχει τρόπος να γίνεται πιο γρήγορα παράλληλα, οπότε θεωρώ το thread απαντημένο (δεδομένου ότι η απάντηση ήταν πράγματι έγκυρη).

Θα δημιουργήσω ένα νέο thread για ένα νέο πρόβλημα που έχω για execution παράλληλων διαφορετικών tasks σε αντίθεση με το 1 task με παραλληλισμό που ήθελα εδώ.

Σας ευχαριστώ πολύ όλους για τη βοήθεια

Όλοι με βάλατε να σκεφτώ κάτι νέο, να ψάξω πληροφορίες και να μάθω κάτι καινούργιο και είμαι ευγνώμων γι'αυτό. 

Wow!!

Το να πω ότι είναι πλήρης η απάντηση είναι understatement - το εκτιμώ πραγματικά.

Ευχαριστώ πάρα πολύ! 

Θα καθίσω να παίξω με τον κώδικα.

Έχω ήδη SQL Server + SQL Server Management Studio λόγω μηχανικής μάθησης και big data analysis

Σε περίπτωση που θέλει κάποιος να πετύχει το ίδιο που ήθελα κι εγώ (να σπάσει 1 task σε κομμάτια και να γίνει σε multi-threaded και concurrent manner, παραθέτω τον κώδικά μου παρακάτω)

Imports System.IO

Public Structure MyStructure
    Dim DateAndTime As Date
    Dim Numbers() As Integer
    Public Overrides Function ToString() As String
        Return DateAndTime.ToString("dd/MM/yyyy HH:mm") & " " & Numbers(0).ToString & " " & Numbers(1).ToString & " " & Numbers(2).ToString
    End Function
End Structure
Public Class Form1
    Dim MyDesign As New List(Of MyStructure)
    Dim strMyDesign As New List(Of String)

    Public Async Function LoadMyDesign(ByVal FromLineIndex As Integer, ByVal ToLineIndex As Integer, ByVal FilePaths() As String) As Task(Of List(Of MyStructure))
        Dim CurMyDesign As New List(Of MyStructure)

        Await Task.Run(
            Sub()
                For j As Integer = FromLineIndex To ToLineIndex
                    Dim FileLines() As String = File.ReadAllLines(FilePaths(j))

                    For i = 0 To FileLines.Length - 1
                        Dim LineContent() As String = FileLines(i).Split(","c)
                        Dim NewDesign As New MyStructure With {.DateAndTime = Date.Parse(LineContent(0)), .Numbers = (From Num In LineContent Skip 1 Select CInt(Num)).ToArray}

                        CurMyDesign.Add(NewDesign)
                    Next
                Next
            End Sub)

        Return CurMyDesign
    End Function

    Private Async Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        Dim DesignsQuery As New List(Of Task(Of List(Of MyStructure)))
        Dim FilesPaths() As String = Directory.GetFiles(My.Application.Info.DirectoryPath & "\Files\")
        Dim IndicesPerIteration As Integer = CInt(Math.Floor(FilesPaths.Length / Environment.ProcessorCount))

        MyDesign.Clear()
        strMyDesign.Clear()
        Button1.Enabled = False

        If FilesPaths.Length >= Environment.ProcessorCount AndAlso Environment.ProcessorCount >= 2 Then
            For i = 1 To Environment.ProcessorCount
                Dim CurIteration As Integer = i
                If CurIteration = 1 Then
                    DesignsQuery.Add(LoadMyDesign(0, IndicesPerIteration - 1, FilesPaths))
                ElseIf CurIteration < Environment.ProcessorCount Then
                    DesignsQuery.Add(LoadMyDesign(((IndicesPerIteration) * (CurIteration - 1)), ((IndicesPerIteration) * CurIteration) - 1, FilesPaths))
                Else
                    DesignsQuery.Add(LoadMyDesign(((IndicesPerIteration) * (CurIteration - 1)), FilesPaths.Length - 1, FilesPaths))
                End If
            Next

            Dim sth As List(Of MyStructure)() = Await Task.WhenAll(DesignsQuery)
            For Each Item As List(Of MyStructure) In sth
                MyDesign.AddRange(Item)
            Next

        Else
            MyDesign = Await LoadMyDesign(0, FilesPaths.Length - 1, FilesPaths)
        End If

        strMyDesign.AddRange((From l As MyStructure In MyDesign Select (l.ToString())).Take(10))

        ListBox1.DataSource = Nothing
        ListBox1.DataSource = strMyDesign
        Button1.Enabled = True
    End Sub

 Για να δουλέψει θέλει αρχεία (ανεξαρτήτως ονόματος) στη διεύθυνση που δείχνει το "FilesPaths" τα οποία θα περιέχουν σειρές τύπου:

28/8/2016 18:00, 1, 2, 3
28/8/2016 18:01, 4, 5, 6
28/8/2016 18:02, 7, 8, 9
28/8/2016 18:03, 10, 11, 12
28/8/2016 18:04, 1, 2, 3
28/8/2016 18:05, 4, 5, 6
28/8/2016 18:06, 7, 8, 9
28/8/2016 18:07, 10, 11,12
28/8/2016 18:08, 1, 2, 3
28/8/2016 18:09, 4, 5, 6
28/8/2016 18:10, 7, 8, 9
28/8/2016 18:11, 10, 11, 12
28/8/2016 18:12, 1, 2, 3
28/8/2016 18:13, 4, 5, 6
28/8/2016 18:14, 7, 8, 9
28/8/2016 18:15, 10, 11, 12
 

 (μπορεί να γίνει copy/paste)