Παραθέτω ένα κομμάτι κώδικα που είχα γράψει πριν πολύ πολύ καιρό και ζητώ τις ιδέες σας. Λέτε να μπορεί να γίνει κάποιο optimization; Η γλώσσα είναι C# και δεκτό είναι οποιοδήποτε optimization χρησιμοποιώντας οποιαδήποτε έκδοση της γλώσσας.

        public static int CountMatches(string inputText, string searchText)
        {
            var newLength = inputText.Replace(searchText, string.Empty).Length;
            return (inputText.Length - newLength)/searchText.Length;
        }

Η συνάρτηση υπολογίζει πόσες φορές το searchText βρίσκεται μέσα στο inputText. Για να το κάνει αυτό κάνει replace το searchText string μέσα στο inputText, βρίσκει το μήκος του νέου κειμένου. Η διαφορά το αρχικού μήκους με το τελικό διά το μήκος του searchText είναι ο αριθμός που βρήθηκε το searchText στο inputText.

(Πριν γίνουν όλα αυτά γίνονται κάποιοι έλεγχοι για null input τιμές, αλλά αφαίρεσα τον κώδικα για λόγους απλότητας)

Η συνάρτηση λειτουργεί ταχύτατα ακόμα και για τεράστια inputText (π.χ. 10MB). Λέτε όμως να μπορεί να γίνει κάποιο optimization;

ps. Οι συμμετέχοντας θα μπουν σε κλήρωση για 6ήμερες διακοπές στο ακριτικό Σύνταγμα σε παγκάκι Α κατηγορίας (ε... καλά δεν μου ερχόταν κάτι πιο αστείο να γράψω).

---

Dimitris Papadimitriou Software Development Professional

Οι απαντήσεις παρέχονται για συγκεκριμένες ερωτήσεις και χωρίς καμιά εγγύηση. Διαβάστε επίσης τους όρους χρήσης.

Γιατί δεν δοκιμάζεις με Regex?

---

Vir prudens non contra ventum mingit

Μου άρεσε η υλοποίηση, πολύ έξυπνη προσέγγιση! Μπορείς να δοκιμάσεις και με string.Split(...).Count() -1 αλλά φαντάζομαι η μνήμη δεν είναι το δυνατό σημείο μιας τέτοιας λύσης.

EDIT. Να και ένα μίνι benchmark. Για ένα αρχείο 50ΜΒ με όλα τα πιθανά compiler optimizations, τα αποτελέσματα σε msec είναι:
Count Matches: 212
String split: 328
Regex: 106

Βέβαια, το Regex έδωσε πολύ καλά αποτελέσματα σε "δύσκολα" strings τα οποία δεν επαναλαμβάνονται συχνά στο κείμενο. Στην χειρότερη περίπτωση (ψάχνοντας για ένα γράμμα στο ίδιο αρχείο), τα αποτελέσματα ήταν:
Count Matches: 204
String split: 326
Regex: 367

Κατά κανόνα όμως, το Regex στην περίπτωσή μου επιτύγχανε τις καλύτερες επιδόσεις.

---

Μην αφήνετε τα media να σας "ταΐζουν"!

Mitsara thanks για το benchmark!

Κοιτάξτε τώρα τι μπορεί να πάθει κανείς. Αυτή τη λύση την κάνω από την VB6. Ούτε μου πέρασε από το μυαλό αν χρησιμοποιήσω RegEx στο .NET, αν και χρησιμοποιώ σε άλλες περιπτώσεις!

Θα πρέπει να κάνουμε και ένα memory profiling να δούμε τι γίνεται (π.χ. χρησιμοποιώντας το εκπληκτικό dotTrace)! Μήπως κανείς μπορεί να πει απευθείας;

---

Dimitris Papadimitriou Software Development Professional

Οι απαντήσεις παρέχονται για συγκεκριμένες ερωτήσεις και χωρίς καμιά εγγύηση. Διαβάστε επίσης τους όρους χρήσης.

Δημήτρη δες και αυτό που έγραψα...

public static int CountMatches(string inputText, string searchText)
{
   int position = -1;
   int startIndex = 0;
   int counter = 0;
   while((position = inputText.IndexOf(searchText, startIndex)) != -1)
   {
      counter++;
      startIndex = position + 1;
   }
   return counter;
}

(Λογικά η IndexOf πρέπει να χρησιμοποιεί Knuth-Morris-Pratt... οποτε είναι optimal)

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

Thanks Νίκο,

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

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

---

Dimitris Papadimitriou Software Development Professional

Οι απαντήσεις παρέχονται για συγκεκριμένες ερωτήσεις και χωρίς καμιά εγγύηση. Διαβάστε επίσης τους όρους χρήσης.

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

Νίκο, kudos to you sir (ειδικά για το διάβασμα για τον αλγόριθμο, τον οποίο αγνοούσα)! Μου άρεσε πάρα πολύ ο μηχανισμός στην πρώτη λύση του Δημήτρη όμως, που μπορεί κάλλιστα να γίνει και one-liner. Προς το παρόν, παίρνω την αργή και memory inefficient λύση μου και πάω πίσω στη γωνιά μου .

---

Μην αφήνετε τα media να σας "ταΐζουν"!

Χμμ, κάνοντας την υπόθεση ότι η IndexOf δουλεύει με χαζό τρόπο, όντως θα ήταν αργή. Αλλά δεν δουλεύει με χαζό τρόπο. Σύμφωνα με τη Wikipedia η ταχύτητα του KMP είναι O(n+k) όπου n και k το μήκος των δύο string. Το θέμα είναι, οι ψ επαναλήψεις για να κάνεις το count θα βγουν γρηγορότερες από το Regex?

 

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

H πρώτη λύση, πέρα από το ότι δημιουργεί άλλο ένα μεγάλο temporary string, προκαλεί και ένα βαρύ memory allocation και ένα βαρύ garbage collection όταν χρησιμοποιούνται μεγάλα strings και πιθανώς και fragmentation της μνήμης. Αν τη δει κανείς μόνη της ίσως να μην φαίνεται τόσο αργή, αν σκεφτείς όμως ότι αυτός ο κώδικας εκτελείται στα πλαίσια μίας εφαρμογής και μπορεί να κληθεί πολλές φορές το δευτερόλεπτο ...

 

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Παναγιώτης Καναβός:

H πρώτη λύση, πέρα από το ότι δημιουργεί άλλο ένα μεγάλο temporary string, προκαλεί και ένα βαρύ memory allocation και ένα βαρύ garbage collection όταν χρησιμοποιούνται μεγάλα strings και πιθανώς και fragmentation της μνήμης. Αν τη δει κανείς μόνη της ίσως να μην φαίνεται τόσο αργή, αν σκεφτείς όμως ότι αυτός ο κώδικας εκτελείται στα πλαίσια μίας εφαρμογής και μπορεί να κληθεί πολλές φορές το δευτερόλεπτο ...

Και αυτός είναι κυρίως ο λόγος που με έκανε να αναζητήσω κάτι καλύτερο.

---

Dimitris Papadimitriou Software Development Professional

Οι απαντήσεις παρέχονται για συγκεκριμένες ερωτήσεις και χωρίς καμιά εγγύηση. Διαβάστε επίσης τους όρους χρήσης.

PALLADIN:

Δημήτρη δες και αυτό που έγραψα...

public static int CountMatches(string inputText, string searchText)
{
   int position = -1;
   int startIndex = 0;
   int counter = 0;
   while((position = inputText.IndexOf(searchText, startIndex)) != -1)
   {
      counter++;
      startIndex = position + 1;
   }
   return counter;
}

(Λογικά η IndexOf πρέπει να χρησιμοποιεί Knuth-Morris-Pratt... οποτε είναι optimal)

.. κι αν κάνεις το  startIndex = position + 1; -> startIndex = position + searchText.Length; δε θα "κόψει" κι άλλο χρόνο; Μπορεί να παραλογίζομαι βέβαια, είμαι "στα πεταχτά" εδώ ... :)

---

Angel
O:]

anjelinio:

.. κι αν κάνεις το  startIndex = position + 1; -> startIndex = position + searchText.Length; δε θα "κόψει" κι άλλο χρόνο; Μπορεί να παραλογίζομαι βέβαια, είμαι "στα πεταχτά" εδώ ... :)

Πόσες φορες εμφανίζεται το "NNΝ" στο "ΝNNNNN" 2 ή 4 ?

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

Σωστοοοοος !

---

Angel
O:]

Φαντάζομαι ότι εγώ πρέπει να το απαντήσω αυτό. Νομίζω 2.

---

Dimitris Papadimitriou Software Development Professional

Οι απαντήσεις παρέχονται για συγκεκριμένες ερωτήσεις και χωρίς καμιά εγγύηση. Διαβάστε επίσης τους όρους χρήσης.

Φεύγοντας από την δουλειά... να ευχηθώ ένα καλο ΣΚ σε όλους σας

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)