Difference between revisions of "Sequence"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(Types: clarify; examples)
(Added Basics sidebar)
 
(13 intermediate revisions by one user not shown)
Line 1: Line 1:
A '''sequence''' is any object or data structure that stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, <code>str</code>, and <code>range</code>. By contrast, [[set]]s and [[dictionary|dictionaries]], while they share some common features with sequences, are ''not'' themselves sequences. Sequences always support [[iteration]] (though not all iterable types are necessarily sequences) and a set of other basic operations.
+
{{C-class}} {{Basics sidebar}}
 +
A '''sequence''' is any object or data structure that stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, <code>str</code>, and <code>range</code>. By contrast, [[set]]s and [[dictionary|dictionaries]], while they share some common features with sequences, are ''not'' themselves sequences because they are unordered.
 +
 
 +
Sequences always support [[iteration#For loop|iteration]] (though not all iterable types are necessarily sequences) and a set of other basic operations.
  
 
== Types ==
 
== Types ==
Line 19: Line 22:
  
 
=== List ===
 
=== List ===
A <code>list</code> also stores elements of any type. Lists behave much like tuples, except lists are mutable (see below). A list is created by enclosing comma-separated values in brackets:
+
A <code>list</code> also stores elements of any type. Lists behave much like tuples, except lists are mutable (see [[#Mutable sequences|below]]). A list is created by enclosing comma-separated values in brackets:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
lst = [1, 2, 3]
 
lst = [1, 2, 3]
</syntaxhighlight> Alternatively, a list can be constructed by calling <code>list(s)</code> for some sequence <code>s</code>.
+
</syntaxhighlight> Alternatively, a list can be constructed by calling <code>list(s)</code> for some sequence <code>s</code>. In addition a list can be created by a [[list comprehension]].
 +
 
 +
=== Range ===
 +
A range is a sequence that contains integers in a specified interval. A range object is constructed by <code>range(start, end, size)</code>, which creates a sequence containing the integers from <code>start</code> to <code>end - 1</code>, with a step size of <code>size</code>. The third argument is optional. If the first and third arguments are not provided, the start value defaults to 0.
  
 
== Operations ==
 
== Operations ==
Line 31: Line 37:
 
Elements in a sequence are organized by ''index'', an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called ''zero-based indexing''. Note that Python also allows ''negative'' indices for convenience. The last element is at -1, the second to last at -2, and so on.
 
Elements in a sequence are organized by ''index'', an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called ''zero-based indexing''. Note that Python also allows ''negative'' indices for convenience. The last element is at -1, the second to last at -2, and so on.
  
A particular element <code>x</code> in a sequence <code>s</code> can be retrieved with <code>s[i]</code>, where <code>i</code> is the index of <code>x</code>. Note that this returns, but does not remove, the element <code>x</code>. Negative indices are permissible.
+
A particular element <code>x</code> in a sequence <code>s</code> can be retrieved with <code>s[i]</code>, where <code>i</code> is the index of <code>x</code>. Note that this returns, but does not remove, the element <code>x</code>. Negative indices are permissible. If <code>i</code> is out of the bounds of the sequence, Python will throw an error.
  
 
=== Slicing ===
 
=== Slicing ===
Indices are also used to return a ''slice'' of the sequence. For a sequence <code>s</code>, create a slice with the format <code>s[start:end:step]</code>. This will return a subsequence that begins with the element at index <code>start</code>, ends with the element at index <code>end - 1</code>, counting indices by <code>step</code>. If not specified <code>start</code> defaults to 0, <code>end</code> defaults to <code>len(s)</code>, and <code>step</code> defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,
+
Indices are also used to return a ''slice'' of the sequence. For a sequence <code>s</code>, create a slice with the syntax <code>s[start:end:step]</code>. This will return a new sequence that begins with the element at index <code>start</code>, ends with the element at index <code>end - 1</code>, counting indices by <code>step</code>. If not specified <code>start</code> defaults to 0, <code>end</code> defaults to <code>len(s)</code>, and <code>step</code> defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
>>> s = "abababab"
 
>>> s = "abababab"
 
>>> s[:-2:2]
 
>>> s[:-2:2]
 
"aaa"
 
"aaa"
 +
</syntaxhighlight>
 +
If no indices overlap with the specified slice, an empty sequence is returned. Example:
 +
<syntaxhighlight lang="python">
 +
>>> s = [1, 2, 3]
 +
>>> s[3:]
 +
[]
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 67: Line 79:
  
 
== Mutable sequences ==
 
== Mutable sequences ==
The only built-in [[mutable types|mutable]] sequence type in Python is the <code>list</code>. In addition to the common sequence operations, lists support internal modification. For example,
+
The only built-in [[mutable types|mutable]] sequence type in Python is the <code>list</code>. In addition to the common sequence operations, lists support internal modification.
  
 +
=== Element assignment ===
 +
An element at index <code>i</code> of list <code>lst</code> can be reassigned to <code>c</code> by <code>lst[i] = c</code>. Example:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
>>> lst = [1, 2, 3]
 
>>> lst = [1, 2, 3]
>>> lst[0] = 5
+
>>> lst[0] = 5 # replaces first element of lst
 
>>> lst
 
>>> lst
 
[5, 2, 3]
 
[5, 2, 3]
 
</syntaxhighlight>
 
</syntaxhighlight>
  
This piece of code creates <code>lst</code> and replaces its first element. As opposed to concatenation and slicing, which leave the original unchanged and create new sequence objects with the specified modification, this changes the original list object itself.
+
=== Slice assignment ===
 
+
A slice of list <code>s</code> can be reassigned to other values. Examples:
Other operations which change the list object include <code>append</code>, which takes in one argument and inserts that at the end of the list,
+
<syntaxhighlight lang="python">
 +
>>> lst = [1, 2, 3]
 +
>>> lst[0:2] = 5, 6
 +
>>> lst
 +
[5, 6, 3]
 +
>>> lst[0:0] = 1, 2
 +
>>> lst
 +
[1, 2, 5, 6, 3]
 +
</syntaxhighlight>
  
 +
=== <code>append</code> ===
 +
<code>append</code> takes in one argument and inserts it at the end of the list. Example:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 +
>>> lst = [5, 2, 3]
 
>>> lst.append(5)
 
>>> lst.append(5)
 
>>> lst
 
>>> lst
Line 86: Line 111:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
<code>remove</code>, which takes in one argument and removes the first instance of it from the list,
+
=== <code>remove</code> and <code>pop</code> ===
 
+
<code>remove</code> takes in one argument and removes the first instance of it from the list. Example:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 +
>>> lst = [5, 2, 3, 5]
 
>>> lst.remove(5)
 
>>> lst.remove(5)
 
>>> lst
 
>>> lst
Line 94: Line 120:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
and <code>pop</code>, which removes and returns the last element if it is not passed any additional arguments, or removes the element at index <code>i</code> for integer <code>i</code>
+
<code>pop</code> removes and returns the last element if it is not passed any additional arguments, or removes and returns the element at index <code>i</code>. Example:
 
+
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 +
>>> lst = [2, 3, 5]
 
>>> lst.pop()
 
>>> lst.pop()
 
5
 
5
Line 107: Line 133:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
=== <code>sort</code> and <code>reverse</code> ===
 
Other built-in methods that rely upon mutability include <code>sort</code> which sorts the given list ''in-place'' (modifies the original object), and <code>reverse</code>, which reverses a list in-place.
 
Other built-in methods that rely upon mutability include <code>sort</code> which sorts the given list ''in-place'' (modifies the original object), and <code>reverse</code>, which reverses a list in-place.
 +
 +
== Copying techniques ==
 +
There are several methods to make a shallow copy of a sequence <code>s</code>:
 +
* <code>s[:]</code>
 +
* <code>constructor(s)</code>, where <code>constructor</code> is the relevant constructor for the sequence
 +
* <code>s + empty_sequence</code>, where <code>empty_sequence</code> is the syntax for an empty version of the sequence
 +
* <code>s * 1</code>
 +
 +
Example:
 +
<syntaxhighlight lang="python">
 +
>>> s = [1, 2, 3]
 +
>>> copy1 = s[:]
 +
>>> copy2 = list(s)
 +
>>> copy3 = s + []
 +
>>> copy4 = s * 1
 +
>>> copy1
 +
[1, 2, 3]
 +
>>> copy2
 +
[1, 2, 3]
 +
>>> copy3
 +
[1, 2, 3]
 +
>>> copy4
 +
[1, 2, 3]
 +
>>> (copy1 is not s) and (copy2 is not s) and (copy3 is not s) and (copy4 is not s)
 +
True
 +
</syntaxhighlight>

Latest revision as of 11:04, 9 July 2014

A sequence is any object or data structure that stores and accesses elements in a fixed order. Built-in sequence types include list, tuple, str, and range. By contrast, sets and dictionaries, while they share some common features with sequences, are not themselves sequences because they are unordered.

Sequences always support iteration (though not all iterable types are necessarily sequences) and a set of other basic operations.

Types

String

A string (str) is a sequence whose elements are characters (letters, symbols, or spaces). A string is surrounded by single quotes, double quotes, or a trio of double quotes:

str = 'test'
str = "test"
str = """test"""

Tuple

A tuple is a sequence that stores elements of any type. A tuple is created by enclosing comma-separated values in parentheses:

tup = (1, 2, 3)
A one-element tuple is created by:
tup = (1,) # (1) would be interpreted as an integer

Alternatively, a tuple can be constructed by calling tuple(s) for some sequence s.

List

A list also stores elements of any type. Lists behave much like tuples, except lists are mutable (see below). A list is created by enclosing comma-separated values in brackets:

lst = [1, 2, 3]
Alternatively, a list can be constructed by calling list(s) for some sequence s. In addition a list can be created by a list comprehension.

Range

A range is a sequence that contains integers in a specified interval. A range object is constructed by range(start, end, size), which creates a sequence containing the integers from start to end - 1, with a step size of size. The third argument is optional. If the first and third arguments are not provided, the start value defaults to 0.

Operations

Length

The number of elements in a sequence s is given by len(s).

Indices and accessing

Elements in a sequence are organized by index, an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called zero-based indexing. Note that Python also allows negative indices for convenience. The last element is at -1, the second to last at -2, and so on.

A particular element x in a sequence s can be retrieved with s[i], where i is the index of x. Note that this returns, but does not remove, the element x. Negative indices are permissible. If i is out of the bounds of the sequence, Python will throw an error.

Slicing

Indices are also used to return a slice of the sequence. For a sequence s, create a slice with the syntax s[start:end:step]. This will return a new sequence that begins with the element at index start, ends with the element at index end - 1, counting indices by step. If not specified start defaults to 0, end defaults to len(s), and step defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,

>>> s = "abababab"
>>> s[:-2:2]
"aaa"

If no indices overlap with the specified slice, an empty sequence is returned. Example:

>>> s = [1, 2, 3]
>>> s[3:]
[]

Concatenation

Two sequences of the same type can be concatenated together with the addition operator, which returns a new sequence containing all the elements in the first sequence followed by all the elements in the second. For example, (1, 2) + (3, 4) returns (1, 2, 3, 4).

Membership test

For sequence s, x in s returns True if x is an element of s. x not in s returns the inverse: returns True if x is not an element of s. For example:

>>> 1 in [1, 2, 3]
True
>>> 1 not in [1, 2, 3]
False

For strings, in and not in act like a substring test. For example:

>>> 'abc' in 'abcde'
True

Shallow copy

For sequence s and integer n, s * n returns n shallow copies of s concatenated. For example:

>>> 'hi ' * 3
'hi hi hi '

Mutable sequences

The only built-in mutable sequence type in Python is the list. In addition to the common sequence operations, lists support internal modification.

Element assignment

An element at index i of list lst can be reassigned to c by lst[i] = c. Example:

>>> lst = [1, 2, 3]
>>> lst[0] = 5 # replaces first element of lst
>>> lst
[5, 2, 3]

Slice assignment

A slice of list s can be reassigned to other values. Examples:

>>> lst = [1, 2, 3]
>>> lst[0:2] = 5, 6
>>> lst
[5, 6, 3]
>>> lst[0:0] = 1, 2
>>> lst
[1, 2, 5, 6, 3]

append

append takes in one argument and inserts it at the end of the list. Example:

>>> lst = [5, 2, 3]
>>> lst.append(5)
>>> lst
[5, 2, 3, 5]

remove and pop

remove takes in one argument and removes the first instance of it from the list. Example:

>>> lst = [5, 2, 3, 5]
>>> lst.remove(5)
>>> lst
[2, 3, 5]

pop removes and returns the last element if it is not passed any additional arguments, or removes and returns the element at index i. Example:

>>> lst = [2, 3, 5]
>>> lst.pop()
5
>>> lst
[2, 3]
>>> lst.pop(0)
2
>>> lst
[3]

sort and reverse

Other built-in methods that rely upon mutability include sort which sorts the given list in-place (modifies the original object), and reverse, which reverses a list in-place.

Copying techniques

There are several methods to make a shallow copy of a sequence s:

  • s[:]
  • constructor(s), where constructor is the relevant constructor for the sequence
  • s + empty_sequence, where empty_sequence is the syntax for an empty version of the sequence
  • s * 1

Example:

>>> s = [1, 2, 3]
>>> copy1 = s[:]
>>> copy2 = list(s)
>>> copy3 = s + []
>>> copy4 = s * 1
>>> copy1
[1, 2, 3]
>>> copy2
[1, 2, 3]
>>> copy3
[1, 2, 3]
>>> copy4
[1, 2, 3]
>>> (copy1 is not s) and (copy2 is not s) and (copy3 is not s) and (copy4 is not s)
True