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.

Αυτό που βλέπεις υποτίθεται ότι είναι το hashcode του object, όχι διευθυνση μνήμης. Επίσης o JVM ειναι έξυπνος ώστε να μην αποθηκεύει καν το ενα object που δεν χρησιμοποίησες ποτέ. Εκτυπωσε τα S1, S2 πριν και μετα το S2=S1 public class HelloWorld{ public static void main(String []args){ T a=new T(); T b=new T(); // System.out.println(a); // System.out.println(b); a=b; System.out.println(a); System.out.println(b); } } class T{} Δες τη διαφορα αν κανεις uncomment τις δυο γραμμές.

Ευκολο ειναι, θα στρογγυλοποιήσεις το x σε ακεραιο. (5330+10x)/(650+x)=8.7

Tα references δειχνουν σε θεσεις μνημης οπως και οι pointers, απλα ειναι πιο βελτιωμένα. Εχουν εκτός apo την διεύθυνση του object καποια επιπλέον metadata οπως τον τυπο της κλασσης π.χ. αν ειναι πινακας τοτε εχει και το Length του. Δεν μπορει το reference ενός Dataset object να δειχνει αργοτερα στο BankAccount. Ειναι πιο ασφαλή επίσης επειδή δεν επιτρέπονται low level arithmetic tricks με τις διευθύνσεις τους.

Το αντικείμενο καταλαμβάνει χωρο μονο για τα πεδία. Οι μέθοδοι 'ανήκουν' στην κλαση. Οταν καλεις μια μεθοδο απο την main τότε οι primitive (int, boolean, float..) τοπικές μεταβλητές και παράμετροι αποθηκεύονται στην stack memory (LIFO) η οποια καθαρίζει μόλις τελειωσει η μέθοδος (οπως στην C). Αν μεσα στη μεθοδο δημιουργείς αντικείμενα τοτε αυτα τα καθαρίζει ο GC όταν δεν υπάρχουν references προς αυτά (Στην C πρέπει να κάνεις deallocate).

Δεν ειναι καλο να εχεις embedded json array μεσα σε ενα field. Θα εχεις θεμα με edit/update καθε φορα. Ασε που μπορεί να μεγαλώνει και να γινει αργο. Θα εχεις ενα αλλο table με info απο τη δραστηριοτητα + customerId + articleId. To join info-customer-article δεν νομιζω να ειναι αργο. Δεν θα εχεις θεμα ουτε με ταχυτητα εισαγωγης στο info.

Σου εχω πιο φθηνή λύση, δηλαδη εντελώς τζαμπα. Μπες στο github, ψαξε για τις τεχνολογίες που λες σιγουρα θα βρεις έτοιμο καποιο (open source) project. Στείλε απλα το λινκ στον καθηγητη αν βαριεσαι να το κατεβασεις.

Αυτο που ηθελα να πω απο ειναι οτι το recursive (level--); ειναι ισοδύναμο με recursive (level); level=level-1; αρα η κάθε νέα θα καλείται με το ιδιο level=10 recursive (--level); ειναι ισοδύναμο με level=level-1; recursive (level); εδω το level μειώνεται σε καθε κληση Βασικά δεν τερματίζει επειδή η συνθήκη τερματισμού ειναι μετά την κλήση την επόμενης recursive(). Το παρακατω εχει το if πριν και τερματίζει γραφοντας 10, 9 ,8,..0 . Aφαίρεσα το level++. public static void recursive(int level) { Console.WriteLine(level); if (level == 0) { return; } recursive(--level); }

Το θεμα ειναι να καταλάβει ο φοιτητής οτι recursive(--level) ειναι διαφορετικό απο recursive(level--)

Ολα τα παραπανω, μην αναρωτιεσαι καθολου.

Επίσης στο 2: το μέγεθος της βάσης δεδομένων μπορεί να είναι πολύ μεγαλύτερο του περιεχόμενου της.