σύγκριση χαρακτήρων στην C

[migf1]

@migf1:

 

Βασικά καλά τα λέμε εδώ για το O(N) της strlen κλπ, αλλά εκτός συγκεκριμένων εξαιρέσεων η απλή αλήθεια είναι ότι εν έτει 2012 με char* δε μπορείς να γράψεις απολύτως κανένα σοβαρό πρόγραμμα γιατί single byte encoding = fail οπότε

 

1) είναι εγκληματικό το γεγονός ότι δε διδάσκουν παντού κάτι σαν κι αυτό

 

2) εφόσον δεν υπάρχει χρήσιμο Unicode support στη C δεν έχει και πολύ νόημα να μιλάμε για strlen -- θα αναγκαστείς να χρησιμοποιήσεις κάποια εξωτερική library στην οποία το string type μπορεί να περιέχει και το μήκος του (a la BSTR)

Το πρόβλημα δεν είναι αυτή κάθε αυτή η strlen(), αλλά το υπόβαθρο χρήσης της. Άλλωστε ότι γράψαμε ισχύει ατόφιο και για την wcslen() που χρησιμοποιείται για την διαχείριση Unicode strings.

[imitheos]

Αν και είμαι αντίθετος από την απευθείας υπόδειξη όλου του κώδικα σε ερωτήσεις ασκήσεων, εφόσον δόθηκε ήδη να σχολιάσω πως η λύση του φίλου pantpesl2 χρησιμοποιεί αχρείαστα 3 κλήσεις της ιδιαίτερα δαπανηρής strlen().

+1

 

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

 

>
char str1[ ] = "abcb";
char str2[ ] = "abc";
bool first1st = false;

int  i=0, j=0;
while ( str1[i] == str2[j++] )
	if ( '\0' == str1[i++] )  // ή if ( !str1[i++] )
		break;
first1st = (str1[i] <= str2[--j]);

printf( "1st: %s\n", first1st ? "str1" : "str2" );

 

Πιστευω οτι οι απαντησεις σου ( χωρις την strlen ) δυσκολευουν περισσοτερο τους αρχαριους. Βεβαια , ο κωδικας σου τους κανει να σκεφτονται διαφορετικα και πιο εξυπνα , αλλα για το επιπεδο που βρισκονται μου φαινεται οτι η strlen ειναι "καλο" να χρησιμοποιειται.

 

Ο κώδικας του migf1 (όπως και πολλοί κώδικες που χρησιμοποιούν ++ μέσα στη συνθήκη του while) όντως ίσως μπερδεύει τους αρχάριους. Αυτό όμως δεν σημαίνει ότι χρειάζεται να χρησιμοποιηθεί η strlen.

>
while ( str1[i] == str2[j] ) {
	j++;
	if ( str1[i] == 0 )
		break;
	i++;
}

 

Ο παραπάνω κώδικας είναι ίδιος με αυτόν του migf1 χωρίς (κατά την γνώμη μου) να μπερδεύει οποιονδήποτε. Όπως βλέπουμε, εκτός από την κλήση της strlen δεν χρειάζεται καν να ξέρουμε ποιο string είναι μικρότερο όπως έκανε ο αρχικός κώδικας.

 

Εχω παρατηρησει οτι καθε φορα που βλεπεις την strlen() βγαζεις αφρους απο το στομα

 

Καλά κάνει :Ρ Η strlen μας επιστρέφει πόσους χαρακτήρες έχει ένας πίνακας χαρακτήρων. Δηλαδή μας δίνει ένα αριθμό. Τον χρειαζόμαστε όμως αυτόν τον αριθμό ? Το κλασικό παράδειγμα είναι αυτό που έδωσε ο migf1 με το for loop. Χρειάζεται να τρέξουμε το loop τόσες φορές όσους χαρακτήρες έχει το string αλλά δεν μας νοιάζει πόσοι είναι αυτοί σαν νούμερο οπότε μπορούμε να εκμεταλλευτούμε το γεγονός ότι τα strings είναι null-terminated και να τρέξουμε το loop μέχρι να βρούμε τον χαρακτήρα NUL '\0'.

 

Shameless Self-Promotion

 

Το πιο χαρακτηριστικό (και συνάμα συνηθισμένο) παράδειγμα αλόγιστης χρήσης της strlen() είναι το ακόλουθο for loop...

 

>
if (i=0; i < strlen(str); i++)
...

Φαντάσου τώρα αυτό το loop να εφαρμοζεται ας πούμε στην αναζήτηση μιας συμβολοσειράς στα λεξικά 20 γλωσσών, με το κάθε λεξικό να αποτελείται κατά μέσο όρο ας πούμε από 100.000 λέξεις (προφανώς οι αναζητήσεις δεν γίνονται έτσι, αλλά το φέρνω σαν απλοϊκό παράδειγμα αναζήτησης σε 2 εκατομμύρια λέξεις).

 

Μετατρέποντας το παραπάνω loop σε...

 

>
int len = strlen(str);
for (i=0; i < len; i++)
	...

μπορείς να φανταστείς πόσο δραματικά πέφτει ο χρόνος αναζήτησης.

 

Σημείωση ότι στην 1η περίπτωση, οι περισσότεροι compilers θα κοιτάξουν αν μέσα στο σώμα του βρόχου αλλάζει το string και αν δεν αλλάζει τότε δεν θα τρέχει την strlen για κάθε εκτέλεση του βρόχου αλλά θα παράξει ίδιο κώδικα με την 2η περίπτωση. Αυτό όμως δεν μειώνει το επιχείρημα του migf1 ότι δεν έχει κανένα νόημα να χρησιμοποιούμε την strlen με αυτό τον τρόπο.

[migf1]

...

Σημείωση ότι στην 1η περίπτωση, οι περισσότεροι compilers θα κοιτάξουν αν μέσα στο σώμα του βρόχου αλλάζει το string και αν δεν αλλάζει τότε δεν θα τρέχει την strlen για κάθε εκτέλεση του βρόχου αλλά θα παράξει ίδιο κώδικα με την 2η περίπτωση.

...

Αυτό δεν το γνώριζα! Εξαιρετικά ενδιαφέρον και χρήσιμο! Thanks!

 

ΥΓ. Ισχύει ανεξαιρέτως optimization flags?

[defacer]

Το πρόβλημα δεν είναι αυτή κάθε αυτή η strlen(), αλλά το υπόβαθρο χρήσης της. Άλλωστε ότι γράψαμε ισχύει ατόφιο και για την wcslen() που χρησιμοποιείται για την διαχείριση Unicode strings.

 

Βέβαια. Πάντως η wcslen() και γενικά ο wchar_t με όλα τα συμπράγκαλά του είναι τόσο under-specified που είναι τελείως άχρηστα στην πράξη.

[migf1]

Βέβαια. Πάντως η wcslen() και γενικά ο wchar_t με όλα τα συμπράγκαλά του είναι τόσο under-specified που είναι τελείως άχρηστα στην πράξη.

Χμμ... γιατί το λες αυτό; Εξ' όσων γνωρίζω η συντριπτική πλειοψηφία προγραμμάτων που διαχειρίζονται Unicode σε C το κάνουν μέσω του wchar_t.

[imitheos]

Αυτό δεν το γνώριζα! Εξαιρετικά ενδιαφέρον και χρήσιμο! Thanks!

 

ΥΓ. Ισχύει ανεξαιρέτως optimization flags?

 

Λογικά όχι. Με ένα γρήγορο τεστ, ο gcc χωρίς optimization καλεί κάθε φορά την strlen, με O1 τρέχει repnz scasb για να βρεί τον χαρακτήρα 0 και με O2 παραδόξως καλεί και πάλι την strlen αλλά μία φορά.

 

 

Χμμ... γιατί το λες αυτό; Εξ' όσων γνωρίζω η συντριπτική πλειοψηφία προγραμμάτων που διαχειρίζονται Unicode σε C το κάνουν μέσω του wchar_t.

 

Η κριτική που διαβάζω να δίνουν πολλοί είναι ότι δεν μπορείς να βασιστείς στον wchar_t για portability μια και σε windows είναι 16bit ενώ σε *nix 32bit. Μου φαίνεται παράξενο αυτό που λες για την χρήση wchar_t από την πλειοψηφία των προγραμμάτων. Εκτός από αυτή τη διαφορά windows-nix ένα άλλο σημαντικό μειονέκτημα είναι ότι κανείς δεν σου εγγυάται ότι ο wchar_t θα υποστηρίζει unicode. Το πρότυπο λέει ότι πρέπει να μπορεί να αναπαραστήσει το μεγαλυτερο σετ χαρακτήρων της υλοποίησης οπότε θα μπορούσε (πχ σε κάποιο embedded) να είναι και 1byte το wchar_t. Για αυτό το λόγο βγήκανε και τα char16_t, char32_t στο νέο πρότυπο ώστε να είσαι σίγουρος ότι είναι παντού ίδια και μπορούν να παίξουν unicode.

[Directx]

Εξαρτάται που στοχεύεις, για παράδειγμα αν σε ενδιαφέρει αποκλειστικά η πλατφόρμα των Windows (και θες υποστήριξη UNICODE) δίχως να σε απασχολεί το portability πχ. σε LINUX, η χρήση wchar_t είναι συνηθισμένη και οι διαθέσιμες w* ρουτίνες μια χαρά.

[defacer]

Χμμ... γιατί το λες αυτό; Εξ' όσων γνωρίζω η συντριπτική πλειοψηφία προγραμμάτων που διαχειρίζονται Unicode σε C το κάνουν μέσω του wchar_t.

 

Πέρα από τα περι portability που λέει ο imitheos:

 

• Δεν υπάρχει καμία υποστήριξη για encodings (παίρνεις αυτό που χρησιμοποιεί ο implementor του C runtime και τέλος). Αν χρειάζεσαι να εισάγεις δεδομένα από οποιαδήποτε πηγή που δεν χρησιμοποιεί το ίδιο encoding (το οποίο δεν ξέρεις και ποιό είναι!) τον ήπιες, άρα άχρηστο.
  
• Δεν υπάρχει καμία υποστήριξη για Unicode collations (UCA) επομένως αν θέλεις να ταξινομήσεις μια λίστα από strings με τρόπο που να έχει νόημα για το χρήστη της εφαρμογής με wcscoll είσαι περιορισμένος σε ο,τι locale έχει προβλέψει ο implementor του C runtime. Επίσης αν η είσοδος περιέχει χαρακτήρες εκτός του domain της συγκεκριμένης collation η wcscoll σηκώνει τα χέρια ψηλά. Αυτό δεν ενδιαφέρει καθόλου το χρήστη της εφαρμογής, άρα άχρηστο.
  
• Δεν υπάρχει καμία υποστήριξη για Unicode normalization forms. Το πόσο σημαντικό είναι αυτό εξαρτάται από την περίσταση, αλλά αν νομίζεις πως δέν έχει πολλή σημασία θα ήθελα να δω μια function που μετατρέπει τονούμενα ελληνικά από/προς lowercase. Edit: λάθος μου, ήθελα να γράψω "να αφαιρεί διακριτικά σημεία από την είσοδο του χρήστη". Use case: έχεις μια search form. Δεν περιμένεις βέβαια ο χρήστης να σου δώσει και τους τόνους ή τα accents για να του βρεις αυτό που ψάχνει γιατί διαφορετικά θα γίνει άμεσα πρώην χρήστης.
  
• Για τους πιο δύσπιστους: τo wchar_t εισήχθη στη C πρίν από το 1991, δηλαδή όταν ακόμα δεν υπήρχε Unicode. Discuss.
  

 

Με τη C++11 πολλά από αυτά έχουν διορθωθεί, αλλά πρώτον μόνο στη C++ και δεύτερον too little too late.

 

Επίσης, υπάρχει κάποιο παράδειγμα από τέτοιο πρόγραμμα που λες; Θα μ' ενδιέφερε πολύ να δω πώς αντιμετωπίζουν τα προβλήματα που αναφέραμε...

[migf1]

Παιδιά παρόλο που έχετε δίκιο για την ασυμβατότητα από πλατφόρμα σε πλατφόρμα, ένας δημοφιλής τρόπος για διαχείριση Unicode σε C ήταν η μετατροπή τους κατά την είσοδο από Unicode σε wide, εσωτερική διαχείριση των πάντων ως wide και κατόπιν μετατροπή τους σε Unicode πριν την έξοδο.

 

Το βασικό μείον ήταν ο έξτρα χώρος για πρότυπα που χρησιμοποιούν λιγότερα από 4 bytes, και το βασικό συν ότι έτσι μπορείς να διαχειριστείς ακόμα και Unicode πρότυπα που χρησιμοποιούν μεταβλητό πλήθος bytes για την αναπαράσταση των χαρακτήρων (δεν θυμάμαι απέξω ποια είναι αυτά, νομίζω το UTF-8 είναι ένα από αυτά... χρησιμοποιεί από 1 έως 4 bytes αν το θυμάμαι καλά).

 

Επίσης, νομίζω πως είναι εγγυημένο πως κανένα Unicode πρότυπο δεν χρησιμοποιεί περισσότερα από 4 bytes. Επειδή όμως ούτε 100% σίγουρος είμαι, ούτε τα έχω πρόσφατα στο μυαλό μου, τσεκάρετέ το κι εσείς όποτε ευκαιρήσετε.

 

Είμαι όμως 100% σίγουρος για την παραπάνω τεχνική. Πιθανότατα να έχουν προστεθεί πιο αποτελεσματικές, αλλά η παραπάνω ήταν πολύ δημοφιλής. Σίγουρα θα υπάρχουν σχετικές αναφορές στο google.

 

EDIT:

 

Στο Win32API όπως ήδη ανέφερε κι ο φίλος xdir το wchar_t εξακολουθεί να είναι το στάνταρ της εσωτερικής UTF16LE απεικόνισης των πάντων (fixed στα 2 bytes).

[defacer]

η μετατροπή τους κατά την είσοδο από Unicode σε wide

Πώς ακριβώς θα γίνει αυτό;

 

βασικό συν ότι έτσι μπορείς να διαχειριστείς ακόμα και Unicode πρότυπα που χρησιμοποιούν μεταβλητό πλήθος bytes για την αναπαράσταση των χαρακτήρων

Αυτό δεν είναι βασικό πλεονέκτημα, είναι απαραίτητο feature (το οποίο φυσικά έχουν όλα τα Unicode libraries που κυκλοφορούν). Επίσης (δεν ξέρω αν ήταν εκ παραδρομής) το Unicode είναι ένα -- πολλά είναι τα encodings.

 

Επίσης, νομίζω πως είναι εγγυημένο πως κανένα Unicode πρότυπο δεν χρησιμοποιεί περισσότερα από 4 bytes. Επειδή όμως ούτε 100% σίγουρος είμαι, ούτε τα έχω πρόσφατα στο μυαλό μου, τσεκάρετέ το κι εσείς όποτε ευκαιρήσετε.

Το UTF-8 encoding (βλέπε παραπάνω σχόλιο) χρησιμοποιεί μέχρι 6. Αυτό όμως δεν έχει καμία σημασία όσον αφορά την ικανότητα ή όχι του wchar_t να αποθηκεύσει οποιοδήποτε Unicode χαρακτήρα γιατί ένα string από wchar_t χρησιμοποιεί τυπικά το encoding του C runtime. Επίσης, μπορείς να έχεις full unicode εφαρμογή που χρησιμοποιεί μόνο char γιατί και πάλι, το μόνο που έχει σημασία είναι το implementation του Unicode library που χρησιμοποιείς.

 

Είμαι όμως 100% σίγουρος για την παραπάνω τεχνική. Πιθανότατα να έχουν προστεθεί πιο αποτελεσματικές, αλλά η παραπάνω ήταν πολύ δημοφιλής. Σίγουρα θα υπάρχουν σχετικές αναφορές στο google.

Eξακολουθώ να μην έχω πάρει ουσιαστική απάντηση για τα 3 points μου. Δεν έχω από κανέναν την απαίτηση να μου δώσει, αλλά θεωρώ πως δε στέκει λογικά να υποστηρίζει κάποιος ότι όλα καλά με το wchar_t χωρίς να απαντήσει εμπεριστατωμένα στα παραπάνω.

 

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

[migf1]

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

 

1. http://www.cl.cam.ac.uk/~mgk25/unicode.html#c

2. http://www.cprogramming.com/tutorial/unicode.html

[ChRis6]

Συμφωνω με οσα ειπατε παραπανω για την strlen . Πιστευω ομως οτι για εναν αρχαριο ειναι πιο σημαντικο να αρχισει να χρησιμοποιει κωδικα που δεν ειναι δικος του , δηλαδη ψαχνει να βρει αν υπαρχει κατι ετοιμο( οχι ετοιμη λυση οπως δωσατε παραπανω ) σε καποια βιβλιοθηκη , να ψαξει στα man pages να δει τι παραμετρους χρειαζεται μια συναρτηση , τι επιστρεφει και πως μπορει να χρησιμοποιησει τα αποτελεσματα κτλ.

 

Με το καιρο , οταν πια θα σκεφτεται πιο ωριμα προγραμματιστικα και ερθει το project που διαδοχικες κλησεις συναρτησεων οπως η strlen αργοπορουν το προγραμμα , τοτε απο μονος του θα βρει μια λυση αποδοτικη που να ταιριαζει στην εφαρμογη.

[defacer]

@migf1: Το πρώτο link που δίνεις μιλάει συγκεκριμένα για τη glibc (portability!) ενώ το δεύτερο κατα βάση δίνει ένα δικό του implementation και μόνο από σπόντα αναφέρεται στη standard library.

 

Βασικά για να κόψω τις πολεμικές μου ιαχές και να το πω λίγο πιο όμορφα:

 

Αν χρησιμοποιείς μια glibc η οποία υποστηρίζει ένα δισεκατομμύριο locales και δεν σε πειράζει να εξαρτάσαι από αυτήν τότε δεν υπάρχει κανένα πρόβλημα. Αλλά ας μη μπερδεύουμε την καταλληλότητα ενός implementation της standard library (όπως η glibc) με την καταλληλότητα του προτύπου της standard library (που είναι ο ελάχιστος κοινός παρονομαστής).

[migf1]

Συμφωνω με οσα ειπατε παραπανω για την strlen . Πιστευω ομως οτι για εναν αρχαριο ειναι πιο σημαντικο να αρχισει να χρησιμοποιει κωδικα που δεν ειναι δικος του , δηλαδη ψαχνει να βρει αν υπαρχει κατι ετοιμο( οχι ετοιμη λυση οπως δωσατε παραπανω ) σε καποια βιβλιοθηκη , να ψαξει στα man pages να δει τι παραμετρους χρειαζεται μια συναρτηση , τι επιστρεφει και πως μπορει να χρησιμοποιησει τα αποτελεσματα κτλ.

...

Σε αυτή την περίπτωση τότε το ιδανικό είναι απευθείας η χρήση της strcmp() ... ούτε loops ούτε τίποτε

 

EDIT:

 

@migf1: Το πρώτο link που δίνεις μιλάει συγκεκριμένα για τη glibc (portability!) ενώ το δεύτερο κατα βάση δίνει ένα δικό του implementation και μόνο από σπόντα αναφέρεται στη standard library.

 

Βασικά για να κόψω τις πολεμικές μου ιαχές και να το πω λίγο πιο όμορφα:

 

Αν χρησιμοποιείς μια glibc η οποία υποστηρίζει ένα δισεκατομμύριο locales και δεν σε πειράζει να εξαρτάσαι από αυτήν τότε δεν υπάρχει κανένα πρόβλημα. Αλλά ας μη μπερδεύουμε την καταλληλότητα ενός implementation της standard library (όπως η glibc) με την καταλληλότητα του προτύπου της standard library (που είναι ο ελάχιστος κοινός παρονομαστής).

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

 

Επίσης νομίζω το locale το αλλάζεις προγραμματιστικά σε ότι θέλεις, δεν χρειάζεται να εξαρτάσαι από αυτό του περιβάλλοντος.

[imitheos]

@migf1:

1) είναι εγκληματικό το γεγονός ότι δε διδάσκουν παντού κάτι σαν κι αυτό

Το UTF-8 encoding (βλέπε παραπάνω σχόλιο) χρησιμοποιεί μέχρι 6. Αυτό όμως δεν έχει καμία σημασία όσον αφορά την ικανότητα ή όχι του wchar_t να αποθηκεύσει οποιοδήποτε Unicode χαρακτήρα γιατί ένα string από wchar_t χρησιμοποιεί τυπικά το encoding του C runtime. Επίσης, μπορείς να έχεις full unicode εφαρμογή που χρησιμοποιεί μόνο char γιατί και πάλι, το μόνο που έχει σημασία είναι το implementation του Unicode library που χρησιμοποιείς.

 

[τιτίζης]

Όταν έγραψε ο joel το μήνυμα που έδωσες όντως το πρότυπο προέβλεπε μέχρι 6 bytes. Όταν ενώθηκαν τα δύο πρότυπα ορίστηκε ότι οι υλοποιήσεις θα πρέπει να δέχονται μέχρι 4 bytes ώστε να υπάρχει μια συνέπεια ανάμεσα σε utf8 και utf16.

[/τιτίζης]

 

Συμφωνώ πάντως με αυτά που λες για την υποστήριξη unicode.

 

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

 

1. http://www.cl.cam.ac.uk/~mgk25/unicode.html#c

2. http://www.cprogramming.com/tutorial/unicode.html

 

Ωραία είναι και τα δύο links αλλά ο defacer έχει δίκιο για την γενική υποστήριξη unicode.

 

Αν δεν σε ενδιαφέρει το μέγεθος κάθε χαρακτήρα τότε μπορείς να δουλέψεις απλά με chars και να είσαι οκ. Σε διαφορετική περίπτωση, όπως αναφέρει και το 2ο link (με κάποιες παραλλαγές) μια καλή τακτική είναι να μετατρέπεις τα κλασικά char σε uint32_t και να είσαι ok. Υπάρχουν πολλές τέτοιες μικρές βιβλιοθήκες και παίζουν οκ. Αυτό όμως το απολύτως βασικό και δεν λαμβάνει υπόψην double-width χαρακτήρες όπως κινέζικα ούτε normalization που ανέφερε ο defacer και πολλά άλλα.

 

Για παράδειγμα ο χαρακτήρας ά (άλφα με τόνο) μπορεί να αναπαρασταθεί ως 0x03AC αλλά και ως 0x03B1 (άλφα) + 0x0301 (διακριτικό τόνος). Για να τα αντιμετωπίσει η εφαρμογή σου ώς ίδια θα πρέπει να χρησιμοποιήσεις μια γεμάτη βιβλιοθήκη όπως η icu.