以python實現merge sort
来源：2-3 归并排序法的内存操作优化
慕用8103342
2021-12-09 14:35:50
講師你好:
以下是我以python3.9實現merge_sort的代碼，我想請問幾個問題:
1) 在以下代碼中實現泛型約束的方式是否洽當
2) 私有化構造方法的形式是法洽當
3) 目前本人正在學習python，想請問講師這樣撰寫python是否洽當
import typing
from abc import abstractmethod, ABCMeta
from typing import Any, Protocol, List
C = typing.TypeVar("C", bound="Comparable")
class Comparable(metaclass=ABCMeta):
@abstractmethod
def __eq__(self, other: Any) -> bool:
pass
@abstractmethod
def __lt__(self: C, other: C) -> bool:
pass
def __gt__(self: C, other: C) -> bool:
return (not self < other) and self != other
def __le__(self: C, other: C) -> bool:
return self < other or self == other
def __ge__(self: C, other: C) -> bool:
return (not self < other)
class MergeSort(object):
__create_key = object()
# 構造方法私有化
@classmethod
def create(cls, value):
return MergeSort(cls.__create_key, value)
def __init__(self, create_key, value):
assert (create_key == MergeSort.__create_key), " objects must be created using MergeSort.create"
self.value = value
@classmethod
def sort(cls, arr: List[Comparable]) -> None:
temp: List = arr[::]
cls.__sort(arr, 0, len(arr) - 1, temp)
@classmethod
def __sort(cls, arr: List[Comparable], start: int, end: int, temp: List[Comparable]) -> None:
if start >= end:
return
mid: int = start + (end - start) // 2
cls.__sort(arr, start, mid, temp)
cls.__sort(arr, mid + 1, end, temp)
if arr[mid] > arr[mid + 1]:
cls.__merge(arr, start, mid, end, temp)
@classmethod
def __merge(cls, arr: List[Comparable], start: int, mid: int, end: int, temp: List[Comparable]) -> None:
temp[start:end + 1] = arr[start:end + 1]
i = start
j = mid + 1
for k in range(start, end + 1):
if i > mid:
arr[k] = temp[j]
j += 1
elif j > end:
arr[k] = temp[i]
i += 1
elif temp[i] <= temp[j]:
arr[k] = temp[i]
i += 1
else:
arr[k] = temp[j]
j += 11回答
-
是否"恰当"是一个主观问题，我也不是 Python 专家。但整体，我的个人观点是：
1）
对于 Python，不需要做泛型约束。
Python 本身就是动态类型语言，首先不需要泛型。
其次，在我看来，做过多约束本身其实背离了 Python 语言的初衷。Python 就是要简单。
你可以尝试一下，对于你的代码，如果扔掉 Comparable 的约束，，排序这样一个没有定义比较相关函数的类，比如这个学生类：
class Student: def __init__(self, name): self.name = name
会返回这个结果：
核心是：Student 没有支持 > 运算。
而如果加上你设计的这个泛型支持，依然是返回这样的结果。试试看？
所以，这个约束只是从源码层面做了约束，从调用的层面，没有实际的约束（反观 Java 的泛型约束，将会让不满足类的对象在编译期间，甚至是 IDE 自身就能检测到这样的调用失败。）
2）
对于排序这个动作，我倾向于认为，不需要私有化构造函数，甚至从根子上，对于 Python 来说，不需要把算法封装在类中。Java 要这么做，是因为 Java 只支持一种设计范式：面向对象。但 Python 不是。Python 不需要所有的内容都放到对象中。所以，Python 自身的 sort，这么调用就好：
if __name__ == '__main__': students = [Student("C"), Student("B"), Student("A")] students = sorted(students)没有任何的类，直接调用 sorted 方法就好。sorted 这样的函数被称为自由函数，不放在任何类中。如果需要做组织，把他们放到一个包里就好。
(比如 Python 的 math 就是这么组织的，里面是一个一个函数)
3)
再次强调，我不是 Python 专家，以上只是我的个人意见。这些内容也和算法的逻辑无关。这个课程以分析学习算法的逻辑为主，对不同语言的不同规范不做深入探讨。如果你对这方面有疑问，还请以后去相关语言的社区，或者相关语言的课程做探讨。
但是有一点需要说一下，我个人并不是很建议使用 Python 做算法的底层实现。如果你只是学习算法的逻辑，没有问题，但如果考虑上性能，那么就会有很大的问题。很有可能你辛辛苦苦实现的一个明明复杂度很优的算法，可结果其运行效率还不如一个复杂度不高的算法。比如我印象中之前试验过，使用 Python 实现一个原地的快排，其性能还不如实现一个不断开空间的非原地快排。
为什么？这是因为 Python 这类解释型语言，对解释器的依赖巨大，而不完全依赖与你的逻辑。一个理论上很费时的操作，有可能在语言内部做了优化，使得性能很快。而你自己实现的一个复杂度相同，甚至更优的算法，可能因为所有的逻辑都架在上层，反而性能很差。
所以如果你搞竞赛，使用 Python 的话，会经常发现这样的问题：完全相同的算法思路，就是因为实现的方式不同，一个多调用了一些库函数，就能通过；另一个自己从底层实现一些内容，就会超时。
那 Python 内部到底做了什么优化？答案是，Python 内部都是靠 C 实现的。
当然，这件事情也有一些解决思路，比如 pypy，但这又引出了更多的内容，全都是 Python 生态圈的事情了。但整体，暂时，Python 还是一种非常优秀的胶水语言，或者脚本语言，或者做探索性工具的语言，因为他能够快速搭建出想要的功能进行试验。但真正在底层，全部都是用 C/C++/Java 这类语言。
Python 为什么在人工智能领域火爆？就是因为人工智能领域需要大量的反复试验，所以需要能够快速搭建原型，但如果真的要做生产环境的部署，Python 绝对不是实现算法的核心语言。
著名的 Python 语言的深度学习框架 tensorflow，其源码 Python 含量只有 20%+，Python 的偶用是用于提供接口。底层全部是 C++：https://github.com/tensorflow/tensorflow
PyTorch 同理：https://github.com/pytorch/pytorch
==========
说了这么多，不是反对你用 Python 写算法，而是：
1）你以后可能会遇到 Python 实现的算法的性能问题，这是正常的；
2）我个人不是 Python 语言专家，所以非逻辑问题，不同语言的规范问题，不是这个课程的探讨范围
继续加油！：）
0
相似问题
回答 1
回答 1