Preallocate python list with tuples?

Question

I'm still figuring out tuples in Python. If I'm creating a list of tuples, which I can't do via list comprehension, should I preallocate the list with some object? Or should I just append tuples as I go along? I currently have:

def get_priorities(words):
    priorities = [0]*len(words)

    for idx, word in enumerate(words):

        # ...calculate priority using word...

        priorities[idx] = (word, priority)

    return set(priorities)

Should I replace [0]*len(words) with just [] and append a tuple for each item in the loop? Which would be faster? I assume the compiler would have to reallocate storage in either instance.

You don't have to pre-allocate anything. Just use `append` (even in your example). `priorities.append((word, priority))`. — Two-Bit Alchemist, Apr 16 '14 at 20:47
He has to preallocate it to at least an empty list. `priorities=[]` (then use append) — anana, Apr 16 '14 at 20:50
@anana I wouldn't really call that "pre-allocating", but sure. You can't `append` to an undeclared variable. — Two-Bit Alchemist, Apr 16 '14 at 21:13

score 2 · Answer 1 · answered Apr 16 '14 at 21:04

2

I may not fully understand your use case, but I'm not sure you need to pre-allocate anything. Wouldn't you get the same result by doing the following?

return set((word, calc_priority(word)) for word in words)

(Presuming, of course, that calc_priority() is a defined function).

answered Apr 16 '14 at 21:04

larsks

277,717
41
399
399

This makes much more sense. And pythonic! Although I was more curious about the storage/time complexity – Hari Ganesan Apr 16 '14 at 22:38

score 1 · Accepted Answer · edited May 23 '17 at 12:11

For this, I'll use the time complexities from the Python site: https://wiki.python.org/moin/TimeComplexity

Using append

def get_priorities(words):
    priorities = []
    for idx, word in enumerate(words):
        ...
        priorities.append(word, priority)
    return set(priorities)

This saves you the cost pre-allocating the array of size which takes O(nk) time 1 * len(words) in this case, but you substitute that for the cost of appending which according to the Python documents is O(1) on average, which should give a time complexity of O(n) where n is the length of the words for your for loop.

On the other hand using a yield to save memory / avoid re-reading while maintaining the same O(n) complexity (What does the "yield" keyword do in Python?):

def get_priorities(words):
    for idx, word in enumerate(words):
        ...
        yield (word, priority)

I would argue for the second approach because you don't need to allocate memory for the priorities list or risk the cost of an append. However, since you're using set, I take it that there are cases of duplicates that you're trying to eliminate? Using the set then would add an additional n to your running time so O(2n) in the first case and O(n) using the yield, though O(2n) is essentially n running time. Regardless, the cost of allocating priorities in the first case is O(1) if you allocate it as an empty list.

Thanks, I always forget about `yield`. – Hari Ganesan Apr 16 '14 at 22:40 — Hari Ganesan, Apr 16 '14 at 22:40

score 0 · Answer 3 · answered Apr 16 '14 at 21:00

A list of tuples is just a list. There is no need to work differently than you would work with a list of strings, integers or even more complex data structures like lists,dictionaries or objects. For more on lists and list comprehension (with examples) have a look here.

From the example that you have given I see that what you are trying to do is build a kind of dictionary that holds the word and the priority at a certain index in the list. I cannot really understand why would you convert everything into a set after you are done (logically there cannot be two words with the same index in a list, so there is no need to eliminate duplicates).

I do not know the use case for the above mentioned code, but from the looks of it you would be much better off using a dictionary where the words are the keys and the values are the priorities. This would allow also to eliminate duplicates (dictionaries do not allow multiple identical keys) and would be easy to use in retrieving per word priorities.

I'm not modifying this list later, and since tuples are immutable I assume they would allow for more efficient use later on (than using dicts). — Hari Ganesan, Apr 16 '14 at 22:22

score 0 · Answer 4 · edited Apr 16 '14 at 21:07

0

You can use both options.
If you want use indices (priorities[idx] = (word, priority)) then you must initialize list with n elements. But alternative with empty list (priorities = []) and append() would look better. I don't expect significant difference in speed between these two alternatives.
And by the way this question isn't about tuples. You can use lists this way with any other elements.

edited Apr 16 '14 at 21:07

askewchan

45,161
17
118
134

answered Apr 16 '14 at 21:02

Effect

85
5

You're right, it's not really about tuples. I was more curious how the compiler would adjust how the list was stored given the two options and if one was faster. – Hari Ganesan Apr 16 '14 at 22:24

Preallocate python list with tuples?

4 Answers4