2022-08-19 00:38 北京科技大学算法工程师发布于浙江

关注

算法面试高频知识点：Python/C/C++知识总结

图片说明

----【Python/C/C++知识】----

【一】Python中迭代器的概念？

可迭代对象是迭代器、生成器和装饰器的基础。简单来说，可以使用for来循环遍历的对象就是可迭代对象。比如常见的list、set和dict。

我们来看一个🌰：

from collections import Iterable
print(isinstance('abcddddd', Iterable))     # str是否可迭代

print(isinstance([1,2,3,4,5,6], Iterable))   # list是否可迭代

print(isinstance(12345678, Iterable))       # 整数是否可迭代

-------------结果如下----------------
True
True
False

当对所有的可迭代对象调用 dir() 方法时，会发现他们都实现了 iter 方法。这样就可以通过 iter(object) 来返回一个迭代器。

x = [1, 2, 3]
y = iter(x)
print(type(x))

print(type(y))

------------结果如下------------
<class 'list'>
<class 'list_iterator'>

可以看到调用iter()之后，变成了一个list_iterator的对象。可以发现增加了一个next方法。所有实现了iter和next两个方法的对象，都是迭代器。

迭代器是带状态的对象，它会记录当前迭代所在的位置，以方便下次迭代的时候获取正确的元素。iter返回迭代器自身，next返回容器中的下一个值，如果容器中没有更多元素了，则抛出Stoplteration异常。

x = [1, 2, 3]
y = iter(x)
print(next(y))
print(next(y))
print(next(y))
print(next(y))

----------结果如下----------
1
2
3
Traceback (most recent call last):
  File "/Users/Desktop/test.py", line 6, in <module>
    print(next(y))
StopIteration

如何判断对象是否是迭代器，和判断是否是可迭代对象的方法差不多，只要把 Iterable 换成 Iterator。

Python的for循环本质上就是通过不断调用next()函数实现的，举个栗子，下面的代码先将可迭代对象转化为Iterator，再去迭代。这样可以节省对内存，因为迭代器只有在我们调用 next() 才会实际计算下一个值。

x = [1, 2, 3]
for elem in x:
    ...

itertools 库提供了很多常见迭代器的使用。

>>> from itertools import count     # 计数器
>>> counter = count(start=13)
>>> next(counter)
13
>>> next(counter)
14

【二】Python中生成器的相关知识

我们创建列表的时候，受到内存限制，容量肯定是有限的，而且不可能全部给他一次枚举出来。Python常用的列表生成式有一个致命的缺点就是定义即生成，非常的浪费空间和效率。

如果列表元素可以按照某种算法推算出来，那我们可以在循环的过程中不断推算出后续的元素，这样就不必创建完整的list，从而节省大量的空间。在Python中，这种一边循环一边计算的机制，称为生成器：generator。

要创建一个generator，最简单的方法是改造列表生成式：

a = [x * x for x in range(10)]
print(a)
b = (x * x for x in range(10))
print(b)

--------结果如下--------------
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
<generator object <genexpr> at 0x10557da50>

还有一个方法是生成器函数，通过def定义，然后使用yield来支持迭代器协议，比迭代器写起来更简单。

def spam():
    yield"first"
    yield"second"
    yield"third"

for x in spam():
    print(x)

-------结果如下---------
first
second
third

进行函数调用的时候，返回一个生成器对象。在使用next()调用的时候，遇到yield就返回，记录此时的函数调用位置，下次调用next()时，从断点处开始。

我们完全可以像使用迭代器一样使用 generator ，当然除了定义。定义一个迭代器，需要分别实现 iter() 方法和 next() 方法，但 generator 只需要一个小小的yield。

generator还有 send() 和 close() 方法，都是只能在next()调用之后，生成器处于挂起状态时才能使用的。

python是支持协程的，也就是微线程，就是通过generator来实现的。配合generator我们可以自定义函数的调用层次关系从而自己来调度线程。

【三】Python中装饰器的相关知识

装饰器允许通过将现有函数传递给装饰器，从而向现有函数添加一些额外的功能，该装饰器将执行现有函数的功能和添加的额外功能。

装饰器本质上还是一个函数，它可以让已有的函数不做任何改动的情况下增加功能。

接下来我们使用一些例子来具体说明装饰器的作用：

如果我们不使用装饰器，我们通常会这样来实现在函数执行前插入日志：

def foo():
    print('i am foo')

def foo():
    print('foo is running')
    print('i am foo')

虽然这样写是满足了需求，但是改动了原有的代码，如果有其他的函数也需要插入日志的话，就需要改写所有的函数，这样不能复用代码。

我们可以进行如下改写：

import logging

def use_log(func):
    logging.warning("%s is running" % func.__name__)
    func()

def bar():
    print('i am bar')

use_log(bar)    #将函数作为参数传入

-------------运行结果如下--------------
WARNING:root:bar is running
i am bar

这样写的确可以复用插入的日志，缺点就是显式的封装原来的函数，我们希望能隐式的做这件事。

我们可以用装饰器来写：

import logging

def use_log(func):
    def wrapper(*args, **kwargs):
        logging.warning('%s is running' % func.__name__)
        return func(*args, **kwargs)

    return wrapper


def bar():
    print('I am bar')


bar = use_log(bar)
bar()

------------结果如下------------
WARNING:root:bar is running
I am bar

其中，use_log函数就是装饰器，它把我们真正想要执行的函数bar()封装在里面，返回一个封装了加入代码的新函数，看起来就像是bar()被装饰了一样。

但是这样写还是不够隐式，我们可以通过@语法糖来起到bar = use_log(bar)的作用。

import logging

def use_log(func):
    def wrapper(*args, **kwargs):
        logging.warning('%s is running' % func.__name__)
        return func(*args, **kwargs)

    return wrapper


@use_log
def bar():
    print('I am bar')


@use_log
def haha():
    print('I am haha')


bar()
haha()

------------结果如下------------
WARNING:root:bar is running
I am bar
WARNING:root:haha is running
I am haha

这样子看起来就非常简洁，而且代码很容易复用。可以看成是一种智能的高级封装。

【四】Python的深拷贝与浅拷贝？

在Python中，用一个变量给另一个变量赋值，其实就是给当前内存中的对象增加一个“标签”而已。

>>> a = [6, 6, 6, 6]
>>> b = a
>>> print(id(a), id(b), sep = '\n')
66668888
66668888

>>> a is b
True（可以看出，其实a和b指向内存中同一个对象。）

浅拷贝是指创建一个新的对象，其内容是原对象中元素的引用（新对象与原对象共享内存中的子对象）。

注：浅拷贝和深拷贝的不同仅仅是对组合对象来说，所谓的组合对象就是包含了其他对象的对象，如列表，类实例等等。而对于数字、字符串以及其他“原子”类型，没有拷贝一说，产生的都是原对象的引用。

常见的浅拷贝有：切片操作、工厂函数、对象的copy()方法，copy模块中的copy函数。

>>> a = [6, 8, 9]
>>> b = list(a)
>>> print(id(a), id(b))
4493469248 4493592128    #a和b的地址不同

>>> for x, y in zip(a, b):
...     print(id(x), id(y))
... 
4489786672 4489786672
4489786736 4489786736
4489786768 4489786768
# 但是他们的子对象地址相同

从上面的例子中可以看出，a浅拷贝得到b，a和b指向内存中不同的list对象，但是他们的元素指向相同的int对象，这就是浅拷贝。

深拷贝是指创建一个新的对象，然后递归的拷贝原对象所包含的子对象。深拷贝出来的对象与原对象没有任何关联。

深拷贝只有一种方式：copy模块中的deepcopy函数。

我们接下来用一个包含可变对象的列表来确切地展示浅拷贝和深拷贝的区别：

>>> a = [[6, 6], [8, 8], [9, 9]]
>>> b = copy.copy(a)   # 浅拷贝
>>> c = copy.deepcopy(a) # 深拷贝
>>> print(id(a), id(b)) # a和b地址不同
4493780304 4494523680
>>> for x, y in zip(a, b):   # a和b的子对象地址相同
...     print(id(x), id(y))
... 
4493592128 4493592128
4494528592 4494528592
4493779024 4493779024
>>> print(id(a), id(c))   # a和c不同
4493780304 4493469248
>>> for x, y in zip(a, c): # a和c的子对象地址也不同
...     print(id(x), id(y))
... 
4493592128 4493687696
4494528592 4493686336
4493779024 4493684896

【五】Python是解释语言还是编译语言？

Python是解释语言。

解释语言的优点是可移植性好，缺点是运行需要解释环境，运行起来比编译语言要慢，占用的资源也要多一些，代码效率低。

编译语言的优点是运行速度快，代码效率高，编译后程序不可以修改，保密性好。缺点是代码需要经过编译才能运行，可移植性较差，只能在兼容的操作系统上运行。

解释语言和编译语言的区别

【六】Python的垃圾回收机制

在Python中，使用引用计数进行垃圾回收；同时通过标记-清除算法解决容器对象可能产生的循环引用问题；最后通过分代回收算法提高垃圾回收效率。

【七】Python里有多线程吗？

Python里的多线程是假的多线程。

Python解释器由于设计时有GIL全局锁，导致了多线程无法利用多核，只有一个线程在解释器中运行。

对于I/O密集型任务，Python的多线程能起到作用，但对于CPU密集型任务，Python的多线程几乎占不到任何优势，还有可能因为争夺资源而变慢。

对所有面向I/O的（会调用内建的操作系统C代码的）程序来说，GIL会在这个I/O调用之前被释放，以允许其它的线程在这个线程等待I/O的时候运行。

如果是纯计算的程序，没有 I/O 操作，解释器会每隔 100 次操作就释放这把锁，让别的线程有机会执行（这个次数可以通过 sys.setcheckinterval 来调整）如果某线程并未使用很多I/O 操作，它会在自己的时间片内一直占用处理器和GIL。

缓解GIL锁的方法：多进程和协程（协程也只是单CPU，但是能减小切换代价提升性能）

【八】Python中range和xrange的区别？

首先，xrange函数和range函数的用法完全相同，不同的地方是xrange函数生成的不是一个list对象，而是一个生成器。

要生成很大的数字序列时，使用xrange会比range的性能优很多，因为其不需要一上来就开辟很大的内存空间。

Python 2.7.15 | packaged by conda-forge | (default, Jul  2 2019, 00:42:22) 
[GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> xrange(10)
xrange(10)
>>> list(xrange(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

xrange函数和range函数一般都用在循环的时候。具体例子如下所示：

>>> for i in range(0,7):
...     print(i)
... 
0
1
2
3
4
5
6

>>> for i in xrange(0,7):
...     print(i)
... 
0
1
2
3
4
5
6

在Python3中，xrange函数被移除了，只保留了range函数的实现，但是此时range函数的功能结合了xrange和range。并且range函数的类型也发生了变化，在Python2中是list类型，但是在Python3中是range序列的对象。

【九】Python中列表和元组的区别？

列表是可变的，在创建之后可以对其进行任意的修改。
元组是不可变的，元组一旦创建，便不能对其进行更改，可以元组当作一个只读版本的列表。
元组无法复制。
Python将低开销的较大的块分配给元组，因为它们是不可变的。对于列表则分配小内存块。与列表相比，元组的内存更小。当你拥有大量元素时，元组比列表快。

【十】Python中dict（字典）的底层结构？

Python的dict（字典）为了支持快速查找使用了哈希表作为底层结构，哈希表平均查找时间复杂度为O(1)。CPython 解释器使用二次探查解决哈希冲突问题。

【十一】常用的深度学习框架有哪些，都是哪家公司开发的？

PyTorch：Facebook
TensorFlow：Google
Keras：Google
MxNet：Dmlc社区
Caffe：UC Berkeley
PaddlePaddle：百度

【十二】PyTorch动态图和TensorFlow静态图的区别？

PyTorch动态图：计算图的运算与搭建同时进行；其较灵活，易调节。

TensorFlow静态图：计算图先搭建图，后运算；其较高效，不灵活。

【十三】C/C++中面向对象的相关知识

面向对象程序设计（Object-oriented programming，OOP）有三大特征 ——封装、继承、多态。

封装：把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。
关键字：public, protected, private。不写默认为 private。

public 成员：可以被任意实体访问。
protected 成员：只允许被子类及本类的成员函数访问。
private 成员：只允许被本类的成员函数、友元类或友元函数访问。

继承：基类（父类）——> 派生类（子类）

多态：即多种状态（形态）。简单来说，我们可以将多态定义为消息以多种形式显示的能力。多态是以封装和继承为基础的。

C++ 多态分类及实现：

重载多态（Ad-hoc Polymorphism，编译期）：函数重载、运算符重载
子类型多态（Subtype Polymorphism，运行期）：虚函数
参数多态性（Parametric Polymorphism，编译期）：类模板、函数模板
强制多态（Coercion Polymorphism，编译期/运行期）：基本类型转换、自定义类型转换

【十四】C/C++中struct的内存对齐与内存占用计算？

什么是内存对齐？计算机系统对基本类型数据在内存中存放的位置有限制，它们会要求这些数据的首地址的值是有效对齐值的倍数。

什么是有效对齐值？计算机系统有默认对齐系数n,可以通过#pragma pack(n)来指定。有效对齐值就等与该对齐系数和结构体中最长的数据类型的长度两者最小的那一个值,比如对齐系数是8,而结构体中最长的是int,4个字节,那么有效对齐值为4。

为什么要内存对齐？假如没有内存对齐机制，数据可以任意存放，现在一个int变量存放在从地址1开始的连续四个字节地址中。当4字节存取粒度的处理器去取数据时，要先从0地址开始读取第一个4字节块,剔除不想要的字节（0地址）,然后从地址4开始读取下一个4字节块,同样剔除不要的数据（5，6，7地址）,最后留下的两块数据合并放入寄存器，这需要做很多工作，整体效率较低。

struct内存占用如何计算？结构体的内存计算方式遵循以下规则：

数据成员对齐规则：第一个数据成员放在offset为0的地方，以后的每一个成员的offset都必须是该成员的大小与有效对齐值相比较小的数值的整数倍,例如第一个数据成员是int型，第二个是double，有效对齐值为8,所以double的起始地址应该为8,那么第一个int加上内存补齐用了8个字节
结构体作为成员：如果一个结构里有某些结构体成员，则结构体成员要从其内部有效对齐值的整数倍地址开始存储。(比如struct a中存有struct b，b里有char, int, double，那b应该从8的整数倍开始存储)
结构体内存的总大小，必须是其有效对齐值的整数倍，不足的要补齐。

我们来举两个🌰：

#include <stdio.h>
#pragma pack(8)
int main()
{
  struct Test
  {
    int a;
    //long double大小为16bytes
    long double b;         
    char c[10];
  };
  printf("%d", sizeof(Test));
  return 0;
} 

struct的内存占用为40bytes

#include <stdio.h>
#pragma pack(16)
int main()
{
  struct Test
  {
    int a;
    //long double大小为16bytes
    long double b;         
    char c[10];
  }
  printf("%d", sizeof(Test));
  return 0;
}

struct的内存占用为48bytes

【十五】C/C++中智能指针的定义与作用？

智能指针是一个类，这个类的构造函数中传入一个普通指针，析构函数中释放传入的指针。智能指针的类都是栈上的对象，所以当函数（或程序）结束时会自动被释放。

（注：不能将指针直接赋值给一个智能指针，一个是类，一个是指针。）

常用的智能指针：智能指针在C++11版本之后提供，包含在头文件<memory>中，主要是shared_ptr、unique_ptr、weak_ptr。unique_ptr不支持复制和赋值。当程序试图将一个 unique_ptr 赋值给另一个时，如果源 unique_ptr 是个临时右值，编译器允许这么做；如果原来的unique_ptr 将存在一段时间，编译器将禁止这么做。shared_ptr是基于引用计数的智能指针。可随意赋值，直到内存的引用计数为0的时候这个内存会被释放。weak_ptr能进行弱引用。引用计数有一个问题就是互相引用形成环，这样两个指针指向的内存都无法释放。需要手动打破循环引用或使用weak_ptr。顾名思义，weak_ptr是一个弱引用，只引用，不计数。如果一块内存被shared_ptr和weak_ptr同时引用，当所有shared_ptr析构了之后，不管还有没有weak_ptr引用该内存，内存也会被释放。所以weak_ptr不保证它指向的内存一定是有效的，在使用之前需要检查weak_ptr是否为空指针。</memory>

智能指针的作用：C++11中引入了智能指针的概念，方便管理堆内存。使用普通指针，容易造成堆内存泄露（忘记释放），二次释放，野指针，程序发生异常时内存泄露等问题等，使用智能指针能更好的管理堆内存。

【十六】C/C++中程序的开发流程？

开发一个C++程序的过程通常包括编辑、编译、链接、运行和调试等步骤。

编辑：编辑是C++程序开发过程的第一步，它主要包括程序文本的输入和修改。任何一种文本编辑器都可以完成这项工作。当用户完成了C++程序的编辑时，应将输入的程序文本保存为以.cpp为扩展名的文件（保存C++头文件时应以.h为扩展名）。

编译：C++是一种高级程序设计语言，它的语法规则与汇编语言和机器语言相比更接近人类自然语言的习惯。然而，计算机能够“看”懂的唯一语言是汇编语言。因此，当我们要让计算机“看”懂一个C++程序时，就必须使用编译器将这个C++程序“翻译”成汇编语言。编译器所做的工作实际上是一种由高级语言到汇编语言的等价变换。

汇编：将汇编语言翻译成机器语言指令。汇编器对汇编语言进行一系列处理后最终产生的输出结构称为目标代码，它是某种计算机的机器指令（二进制），并且在功能上与源代码完全等价。保存源代码和目标代码的文件分别称为源文件和目标文件（ .obj）。

链接：要将汇编器产生的目标代码变成可执行程序还需要最后一个步骤——链接。链接工作是由“链接器”完成的，它将编译后产生的一个或多个目标文件与程序中用到的库文件链接起来，形成一个可以在操作系统中直接运行的可执行程序。（linux中的.o文件）

运行和调试：我们接下来就可以执行程序了。如果出现问题我们可以进行调试debug。

【十七】C/C++中数组和链表的优缺点？

数组和链表是C/C++中两种基本的数据结构，也是两个最常用的数据结构。

数组的特点是在内存中，数组是一块连续的区域，并且数组需要预留空间。链表的特点是在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续。链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址。每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据。

数组的优缺点：

优点：查询效率高，时间复杂度可以达到O(1)。

缺点：新增和修改效率低，时间复杂度为O(N)；内存分配是连续的内存，扩容需要重新分配内存。

链表的优缺点：

优点：新增和修改效率高，只需要修改指针指向即可，时间复杂度可以达到O(1)；内存分配不需要连续的内存，占用连续内存少。

缺点：链表查询效率低，需要从链表头依次查找，时间复杂度为O(N)。

【十八】C/C++中的new和malloc有什么区别？

new和malloc主要有以下三方面的区别：

malloc和free是标准库函数，支持覆盖；new和delete是运算符，支持重载。
malloc仅仅分配内存空间，free仅仅回收空间，不具备调用构造函数和析构函数功能，用malloc分配空间存储类的对象存在风险；new和delete除了分配回收功能外，还会调用构造函数和析构函数。
malloc和free返回的是void类型指针（必须进行类型转换），new和delete返回的是具体类型指针。

#秋招##实习##面经##面试八股文##面霸的自我修养#