.NET Framework

Απ: Code optimization (text replace and count)

Mitsaras — Sat, 02 Aug 2008 19:49:16 GMT

Ενδιαφέρον. Thumbs up!

Απ: Code optimization (text replace and count)

Παναγιώτης Καναβός — Sat, 02 Aug 2008 18:04:32 GMT

Όχι, μόνο N strings αλλά n(n+1) chars καθώς χρησιμοποιούνται οι καταλήξεις κι όχι όλα τα δυνατά substrings. Στόχος δεν είναι η ελάχιστη μνήμη αλλά η μέγιστη ταχύτητα. Γι αυτό και είπα ότι είναι για μεγάλα strings και αλλεπάλληλες αναζητήσεις. Για μία αναζήτηση μόνο είναι εντελώς περιττό. Αν όμως θέλει κανείς να ψάξει επανηλλημένα για ένα substring η αναζήτηση είναι ένα πολύ γρήγορο binary search. Η γραμμική αναζήτηση έχει πολυπλοκότητα Ο(m+n) όπου m το μέγεθος του substring και n το μέγεθος του μεγάλου string. Η πολυπλοκότητα του binary search είναι O(m*logn). Αν το substring είναι μικρό σε σχέση με το αρχικό string η διαφορά ταχύτητας είναι σημαντική. Ψάχνοντας για ένα substring των 10 χαρακτήρων σε ένα string των 1000 χαρακτήρων θα δώσει στην πρώτη περίπτωση 1010 ενώ στη δεύτερη 30. Και μετά πολλαπλασιάζουμε το νούμερο με τον αριθμό queries που θέλουμε να κάνουμε.

Το ίδιο πράγμα συμβαίνει με οποιαδήποτε δομή η οποία χρησιμοποιείται για indexing, παίρνουν συνήθως πολύ περισσότερη μνήμη αλλά επιταχύνουν τόσο πολύ τις αναζητήσεις ώστε το κόστος της δημιουργίας του index θεωρείται ότι μοιράζεται και είναι αμελητέο. Αν η πληροφορία που αναζητούμε είναι μικρή σε σχέση με το συνολικό όγκο πληροφορίας, ένα index επιταχύνει τη διαδικασία. Διαφορετικά είναι καλύτερη η γραμμική αναζήτηση. Αυτό γίνεται και με τον SQL Server, όταν κάποιες φορές επιλέγει να κάνει table scan αντί να χρησιμοποιήσει κάποιο index.

Τον κώδικα που έγραψα τον ψιλοέκλεψα από ένα απλό implementation σε Ruby με τη διαφορά ότι χρησιμοποίησα τα έτοιμα functions του .ΝΕΤ. H List<T>.Sort() χρησιμοποιεί QuickSort οπότε δεν είχα τις ανησυχίες του αρθρογράφου για το Enumerable#sort της Ruby, ενώ το BinarySearch ήταν κι αυτό έτοιμο. Η γραμμική αναζήτηση μετά για να βρώ όλα τα substrings που ξεκινούν με το substring που ψάχνω είναι λίγο χαζή, αλλά βαρέθηκα να ψάξω και για κάποιο καλύτερο αλγόριθμο!

Η ταχύτητα, ειδικά για το substring count, μπορεί να βελτιωθεί αρκετά αν χρησιμοποιηθούν suffix trees, στην οποία περίπτωση το substring count είναι ο αριθμός των πεδιών του πρώτου κόμβου που ξεκινάει με το substring που ψάχνουμε. Αυτός ο υπολογισμός μπορεί να γίνει άνετα τη στιγμή που δημιουργείται ένα δέντρο οπότε η αναζήτηση για ένα substring μπορεί να γίνει απλά O(logn). Βρήκα μία υλοποίηση σε C++ στο http://blog.lizhao.net/2005/01/c-implementation-of-ukkonens-suffix.html η οποία φτιάχνει το δέντρο σε Ο(n) αλλά ... κάτι δεν πήγε καλά στη μετατροπή σε C# και το δέντρο που παίρνω είναι λίγο μυστήριο.

Τα suffix trees και τα suffix arrays δημιουργούνται για να επιταχύνουν πολλαπλά queries π.χ. σε εφαρμογές βιοπληροφορικής όπου μπορεί να έχεις πολύ μεγάλα strings που αντιπροσωπεύουν γονίδια και ψάχνεις να βρεις μία συγκεκριμένη αλληλλουχία δηλαδή ... ένα substring. Επίσης χρησιμοποιούνται από ... προγράμματα antivirus για να ψάξουν για κάποια substrings μέσα σε προγράμματα ή τη μνήμη και τέλος σε μηχανής αναζήτησης. Αλήθεια, ο Δημήτρης τί θέλει να το κάνει?

Απ: Code optimization (text replace and count)

Mitsaras — Sat, 02 Aug 2008 11:39:46 GMT

Είσαι λίγο μνημοβόρος όμως. Χρειάζεσαι n(n+1)/2 ενδιάμεσα strings, ή κάνω λάθος;

Απ: Code optimization (text replace and count)

Παναγιώτης Καναβός — Sat, 02 Aug 2008 10:14:56 GMT

Βρήκα και αυτά τα αρθράκια στο Wikipedia για Suffix trees και Suffix arrays, τα οποία χρησιμοποιούνται για να επιταχύνουν αναζητήσεις και substring counts σε ΜΕΓΑΛΑ strings. Ουσιαστικά, δημιουργείται από το αρχικό string ένα δέντρο ή ένα sorted array με όλα τα substrings, από το τέλος προς την αρχή. Για το string "abracadabra" ένα suffix array θα περιέχει τα παρακάτω strings:

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

Μετά είναι εύκολο να βρει κανείς ένα συγκεκριμένο suffix με binary search. Για να βρεί κανείς το substring count μετράει πόσα suffixes ξεκινάνε με το συγκεκριμένο substring. Χρησιμοποιώντας τα καλούδια του .NET η υλοποίηση γίνεται :

public static class SuffixExtensions
{
   public static int CountSubstring(this List<string> list, string needle)
   {
      int startIndex = list.BinarySearch(needle);
      //If no exact match is found, the bitwise complement of the index is the first string greater than the needle,
      //ie. the first string that starts with the needle
      startIndex = startIndex >= 0 ? startIndex : ~startIndex;

      int count = 0;
      for (int j = startIndex; j < list.Count; j++)
      {
         if (list[j].StartsWith(needle))
            count++;
         else
            return count;
      }
      return count;
   }

   public static List<string> CreateSuffixArray(this string haystack)
   {
      List<string> list = new List<string>();
      for (int i = 0; i < haystack.Length; i++)
      {
         list.Add(haystack.Substring(i));
      }
      list.Sort();
      return list;
   }
}

Έτσι το substring count γίνεται ως εξής:

List<string> list = "abracadabrabra".CreateSuffixArray();
int count = list.CountSubstring("ra");

το οποίο θα γυρίσει 3. Η υλοποίηση αυτή επιστρέφει και τα overlapping substrings. Η δημιουργία του suffix array κοστίζει αλλά οι αναζητήσεις γίνονται πολύ γρήγορες. Αν θέλει κανείς να κάνει πολλές αναζητήσεις στο ίδιο κείμενο η ταχύτητα αυξάνεται σημαντικά.

Απ: Code optimization (text replace and count)

Παναγιώτης Καναβός — Sat, 02 Aug 2008 05:51:03 GMT

Ορίστε και η δική μου έκδοση, καταρχήν ως substr_count, για να τιμήσουμε την PHP που έχει αυτό το function:

static int substr_count(string haystack, string needle,bool countOverlaps)
{
   int startIndex=0,counter=0;
   int needleLength = countOverlaps ? 1 : needle.Length;
   while ((startIndex= haystack.IndexOf(needle, startIndex)+needleLength) >= needleLength)
      counter++;
   return counter;
}

και ως extension method στην String, για να γράφουμε "NNNNNN".SubstringCount("NN",true)==3!

public static class StringExtensions
{
   public static int SubstringCount(this string haystack, string needle, bool countOverlaps)
   {
      int startIndex = 0, counter = 0;
      int needleLength = countOverlaps ? 1 : needle.Length;
      while ((startIndex = haystack.IndexOf(needle, startIndex) + needleLength) >= needleLength)
         counter++;
      return counter;
   }
}

Ουσιαστικά, η position που είχε βάλει ο Palladin έφυγε και αντί γι αυτή ανανεώνεται απευθείας η startIndex. Αν δεν βρεθεί ένα substring, το αποτέλεσμα της IndexOf θα είναι αρνητικό οπότε το άθροισμα του αποτελέσματος + το μήκος της λέξης θα είναι μικρότερα από το μήκος της λέξης. Μπήκα στον πειρασμό να βάλω και τον ορισμό της needleLength στην πρώτη γραμμή, αλλά είπα να δείξω χαρακτήρα!

Απ: Code optimization (text replace and count)

Παναγιώτης Καναβός — Sat, 02 Aug 2008 05:05:30 GMT

Αυτές τις απορρίψαμε πριν από 10 posts!

Απ: Code optimization (text replace and count)

Mitsaras — Sat, 02 Aug 2008 05:00:10 GMT

Χμ... ελπίζω να μην είναι κάτι προφανές που αγνοώ, αλλά δεν βλέπω πώς θα μπορούσε η λύση με το replace ή το Split() να επιστρέψει 4 στο παράδειγμα με το "NNN" string του Νίκου, τουλάχιστον όπως το κοιτάω τώρα, μετά από 36 ώρες αϋπνίας + δουλειάς.

Απ: Code optimization (text replace and count)

Παναγιώτης Καναβός — Sat, 02 Aug 2008 04:32:56 GMT

Το τί θα επιστρέψει ο κάθε τρόπος αλλάζει εύκολα όπως έδειξε και ο anjelinio. Όλες οι περιπτώσεις μπορούν να δώσουν είτε 2 είτε 4 ως αποτέλεσμα.

Απ: Code optimization (text replace and count)

Mitsaras — Sat, 02 Aug 2008 04:00:43 GMT

Το IndexOf θα επιστρέψει 4 φορές, οι άλλες λύσεις και ένα απλό regex (χωρίς lookback) θα επιστρέψουν 2. Το θέμα είναι κατά πόσο θεωρείται αποδεκτό από το context τα αποτελέσματα να αναφέρονται σε επικαλυπτόμενα strings.

Απ: Code optimization (text replace and count)

PALLADIN — Sat, 02 Aug 2008 03:28:15 GMT

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

Απ: Code optimization (text replace and count)

Dimitris Papadimitriou — Sat, 02 Aug 2008 03:27:05 GMT

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

Απ: Code optimization (text replace and count)

anjelinio — Sat, 02 Aug 2008 03:24:48 GMT

Σωστοοοοος !

Απ: Code optimization (text replace and count)

PALLADIN — Sat, 02 Aug 2008 03:21:11 GMT

anjelinio:

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

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

Απ: Code optimization (text replace and count)

anjelinio — Sat, 02 Aug 2008 02:38:50 GMT

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; δε θα "κόψει" κι άλλο χρόνο; Μπορεί να παραλογίζομαι βέβαια, είμαι "στα πεταχτά" εδώ ... :)

Απ: Code optimization (text replace and count)

Dimitris Papadimitriou — Fri, 01 Aug 2008 21:09:27 GMT

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

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