1
votes

Comment déterminer si une chaîne est trop longue en complexité temporelle O (1)?

J'essaie de voir si une chaîne contient plus de 10 000 caractères. si c'est le cas, il devrait imprimer trop longtemps . Je sais que je peux le faire avec strlen , mais la complexité temporelle est O (n) , ce qui n'est pas trop mal, mais je dois encore parcourir 10000 caractères à chaque fois si quelqu'un entre 10 000 caractères, mais si quelqu'un entre 1 million de caractères, c'est un mauvais n . Ma solution est donc de vérifier si le 10 001e caractère est défini. S'il est défini, alors c'est évidemment trop long. Cela fonctionnerait-il? Ou cela fonctionnerait-il parfois (et dépend de la façon dont la mémoire a été / est allouée).

php strlen

0 commentaires

4 Réponses :

0
votes

Utilisez substr

substr(yourString, lengthConstraint, 1);

p >

0 commentaires

0
votes

<?php 
if (isset($str[100001])) { 
     ... do my stuff ... 
} ?> 
The isset function is run on $str[10001] which is only one address in the array, hence o[1]. Also, while accessing key out of index in php, it does not throw error or cause memory leak. It throws an OutOfBoundsException exception which can be caught with a try catch block.

5 commentaires

Peut-être expliquer cela.

@AbraCadaver, la fonction isset est exécutée sur $ str [10001] qui n'est qu'une seule adresse dans le tableau, d'où o [1]. En outre, l'accès au tableau hors de l'index dans la fonction isset ne génère aucune erreur.

Qu'en est-il de l'allocation de mémoire? Le résultat serait-il affecté? Par exemple, si la chaîne ne contient que 250 caractères et que nous recherchons le caractère 10001, il se peut qu'il y ait quelque chose en mémoire (données inutiles)

@Yuri, En fait, si vous avez le code dans un bloc try, php lancera une OutOfBoundsException à condition que vous l'attrapiez. Rien n'est ajouté dans la mémoire. Jetez un œil à ceci - stackoverflow.com/questions/8193798/…

Je connais l'explication, ajoutez-la à la réponse, pas seulement Cela pourrait fonctionner.

0
votes

strlen a déjà une complexité temporelle de O (1), du fait que la longueur est simplement stockée en tant qu'attribut.

http://php.net/manual/en/function.strlen.php

0 commentaires

1
votes

Je sais que je peux faire cela avec strlen, mais alors la complexité temporelle est O (n)

Je ne sais pas qui vous dit cela, strlen renvoie simplement la propriété len .

Définition de strlen , il utilise la macro ZSTR_LEN ZSTR_LEN obtenir la longueur de la chaîne
#define ZSTR_LEN(zstr) (zstr)->len
Et la définition de ZSTR_LEN
ZEND_FUNCTION(strlen)
{
    zend_string *s;

    ZEND_PARSE_PARAMETERS_START(1, 1)
        Z_PARAM_STR(s)
    ZEND_PARSE_PARAMETERS_END();

    RETVAL_LONG(ZSTR_LEN(s));
}

1 commentaires

J'ai appris en c . Et on m'a dit que dans c strlen est O (n). J'ai supposé que ce serait la même chose en php