albNik

Δεν το υλοποιησες με στοίβα, ούτε στο geeksforgeeks. search: reverse a string using stack in Java

Εγω παίρνω hello, world! αποτέλεσμα οταν το αντιγραφω στο chrome console. Ποιο είναι το (παραξενο) αποτέλεσμα που σου εβγαλε εσενα?

Αν χρειαστείς περαιτέρω size/speed το παρακάτω είναι 10-12 sec χωρίς Parallel.For. Xρησιμοποιώ το wordIndicesMap που πόσταρα σε προηγούμενο μήνυμα οπου τροποποίησα λίγο το loop για να φιλτράρω πεντάδες. foreach(var sentence in list140_20) { var commonIndices = new List<int>(); foreach(var word in sentence) { if(wordIndicesMap.ContainsKey(word)) commonIndices.AddRange(wordIndicesMap[word]); } var commonFive = commonIndices.GroupBy(x => x).Where(x => x.Count() >= 5).Select(x => x.Key).ToList(); foreach(var ind in commonFive) { //sentence has 5 common words with list340000_20[ind] } }

Χρειαζεται μεσα στο nested loop, πρεπει να δημιουργείς καινούριο πριν απο καθε IntersectWith, διαφορετικά αδειάζει και το tmpHashSet. var tmpHashSet = new HashSet<string>(sourceWordsList);

Βασικα εχω ενα bug. Δεν ειναι θεμα ελληνικά/αγγλικά, τα string είναι unicode. H sourceWords.IntersectWith(targetWords); μεταβάλει την sourceWords (αφαιρει οσα δεν ειναι κοινα) και γινεται ολο και μικρότερη μεχρι που αδειαζει και δεν εχει κοινο τιποτα. Φτιάξε μια sourceWordsCopy και κανε σε αυτην InterSectWith. Ο χρόνος θα ειναι μεγαλύτερος τωρα. var sourceWordsCopy=new HashSet(sourceWords); sourceWordsCopy.IntersectWith(targetWords); if (sourceWordsCopy.Count > 5) { // });

Mια τελευταία προσπάθεια. Εχεις μια λιστα απο 140 HashSet<string> των 20 και μια με 340000 List<string> των 20. H HashSet.IntersectsWith() είναι optimized να βρίσκει τα κοινά στοιχεία πολύ γρήγορα (2 εικοσάδες είναι τίποτα). Θα κάνεις 140*340000= 47εκ ελέγχους αντί για 19 δισ. Έβαλα random words και το παρακάτω τρέχει σε 1.4 sec στο pc μου συμπεριλαμβάνοντας το χρόνο για να κατασκευάσω τις 2 λιστες. Το τελευταίο double loop που είναι ο έλεγχος για 5 κοινά κάνει μόνο 0.18 sec. var list_140 = new List<HashSet<string>>(); var list_340k = new List<List<string>>(); Random r = new Random(); for(int i = 0; i < 340000; i++) { var list = new List<string>(); for(int j = 0; j < 20; j++) { list.Add(r.Next(1, 1000).ToString()); } list_340k.Add(list); } for(int i = 0; i < 140; i++) { var list = new List<string>(); for(int j = 0; j < 20; j++) { list.Add(r.Next(1, 1000).ToString()); } list_140.Add(list.ToHashSet()); } foreach(var hash in list_140) foreach(var sentence in list_340k) { hash.IntersectWith(sentence); if(hash.Count >= 5) { Console.WriteLine("found 5"); // found 5 commons } }

Για λίγες λέξεις (20 στην περίπτωση σου) δεν βλέπεις τεράστια διαφορά στην linear αναζήτηση σε List vs Dictionary lookup εξ ου και το μικρο 40%. Εξακολουθώ να πιστευω οτι υπαρχει αλγόριθμος <1 sec ακόμα και με αυτόν τον περιορισμό χωρίς να ξοδεύεις σε harware. Γενικά μιλώντας δεν χρειάζεσαι μνήμη αφού τα δεδομένα σου είναι κατι δεκάδες MB. Αυτο που ίσως θα βοηθούσε είναι cpu με μεγαλύτερη cache. Η cache είναι σε επίπεδα L1-L2-L3. H L1 είναι εως και 100 φορες ταχυτερη απο τη RAM, L2 πιο αργη από L1, L3 πιο αργή από L2. Οταν ο cpu χρειάζεται π.χ. μια value κοιτάει πρώτα στις cache, αν υπάρχουν είναι cache-hit αλλιώς cache-miss και θα περιμένει (delay for hundreds of cpu cycles) να έρθουν από την (αργη) RAM. Οσο μεγαλύτερη η cache, ειδικά η L1 που είναι πανάκριβη τόσο καλυτέρα. Στην C# τα collections List, Array, Dictionary etc είναι cache-friendly , δλδ αν το list[5] είναι στην cache τότε υπάρχει μεγάλη πιθανότητα και οι επόμενες τιμές list[6], list[7]… να είναι εκεί.

Δοκιμασε αυτο βαζοντας τα data σου στις list140_20 και list340000_20. Η κατασκευή του wordIndicesMap δεν πρέπει να παρει πανω απο 1 sec ακομα και αν ολες οι 340000*20 λεξεις ειναι διαφορετικες. Στο τελευταίο double loop έχεις να κάνεις 2800 dictionary lookups (λιγότερο από millisecond) αντί για 19 δις comparisons var list140_20 = new List<List<string>>() { new List<string>() { "x", "y", "z" }, new List<string>() { "x1", "y1", "z1" }, }; var list340000_20 = new List<List<string>>() { new List<string>() { "a", "b", "c" }, new List<string>() { "a", "b", "d" }, new List<string>() { "a" } }; var wordIndicesMap = new Dictionary<string, List<int>>(); // a:{0,1,2} | b:{0,1} | c:{0} | d:{1} for(int i = 0; i < list340000_20.Count; i++) foreach(var word in list340000_20[i]) { if(wordIndicesMap.ContainsKey(word)) wordIndicesMap[word].Add(i); else wordIndicesMap[word] = new List<int> { i }; } foreach(var sentence in list140_20) foreach(var word in sentence) { if(wordIndicesMap.ContainsKey(word)) { var indices = wordIndicesMap[word]; //word found in these 'rows' of 340000 x 20 'table' } }

Ενα παρόμοιο παραδειγμα Αν ειχες 2 λιστες απο 1.000.000 λεξεις για να βρεις τις κοινές θα ήθελες 1 τρις συγκρίσεις, δλδ αρκετά λεπτά: O(1000000*1000000) foreach(var word1 in list1) foreach (var word2 in list2) { if(word1==word2) .... } Αν οι λίστες ηταν sorted τοτε με List.BinarySearch θα ηταν πολύ πιο γρήγορο: Ο(log(1000000)*1000000) foreach(var word1 in list1) foreach (var word2 in sortedList2) { if(sortedList2.BinarySearch(word1)>=0) .... } Με 1 dictionary και μια λίστα αυτό βγαίνει σε <1 sec: O(1000000) foreach(var word in list) { if(dict.ContainsKey(word) .... } Για το πρόβλημα σου θα μπορουσες να εχεις List<Dictionary>> ... Δεν ξερω τι εννοεις "χανει χρονο " και "απωλεια" αλλα η dictionary.ContainKey είναι πολύ!!! πιο γρήγορη απο list.Contains

Παντως εχεις πολυ χώρο για βελτίωση αλγοριθμικά. Π.χ. θα μπορούσες να συγκρίνεις τα hash των strings και να τα συνέχισες μονο αν τα hash ειναι ιδια. Επίσης αν τα hash ειναι sorted γλυτώνεις πολλες συγκρισεις. Ειμαι σίγουρος οτι το brute-force νούμερο (20*20*140*340000= 19 δις) μπορει να μειωθεί δραστικά. Δες και τις δομές HashSet και Dictionary με αναζήτηση σε Ο(1) αντι για List O(n).

Δεν ειναι πάντα θεμα ταιριασματος. Πολλές ομάδες είναι μη-αποδοτικές, τα bugs δεν τελειώνουν, τα deadlines δεν τηρούνται, τα projects δεν ολοκληρώνονται. Η διοικηση με ψευτουπολογισμους (του στυλ 5 developers βγάζουν δουλειά x5 ή 5 φορες γρηγορότερα) αποφασίζει ότι χρειάζονται επιπλέον προγραμματιστες...

Παραθετω αυτη την απάντηση με την οποια συμφωνώ. https://news.ycombinator.com/item?id=25414534 Σχετικα με το παρακατω θεμα https://www.quantcast.com/blog/death-by-1000-layers-the-perils-of-over-abstraction-in-java/

Γενικα εγω τα παω καλα με σύντομες τεχνικες ερωτήσεις και μικρές ασκησουλες. Η συζήτηση προχωράει γρήγορα και ολοι ειναι happy. Μετα σου βαζουν ενα design problem. Π.χ να δεις κωδικα (5-6 αρχεια) ή να σχεδιασεις ενα μικρο προγραμματακι μονο UML. Εδω αρχίζουν τα δυσκολα, η αποψη μου δεν συμφωνεί σχεδόν ποτε με τη δική τους. Προτιμώ ελάχιστες κλάσεις, χωρίς περιττα abstractions, οχι unit tests, θελω η μεθοδος να κανει κατι μονη της, οχι μικρες που καλουν αλλες μικρες ... και καμια δεν κανει κατι απο μονη της. Συνηθως διαφωνούμε και ξερω απο μονος οτι αποριφθηκα.

https://gir.st/blog/greenpass.html

Οι managed γλωσσες Java, C#... εχουν εξελιχθεί αρκετα στο code optimisation και ειδικά στην διαχείριση μνήμης. To εκτελέσιμο τους ξεπερνάει ανετα σε ταχύτητα τα αντίστοιχα των c/c++. Ο GC είναι ουσιαστικά ενας perfomance booster.