每日一题——Python实现PAT甲级1042 Shuffling Machine（举一反三+思想解读+逐步优化）

2024-06-01 13:52
文章标签 python 实现 优化 每日 解读 逐步 思想 pat machine 甲级 举一反三 shuffling 1042

本文主要是介绍每日一题——Python实现PAT甲级1042 Shuffling Machine（举一反三+思想解读+逐步优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！


一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

目录

我的写法

功能分析

时间复杂度

空间复杂度

总结

代码点评

我要更强

优化方向

优化后的代码

优化分析

代码点评

哲学和编程思想

1. 空间-时间权衡（Space-Time Tradeoff）

2. 内存重用（Memory Reuse）

3. 最小化副作用（Minimize Side Effects）

4. 简洁性（Simplicity）

5. 局部性原理（Principle of Locality）

6. KISS 原则（Keep It Simple, Stupid）

7. DRY 原则（Don't Repeat Yourself）

举一反三

1. 空间-时间权衡（Space-Time Tradeoff）

技巧：

示例：

2. 内存重用（Memory Reuse）

技巧：

示例：

3. 最小化副作用（Minimize Side Effects）

技巧：

示例：

4. 简洁性（Simplicity）

技巧：

示例：

5. 局部性原理（Principle of Locality）

技巧：

示例：

6. KISS 原则（Keep It Simple, Stupid）

技巧：

示例：

7. DRY 原则（Don't Repeat Yourself）

技巧：

示例：

总结

 题目链接
 


我的写法

K = int(input())  # 读取输入的K值，表示需要进行洗牌的次数
orders = list(map(int, input().split()))  # 读取输入的顺序列表，表示洗牌后的顺序# 初始化一副扑克牌
init_cards = []
init_cards += ['S' + str(i + 1) for i in range(13)]  # 添加黑桃(S)1到13
init_cards += ['H' + str(i + 1) for i in range(13)]  # 添加红桃(H)1到13
init_cards += ['C' + str(i + 1) for i in range(13)]  # 添加梅花(C)1到13
init_cards += ['D' + str(i + 1) for i in range(13)]  # 添加方块(D)1到13
init_cards.append('J1')  # 添加小王(J1)
init_cards.append('J2')  # 添加大王(J2)outputs = []  # 初始化输出列表for i in range(K):  # 进行K次洗牌outputs = [''] * 54  # 每次洗牌后创建一个空的输出列表for j in range(54):  # 遍历每一张牌outputs[orders[j] - 1] = init_cards[j]  # 根据orders中的顺序将init_cards中的牌放到对应位置init_cards = outputs  # 更新init_cards为新排列的牌，准备进行下一次洗牌print(*outputs)  # 打印最终结果，将输出列表中的牌以空格分隔


 

这段代码是一个模拟扑克牌洗牌过程的程序，详细分析如下：

功能分析

这段代码的功能是根据用户输入的顺序 orders 和洗牌次数 K 模拟扑克牌的洗牌过程。输入顺序 orders 是一个包含 54 个整数的列表，表示每张牌在洗牌之后的新位置。程序按照这个顺序对扑克牌进行 K 次洗牌，并最终输出洗牌后的扑克牌顺序。

时间复杂度

  1. 初始化扑克牌：
    • 使用列表推导式初始化扑克牌，时间复杂度为 (O(1))，因为这是固定的 54 张牌。
  2. 洗牌过程：
  • 外层循环执行 (K) 次，其中 (K) 是输入的洗牌次数。
  • 内层循环执行 54 次，处理每一张牌的移动。
  • 整体的时间复杂度为 (O(K \times 54))，即 (O(54K))。通常情况下 (O(54K)) 可以简化为 (O(K))，因为 54 是一个常数。

空间复杂度

  1. 固定空间：
    • init_cards 和 outputs 各有 54 个元素，空间复杂度为 (O(54))，即 (O(1))，因为 54 是常数。
    • 其它变量如 K 和 orders（长度为 54）也是常量级别的空间开销。
  2. 洗牌过程：
  • 在每次洗牌中，新的 outputs 列表会覆盖旧的 init_cards 列表，但总的占用空间仍然是两个 54 元素的列表，空间复杂度为 (O(54 \times 2))，即 (O(108))。但这仍然是常数级别，简化为 (O(1))。

总结

  • 时间复杂度： (O(K))
  • 空间复杂度： (O(1))

代码点评

  1. 代码结构清晰：初始化扑克牌，循环 K 次洗牌，最后输出结果，逻辑非常清晰。
  2. 注释明确：每步操作都有详细注释，便于理解。
  3. 效率合理：时间复杂度和空间复杂度都很低，适用于大多数实际应用场景。
  4. 可扩展性：如果扑克牌数目或洗牌规则发生变化，代码也易于修改和扩展。

总体来说，这段代码简洁高效，符合专业编程规范。

我要更强

优化这段代码的时间复杂度和空间复杂度并不容易，因为洗牌过程本身需要对每张牌进行重新排列。然而，可以通过减少不必要的内存分配和复制来优化空间使用。以下是几个可能的优化方向：

优化方向

  1. 内存优化：避免在每次洗牌时创建新的列表，而是使用额外的空间来保存当前和下一步的状态。
  2. 减少复制操作：尽量减少对列表的整体复制操作。

优化后的代码

通过优化空间使用，我们可以改进代码的内存效率。以下是优化后的代码：

K = int(input())  # 读取输入的K值，表示需要进行洗牌的次数
orders = list(map(int, input().split()))  # 读取输入的顺序列表，表示洗牌后的顺序# 初始化一副扑克牌
init_cards = []
init_cards += ['S' + str(i + 1) for i in range(13)]  # 添加黑桃(S)1到13
init_cards += ['H' + str(i + 1) for i in range(13)]  # 添加红桃(H)1到13
init_cards += ['C' + str(i + 1) for i in range(13)]  # 添加梅花(C)1到13
init_cards += ['D' + str(i + 1) for i in range(13)]  # 添加方块(D)1到13
init_cards.append('J1')  # 添加小王(J1)
init_cards.append('J2')  # 添加大王(J2)current = init_cards[:]  # 当前牌组初始化为init_cards的复制
next_cards = [''] * 54  # 初始化一个空的牌组用于保存下一步结果for i in range(K):  # 进行K次洗牌for j in range(54):  # 遍历每一张牌next_cards[orders[j] - 1] = current[j]  # 根据orders中的顺序将current中的牌放到对应位置current, next_cards = next_cards, current  # 交换current和next_cards，准备进行下一次洗牌print(*current)  # 打印最终结果，将current牌组中的牌以空格分隔

优化分析

  1. 时间复杂度：
    • 外层循环执行 (K) 次，其中 (K) 是输入的洗牌次数。
    • 内层循环执行 54 次，处理每一张牌的移动。
    • 时间复杂度仍为 (O(K \times 54))，即 (O(K))，因为 54 是常数。
  2. 空间复杂度：
  • 使用了两个固定大小的列表 current 和 next_cards，每个列表包含 54 个元素。
  • 总的空间复杂度还是 (O(54 \times 2))，即 (O(1))，因为 54 是常数。

代码点评

  • 内存优化：新代码避免了重复分配和复制列表，通过交换引用来保存洗牌结果。
  • 逻辑清晰：洗牌过程的逻辑保持不变，代码结构仍然清晰易懂。
  • 效率提升：减少了内存分配和复制操作，提高了内存使用效率。

总的来说，这段优化后的代码在保留了原有逻辑的基础上优化了内存使用，更加高效。

哲学和编程思想

优化代码不仅仅是一个技术问题，也涉及到一些哲学和编程思想。这些思想可以帮助我们更好地理解为什么进行某些优化，以及如何进行有效的优化。以下是这段代码优化涉及到的主要哲学和编程思想：

1. 空间-时间权衡（Space-Time Tradeoff）

  • 哲学：在计算中，有时我们可以用更多的空间来换取更少的时间，反之亦然。这种权衡是许多优化决策的核心。
  • 应用：在这段代码中，通过使用两个固定大小的列表（current 和 next_cards），我们避免了每次洗牌都创建新的列表，从而节省了时间。

2. 内存重用（Memory Reuse）

  • 哲学：重用现有的资源而不是频繁分配和释放资源，可以提高效率和性能。
  • 应用：我们通过交换 current 和 next_cards 的引用来重用内存，而不是每次都创建新的列表。这减少了内存分配的开销，提高了性能。

3. 最小化副作用（Minimize Side Effects）

  • 哲学：减少函数或过程对外部状态的影响，有助于提高代码的可维护性和可预测性。
  • 应用：通过交换引用而不是复制列表，我们有效地将副作用限制在局部变量内部。这使得代码更容易理解和维护。

4. 简洁性（Simplicity）

  • 哲学：简洁的代码通常更容易理解、维护和调试。复杂性应尽可能地被消除。
  • 应用：代码结构清晰，逻辑明确，没有不必要的操作，保持了代码的简洁性。

5. 局部性原理（Principle of Locality）

  • 哲学：程序应尽量在局部范围内操作数据，以提高缓存效率和性能。
  • 应用：通过使用固定大小的列表，我们确保操作是局部的，数据在内存中的位置相对固定，从而提高了缓存命中率。

6. KISS 原则（Keep It Simple, Stupid）

  • 哲学：代码应保持尽可能简单，不引入不必要的复杂性。
  • 应用：通过简单地交换列表的引用，而不是复杂的复制和分配操作，我们遵循了 KISS 原则。

7. DRY 原则（Don't Repeat Yourself）

  • 哲学：尽量避免代码重复，提取公共逻辑到单一的地方。

应用：在优化过程中，避免了重复分配和复制列表的操作，集中在一个简单的引用交换上。

举一反三

理解并应用这些哲学和编程思想可以帮助你在编程中举一反三，开发出更高效、可维护的代码。以下是一些技巧和建议，结合之前提到的哲学和编程思想，帮助你在实际编程中应用：

1. 空间-时间权衡（Space-Time Tradeoff）

技巧：
  • 缓存计算结果：如果一个函数的计算结果会被多次使用，可以缓存结果以减少重复计算。
  • 预处理数据：在数据处理前进行一些预处理，可能会增加一些空间开销，但可以显著减少后续处理时间。
示例：

def fibonacci(n, memo={}):if n in memo:return memo[n]if n <= 1:return nmemo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)return memo[n]

2. 内存重用（Memory Reuse）

技巧：
  • 池化对象：复用对象而不是频繁地创建和销毁它们，比如使用对象池。
  • 就地修改：当安全和可行时，尽量就地修改数据而不是创建新的副本。
示例：

def in_place_reverse(arr):left, right = 0, len(arr) - 1while left < right:arr[left], arr[right] = arr[right], arr[left]left += 1right -= 1

3. 最小化副作用（Minimize Side Effects）

技巧：
  • 函数式编程：尽量编写纯函数（无副作用），避免修改全局状态。
  • 局部变量：使用局部变量而不是全局变量或类变量来保存临时状态。
示例：

def pure_function(x, y):return x + y

4. 简洁性（Simplicity）

技巧：
  • 拆分函数：将复杂的函数拆分成多个小函数，每个函数只做一件事。
  • 清晰命名：使用清晰、描述性的变量和函数名称，便于理解代码意图。
示例：

def process_data(data):clean_data = clean(data)transformed_data = transform(clean_data)return transformed_datadef clean(data):# 清理数据passdef transform(data):# 转换数据pass

5. 局部性原理（Principle of Locality）

技巧：
  • 数据局部性：尽量让相关的数据在内存中存放在一起，减少缓存未命中。
  • 代码局部性：尽量在一个局部范围内完成相关操作，减少跨模块调用。
示例：

def sum_of_squares(arr):return sum(x * x for x in arr)

6. KISS 原则（Keep It Simple, Stupid）

技巧：
  • 避免过度优化：在没有明确性能问题时，不要过早进行复杂的优化。
  • 直观实现：优先选择直观、简单的实现方法，复杂的方法留作备选。
示例：

def calculate_area(radius):return 3.14 * radius * radius  # 简单计算圆的面积

7. DRY 原则（Don't Repeat Yourself）

技巧：
  • 抽取公共代码：将重复出现的代码抽取到一个独立函数或模块中。
  • 使用参数化：通过参数化来减少代码重复，增强代码的灵活性。
示例：

def calculate(operation, x, y):if operation == 'add':return x + yelif operation == 'subtract':return x - y# 更多操作...

总结

通过理解和应用这些哲学和编程思想，可以帮助在编程中实现以下目标：

  • 优化性能：通过合理的空间-时间权衡和内存重用，改进代码效率。
  • 提高可维护性：通过最小化副作用、保持代码简洁和避免重复，增强代码的可读性和可维护性。
  • 提高代码局部性：通过遵循局部性原理，改进代码运行效率和可预测性。

记住，这些技巧和思想不是独立的，而是相互关联和互补的。理解和实践这些思想不仅能提高你的编程能力，还能写出更加优雅和高效的代码。

感谢。

这篇关于每日一题——Python实现PAT甲级1042 Shuffling Machine（举一反三+思想解读+逐步优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1021195。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2