Python Lists



  • Do lists in Python work like arrays or like linked lists?  I mean in terms of performance.  Is list[0] always as fast as list[1000], or does list.append(x) take constant time?

    Suppose I'm translating a string like "1234" into "onetwothreefour".  In C++ or Java I can think of three ways (in pseudocode that sort of mixes Java and C++):

    Slow:

       if (a == '1') then str = str + "one";

       else if (a == '2') then str = str + "two";  etc.

    Faster:

       Define a hashtable:  1 -> "one", 2 -> "two"

       strbuf.append(hashtable.lookup(a));

    Fastest:

       Array 1 contains pointers or refs to strings:  [ "zero", "one", "two", ...]

       Array 2 is a large array of char.  a2ix points to next unused one (plus other overhead to keep track of end).

       strcpy(array2 + a2ix, string at array1[a - '0']);  then point a2ix to next null byte.

    What's the fastest way in Python?

     



  • Depends on your implementation (AFAIK). At least CPython (what you get at python.org) has a Vector-like implementation (i.e. array of references).

    "The fastest way"™ in Python is in most cases to just write good code, using the appropriate data structures and the like. For your weird problem that would be something like:

    >>> digit_as_word = {'0': 'zero', '1': 'one', ..., '9': 'nine'}
    >>> ''.join( digit_as_word[x] for x in '1234' )
    'onetwothreefour'



  • @newfweiler said:

    Do lists in Python work like arrays or like linked lists?

    Yes

    And Radiation Dude approach to the problem looks good to me.


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.