<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>In-Memory Data Structures — Python Module of the Week</title>
<link rel="stylesheet" href="../_static/sphinxdoc.css" type="text/css" />
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../',
VERSION: '1.132',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="../_static/jquery.js"></script>
<script type="text/javascript" src="../_static/underscore.js"></script>
<script type="text/javascript" src="../_static/doctools.js"></script>
<link rel="author" title="About these documents" href="../about.html" />
<link rel="top" title="Python Module of the Week" href="../index.html" />
<link rel="up" title="Features of the Standard Library" href="index.html" />
<link rel="next" title="File Access" href="file_access.html" />
<link rel="prev" title="Data Persistence and Exchange" href="data_persistence.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="file_access.html" title="File Access"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="data_persistence.html" title="Data Persistence and Exchange"
accesskey="P">previous</a> |</li>
<li><a href="../contents.html">PyMOTW</a> »</li>
<li><a href="index.html" accesskey="U">Features of the Standard Library</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="../contents.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">In-Memory Data Structures</a><ul>
<li><a class="reference internal" href="#array">array</a></li>
<li><a class="reference internal" href="#sorting">Sorting</a></li>
<li><a class="reference internal" href="#queue">Queue</a></li>
<li><a class="reference internal" href="#collections">collections</a></li>
<li><a class="reference internal" href="#decoding-data">Decoding Data</a></li>
<li><a class="reference internal" href="#custom-variations">Custom Variations</a></li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="data_persistence.html"
title="previous chapter">Data Persistence and Exchange</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="file_access.html"
title="next chapter">File Access</a></p>
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/articles/data_structures.txt"
rel="nofollow">Show Source</a></li>
</ul>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="../search.html" method="get">
<input type="text" name="q" size="18" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="in-memory-data-structures">
<span id="article-data-structures"></span><h1>In-Memory Data Structures<a class="headerlink" href="#in-memory-data-structures" title="Permalink to this headline">¶</a></h1>
<p>Python includes several standard programming data structures as <a class="reference external" href="http://docs.python.org/library/stdtypes.html">built-in types</a> (list, tuple, dictionary, and set). Most applications won’t need any other structures, but when they do the standard library delivers.</p>
<div class="section" id="array">
<h2>array<a class="headerlink" href="#array" title="Permalink to this headline">¶</a></h2>
<p>For large amounts of data, it may be more efficient to use an <a class="reference internal" href="../array/index.html#module-array" title="array: Manage sequences of fixed-type numerical data efficiently."><tt class="xref py py-mod docutils literal"><span class="pre">array</span></tt></a> instead of a <tt class="docutils literal"><span class="pre">list</span></tt>. Since the array is limited to a single data type, it can use a more compact memory representation than a general purpose list. As an added benefit, arrays can be manipulated using many of the same methods as a list, so it may be possible to replaces lists with arrays in to your application without a lot of other changes.</p>
</div>
<div class="section" id="sorting">
<h2>Sorting<a class="headerlink" href="#sorting" title="Permalink to this headline">¶</a></h2>
<p>If you need to maintain a sorted list as you add and remove values, check out <a class="reference internal" href="../heapq/index.html#module-heapq" title="heapq: In-place heap sort algorithm"><tt class="xref py py-mod docutils literal"><span class="pre">heapq</span></tt></a>. By using the functions in <a class="reference internal" href="../heapq/index.html#module-heapq" title="heapq: In-place heap sort algorithm"><tt class="xref py py-mod docutils literal"><span class="pre">heapq</span></tt></a> to add or remove items from a list, you can maintain the sort order of the list with low overhead.</p>
<p>Another option for building sorted lists or arrays is <a class="reference internal" href="../bisect/index.html#module-bisect" title="bisect: Maintains a list in sorted order without having to call sort each time an item is added to the list."><tt class="xref py py-mod docutils literal"><span class="pre">bisect</span></tt></a>. bisect uses a binary search to find the insertion point for new items, and is an alternative to repeatedly sorting a list that changes frequently.</p>
</div>
<div class="section" id="queue">
<h2>Queue<a class="headerlink" href="#queue" title="Permalink to this headline">¶</a></h2>
<p>Although the built-in list can simulate a queue using the <tt class="docutils literal"><span class="pre">insert()</span></tt> and <tt class="docutils literal"><span class="pre">pop()</span></tt> methods, it isn’t thread-safe. For true ordered communication between threads you should use a <a class="reference internal" href="../Queue/index.html#module-Queue" title="Queue: Provides a thread-safe FIFO implementation"><tt class="xref py py-mod docutils literal"><span class="pre">Queue</span></tt></a>. <a class="reference internal" href="../multiprocessing/index.html#module-multiprocessing" title="multiprocessing: Manage processes like threads."><tt class="xref py py-mod docutils literal"><span class="pre">multiprocessing</span></tt></a> includes a version of a Queue that works between processes, making it easier to port between the modules.</p>
</div>
<div class="section" id="collections">
<h2>collections<a class="headerlink" href="#collections" title="Permalink to this headline">¶</a></h2>
<p><a class="reference internal" href="../collections/index.html#module-collections" title="collections: Container data types."><tt class="xref py py-mod docutils literal"><span class="pre">collections</span></tt></a> includes implementations of several data structures that extend those found in other modules. For example, Deque is a double-ended queue, and allows you to add or remove items from either end. The <tt class="docutils literal"><span class="pre">defaultdict</span></tt> is a dictionary that responds with a default value if a key is missing. And <tt class="docutils literal"><span class="pre">namedtuple</span></tt> extends the normal tuple to give each member item an attribute name in addition to a numerical index.</p>
</div>
<div class="section" id="decoding-data">
<h2>Decoding Data<a class="headerlink" href="#decoding-data" title="Permalink to this headline">¶</a></h2>
<p>If you are working with data from another application, perhaps coming from a binary file or stream of data, you will find <a class="reference internal" href="../struct/index.html#module-struct" title="struct: Convert between strings and binary data."><tt class="xref py py-mod docutils literal"><span class="pre">struct</span></tt></a> useful for decoding the data into Python’s native types for easier manipulation.</p>
</div>
<div class="section" id="custom-variations">
<h2>Custom Variations<a class="headerlink" href="#custom-variations" title="Permalink to this headline">¶</a></h2>
<p>And finally, if the available types don’t give you what you need, you may want to subclass one of the native types and customize it. You can also start from scratch by using the abstract base classes defined in <a class="reference internal" href="../collections/index.html#module-collections" title="collections: Container data types."><tt class="xref py py-mod docutils literal"><span class="pre">collections</span></tt></a>.</p>
</div>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="file_access.html" title="File Access"
>next</a> |</li>
<li class="right" >
<a href="data_persistence.html" title="Data Persistence and Exchange"
>previous</a> |</li>
<li><a href="../contents.html">PyMOTW</a> »</li>
<li><a href="index.html" >Features of the Standard Library</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright Doug Hellmann.
Last updated on Oct 24, 2010.
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a>.
<br/><a href="http://creativecommons.org/licenses/by-nc-sa/3.0/us/" rel="license"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-nc-sa/3.0/us/88x31.png"/></a>
</div>
</body>
</html>