陣列(Array)

Da-Wei Chiang

大綱

  • 何謂陣列
  • 串列與陣列的差異
  • 陣列的基本概念
  • 陣列的時間複雜度

何謂陣列

  • 將相同資料型態的資料儲存於一塊連續的記憶體空間中

串列與陣列的差異

  • 存放資料的彈性度
  • 底層存放資料的記憶體配置
  • 執行速度的快慢

陣列的基本概念

  • 讀取、新增、刪除

實作陣列結構(Python已有Array結構可直接引用)

引用陣列結構

from array import *
In [1]:
from array import *

help(array)
Help on class array in module array:

class array(builtins.object)
 |  array(typecode [, initializer]) -> array
 |  
 |  Return a new array whose items are restricted by typecode, and
 |  initialized from the optional initializer value, which must be a list,
 |  string or iterable over elements of the appropriate type.
 |  
 |  Arrays represent basic values and behave very much like lists, except
 |  the type of objects stored in them is constrained. The type is specified
 |  at object creation time by using a type code, which is a single character.
 |  The following type codes are defined:
 |  
 |      Type code   C Type             Minimum size in bytes 
 |      'b'         signed integer     1 
 |      'B'         unsigned integer   1 
 |      'u'         Unicode character  2 (see note) 
 |      'h'         signed integer     2 
 |      'H'         unsigned integer   2 
 |      'i'         signed integer     2 
 |      'I'         unsigned integer   2 
 |      'l'         signed integer     4 
 |      'L'         unsigned integer   4 
 |      'q'         signed integer     8 (see note) 
 |      'Q'         unsigned integer   8 (see note) 
 |      'f'         floating point     4 
 |      'd'         floating point     8 
 |  
 |  NOTE: The 'u' typecode corresponds to Python's unicode character. On 
 |  narrow builds this is 2-bytes on wide builds this is 4-bytes.
 |  
 |  NOTE: The 'q' and 'Q' type codes are only available if the platform 
 |  C compiler used to build Python supports 'long long', or, on Windows, 
 |  '__int64'.
 |  
 |  Methods:
 |  
 |  append() -- append a new item to the end of the array
 |  buffer_info() -- return information giving the current memory info
 |  byteswap() -- byteswap all the items of the array
 |  count() -- return number of occurrences of an object
 |  extend() -- extend array by appending multiple elements from an iterable
 |  fromfile() -- read items from a file object
 |  fromlist() -- append items from the list
 |  frombytes() -- append items from the string
 |  index() -- return index of first occurrence of an object
 |  insert() -- insert a new item into the array at a provided position
 |  pop() -- remove and return item (default last)
 |  remove() -- remove first occurrence of an object
 |  reverse() -- reverse the order of the items in the array
 |  tofile() -- write all items to a file object
 |  tolist() -- return the array converted to an ordinary list
 |  tobytes() -- return the array converted to a string
 |  
 |  Attributes:
 |  
 |  typecode -- the typecode character used to create the array
 |  itemsize -- the length in bytes of one array item
 |  
 |  Methods defined here:
 |  
 |  __add__(self, value, /)
 |      Return self+value.
 |  
 |  __contains__(self, key, /)
 |      Return key in self.
 |  
 |  __copy__(self, /)
 |      Return a copy of the array.
 |  
 |  __deepcopy__(self, unused, /)
 |      Return a copy of the array.
 |  
 |  __delitem__(self, key, /)
 |      Delete self[key].
 |  
 |  __eq__(self, value, /)
 |      Return self==value.
 |  
 |  __ge__(self, value, /)
 |      Return self>=value.
 |  
 |  __getattribute__(self, name, /)
 |      Return getattr(self, name).
 |  
 |  __getitem__(self, key, /)
 |      Return self[key].
 |  
 |  __gt__(self, value, /)
 |      Return self>value.
 |  
 |  __iadd__(self, value, /)
 |      Implement self+=value.
 |  
 |  __imul__(self, value, /)
 |      Implement self*=value.
 |  
 |  __iter__(self, /)
 |      Implement iter(self).
 |  
 |  __le__(self, value, /)
 |      Return self<=value.
 |  
 |  __len__(self, /)
 |      Return len(self).
 |  
 |  __lt__(self, value, /)
 |      Return self<value.
 |  
 |  __mul__(self, value, /)
 |      Return self*value.
 |  
 |  __ne__(self, value, /)
 |      Return self!=value.
 |  
 |  __reduce_ex__(self, value, /)
 |      Return state information for pickling.
 |  
 |  __repr__(self, /)
 |      Return repr(self).
 |  
 |  __rmul__(self, value, /)
 |      Return value*self.
 |  
 |  __setitem__(self, key, value, /)
 |      Set self[key] to value.
 |  
 |  __sizeof__(self, /)
 |      Size of the array in memory, in bytes.
 |  
 |  append(self, v, /)
 |      Append new value v to the end of the array.
 |  
 |  buffer_info(self, /)
 |      Return a tuple (address, length) giving the current memory address and the length in items of the buffer used to hold array's contents.
 |      
 |      The length should be multiplied by the itemsize attribute to calculate
 |      the buffer length in bytes.
 |  
 |  byteswap(self, /)
 |      Byteswap all items of the array.
 |      
 |      If the items in the array are not 1, 2, 4, or 8 bytes in size, RuntimeError is
 |      raised.
 |  
 |  count(self, v, /)
 |      Return number of occurrences of v in the array.
 |  
 |  extend(self, bb, /)
 |      Append items to the end of the array.
 |  
 |  frombytes(self, buffer, /)
 |      Appends items from the string, interpreting it as an array of machine values, as if it had been read from a file using the fromfile() method).
 |  
 |  fromfile(self, f, n, /)
 |      Read n objects from the file object f and append them to the end of the array.
 |  
 |  fromlist(self, list, /)
 |      Append items to array from list.
 |  
 |  fromstring(self, buffer, /)
 |      Appends items from the string, interpreting it as an array of machine values, as if it had been read from a file using the fromfile() method).
 |      
 |      This method is deprecated. Use frombytes instead.
 |  
 |  fromunicode(self, ustr, /)
 |      Extends this array with data from the unicode string ustr.
 |      
 |      The array must be a unicode type array; otherwise a ValueError is raised.
 |      Use array.frombytes(ustr.encode(...)) to append Unicode data to an array of
 |      some other type.
 |  
 |  index(self, v, /)
 |      Return index of first occurrence of v in the array.
 |  
 |  insert(self, i, v, /)
 |      Insert a new item v into the array before position i.
 |  
 |  pop(self, i=-1, /)
 |      Return the i-th element and delete it from the array.
 |      
 |      i defaults to -1.
 |  
 |  remove(self, v, /)
 |      Remove the first occurrence of v in the array.
 |  
 |  reverse(self, /)
 |      Reverse the order of the items in the array.
 |  
 |  tobytes(self, /)
 |      Convert the array to an array of machine values and return the bytes representation.
 |  
 |  tofile(self, f, /)
 |      Write all items (as machine values) to the file object f.
 |  
 |  tolist(self, /)
 |      Convert array to an ordinary list with the same items.
 |  
 |  tostring(self, /)
 |      Convert the array to an array of machine values and return the bytes representation.
 |      
 |      This method is deprecated. Use tobytes instead.
 |  
 |  tounicode(self, /)
 |      Extends this array with data from the unicode string ustr.
 |      
 |      Convert the array to a unicode string.  The array must be a unicode type array;
 |      otherwise a ValueError is raised.  Use array.tobytes().decode() to obtain a
 |      unicode string from an array of some other type.
 |  
 |  ----------------------------------------------------------------------
 |  Static methods defined here:
 |  
 |  __new__(*args, **kwargs) from builtins.type
 |      Create and return a new object.  See help(type) for accurate signature.
 |  
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |  
 |  itemsize
 |      the size, in bytes, of one array item
 |  
 |  typecode
 |      the typecode character used to create the array
 |  
 |  ----------------------------------------------------------------------
 |  Data and other attributes defined here:
 |  
 |  __hash__ = None

建立、存取陣列

variable = array(typecode, [value1, value2, ...])   #create array
variable[index]   #get array value
In [16]:
#範例

from array import *

my_array = array('u', ['H', 'a'])   #建立陣列
print(my_array)
print(type(my_array))
print(type(my_array.tounicode()))
print("- - - - - - - - - - - - - - ")
print("存取陣列方法一:")
for i in my_array:
    print(i)
print("存取陣列方法二:")    
for i in range(len(my_array)):
    print(my_array[i])
print("- - - - - - - - - - - - - - ")
print(my_array.tounicode())
array('u', 'Ha')
<class 'array.array'>
<class 'str'>
- - - - - - - - - - - - - - 
存取陣列方法一:
H
a
存取陣列方法二:
H
a
- - - - - - - - - - - - - - 
Ha
In [9]:
#範例

from array import *

my_array = array('i', [1, 2, 3, 4, 5])   #建立陣列

print(type(my_array))
print(my_array.typecode)
print(my_array)
print("存取陣列方法一:")
for i in my_array:
    print(i)
print("存取陣列方法二:")  
for i in range(len(my_array)):
    print(my_array[i])
<class 'array.array'>
i
array('i', [1, 2, 3, 4, 5])
存取陣列方法一:
1
2
3
4
5
存取陣列方法二:
1
2
3
4
5

練習

  • 請讓使用者輸入一個單字, 並儲存於array
  • array中輸出該單字

插入資料

variable.insert(index, value)    
variable.append(value)
In [10]:
#範例

from array import *

my_array = array('i', [1, 2, 3, 4, 5]) 
my_array.insert(2, 100)
my_array.append(600)
for i in my_array:
    print(i, end=" ")
1 2 100 3 4 5 600 

練習

請自行練習array的插入資料方法

刪除資料

variable.remove(value)
variale.pop()
In [19]:
# 範例

from array import *

my_array = array('i', [1, 2, 3, 4, 5]) 
my_array.pop()
print(my_array)
my_array.remove(3)
print(my_array)
array('i', [1, 2, 3, 4])
array('i', [1, 2, 4])

練習

  • 請建構一個array如下
    • [1, 4, 6, 2, 4, 3, 2, 4]
  • 請刪除所有4的元素, 並印出array

更新資料

array_variable[index] = data
In [4]:
# 範例

from array import *

my_array = array('i', [1, 2, 3, 4, 5]) 
my_array[2] = 10
print(my_array)
array('i', [1, 2, 10, 4, 5])

pythonarray

  • 適用於list的切片
  • 適用於pythonshadow copy
  • 適用於內建函數sum, max, min...等等

練習

  • 請讓使用者輸入一段數字
    • 列出儲存array的資料型態
    • 最大值
    • 最小值
    • 平均值
      例:
      輸入:1 2 3 4 5
      輸出:
        資料型態: <class 'array.array'>
        最大值: 5
        最小值: 1
        平均值: 3.0

練習

  • 請輸入兩組數組字串, 並將兩組數組字串合併為浮點數的array
輸入:
    數組字串1:1 2 3 4 5
    數組字串2:6 7 8 9 0
輸出:
    array('f', [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 0.0])

練習

  • 輸入一組字串數組儲存為浮點數array, 並輸出偶數的位置號碼及資料值
    輸入:
        數組:10 21 32 1 2
    輸出:
        (2, 21.0)
        (4, 1.0)

練習

  • 輸入一組字串數組儲存為整數array
  • 輸出
    • 資料型態
    • 反向輸出資料
    • 由大到小排序資料並輸出
      例:
      輸入:
        數組:1 6 2 5 3
      輸出:
        資料型態: <class 'array.array'>
        反向輸出: array('i', [3, 5, 2, 6, 1])
        由大到小排序: [6, 5, 3, 2, 1]

陣列的時間複雜度

  • 索引值存取內容
  • 插入新資料
  • 刪除資料

動腦時間 - 索引值存取內容 的時間複雜度為何?

索引值存取內容

  • 直接指定索引, 只需一個步驟即可取值. 故為O(1)

動腦時間 - 插入新資料 的時間複雜度為何?

插入新資料

  • 有足夠的記憶體空間插入資料時
    • 在插入的當下可能需搬動所有的元素. 故為O(n)
  • 沒有足夠的記憶體空間插入資料時
    • 需將所有資料搬到足夠的記憶體區塊. 故為O(n)

動腦時間 - 插入新資料 的時間複雜度為何?

刪除資料

  • 刪除完某元素資料後, 需將後方元素資料的記憶體空間往前搬. 故為O(n)