Time Complexity for substr() function

Discussion in 'Perl Misc' started by Walter Roberson, May 13, 2004.

  1. In article <>,
    Edward Wijaya <> wrote:
    :Any idea of the time complexity of the substr()
    :in Perl?

    :Is it under linear time?

    :Any reference I can go to for that?

    There's always the source...

    perl knows the length of strings. Strings are stored as arrays
    of characters, so whether you are going from the front or the back,
    it's a fairly simple address calculation and length calculation.
    Then it's just a matter of strncpy() and promoting the result
    to a perl variable structure.

    substr() is thus [near] constant-time with respect to the length of the
    original string, and linear with respect to the length of the
    extracted string.


    However, this calculation goes out the window when you are using
    unicode; I have never looked at the internal details of how
    unicode is handled. substr() is defined in terms of characters,
    not in terms of bytes, and the description of length() makes it clear
    that the two are not the same.
    --
    Live it up, rip it up, why so lazy?
    Give it out, dish it out, let's go crazy, yeah!
    -- Supertramp (The USENET Song)
     
    Walter Roberson, May 13, 2004
    #1
    1. Advertising

  2. Hi,

    Any idea of the time complexity of the substr()
    in Perl?

    Is it under linear time?

    Any reference I can go to for that?

    Thanks for your time.
    Hope to hear from you again.

    Regards
    Edward WIJAYA
    SINGAPORE

    --
    Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
     
    Edward Wijaya, May 13, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Time Complexity

    , Jul 11, 2006, in forum: C Programming
    Replies:
    9
    Views:
    448
    Martin Ambuhl
    Jul 11, 2006
  2. Replies:
    2
    Views:
    662
    red floyd
    Jun 12, 2006
  3. tfelb

    Missing removeStr and substr function

    tfelb, Nov 26, 2007, in forum: C Programming
    Replies:
    13
    Views:
    616
    Harald van Dijk
    Dec 6, 2007
  4. Veli-Pekka Tätilä
    Replies:
    6
    Views:
    114
    Anno Siegel
    Aug 23, 2005
  5. Stu

    substr taking time

    Stu, Aug 23, 2006, in forum: Perl Misc
    Replies:
    4
    Views:
    131
    John W. Krahn
    Aug 24, 2006
Loading...

Share This Page