Skip to content

Resolved issue #174 by subdividing list idioms and replacing dict w/ set #576

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
sigmavirus24 merged 2 commits into from
Oct 3, 2015
Merged

Resolved issue #174 by subdividing list idioms and replacing dict w/ set #576

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
680f7d8
Resolved issue #174 by subdividing list idioms and replacing dict w/ set
emilydolson Oct 2, 2015
df255fa
Fixed typo + formatting
emilydolson Oct 3, 2015
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
47 changes: 36 additions & 11 deletions docs/writing/style.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -351,6 +351,8 @@ Instead, use a list comprehension:

four_lists = [[] for __ in xrange(4)]

Create a string from a list
~~~~~~~~~~~~~~~~~~~~~~~~~~~

A common idiom for creating strings is to use :py:meth:`str.join` on an empty
string.
Expand All @@ -363,30 +365,53 @@ string.
This will set the value of the variable *word* to 'spam'. This idiom can be
applied to lists and tuples.

Searching for an item in a collection
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Sometimes we need to search through a collection of things. Let's look at two
options: lists and dictionaries.
options: lists and sets.

Take the following code for example:

.. code-block:: python

d = {'s': [], 'p': [], 'a': [], 'm': []}
s = set(['s', 'p', 'a', 'm'])
l = ['s', 'p', 'a', 'm']

def lookup_dict(d):
return 's' in d
def lookup_set(s):
return 's' in s

def lookup_list(l):
return 's' in l

Even though both functions look identical, because *lookup_dict* is utilizing
the fact that dictionaries in Python are hashtables, the lookup performance
between the two is very different. Python will have to go through each item
in the list to find a matching case, which is time consuming. By analysing
the hash of the dictionary, finding keys in the dictionary can be done very
quickly. For more information see this
Even though both functions look identical, because *lookup_set* is utilizing
the fact that sets in Python are hashtables, the lookup performance
between the two is very different. To determine whether an item is in a list,
Python will have to go through each item until it finds a matching item.
This is time consuming, especially for long lists. In a set, on the other
hand, the hash of the item will tell Python where in the set to look for
a matching item. As a result, the search can be done quickly, even if the
set is large. Searching in dictionaries works the same way. For
more information see this
`StackOverflow <http://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table>`_
page.
page. For detailed information on the amount of time various common operations
take on each of these data structures, see
`this page <https://wiki.python.org/moin/TimeComplexity?>`_.

Because of these differences in performance, it is often a good idea to use
sets or dictionaries instead of lists in cases where:

* The collection will contain a large number of items

* You will be repeatedly searching for items in the collection

* You do not have duplicate items.

For small collections, or collections which you will not frequently be
searching through, the additional time and memory required to set up the
hashtable will often be greater than the time saved by the improved search
speed.


Zen of Python
-------------
Expand Down