typique Y a-t-il un moyen plus rapide de le faire où l'entrée est vaguement définie.
Comme: la longueur serait inférieure à 50 ou la longueur serait d'environ 200 caractères.
J'ai pensé aux blocs de recherche et à tous mais n'a pas eu d'optimisation. strlen () traverser du premier caractère jusqu'à ce qu'il trouve \ 0 .
Cela vous oblige à traverser chaque caractère.
Dans le sens de l'algorithme, son O (n).
9 Réponses :
Bien sûr. Gardez une trace de la longueur pendant que vous écrivez sur la chaîne.
+1: Hourra Fortran (et ne permettez pas de le changer de quelque manière que ce soit après la déclaration)
J'ai des améliorations importantes sur Strcat en utilisant cette technique
Bob, la plupart du temps, il est possible de maintenir une longueur explicite lorsque nous écrivons une chaîne. Parfois, ce n'est pas possible :( pour exa: lecture de flux de fichier ou réseau. J'aurais peut-être 500 caractères mais que seul le premier personnage effectue une chaîne valide et des 300 restants ne sont pas utiles
Ça ... ne sonne pas juste pour moi. La plupart des situations impliquant Fichier / Network Io vous permettent de lire le nombre d'octets.
Oui, ils donnent des nombres d'octets lus. Et si je ne suis pas intéressé par tous, mais besoin d'une première chaîne valide?
OUI. Aussi, veuillez comprendre que tous les programmes ne se comportent pas comme vous le souhaitez. Vous pourriez obtenir cette chaîne d'un autre processus / machine où vous n'avez pas beaucoup de contrôle. En général, mon intention était d'améliorer le prototype de SHLEN.
Si c'est ce que vous essayez de faire, alors non, il n'est pas possible de faire mieux que O (n). Strlen est ce que vous voulez.
+0: Hourra Cobol! (+0 parce que je ne suis pas inscrit :()
La réponse courte: non.
La réponse la plus longue: pensez-vous vraiment que s'il y avait un moyen plus rapide de vérifier la longueur de la chaîne pour les cordes barebones, aussi couramment utilisée que la bibliothèque de cordes C ne l'aurait pas déjà incorporée?
Sans une sorte de connaissances supplémentaires sur une chaîne, vous devez vérifier chaque personnage. Si vous êtes prêt à conserver cette information supplémentaire, vous pouvez créer un struct qui stocke la longueur en tant que champ dans la structure (en plus du tableau de caractères réel / pointeur de la chaîne), dans lequel Case, vous pouvez alors effectuer le temps constant de la recherche de la longueur, mais devriez mettre à jour ce champ chaque fois que vous avez modifié la chaîne.
Ensuite, nous aurions encore plus de cordes Pascal. :)
Mais nous aurions probablement moins de débordements de tampon (s'ils étaient intégrés à la langue ou utilisés de manière cohérente) - ce qui serait une bonne chose!
Évidemment, si votre chaîne a une longueur minimale connue, vous pouvez commencer votre recherche à cette position.
au-delà de cela, il n'y a pas vraiment de quoi que vous puissiez faire; Si vous essayez de faire quelque chose d'intelligent et de trouver un octet Cela ne veut pas dire que \ 0 , vous devez toujours vérifier tous les octets entre le début de la chaîne et ce point pour vous assurer qu'il n'y avait pas de \ 0 < / code>.
Strlen ne peut pas être optimisé. Il peut être pipeliné et il peut être fait pour traiter des morceaux de format de mots ou de vecteur avec chaque comparaison. Sur la plupart des architectures, une combinaison de ces approches et d'autres apportera une vitesse de facteur constante substantielle sur une boucle de comparaison des octets naïques. Bien sûr, sur la plupart des plates-formes matures, le système Strlen est déjà implémenté à l'aide de ces techniques.
Vous pouvez essayer d'utiliser une vectorisation. Je ne sais pas si le compilateur sera capable de le faire, mais je l'ai fait manuellement (en utilisant intrinsique). Mais cela pourrait vous aider que pour de longues chaînes.
Utilisez des chaînes STL, c'est plus sûr et STD :: La classe de cingler contient sa longueur.
Comment l'aide de vectorisation pourrait-elle? Même si le tampon était, dites 4 kb, il n'y a aucune garantie sur le contenu de la chaîne après la première null, donc si la vectorisation a commencé 4 opérations (threads?) Sur les frontières de 1 Ko, il n'y a pas de dire ce que les trois à partir de Un décalage non zéro verrait. Je suppose que le résultat devrait être le minimum des 4 valeurs retournées - où les fils de décalage non nuls devraient ajouter leur position de départ à la longueur renvoyée.
Je pense que Emalfer propose d'attribuer chaque octet consécutif à un vecteur à vérifier dans son ensemble, puis à faire défiler la chaîne de numérisation de la longueur du vecteur. Cela fonctionnerait certainement, en supposant que vous ayez une architecture basée sur un vecteur.
@Jonathan Vectorization n'utilise pas de threads! Vectorisation signifie utiliser le modèle de programmation SIMD pour vérifier simultanément les octets consécutifs de zéro. EN.Wikipedia.org/wiki/simd Cela aide que l'alignement de vecteur les rend toujours en forme dans un une seule page. Cette mise en œuvre déborde généralement de la mémoire tampon mais qui n'est pas capturée par la MMU. Nous trouvons ces dépassements de tampons bénins dans l'analyseur que je travaille. Voir aussi tsunanet.net/~tsuna/strlen.c.html pour un impressionnant C Mise en œuvre sans instructions de vecteur spécial.
@Jonathan: Il existe par exemple les instructions "PCMPEQB", qui compare 16 octets à la fois. De plus, SSE 4.2 contient des extensions de vecteur spécifiques pour les chaînes, comme "PCMPistri". Cela n'a rien à faire avec le filetage.
Cela dépendrait considérablement de votre taille moyenne de la chaîne. Si votre taille moyenne de chaîne est grande. Vous allez certainement bénéficier de SIMD. Si votre taille moyenne de chaîne est petite, vous ne bénéficierez pas de cela. Comme avec tout ce qui s'efforce de résultat basé sur la mesure (AKA Science) et non du battage médiatique (aka dogma)
Jack,
SHLEN code> Fonctionne en recherchant la fin "\ 0 ', voici une implémentation prise de OpenBSD: p> size_t
strlen(const char *str)
{
const char *s;
for (s = str; *s; ++s)
;
return (s - str);
}
Merci de répondre. Comme je l'ai dit, la longueur est vaguement prédite et peut ne pas se terminer après le personnage 200. En outre, si nous commençons à lire après 200e caractère, nous pourrions lire une chaîne non valide (si la chaîne est terminée autour de 100 caractères ...)
Le lien dit également identique: OpenBSD .org / cgi-bin / cvsweb / src / lib / libc / string / ...
En réalité, implémentation de glibc de SHLEN est un Exemple intéressant de l'approche de vectorisation. Il est particulièrement particulier qu'il n'utilise pas d'instructions vectorielles, mais trouve un moyen d'utiliser uniquement des instructions ordinaires sur les mots 32 ou 64 bits du tampon.
D'autre part, au moins sur X86 / X86_64 et GCC, vous obtiendrez de toute façon la construction du compilateur.
Oui, vous devez lui donner un autre nom si vous souhaitez vous assurer que la version utilisée est la vôtre. Si vous allez faire cela, vous pourriez aussi bien vous assurer que toutes les chaînes de votre version seront transmises sont alignées par Word-alignées (si possible) et supprimez complètement la boucle initiale de Char-By-Char.
Maintenant, il y a la version SSE2 de Strlen: Sourceware.org/git/?p=glc.git;A=Blob_Plain ;f=sysdeps/X86_6 4 / ...
@Simon et comment puis-je compiler cela avec Visual C ++?
Obtenez un processeur Core i7.
Core i7 est livré avec l'ensemble d'instructions SSE 4.2. Intel a ajouté quatre instructions de vecteur supplémentaires pour accélérer les tâches de recherche SHLEN et des recherches associées.
Voici quelques pensées intéressantes sur les nouvelles instructions:
Merci de répondre. Comme le dit George Varghese, le matériel de matériel aide toujours :)
Ici, j'ai joint le code ASM de GLIBC 2.29. J'ai enlevé l'extrait pour les CPU des bras. Je l'ai testé, c'est vraiment rapide, au-delà de mes attentes. Il s'agit simplement d'alignement alors 4 octets comparaison. extrémité (strilen)
Si vous contrôlez l'allocation de la chaîne, vous pouvez vous assurer qu'il n'y a pas que l'octet d'octet Vous auriez besoin de itérer sur quelques octets normalement au début, jusqu'à ce que vous atteigniez une adresse alignée sur une limite de x octets. P> Le cas d'utilisation pour cela est gentil d'inexistant cependant: la quantité d'octets supplémentaires que vous devez allouer serait facilement plus que simplement stocker un simple entier de 4 ou 8 octets contenant la taille directement. Même si cela est important pour vous pour une raison quelconque de cette chaîne peut être transmise uniquement en tant que pointeur, sans passer sa taille, je pense que la taille que les premiers octets de y pendant l'attribution pourraient être le plus rapide. Mais c'est déjà loin de l'optimisation Clarification: P> \ 0 code>, mais plusieurs dans une rangée en fonction de la taille maximale des instructions de vecteur pour votre plate-forme. Ensuite, vous pouvez écrire le même algorithme O (n) à l'aide de x octets à une heure comparant 0, rendant strylen code> amortizé O (n / x). Notez que la quantité de supplément \ 0 code> octets ne serait pas égale à la quantité d'octets sur laquelle vos instructions de vecteur fonctionnent (x), mais plutôt 2 * x - 1, car une région alignée doit être remplie de zéros. Strlen code> que vous posez sur vous. P> the_size | the string ...
^
the pointer to the string
Sûr.
retour 4; . Garanti d'être un éclair rapide! Le nombre a été choisi par le rouleau de dés juste.@Geo mignon , mais cela ne met pas en œuvre
SHLEN pour la grande majorité de contributions.