Python - convert list into dictionary in order to reduce complexity
<p>Let's say I have a big list:</p>

<pre><code>word_list = [elt.strip() for elt in open("bible_words.txt", "r").readlines()] 
</code></pre>

<p><code>//complexity O(n) --&gt; proporcional to list length "n"</code></p>

<p>I have learned that <code>hash function</code> used for building up <code>dictionaries</code> allows <code>lookup</code> to be much faster, like so:</p>

<pre><code>word_dict = dict((elt, 1) for elt in word_list) 
</code></pre>

<p><code>// complexity O(l) ---&gt; constant.</code></p>

<p>using <code>word_list</code>, is there a <strong>most efficient way</strong> which is recommended to reduce the complexity of my code?</p>

<p>The code from the question does just one thing: fills all words from a file into a list. The complexity of that is O(n).</p>

<p>Filling the same words into any other type of container will still have at least O(n) complexity, because it has to read all of the words from the file and it has to put all of the words into the container.</p>

<h2>What is different with a <code>dict</code>?</h2>

<p>Finding out whether something is in a <code>list</code> has O(n) complexity, because the algorithm has to go through the list item by item and check whether it is the sought item. The item can be found at position 0, which is fast, or it could be the last item (or not in the list at all), which makes it O(n).</p>

<p>In <code>dict</code>, data is organized in <em>"buckets"</em>. When a key:value pair is saved to a <code>dict</code>, <code>hash</code> of the key is calculated and that number is used to identify the <em>bucket</em> into which data is stored. Later on, when the key is looked up, <code>hash(key)</code> is calculated again to identify the bucket and then only that bucket is searched. There is typically only one key:value pair per bucked, so the search can be done in O(1).</p>

<p>For more detils, see <a href="https://wiki.python.org/moin/DictionaryKeys" rel="nofollow">the article about DictionaryKeys on python.org</a>.</p>

<h2>How about a <code>set</code>?</h2>

<p>A set is something like a dictionary with only keys and no values. The question contains this code:</p>

<pre><code>word_dict = dict((elt, 1) for elt in word_list) 
</code></pre>

<p>That is obviously a dictionary which does not need values, so a set would be more appropriate.</p>

<p>BTW, there is no need to create a <code>word_list</code> which is a list first and convert it to <code>set</code> or <code>dict</code>. The first step can be skipped:</p>

<pre><code>set_of_words = {elt.strip() for elt in open("bible_words.txt", "r").readlines()}
</code></pre>

<h2>Are there any drawbacks?</h2>

<p>Always ;)</p>

<ul>
<li><p>A set does not have duplicates. So counting how many times a word is in the set will never return 2. If that is needed, don't use a set.</p></li>
<li><p>A set is not ordered. There is no way to check which was the first word in the set. If that is needed, don't use a set.</p></li>
<li><p>Objects saved to sets have to be hashable, which kind-of implies that they are immutable. If it was possible to modify the object, then its <em>hash</em> would change, so it would be in the wrong bucket and searching for it would fail. Anyway, <code>str</code>, <code>int</code>, <code>float</code>, and <code>tuple</code> objects are immutable, so at least those can go into sets.</p></li>
<li><p><strong>Writing</strong> to a set is probably going to be a bit slower than writing to a list. Still O(n), but a slower O(n), because it has to calculate hashes and organize into buckets, whereas a list just dumps one item after another. See timings below.</p></li>
<li><p><strong>Reading everything</strong> from a set is also going to be a bit slower than reading <strong>everything</strong> from a list.</p></li>
</ul>

<p>All of these apply to <code>dict</code> as well as to <code>set</code>.</p>

<h2>Some examples with timings</h2>

<p>Writing to list vs. set:</p>

<pre><code>&gt;&gt;&gt; timeit.timeit('[n for n in range(1000000)]', number=10)
0.7802875302271843
&gt;&gt;&gt; timeit.timeit('{n for n in range(1000000)}', number=10)
1.025623542189976
</code></pre>

<p>Reading from list vs. set:</p>

<pre><code>&gt;&gt;&gt; timeit.timeit('989234 in values', setup='values=[n for n in range(1000000)]', number=10)
0.19846207875508526
&gt;&gt;&gt; timeit.timeit('989234 in values', setup='values={n for n in range(1000000)}', number=10)
3.5699193290383846e-06
</code></pre>

<p>So, writing to a set seems to be about 30% slower, but finding an item in the set is thousands of times faster when there are thousands of items.</p>

python list dictionary asymptotic-complexity