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.