hi,你好!欢迎访问本站!登录
本站由简数采集腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

用最庞杂的体式格局学会数组(Python完成动态数组)

2019-11-18杂谈搜奇网32°c
A+ A-

Python序列范例的实质

在本博客中,我们将进修讨论Python的种种“序列”类,内置的三大经常运用数据组织——列表类(list)、元组类(tuple)和字符串类(str)的实质。

不晓得你发明没有,这些类都有一个很明显的共性,都可以用来保留多个数据元素,最主要的功用是:每一个类都支撑下标(索引)接见该序列的元素,比方运用语法 Seq[i]。实在上面每一个类都是运用 数组 这类简朴的数据组织示意。

然则熟习Python的读者可以晓得这3种数据组织又有一些差别:比方元组和字符串是不能修正的,列表可以修正。

计算机内存中的数组组织

计算机体系组织中,我们晓得计算机主存由位信息构成,这些位一般被归类成更大的单位,这些单位则取决于精准的体系架构。一个典范的单位就是一个字节,相当于8位。

计算机体系具有巨大数目标存储字节,那末怎样才找到我们的信息存在哪一个字节呢?答案就是人人日常平凡熟知的 存储地点 。基于存储地点,主存中的任何字节都能被有用的接见。现实上,每一个存储字节都和一个作为其地点的唯一二进制数字相干联。以下图中,每一个字节均被指定了存储地点:

一般来说,编程言语纪录标识符和其关联值所存储的地点之间的关联。比方,当我们声明标识符 \(x\) 就有可以和存储器中的某一值相干联,而标识符 \(y\)就可以和其他的值相干联。一组相干的变量可以一个接一个地存储在计算机存储器的一块一连地区内。我们将这类体式格局称为 数组

我们来看Python中的例子,一个文本字符串 HELLO 是以一列有序字符的情势存储的,假定该字符串的每一个Unicode字符须要两个字节的存储空间。最下面的数字就是该字符串的索引值。

我们可以看到,数组可以存储多个值而无需组织具有特定索引的多个变量来指定个中的每一个项目,而且几乎在一切编程言语(比方C、Java、C#、C++)中运用,然则Python更具有上风。Python在构建列表时,熟习的读者可以晓得,不须要预先定义数组或列表的大小,相反,在Python中,列表具有动态性子,我们可以不停的往列表中增添我们想要的数据元素。接下来,让我们看看Python列表的学问(已熟习的读者可以疾速阅读或许跳过)。

Python列表

Python列表的操纵

  • 建立列表的语法花样:

[ele1, ele2, ele3, ele4, ...]

  • 建立元组的语法花样:

(ele1, ele2, ele3, ele4, ...)

元组比列表的内存空间应用率更高,由于元组是牢固稳定的,所以没有必要建立具有盈余空间的动态数组。

我们先在Python的IDE中建立一个列表,然后大抵相识一下列表部份内置操纵,我们先建立了一个名为test_list的列表,然后修正(插进去或删除)元素,反转或清空列表,详细以下:

>>> test_list = []  # 建立名为test_list的空列表
>>> test_list.append("Hello")
>>> test_list.append("World")
>>> test_list
['Hello', 'World']
>>> test_list = ["Hello", "Array", 2019, "easy learning", "DataStructure"]  # 从新给test_list赋值
>>> len(test_list)  # 求列表的长度
5
>>> test_list[2] = 1024 # 修正列表元素
>>> test_list
['Hello', 'Array', 1024, 'easy learning', 'DataStructure']
>>>
>>> test_list.insert(1, "I love")   # 向列表中指定位置中插进去一个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure']
>>> test_list.append(2020)  # 向列表末端增添一个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure', 2020]
>>>
>>> test_list.pop(1)    # 删除指定位置的元素
'I love'
>>> test_list.remove(2020)  # 删除指定元素
>>> 
>>> test_list.index('Hello')    # 查找某个元素的索引值
0
>>> test_list.index('hello')    # 假如查找某个元素不在列表中,返回ValueError毛病
Traceback (most recent call last):
  File "<pyshell#11>", line 1, in <module>
    test_list.index('hello')
ValueError: 'hello' is not in list
>>> 
>>> test_list.reverse() # 反转全部列表
>>> test_list
['DataStructure', 'easy learning', 2019, 'Array', 'Hello']
>>> test_list.clear()   # 清空列表
>>> test_list
[]

我们看上面的代码,可以看到list的相干操纵——增编削查,已很壮大了,另有一些内置要领这里并没有做展现,留给读者本身去发明并体验。

Python列表的内存分派背地的基础学问

因而,让我们经由过程编码实践以及内存中保留的数组的现实大小与给定大小之间的关联来检察这类分外的空间演示。

前去Jupyter notebook举行演习。或许运用本身挑选的任何编辑器或开辟环境。复制下面编写的代码。

# 导入sys模块能轻易我们运用gestsizeof函数
import sys

# set n
n = 20
# set empty list
list = []
for i in range(n):
    a = len(list)
    # 挪用getsizeof函数用于给出Python中存储对象的实在字节数
    b = sys.getsizeof(list)
    print('Length:{0:3d}; Size of bytes:{1:4d}'.format(a, b))
    # Increase length by one
    list.append(n)

运转代码,可以看到以下输出:

如今,跟着我们增添列表的长度,字节也增添了。我们剖析一下,Length:1位置的元素填入列表时,字节数从64跳到96,增添了32个字节。由于本试验是在64位机械上运转的,这表明每一个内存地点是64位(即8个字节)。增添的32个字节即为分派的用于存储4个对象援用的数组大小。当增添第2个、第3个或许第4个元素时,内存占用没有任何转变。字节数96可以供应4个对象的援用。
\[ 96\ =\ 64\ +\ 8\ \times \ 4 \]
Length:10时,字节数从一最先的64跳到192,能存下16个对象的援用,
\[ 192\ =\ 64\ +\ 8\ \times \ 16 \]
一直到Length: 17后又最先跳转,所以理论上264个字节数应当可以存下25个对象
\[ 264\ =\ 64\ +\ 8\ \times \ 25 \]
但由于我们在代码中设置n=20,然后顺序就停止了。

我们可以看到Python内置的list类充足智能,晓得当须要分外的空间来分派数据时,它会为它们供应分外的大小,那末这究竟是怎样被完成的呢?

好吧,答案是动态数组。说到这里,不晓得人人学Python列表的时候是否是如许想的——列表很简朴嘛,就是list()类、用中括号[]括起来,然后指点书本或文档上的各种要领append、insert、pop...在种种IDE一顿操纵事后,是的我以为我学会了。

但实在背地的道理真的很不简朴,比方我举个例子:A[-1]这个操纵怎样完成?列表切片功用怎样完成?怎样本身写pop()默许删除列表最右侧的元素(popleft删除最左侧简朴)?...这些功用用起来爽,但真的本身完成太难了(我也还在进修中,大佬们请轻喷!)假如我们能进修并明白,一定可以增强我们对数组这一组织的明白。

动态数组

什么是动态数组

动态数组是内存的一连地区,其大小跟着插进去新数据而动态增进。在静态数组中,我们须要在分派时指定大小。在定义数组的时候,实在计算机已帮我们分派好了内存来存储,现实上我们不能扩大数组,由于它的大小是牢固的。比方:我们分派一个大小为10的数组,则不能插进去凌驾10个项目。

然则动态数组会在须要的时候自动调解其大小。这一点有点像我们运用的Python列表,可以存储恣意数目标项目,而无需在分派时指定大小。

所以完成一个动态数组的完成的关键是——怎样扩大数组?当列表list1的大小已满时,而此时有新的元素要增添进列表,我们会实行一下步骤来战胜其大小限定的瑕玷:

  1. 分派具有更大容量的新数组 list2
  2. 设置 list2[i] = list1[i] (i=0,1,2,...,n-1),个中n是该项目标当前编号
  3. 设置list1 = list2,也就是说,list2正在作为新的数组来援用我们的新列表。
  4. 然后,只要将新的元素插进去(增添)到我们的列表list1即可。

接下来要思索的问题是,新数组应当多大?一般我们得做法是:新数组的大小是已满的旧数组的2倍。我们将在Python中编程完成动态数组的观点,并建立一个简朴的代码,许多功用不及Python壮大。

完成动态数组的Python代码

在Python中,我们应用ctypes的内置库来建立本身的动态数组类,由于ctypes模块供应对原始数组的支撑,为了更快的对数组举行进修,所以对ctypes的学问可以检察官方文档举行进修。关于Python的公有要领与私有要领,我们在要领称号前运用双下划线**__**使其坚持隐蔽状况,代码以下:

# -*- coding: utf-8 -*-
# @Time      : 2019-11-01 17:10
# @Author    : yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File      : DynamicArray.py
# @Software  : PyCharm

import ctypes


class DynamicArray:
    """A dynamic array class akin to a simplified Python list."""

    def __init__(self):
        """Create an empty array."""
        self.n = 0             # count actual elements
        self.capacity = 1      # default array capacity
        self.A = self._make_array(self.capacity)      # low-level array

    def is_empty(self):
        """ Return True if array is empty"""
        return self.n == 0

    def __len__(self):
        """Return numbers of elements stored in the array."""
        return self.n

    def __getitem__(self, i):
        """Return element at index i."""
        if not 0 <= i < self.n:
            # Check it i index is in bounds of array
            raise ValueError('invalid index')
        return self.A[i]

    def append(self, obj):
        """Add object to end of the array."""
        if self.n == self.capacity:
            # Double capacity if not enough room
            self._resize(2 * self.capacity)
        self.A[self.n] = obj    # Set self.n index to obj
        self.n += 1

    def _resize(self, c):
        """Resize internal array to capacity c."""
        B = self._make_array(c)     # New bigger array
        for k in range(self.n):    # Reference all existing values
            B[k] = self.A[k]
        self.A = B          # Call A the new bigger array
        self.capacity = c   # Reset the capacity

    @staticmethod
    def _make_array(c):
        """Return new array with capacity c."""
        return (c * ctypes.py_object)()

    def insert(self, k, value):
        """Insert value at position k."""
        if self.n == self.capacity:
            self._resize(2 * self.capacity)
        for j in range(self.n, k, -1):
            self.A[j] = self.A[j-1]
        self.A[k] = value
        self.n += 1

    def pop(self, index=0):
        """Remove item at index (default first)."""
        if index >= self.n or index < 0:
            raise ValueError('invalid index')
        for i in range(index, self.n-1):
            self.A[i] = self.A[i+1]
        self.A[self.n - 1] = None
        self.n -= 1

    def remove(self, value):
        """Remove the first occurrence of a value in the array."""
        for k in range(self.n):
            if self.A[k] == value:
                for j in range(k, self.n - 1):
                    self.A[j] = self.A[j+1]
                self.A[self.n - 1] = None
                self.n -= 1
                return
        raise ValueError('value not found')

    def _print(self):
        """Print the array."""
        for i in range(self.n):
            print(self.A[i], end=' ')
        print()

测试动态数组Python代码

上面我们已完成了一个动态数组的类,置信都很冲动,接下来让我们来测试一下,看能不能胜利呢?在同一个文件下,写的测试代码以下:

def main():
    # Instantiate
    mylist = DynamicArray()

    # Append new element
    mylist.append(10)
    mylist.append(9)
    mylist.append(8)
    # Insert new element in given position
    mylist.insert(1, 1024)
    mylist.insert(2, 2019)
    # Check length
    print('The array length is: ', mylist.__len__())
    # Print the array
    print('Print the array:')
    mylist._print()
    # Index
    print('The element at index 1 is :', mylist[1])
    # Remove element
    print('Remove 2019 in array:')
    mylist.remove(2019)
    mylist._print()
    # Pop element in given position
    print('Pop pos 2 in array:')
    # mylist.pop()
    mylist.pop(2)
    mylist._print()


if __name__ == '__main__':
    main()

测试效果

冲动人心的时候发表,测试效果以下。请连系测试代码和数组的组织举行明白,假如由疏漏,迎接人人指出。

The array length is:  5
Print the array:
10 1024 2019 9 8 
The element at index 1 is : 1024
Remove 2019 in array:
10 1024 9 8 
Pop pos 2 in array:
10 1024 8 

总结

经由过程以上的引见,我们晓得了数组存在静态和动态范例。对应到Python——列表就是动态数组,而元组和字符串就是静态数组。
而在本博客中,我们偏重引见了什么是动态数组,并经由过程Python代码举行完成。愿望你能今后以庞杂的体式格局学会数组。
总结谈话,看似简朴的操纵,背地完成道理可以很庞杂。

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
用最庞杂的体式格局学会数组(Python完成动态数组)

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282000.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>