跳转至

Programming

[C++ Basic] Grammar

概要

C++ 基础知识和语法,包括C++11,C++17,C++23的各种语言支持。

C++编程语言历史 和 设计思路

在纷繁多变的世界里茁壮成长:C++ 2006–2020

C 与 C++、java 的 区别

支持范式模板编程 (generic programming)

  1. 模板代码(增加泛型编程能力,类似python),
  2. 泛型编程是一种以通用性为中心的编程范式。在泛型编程中,程序通过使用参数化类型(或称为模板)来实现数据类型无关的算法和数据结构
  3. 强⼤的 Standard Template Library (STL) 标准库, 也是基于泛型编程的产物。
  4. 包括:容器、迭代器、算法和函数对象 四类
  5. 元编程(e.g., constexpr )编译时推导出变量是否为固定常数。
  6. 一些语法和关键字,增加了 new 和 delete,auto

支持面向对象编程 (object-oriented programming) 的拓展

  • 类和对象:C++允许定义类和创建对象。类是一种用户自定义的数据类型,可以包含成员变量和成员函数。对象是类的一个实例,可以通过类来创建多个对象。C语言中没有类和对象的概念,只能使用结构体和函数来组织数据和行为。
  • 封装:C++支持封装,可以将数据和相关的操作封装在一个类中,并使用访问修饰符来控制对类成员的访问权限。C语言没有封装的概念,所有的数据和函数都是公开的。
  • 继承:C++支持继承,允许创建派生类从基类继承属性和行为。继承可以实现代码重用和类的层次化。C语言没有继承的概念。
  • 多态:C++支持多态,允许通过基类指针或引用来调用派生类的虚函数,实现动态绑定和运行时多态性。C语言没有多态的概念。
  • 异常处理:C++提供异常处理机制,可以通过抛出和捕获异常来处理程序中的错误和异常情况。C语言没有内置的异常处理机制。
C++ 与 java 的区别
  1. 内存管理:C++中的内存管理是手动的,程序员需要显式地分配和释放内存。C++提供了new和delete关键字来进行动态内存分配和释放。Java中的内存管理是自动的,使用垃圾回收机制来自动管理内存,程序员不需要手动释放内存。
  2. 指针:C++支持指针操作,允许直接访问和修改内存地址。Java中没有指针的概念,所有的数据访问都是通过引用进行的。
  3. 运行环境:C++是一种编译型语言,源代码在编译后被转换为机器码,并直接在操作系统上运行。Java是一种解释型语言,源代码在编译后生成字节码,然后由Java虚拟机(JVM)解释执行。
  4. 平台依赖性:C++代码在不同的平台上需要重新编译,因为它直接与底层系统交互。Java代码是平台无关的,一次编译的字节码可以在任何支持Java虚拟机的平台上运行。

  5. C++更适合系统级编程、游戏开发等需要更高的性能和底层控制的场景。

  6. Java更适合企业级应用开发、网络编程等需要跨平台和可移植性的场景。

基础知识与坑

程序执行入口

The default program entry function is main, but can be changed in two situations:

  1. use stupid #define xxx main in header file to replace the name which maybe ignored by silly search bar in VSCODE.
  2. use -exxx compile flag

语句末尾的分号

  • 在 C++ 中,是否需要在语句的末尾使用分号(;)取决于上下文。
  • C++ 语法的基本规则是:分号用来标识一条语句的结束,而有些结构并不是严格的语句,因此不需要分号。

  • 声明(变量、类、结构体、枚举、函数原型、类型别名):都需要分号作为结束。

  • 函数定义控制语句(如 if, while, for)、复合语句{}) 不需要分号。
  • 预处理指令(如 #define, #include):不需要分号,因为它们不是 C++ 语法层面的内容。
  • 作用域结束的 } 不需要分号,但声明类或结构体时 } 后要加分号。

为什么类/结构体需要分号

C++ 中的类和结构体定义实际上是一种声明,它们的定义是一种复杂的声明语句,因此必须用分号来结束它们。

总结来说,分号用来结束语句,包括声明、表达式和执行体等,但当你定义一个复合结构(如函数定义、控制语句)时,不需要分号来结束复合结构的定义。

逗号运算符(Comma)

重名变量的优先级

int getKthAncestor(int node, int k) {
    int node= getKthAncestor(saved[node],--k);  
    return node;
}
 //为什么第二行的node会提前被修改为0,导致传入函数getKthAncestor的saved[node]的node值为0
 //如下去掉int,也不会错。因为int node 会初始化node为0
 int getKthAncestor(int node, int k) {
    node= getKthAncestor(saved[node],--k);  
    return node;
}

根据C++的作用域规则,内层的局部变量会覆盖外层的同名变量。因此,在第二行的语句中,node引用的是函数参数中的node,而不是你想要的之前定义的node。

为了避免这个问题,你可以修改代码,避免重复定义变量名。例如,可以将第二行的变量名改为newNode或其他不同的名称,以避免与函数参数名冲突。

运算符优先级

运算符性质:

  • 接受的操作数,
  • 优先级,
    • 特殊:逻辑和(&&)先于逻辑或(||)、四则运算先于位运算
    • 位运算优先级低于判断符号,记得写括号。
    • 赋值(=)优先级最低
  • 结合性,
    • 左结合性: 大部分运算(加减乘除)
    • 右结合性:赋值运算符。程序会先计算它右边的表达式的值,然后再计算它左边的表达式的值
  • 返回值
    • 赋值运算符的返回值是赋值后左操作数的引用

变量类型以及Macro constants

https://en.cppreference.com/w/cpp/language/types

https://en.cppreference.com/w/cpp/types/integer

//返回与平台相关的数值类型的极值
std::numeric_limits<double>::max()
std::numeric_limits<int>::min()

#include<limits.h>
INT_MAX
FLT_MAX (or DBL_MAX ) 
-FLT_MAX (or -DBL_MAX ) 

关键词

extern 
const
constexpr //C++11引入的关键字,用于编译时的常量与常量函数。
volatile    //是指每次需要引用某个变量的数据时,都必须从内存原地址读取,而不是编译器优化后寄存器间接读取.(必须写回内存,为了多进程并发而设计的。)
inline 

static 关键字

static 作⽤:控制变量的存储⽅式和作用范围(可⻅性)。

  1. 修饰局部变量
    • 存放位置:栈区 -> 静态数据区(data段或者bss段)
    • 生命周期:程序结束才会释放
    • 作用域:还是局部代码块
  2. 修饰函数与全局变量
    • 使其作用范围由全工程文件可见变成了本文件可见
  3. 修饰类内函数
    • 静态成员函数:使用"static"修饰的成员函数称为静态成员函数。静态成员函数与类的对象无关,可以在没有创建对象的情况下直接通过类名调用。这意味着它们不需要通过类的对象来访问,而是属于整个类的。举例
    • 静态成员函数没有隐式的this指针,因此不能直接访问非静态成员变量和非静态成员函数。静态成员函数可以访问类的静态成员变量和其他静态成员函数。
    • static 成员函数不能被 virtual 修饰, static 成员不属于任何对象或实例,所以加上 virtual没有任何实际意义;
      • 静态成员函数没有 this 指针,虚函数的实现是为每⼀个对象分配⼀个vptr 指针,⽽ vptr 是通过 this 指针调⽤的,所以不能为 virtual;虚函数的调⽤关系,this->vptr->ctable->virtual function。
  4. 修饰类内的变量
    • 存放位置:栈区 -> 静态数据区(data段或者bss段)
    • 生命周期:程序结束才会释放
    • 意味着下一次调用函数时,静态局部变量将保持上一次调用时的值。
    • 由于不再属于某个类对象,可以直接通过类名初始化 int MyClass::staticVariable = 10;
静态成员函数
#include <iostream>

class MyClass {
public:
    static void staticFunction() {
        std::cout << "This is a static member function." << std::endl;
    }
};

int main() {
    MyClass::staticFunction(); // 直接通过类名调用静态成员函数
    return 0;
}

const 关键字

当const修饰基本数据类型时,可以将其放置在类型说明符的前面或后面,效果是一样的。const关键字用于声明一个常量,即其值在声明后不可修改。

const int constantValue1 = 10; // const在类型说明符前
int const constantValue2 = 20; // const在类型说明符后

当const关键字位于指针变量或引用变量的左侧时,它用于修饰指针所指向的变量,即指针指向的内容为常量。当const关键字位于指针变量或引用变量的右侧时,它用于修饰指针或引用本身,即指针或引用本身是常量。

  1. 修饰指针指向的变量, 它指向的值不能修改:

    int x = 5;
    const int* ptr = &x;  // 指向常量整数的指针
    // *ptr = 10;        // 错误:不能通过const指针修改值
    x = 10;               // 合法:可以修改变量本身的值
    
  2. 修饰指针本身 ,它不能再指向别的变量,但指向(变量)的值可以修改。:

    const int y = 10;
    int* const ptr = &y;  // 常量指针指向整数
    // ptr = &x;         // 错误:不能修改指针本身
    // *ptr = 5;         // 合法:可以修改常量变量的值
    
  3. const int *const p3; //指向整形常量 的 常量指针 。它既不能再指向别的常量,指向的值也不能修改。

explicit

在C++, explicit 是一个关键字,用于修饰单参数构造函数,用于禁止隐式类型转换。

当一个构造函数被声明为 explicit 时,它指示编译器在使用该构造函数进行类型转换时只能使用显式调用,而不允许隐式的类型转换发生。

通过使用 explicit 关键字,可以防止一些意外的类型转换,提高代码的清晰性和安全性。它通常用于防止不必要的类型转换,特别是在单参数构造函数可能引起歧义或产生意外结果的情况下。

preprocessor directive

  • #include_next作用是 在寻找头文件时的头文件搜索优先级里,去除该文件所在的当前目录,主要是为C++头文件的重名问题提供一种解决方案。
    • 正确的用法:代码b.cpp想使用 自己拓展修改的stdlib.h, 那么在代码的目录下创建stdlib.h,并在该文件里#include_next "stdlib.h" 防止递归引用。

define、 const、 typedef、 inline

  • define:
    • define是一个预处理器指令,用于创建宏定义。它在编译之前对源代码进行简单的文本替换。可以用来定义常量、函数宏和条件编译等。
    • define的替换是简单的文本替换,没有类型检查和作用域限制。因此,它可能存在一些潜在的问题,如意外的副作用或命名冲突。
    • 例如:#define PI 3.14159,在代码中将PI替换为3.14159。
  • const:
    • const用于声明一个常量,指示标识符的值在程序执行期间不能被修改。
    • const可以用于变量、函数参数、函数返回类型和成员函数。使用const可以提高代码的可读性和安全性。
    • 例如:const int MAX_VALUE = 100;,声明一个名为MAX_VALUE的常量。
  • typedef:
    • typedef用于为数据类型创建别名。它可以用于为复杂的数据类型提供更简洁的名称,增强代码的可读性和可维护性。
    • typedef创建的别名可以像原始类型一样使用,并且不会引入新的类型,只是为已有类型提供了一个新的名称。
    • 例如:typedef int Age;,为int类型创建了一个别名Age。
  • inline:
  • inline用于声明内联函数,它是一种编译器的建议,用于将函数的定义直接插入到调用处,以避免函数调用的开销。
  • 内联函数通常在函数体较小且频繁调用的情况下使用,可以提高程序的执行效率。
  • inline关键字只是给编译器一个提示,编译器可以选择忽略该提示。在大多数情况下,编译器会自动进行内联优化。
  • 例如:inline int add(int a, int b) { return a + b; },声明了一个内联函数add。

  • define主要用于宏定义,const用于声明常量,typedef用于创建类型别名,inline用于内联函数的声明。

#ifndef & #pragma once

为了避免同一个文件被include多次,C/C++中有两种方式,一种是#ifndef方式,一种是#pragma once方式。在能够支持这两种方式的编译器上,二者并没有太大的区别,但是两者仍然还是有一些细微的区别

new & delete

  • new和delete 相对于 malloc/free 分配和释放堆空间。
  • 额外会执行构造函数和析构函数
#include <iostream>

class MyClass {
public:
    MyClass() {
        std::cout << "Constructing MyClass" << std::endl;
    }

    ~MyClass() {
        std::cout << "Destructing MyClass" << std::endl;
    }
};

int main() {
    // 使用new动态分配内存,并调用构造函数
    MyClass* obj = new MyClass();

    // 执行一些操作...

    // 使用delete释放内存,并调用析构函数
    delete obj;

    return 0;
}

namespace

namespace 会影响 typedef 的作用范围,但不会直接限制 #define 宏的作用范围。

头文件

  • 相互引用,前置声明
  • include头文件其实就是将对应的头文件内容贴在include的位置

A.h, B.h 都需要string.h的头文件,然后B.h 会include A.h,那么我在B.h里是不是可以省略include string.h

不应该省略,

  1. 防止代码变更引发的问题: 如果某天 A.h 中移除了 #include ,而 B.h 依赖 A.h 提供的 #include ,那么 B.h 将会因找不到 std::string 而编译失败。因此,显式包含依赖的头文件可以避免这种隐含依赖引发的问题。
  2. 提高可读性和自包含性: 每个头文件应该尽量做到自包含,意思是每个头文件应该独立地包含所有它所需要的头文件。这样做的好处是,任何其他文件都可以安全地单独包含 B.h,而无需额外关心它依赖于哪些头文件。
  3. 减少隐式依赖: 隐式依赖(依赖另一个头文件帮你包含所需的头文件)可能导致维护性问题。显式 #include 可以让代码更具可预测性和可维护性。

include的位置有什么规则和规律吗,头文件和cpp文件前都可以吗?

在编写代码时,往往A.cpp需要include A.h。那A.cpp需要的头文件,我是写在A.cpp里还是A.h里?

  1. 头文件 (A.h):只包含声明所需的头文件,不包含仅在实现中需要的头文件。
  2. 源文件 (A.cpp):包含所有实现需要的头文件,特别是那些仅在实现部分用到的头文件。此外,A.cpp 应该总是包含 A.h。6.

函数的特殊写法

函数传参

  1. 值传递
  2. 引用传递
  3. 指针传递
//值传递
change1(n);
void change1(int n){
    n++;
}

//引用传递,操作地址就是实参地址 ,只是相当于实参的一个别名,在符号表里对应是同一个地址。对它的操作就是对实参的操作
    change2(n);
    void change2(int &n){
        n++;
    }
    //特殊对vector
    void change2(vector<int> &n)
    //特殊对数组
    void change2(int (&n)[1000])

//指针传递,其实是地址的值传递
change3(&n);
void change3(int *n){
    *n=*n+1;
}

引用传递和指针传递的区别:

  • 引用被创建的同时必须被初始化(指针则可以在任何时候被初始化)。
  • 不能有NULL引用,引用必须与合法的存储单元关联(指针则可以是NULL)。
  • 一旦引用被初始化,就不能改变引用的关系(指针则可以随时改变所指的对象)。

指针传递和引用传递的使用情景:

  1. 函数内部修改参数并且希望改动影响调用者。
  2. 当一个函数实际需要返回多个值,而只能显式返回一个值时,可以将另外需要返回的变量以指针/引用传递

闭包、匿名函数

闭包是捕获并持有了外部作用域变量的函数。

闭包(Closure)是指在程序中,函数可以捕捉并记住其作用域(环境)中的变量,即使在函数执行完成后,这些变量依然保存在内存中,并能在后续的函数调用中被使用。闭包的一个重要特性是,它不仅保存了函数本身的逻辑,还“闭合”了函数执行时的上下文环境(即该函数所在的作用域)。

闭包通常用于实现函数内部的状态保持、回调函数等场景。在 C++ 中,闭包通过 lambda 表达式 实现,lambda 表达式可以捕获外部变量并在其内部使用。

例子

auto add = [](int x) {
    return [x](int y) {
        return x + y;
    };
};

auto add5 = add(5);
std::cout << add5(3); // 输出 8
在上面的例子中,add 函数返回了一个闭包,捕获了变量 x 的值。即使 x 在原作用域中不再可用,返回的闭包仍然可以访问并使用 x 的值。

  • 匿名函数是一种没有被绑定标识符的函数
  • lambda 是一种匿名函数
  • lambda 可以表示闭包

匿名函数(lambda)和闭包的关系就如同类和类对象的关系

匿名函数和类的定义都只存在于源码(代码段)中,而闭包和类对象则是在运行时占用内存空间的实体;

类型变参模板

template<typename T>
void swap(T& t1, T& t2)
{
    T temp = t2;
    t2 = t1;
    t1 = temp;
}
swap<int>(a,b);
条件模板类

假设我们有一个模板类 Wrapper,我们希望禁止 VirtualGuardImpl 类型作为模板参数:

template <
    typename T,
    typename U = T,
    typename = typename std::enable_if<!std::is_same<U, VirtualGuardImpl>::value>::type>
class Wrapper {
public:
    void function() {
        // 实现
    }
};

在这个例子中,如果用户尝试创建 Wrapper<VirtualGuardImpl>Wrapper<VirtualGuardImpl, VirtualGuardImpl> 的实例,编译器将报错,因为 std::enable_if 的条件不满足。但如果使用其他类型,比如 int 或自定义类型,就可以正常编译。

这段代码是 C++ 中的一个模板函数或模板类模板参数的定义,它使用了模板默认参数、std::enable_if 条件编译技术以及类型萃取(type traits)。下面是对这段代码的详细解释:

  1. 模板参数 U:

    • typename U = T 定义了一个模板类型参数 U,并给它一个默认值 T。这意味着如果在使用模板时没有指定 U 的话,它将默认使用模板参数 T 的值。
  2. std::enable_if:

    • std::enable_if 是一个条件编译技术,它只在给定的布尔表达式为 true 时启用某个模板。
    • 在这个例子中,std::enable_if 后面的布尔表达式是 !std::is_same<U, VirtualGuardImpl>::value。这意味着只有当 U 不等于 VirtualGuardImpl 类型时,这个模板参数才有效。
  3. typename 关键字:

    • typename 关键字用于告诉编译器 std::enable_if 的结果是一个类型。std::enable_if 返回的是一个类型,如果条件为 true,它返回一个空的类型,否则会导致编译错误。
  4. std::is_same:

    • std::is_same<U, VirtualGuardImpl>::value 是一个编译时检查,用于判断 UVirtualGuardImpl 是否是相同的类型。::value 是类型特征 std::is_same 的一个成员,它是一个布尔值,如果类型相同则为 true,否则为 false
  5. 组合解释:

    • 这段代码的意思是:定义一个模板参数 U,默认值为 T,并且这个模板参数只有在 U 不是 VirtualGuardImpl 类型时才有效。
    • 这是一种常见的模板编程技巧,用于约束模板参数的类型,以确保它们符合特定的要求。

个数变参模板

#include <stdarg.h>
void Error(const char* format, ...)
{
    va_list argptr;
    va_start(argptr, format);
    vfprintf(stderr, format, argptr);
    va_end(argptr);
}

VA_LIST 是在C语言中解决变参问题的一组宏,变参问题是指参数的个数不定,可以是传入一个参数也可以是多个;可变参数中的每个参数的类型可以不同,也可以相同;可变参数的每个参数并没有实际的名称与之相对应,用起来是很灵活。

(1)首先在函数里定义一具VA_LIST型的变量,这个变量是指向参数的指针; (2)然后用VA_START宏初始化变量刚定义的VA_LIST变量; (3)然后用VA_ARG返回可变的参数,VA_ARG的第二个参数是你要返回的参数的类型(如果函数有多个可变参数的,依次调用VA_ARG获取各个参数); (4)最后用VA_END宏结束可变参数的获取。

系统提供了vprintf系列格式化字符串的函数,用于编程人员封装自己的I/O函数。

int vprintf  / vscanf   (const char * format, va_list ap);                  // 从标准输入/输出格式化字符串 
int vfprintf / vfsacanf (FILE * stream, const char * format, va_list ap);   // 从文件流 
int vsprintf / vsscanf  (char * s, const char * format, va_list ap);        // 从字符串

返回多个数

使用结构体

struct RowAndCol { int row;int col; };

RowAndCol r(string fn) {
    /*...*/
    RowAndCol result;
    result.row = x;
    result.col = y;
    return result;
}

左值与右值

在 C++ 中,左值(lvalue)右值(rvalue) 是两个重要的概念,用来描述表达式的值和内存的关系。它们帮助开发者理解变量的生命周期、赋值和对象管理,特别是在现代 C++ 中引入了右值引用后,优化了移动语义和资源管理。

1. 左值(lvalue)

左值(lvalue,locatable value) 是指在内存中有明确地址、可持久存在的对象,可以对其进行赋值操作。通俗地说,左值是能够取地址的值,可以出现在赋值操作符的左边。

特点:

  • 左值具有持久的内存地址。
  • 左值可以取地址(使用 & 运算符)。
  • 左值通常表示已经存在的变量或对象。

示例

int x = 10;   // x 是左值
int* p = &x;  // 可以取 x 的地址

x = 20;       // 可以对左值进行赋值

在这个例子中,x 是一个左值,因为它表示了内存中的某个对象,并且可以通过赋值语句修改它的值。

2. 右值(rvalue)

右值(rvalue,readable value) 是没有明确地址、临时存在的对象,不能对其进行赋值操作。它们通常是字面值常量或表达式的结果。右值只能出现在赋值操作符的右边,表示一个临时对象或数据。

特点:

  • 右值是临时的,通常会在表达式结束时销毁。
  • 右值不能取地址(即不能使用 & 获取右值的地址)。
  • 右值表示表达式的计算结果或临时对象。

示例

int y = 10;       // 10 是右值
int z = y + 5;    // y + 5 是右值表达式

在这个例子中,10y + 5 是右值,因为它们表示计算出的临时数据,并且不能直接对这些值进行赋值操作。

3. 现代 C++ 中的右值引用(rvalue reference)

C++11 引入了 右值引用,即通过 && 符号表示。这使得右值也能通过引用进行操作,特别是在实现移动语义(move semantics)和避免不必要的拷贝时非常有用。右值引用允许我们通过右值管理资源,避免性能上的损失。

示例:右值引用与移动语义

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2 = std::move(vec1);  // vec1 资源移动到 vec2

    std::cout << "vec1 size: " << vec1.size() << std::endl;
    std::cout << "vec2 size: " << vec2.size() << std::endl;

    return 0;
}

在这个例子中,std::movevec1 变为一个右值引用,使其内部的资源(如动态分配的内存)直接转移给 vec2,避免了拷贝。

4. 区分左值与右值

通常,左值是表示持久存在的对象,可以通过取地址符 & 获取其地址,而右值是临时的、短暂存在的值,不能直接获取其地址。理解这两者对于编写高效的 C++ 代码和使用现代特性(如右值引用和移动语义)非常重要。

常见误区

  • 字面值常量(如 42、'a')是右值
  • 表达式的结果(如 x + y)通常是右值。
  • 函数返回值若返回的是值,而不是引用,则该返回值是右值。
  • 左值(lvalue) 是可以取地址的值,通常是变量或持久的对象。
  • 右值(rvalue) 是临时值,通常是表达式的结果或字面量。
  • 右值引用(&&)是 C++11 引入的新特性,用来优化资源管理和避免不必要的拷贝操作。

C++11: 花括号初始化列表

使用

在C++98/03中我们只能对普通数组和POD(plain old data,简单来说就是可以用memcpy复制的对象)类型可以使用列表初始化,如下:

//数组的初始化列表: 
int arr[3] = {1,2,3}
//POD类型的初始化列表:
struct A
{
 int x;
 int y;
}a = {1,2};

在C++11中初始化列表被适用性被放大,可以作用于任何类型对象的初始化。如下:

X x1 = X{1,2};
X x2 = {1,2}; // 此处的'='可有可⽆
X x3{1,2};
X* p = new X{1,2};

//列表初始化也可以用在函数的返回值上
std::vector<int> func() {
    return {};
}

变量类型的适用范围

聚合类型可以进行直接列表初始化

聚合类型包括

  1. 普通数组,如int[5],char[],double[]等
  2. 一个类,且满足以下条件:
    1. 没有用户声明的构造函数
    2. 没有用户提供的构造函数(允许显示预置或弃置的构造函数)
    3. 没有私有或保护的非静态数据成员
    4. 没有基类
    5. 没有虚函数
    6. 没有{}和=直接初始化的非静态数据成员
    7. 没有默认成员初始化器

原理

对于一个聚合类型,使用列表初始化相当于使用std::initializer_list对其中的相同类型T的每个元素分别赋值处理,类似下面示例代码;

struct CustomVec {
    std::vector<int> data;
    CustomVec(std::initializer_list<int> list) {
        for (auto iter = list.begin(); iter != list.end(); ++iter) {
            data.push_back(*iter);
        }
    }
};

优势

  1. 方便,且基本上可以替代括号初始化
  2. 可以使用初始化列表接受任意长度
  3. 可以防止类型窄化,避免精度丢失的隐式类型转换

参考文献

  1. https://zh.cppreference.com/

  2. https://leetcode-cn.com/problems/path-with-maximum-gold/solution/huang-jin-kuang-gong-by-leetcode-solutio-f9gg/

  3. https://blog.csdn.net/qq_33221533/article/details/82119031

  4. ⼩贺 C++ ⼋股⽂ PDF 的作者,电⼦书的内容整理于公众号「herongwei」

  5. https://blog.csdn.net/hailong0715/article/details/54018002

Python

装饰器 decorator

@能在最小改变函数的情况下,包装新的功能。1

def use_logging(func):

    def wrapper():
        logging.warn("%s is running" % func.__name__)
        return func()
    return wrapper

@use_logging
def foo():
    print("i am foo")

foo()

Programming Specification

  1. 命名空间(namespace)可以基本理解成每个文件是一个,通过import来使用

if name == "main"

在Python中,if __name__ == "__main__"这种写法通常出现在模块中,它的作用是控制模块的执行流程。

当一个模块被导入时,Python解释器会自动将这个模块的__name__属性设置为模块名称。但是如果模块是被直接运行的,则__name__属性会被设置为字符串__main__。

所以if name == "main"可以用来区分模块是被导入运行还是被直接运行:

如果模块是被导入的,if语句不会执行。因为模块的__name__不等于__main__。 如果模块是被直接运行的,if语句会执行。因为模块的__name__等于__main__。

单下划线、双下划线、头尾双下划线说明:

__foo__: 定义的是特殊方法,一般是系统定义名字 ,类似 init() 之类的。

_foo: 以单下划线开头的表示的是 protected 类型的变量,即保护类型只能允许其本身与子类进行访问,不能用于 from module import *

__foo: 双下划线的表示的是私有类型(private)的变量, 只能是允许这个类本身进行访问了。

数据快速写入和读取文件

任意变量使用pickle

# 使用二进制
with open('my_dict.json', 'wb') as f: 
    pickle.dump(my_dict, f)
with open('my_dict.json', 'rb') as f:
    loaded_dict = pickle.load(f)

可以序列化的使用json

import json
# 将 dict 保存为 JSON 格式
with open('my_dict.json', 'w') as f:
    json.dump(my_dict, f)

# 加载 dict
with open('my_dict.json', 'r') as f:
    loaded_dict = json.load(f)

多个变量

# 将多个变量组织成字典或列表
data = {
    "scaAvgTime": scaAvgTime,
    "var2": var2,
    "var3": var3
}

result_file = "result.json"

# 将数据写入JSON文件
with open(result_file, "w") as f:
    json.dump(data, f)

# 读取JSON文件
with open(result_file, "r") as f:
    data = json.load(f)

# 获取保存的变量值
scaAvgTime = data["scaAvgTime"]
var2 = data["var2"]
var3 = data["var3"]

python优化 可视化

cProfile + snakeviz + gprof2dot

 ./gprof2dot.py -f pstats Diff.status | dot -Tpng -o ./output/Diff.png

https://github.com/plasma-umass/scalene

reference

https://github.com/jrfonseca/gprof2dot

https://zhuanlan.zhihu.com/p/58535923

https://www.cnblogs.com/oloroso/p/6548189.html

Debug

打印当前堆栈

traceback.print_stack()

icecream for debug

  • 优雅打印对象:函数名,结构体
  • 打印行号和栈(没用输入时
  • 允许嵌套(会将输入传递到输出
  • 允许带颜色ic.format(*args)获得ic打印的文本
  • debug ic.disable()and ic.enable()
  • 允许统一前缀 ic.configureOutput(prefix='Debug | ')
  • 不用每个文件import
from icecream import ic
ic(STH)

from icecream import install
install()

ic.configureOutput(prefix='Debug -> ', outputFunction=yellowPrint)

prefix 添加时间

import datetime
def ic_with_timestamp(*args):
    return '\n\n%s shaojieLog >| ' % datetime.datetime.now().strftime("%Y-%m-%d %H:%M:%S")

ic.configureOutput(prefix=ic_with_timestamp)

hide message

# Disable icecream
ic.disable()

# This message will be hidden
ic("This message will NOT be shown")

# Re-enable icecream
ic.enable()

ic()的输出无法被tee的log文件捕获

这个问题与 icecream 库的 ic() 函数的默认输出机制有关。icecream 默认将输出发送到标准错误(stderr),而 tee 命令的默认行为是只捕获标准输出(stdout)。因此,ic() 的输出不会被 tee 捕获到。

要解决这个问题,你可以采取以下几种方式:

  1. 使用 ic() 输出到标准输出
  2. 你可以配置 icecream 的输出流,使其输出到标准输出,而不是默认的标准错误。这样,tee 就可以捕获 ic() 的输出。
from icecream import ic
import sys

ic.configureOutput(outputFunction=sys.stdout.write)

这样,ic() 的输出就会被发送到标准输出,然后可以被 tee 命令捕获到。

  1. tee 捕获标准错误和标准输出

你也可以让 tee 捕获标准错误(stderr)和标准输出(stdout),这样无需修改 icecream 的配置。

在你的命令中,可以使用如下方式:

python3.8 setup.py build bdist_wheel 2>&1 | tee compile.log

在这个命令中,2>&1 将标准错误重定向到标准输出,因此 tee 可以同时捕获两者。

  1. 使用 tee 捕获标准错误单独输出

如果你只想捕获标准错误的输出,并将其保存到日志文件,可以使用以下命令:

python3.8 setup.py build bdist_wheel 1>&2 | tee compile.log

或将 stderrstdout 单独重定向:

python3.8 setup.py build bdist_wheel 2>compile.log

虚拟环境venv

python3 -m venv name

#在Windows上,运行:
name\Scripts\activate.bat # poweshell运行activate.ps1
#在Unix或MacOS上,运行:
source name/bin/activate
#(这个脚本是为bash shell编写的。如果你使用 csh 或 fish shell,你应该改用 activate.csh 或 activate.fish 脚本。)
python3 setup.py install

各种依赖

pip freeze >requirements.txt //导出
pip install -r requirements.txt //安装

pip换源

有时候开代理会出现Retry

vim ~/.pip/pip.conf 
[global]
index-url = https://pypi.tuna.tsinghua.edu.cn/simple

pip config set global.trusted-host pypi.mirrors.ustc.edu.cn  
pip install --trusted-host mirrors.bfsu.edu.cn icecream  

python的实现过的各种功能模块

并行调用shell命令,超时kill

https://github.com/Kirrito-k423/BHive-Prediction-Compare/blob/main/pythonTest/0326_newBar_qcjiang.py

基于Pipe的自定义多进程进度条

https://github.com/Kirrito-k423/BHive-Prediction-Compare/blob/main/pythonTest/0326_newBar_qcjiang.py

为什么c语言运行比python快

运行流程区别

python的传统运行执行模式:录入的源代码转换为字节码,之后字节码在python虚拟机中运行。代码自动被编译,之后再解释成机器码在CPU中执行。

c编译器直接把c源代码编译成机器码。过程比python执行过程少了字节码生成和虚拟机执行字节码过程。所以自然比python快。

解释性语言

解释型语言没有严格编译汇编过程,由解释器将代码块按需要变运行边翻译给机器执行。因此解释型语言一度存在运行效率底,重复解释的问题。但是通过对解释器的优化!可以提高解释型语言的运行效率。

Python 字节码

Python 以 .pyc 结尾的 “ 字节码(bytecode)” 文件(二进制文件),一般位于__pycache__ 的子目录中,可以避免每次运行 Python 时去重新解析源代码。

python -m py_compile file.py  # 生成单个pyc文件

python程序运行中的 Python 字节码 是什么时候产生的,我修改py文件,其对应的字节码文件会在何时更新

gpt3.5: Python字节码是由Python解释器在执行Python源代码之前生成的中间表示形式。它是将源代码翻译为机器可以理解的指令序列的一种形式。字节码文件的扩展名通常为.pyc(Python 3)或.pyo(Python 2)。

当你运行Python程序时,如果存在对应的字节码文件(.pyc或.pyo),解释器会首先检查字节码文件的时间戳。如果字节码文件的时间戳比源代码文件的时间戳更晚,且没有进行代码的修改,解释器会直接加载和执行字节码,跳过源代码的编译过程。

当你修改了Python源代码文件时,字节码文件不会立即更新。Python解释器会在下一次运行程序时,检测到源代码文件的修改,并重新编译生成新的字节码文件。这样,更新后的字节码文件将反映源代码的更改,并用于后续的执行。

访问和理解 Python 字节码

经过编译的python文件可以提高程序的运行速度,一定程度上也对源代码起到了保护作用。然而如果我们只有编译过的python字节码文件,就给我们审查源码造成了一定的困难,这就引出了python字节码反编译的需求。

如果你想玩转字节码,那么,Python 标准库中的 dis 模块将对你有非常大的帮助;dis 模块为 Python 字节码提供了一个 “反汇编”,它可以让你更容易地得到一个人类可读的版本,以及查找各种字节码指令。

知道如何去访问和阅读 Python 字节码将让你很容易回答为什么某些结构比其它结构运行的更快这样的问题(比如,为什么 {} 比 dict() 快)(尝试对比一下: dis.dis("{}") 与 dis.dis("dict()") 就会明白)。

pyo优化文件

pyo文件是源代码文件经过优化编译后生成的文件,是pyc文件的优化版本。编译时需要使用-O和-OO选项来生成pyo文件。在Python3.5之后,不再使用.pyo文件名,而是生成文件名类似“test.opt-n.pyc的文件。

python -O -m py_compile test.py

Python 虚拟机

CPython 使用一个基于栈的虚拟机。(你可以 “推入” 一个东西到栈 “顶”,或者,从栈 “顶” 上 “弹出” 一个东西来)。

CPython 使用三种类型的栈:

  1. 调用栈(call stack)。这是运行 Python 程序的主要结构。它为每个当前活动的函数调用使用了一个东西 —— “ 帧(frame)”
  2. 在每个帧中,有一个 计算栈(evaluation stack)(也称为 数据栈(data stack))。这个栈就是 Python 函数运行的地方,运行的 Python 代码大多数是由推入到这个栈中的东西组成的,操作它们,然后在返回后销毁它们。
  3. 在每个帧中,还有一个块栈(block stack)。它被 Python 用于去跟踪某些类型的控制结构:循环、try / except 块、以及 with 块,全部推入到块栈中,当你退出这些控制结构时,块栈被销毁。

Python 如何工作

Python 与大多数解释型语言一样,确实是将源代码编译为一组虚拟机指令,并且 Python 解释器是针对相应的虚拟机实现的。这种中间格式被称为 “字节码”。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

在了解c语言编译流程的时候,联想到了python有什么不同。

参考文献

https://zhuanlan.zhihu.com/p/39259061

[C++ Basic] STL Data Structure

基础杂项

auto的使用

  • 当你想要拷贝range的元素时,使用 for(auto x : range).
  • 当你想要修改range的元素时,使用 for(auto && x : range)
  • 当你想要只读range的元素时,使用 for(const auto & x : range).

容器间的转换 begin end

vector<int>& nums1
unordered_set<int> nums_set(nums1.begin(), nums1.end());

unordered_set<int> result;
return vector<int>(result.begin(), result.end());

迭代器知识

前后第k个元素

  • std::prev 函数接受两个参数:一个是指向迭代器的参数,另一个是整数偏移量。它返回从指定迭代器开始向前移动指定偏移量后的迭代器。
  • std::next 函数接受两个参数:一个是指向迭代器的参数,另一个是整数偏移量。它返回从指定迭代器开始向前或后移动指定偏移量后的迭代器。
auto prevIt = std::prev(it);

auto next2It = std::next(it, 2);

auto it2 = it;
advance(it2,k);

advance : 形似index的随机访问

  • std::advance 函数的实现方式取决于迭代器的类型。
  • 对于随机访问迭代器(后面解释),它会直接使用 += 运算符来实现移动。
  • 对于双向迭代器和输入迭代器,它会使用循环来实现移动。
  • 例如,以下是 std::advance 的一个简单实现, 这个实现使用了 C++17 的 if constexpr 特性,以便在编译时选择不同的实现方式。:
template <typename InputIt, typename Distance>
void advance(InputIt& it, Distance n) {
    if constexpr (std::is_same_v<std::random_access_iterator_tag,
                typename std::iterator_traits<InputIt>::iterator_category>) {
        it += n; //如果迭代器是随机访问迭代器(后面解释),它会使用 += 运算符来移动;
    } else {
        if (n >= 0) {
            while (n--) {
                ++it; //否则,它会使用循环来移动。
            }
        } else {
            while (n++) {
                --it;
            }
        }
    }
}

随机访问迭代器

  • 随机访问迭代器是一种迭代器类型,它支持在常数时间内访问序列中的任何元素。
  • 它们还支持指针算术运算,例如 +- 运算符,以及下标运算符 []
  • 例如,对于一个指向数组的随机访问迭代器 it,可以使用以下语法访问第 i 个元素:*(it + i) or it[i]
  • STL 中的容器 vector 和 deque 都提供了随机访问迭代器。除此之外,C++ 标准库中的很多算法也要求输入迭代器是随机访问迭代器,例如 std::sortstd::nth_element 等。

正向迭代器和反向迭代器

  • 由于类型不同经常需要转换
  • 对于一个正向迭代器 it,可以使用以下语法将其转换为反向迭代器ritstd::reverse_iterator<Iterator> rit(it);
  • 反向迭代器可以使用以下语法转换为正向迭代器:
std::reverse_iterator<Iterator> rit;
Iterator it = rit.base();

反向遍历

  • 建议使用rbegin rend。注意++it而不是--it
  • rbegin指向最后一个元素
  • rend 指向reverse遍历的后一个元素。
for(auto it = collection.rbegin(); it != collection.rend(); ++it) {
    std::cout << *it << std::endl;
    // std::cout << it->first << ", " << it->second << std::endl;
}
  • 错误的原始写法, 错误原因showedPositive.begin()==(--showedPositive.begin()
  • std设计了一个循环。
  • 同样的设计在showedPositive.rend()==(++showedPositive.rend())
  • 但是showedPositive.rbegin() != (--showedPositive.rbegin())
for(auto it=--showedPositive.end(); it!=--showedPositive.begin(); it--){

}

bitset

bitset类型存储二进制数位。

初始化

std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));

//foo: 0000000000000000
//bar: 0000111110100010
//baz: 0000000101111001

将数转化为其二进制的字符串表示

int i = 3;
string bin = bitset<16>(i).to_string(); //bin = "0000000000000011"
bin = bin.substr(bin.find('1'));        //bin = "11"

char 与 字符串

元音与index的相互映射

string vowel = "AEIOUaeiou";
if vowel.find(c) != std::string::npos;

voewl[0] = 'A';

string

读取空格分割的

stringstream txt(s);
string word;
while(txt>>word){
    // to do
}

遍历

string s;
for(auto && x : s)

打印string

printf("%s", your_string.c_str()); //不推荐
cout << your_string;

string不同于C语言的char来存储字符串

//复制
str3 = str1;    len = str3.size();
//连接
str1 = str1 + str2;  strcat( str1, str2);
//总长度
len = str3.size();  strlen(s1);

C++ string 成员函数 length() 等同于 size(),但是和 C 库函数 strlen() 有着本质区别

https://blog.csdn.net/K346K346/article/details/79546919

初始化

std::string s0 ("Initial string");

// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);
std::string s3 (s0, 8, 3);
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);
std::string s6a (10, 'x');
std::string s6b (10, 42);      // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);

std::cout << "s1: " << s1 << "\ns2: " << s2 << "\ns3: " << s3;
std::cout << "\ns4: " << s4 << "\ns5: " << s5 << "\ns6a: " << s6a;
std::cout << "\ns6b: " << s6b << "\ns7: " << s7 << '\n';

//output
s1: 
s2: Initial string
s3: str
s4: A character sequence
s5: Another char
s6a: xxxxxxxxxx
s6b: **********
s7: Initial

插入insert

在指向位置的右边插入

// inserting into a string
#include <iostream>
#include <string>

int main ()
{
  std::string str="to be question";
  std::string str2="the ";
  std::string str3="or not to be";
  std::string::iterator it;

  // used in the same order as described above:
  str.insert(6,str2);                 // to be (the )question
  str.insert(6,str3,3,4);             // to be (not )the question
  str.insert(10,"that is cool",8);    // to be not (that is )the question
  str.insert(10,"to be ");            // to be not (to be )that is the question
  str.insert(15,1,':');               // to be not to be(:) that is the question
  it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
  str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
  str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

  std::cout << str << '\n';
  return 0;
} 

尾部插入char

不同的方法

std::string s = "C+";
char ch = '+';

s.push_back(ch);
s += ch; //string::operator+=, which is overloaded for chars and internally calls to the push_back() function.
s.append(1, ch); //1*ch个字符
s.append("abcd"); //后面添加abcd字符串

std::stringstream ss;
ss << s << ch;
ss >> s;

s.insert(s.length(), 1, ch);

截取string

// Copy three characters of s1 (starting
// from position 1)
//第一个参数是要截取的字符串,第二个参数是截取的开始位置,第三个参数是截取长度(可选)1。如果没有指定长度,则子字符串将延续到源字符串的结尾。
string r = s1.substr(1, 3);

// Take any string
string s = "dog:cat";
// Find position of ':' using find()
int pos = s.find(":");
// Copy substring after pos(include pos)
string sub = s.substr(pos);
// Copy substring before pos(not include pos)
string sub = s.substr(0 , pos);

反转reverse string

reverse(greeting.begin(),greeting.end());

寻找子元素位置

// log1 中找空格
int pos1 = log1.find_first_of(" ");

// 判断数字
bool isDigit1 = isdigit(log1[pos1 + 1]);

// 判断是否找到
if(s.find(goal) != string::npos){
}

npos是一个常数,表示size_t的最大值(Maximum value for size_t)。许多容器都提供这个东西,用来表示不存在的位置,类型一般是std::container_type::size_type。

string erase

三种情况

// string::erase
#include <iostream>
#include <string>

int main ()
{
  std::string str ("This is an example sentence.");
  std::cout << str << '\n';
                                           // "This is an example sentence."
  str.erase (10,8);                        //            ^^^^^^^^
  //去除index=10的连续8个元素
  std::cout << str << '\n';
                                           // "This is an sentence."
  str.erase (str.begin()+9);               //           ^
  //去除itr指向的元素
  std::cout << str << '\n';
                                           // "This is a sentence."
  str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
  //去除[first,last).的元素
  std::cout << str << '\n';
                                           // "This sentence."
  return 0;
}

删除最后一个元素

std::string s = "C,C++,Java,";
if (!s.empty()) {
 s.pop_back();
}

if (!s.empty()) {
 s.resize(s.size() - 1);
}

if (!s.empty()) {
 s.erase(std::prev(s.end()));
}

if (!s.empty()) {
 s.erase(s.size() - 1);
}

容器适配器

STL 提供了 3 种容器适配器,分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

stack 栈

stack<int> minStack;
minStack = stack<int>();

// 支持初始化,但是注意将整个数组元素推入堆栈,堆栈的顶部元素top将是数组的第一个元素。
std::vector<int> elements = {1, 2, 3, 4, 5};
std::stack<int> myStack(elements.begin(), elements.end());


!minStack.empty()
minStack.pop(); //该函数仅用于从堆栈中删除元素,并且没有返回值。因此,我们可以说该函数的返回类型为void。
minStack.push();
minStack.top();

stack

注意pop仅用于从堆栈中删除元素,并且没有返回值, 一般用法如下

top_value = stIn.top();
stIn.pop();

堆栈,先进先出

empty 该函数用于测试堆栈是否为空如果堆栈为空则该函数返回true否则返回false
size 该函数返回堆栈容器的大小该大小是堆栈中存储的元素数量的度量
top 该函数用于访问堆栈的顶部元素该元素起着非常重要的作用因为所有插入和删除操作都是在顶部元素上执行的
push 该函数用于在堆栈顶部插入新元素
pop 该函数用于删除元素堆栈中的元素从顶部删除
emplace 该函数用于在当前顶部元素上方的堆栈中插入新元素
swap 该函数用于交换引用的两个容器的内容

清空

stack不支持clear, 除开一个个pop

std::stack<int> myStack;
// 添加元素到 myStack

myStack = std::stack<int>(); // 清空 myStack, 丢弃原有对象

std::stack<int> emptyStack;
myStack.swap(emptyStack); // 清空 myStack

queue

empty() 如果 queue 中没有元素的话,返回 true。
size() 返回 queue 中元素的个数。

front() 返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
back() 返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。

push(const T& obj) 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
emplace() 在 queue 的尾部直接添加一个元素。
push(T&& obj) 以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop() 删除 queue 中的第一个元素。
swap(queue<T> &other_queue) 将两个 queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

特点

  1. 队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构;
  2. 在队尾添加元素,在队头删除元素。

操作

c++ #include< queue> 。定义:queue< int > q;

q.empty()               如果队列为空返回true,否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值,但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值,但不删除该元素

C++ 清空队列(queue)的几种方法

直接用空的队列对象赋值

queue<int> q1;
// process
// ...
q1 = queue<int>();
使用swap,这种是最高效的,定义clear,保持STL容器的标准。
void clear(queue<int>& q) {
    queue<int> empty;
    swap(empty, q);
}

队列保存一对数

queue<pair<int, int> > gq;
gq.push({ 10, 20 });

pair<int, int> p;
int x,y;
p = gq.front();
x = p.first;
y = p.second;

队列保存结构体

typedef struct
{
    int y;
    int xbegin;
    int xend;
}triple;
queue<triple> threadq[64];
delaytask.push({x1+delay,y-1});
p = threadq[c].front(); 
p.xbegin;
p.xend;

deque 双端队列

deque 容器也擅长在序列尾部添加或删除元素(时间复杂度为O(1)),而不擅长在序列中间添加或删除元素。

begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。

size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值,一般是 232-1,我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。

at() 使用经过边界检查的索引访问元素。

front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。

insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素,容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。

emplace_back() not support <brace-enclosed initializer list> for this

priority_queue(优先队列)

自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

#include <queue>

优先级排序原理

缺省情况下priority_queue利用max-heap(大顶堆)完成对元素的排序,这个大顶堆是以vector为表现形式的complete binary tree(完全二叉树)。

声明

priority_queue<Type, Container, Functional>

//自定义降序1
class _c{
public:

 bool operator () (const pair<int, int> &p, const pair<int, int> &q) const
 {
  return p.first < q.first;
 }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, _c> pq;
//自定义降序2
auto cmp = [](pair<int,int>&a, pair<int,int>&b){return a.second<=b.second;};
priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> q(cmp);
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)

//默认排序是less,但是在priority_queue是降序。在其余数据结构里都是升序
priority_queue<pair<int, int>> answer;
//example
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;
  1. Type 就是数据类型,
  2. Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),
  3. Functional 就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆

基本操作

size() 返回优先队列的大小。
empty() 它验证队列是否为空。基于验证,它返回队列的状态。

top() 此函数用于寻址优先队列的最顶层元素。

emplace() 它在优先队列的顶部插入一个新元素。
push() 它将新元素插入优先队列。
pop() 它将优先级最高的元素从队列中删除。
swap() 它将优先队列的元素与具有相同类型和大小的另一个队列交换。

顺序容器与关联容器

顺序容器包括vector、deque、list、forward_list、array、string,所有顺序容器都提供了快速顺序访问元素的能力。

关联容器包括set、map

关联容器和顺序容器有着根本的不同:关联容器中的元素是按关键字来保存和访问的。与之相对,顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器不支持顺序容器的位置相关的操作。原因是关联容器中元素是根据关键字存储的,这些操作对关联容器没有意义。而且,关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值得操作。

关联容器支持高效的关键字查找和访问。

二叉树

分类

存储方式

链表,或者数组(如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。)

链式结构如下,注意左右孩子节点

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;

遍历方式

深度遍历: 前/中/后序遍历。

注意:这里前中后,其实指的就是中间节点/根节点的遍历顺序

heap 堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值。
  • 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;
  • 或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
  • 堆总是一棵完全二叉树。

STL操作

  • make_heap()​​将区间内的元素转化为heap.
  • ​push_heap()​​对heap增加一个元素.
  • ​​pop_heap()​​对heap取出下一个元素.
  • ​sort_heap()​​对heap转化为一个已排序群集.
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;

make_heap (v.begin(),v.end());//male_heap就是构造一棵树,使得每个父结点均大于等于其子女结点
cout << "initial max heap   : " << v.front() << endl;

pop_heap (v.begin(),v.end());//pop_heap不是删除某个元素而是把第一个和最后一个元素对调后[first,end-1]进行构树,最后一个不进行构树
v.pop_back();//删除最后一个的结点
cout << "max heap after pop : " << v.front() << endl;

v.push_back(99);//在最后增加一个结点
push_heap (v.begin(),v.end());//重新构树
cout << "max heap after push: " << v.front() << endl;

sort_heap (v.begin(),v.end());//把树的结点的权值进行排序,排序后,序列将失去堆的特性
//请在使用这个函数前,确定序列符合堆的特性,否则会报错!

hash_map VS unordered_map

由于在C++标准库中没有定义散列表hash_map,标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的,所以它们在功能和性能保证上都有微妙的差别。

从C++11开始,哈希表实现已添加到C++标准库标准。决定对类使用备用名称,以防止与这些非标准实现的冲突,并防止在其代码中有hash_table的开发人员无意中使用新类。

所选择的备用名称是unordered_map,它更具描述性,因为它暗示了类的映射接口和其元素的无序性质。

可见hash_map , unordered_map本质是一样的,只不过 unordered_map被纳入了C++标准库标准

map vs unordered_map

  1. map
  2. 内部数据的组织,基于红黑树实现,红黑树具有自动排序的功能,因此map内部所有的数据,在任何时候,都是有序的。其中每个键都是唯一的,可以插入或删除,但不能更改。但是与键关联的值可以更改。
  3. 红黑树是一种含有红黑结点并能自平衡的二叉查找/搜索树, 别称平衡二叉B树(symmetric binary B-trees)
  4. unordered_map(hash_map)
  5. 基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。
  6. 标准库的unordered_map,底层实现是基于hashtable的,其避免冲突的方法是使用开链(seperate chaining)法,这种做法是在每一个表格元素中维护一个list,每个表格元素称之为buket(桶)
                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required| 

map初始化

//c++11以上
map<string,int> m3 = {
    {"string",1}, {"sec",2}, {"trd",3}
    };

map<string,string> m4 = {
{"first","second"}, {"third","fourth"},
{"fifth","sixth"}, {"begin","end"}
};

unordered_map 哈希表

unordered_map<int, int> umap;
umap[a + b]++;

map的value是int,默认为0。可以直接++

unordered_map<int, int> cnt;
++cnt[num];
// c++17 支持
for (auto &[num, c] : cnt) {
}
// 否则
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    auto& key = it->first;
    auto& value = it->second;
    // 使用 key 和 i 进行操作
}
for (auto &[x, _] : cnt) {
    //sth
}
cnt.at(num) //unordered_map 类模板中,还提供有 at() 成员方法,和使用 [ ] 运算符一样,at() 成员方法也需要根据指定的键,才能从容器中找到该键对应的值;不同之处在于,如果在当前容器中查找失败,该方法不会向容器中添加新的键值对,而是直接抛出out_of_range异常。

插入元素

// insert 不能覆盖元素,已经存在会失败
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
// 数组方式可以覆盖
mapStudent[1] = "student_one";  

可以用pair来获得是否insert成功,程序如下

pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));

我们通过pair的第二个变量来知道是否插入成功,它的第一个变量返回的是一个map的迭代器,如果插入成功的话Insert_Pair.second应该是true的,否则为false。

查找是否存在 count

用count函数来判定关键字是否出现,其缺点是无法定位数据出现位置,由于map的特性,一对一的映射关系,就决定了count函数的返回值只有两个,要么是0,要么是1,出现的情况,当然是返回1了

查找是否存在 find

通过 find() 方法得到的是一个正向迭代器,该迭代器的指向分以下 2 种情况:

  1. 当 find() 方法成功找到以指定元素作为键的键值对时,其返回的迭代器就指向该键值对;
  2. 当 find() 方法查找失败时,其返回的迭代器和 end() 方法返回的迭代器一样,指向容器中最后一个键值对之后的位置。
//查找成功
unordered_map<string, string>::iterator iter = umap.find("Python教程");
cout << iter->first << " " << iter->second << endl;
//查找失败
unordered_map<string, string>::iterator iter2 = umap.find("GO教程");
if (iter2 == umap.end()) {
    cout << "当前容器中没有以\"GO教程\"为键的键值对";
}

删除

mymap.erase ('c');               // erasing by key

set

  1. 按关键字有序保存元素:
  2. set(关键字即值,即只保存关键字的容器);
  3. multiset(关键字可重复出现的set);
  4. 无序集合:
  5. unordered_set(用哈希函数组织的set);
  6. unordered_multiset(哈希组织的set,关键字可以重复出现)。

set就是关键字的简单集合。当只是想知道一个值是否存在时,set是最有用的。

在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树:红黑树,也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。

set具备的两个特点:

  • set中的元素都是排序好的
  • set中的元素都是唯一的,没有重复的

常用函数

定义的参数compare可见,为了确定唯一性,需要有个值唯一表示存储的复杂类型

template < class T,                             // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>         // set::allocator_type
           > class set;

//初始化
set<char> vowel {'a','e','i','o','u'};
insert()在集合中插入元素
emplace() 最大的作用是避免产生不必要的临时变量
erase()删除集合中的元素
//删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);
//第 1 种格式的 erase() 方法,其返回值为一个整数,表示成功删除的元素个数;
//后 2 种格式的 erase() 方法,返回值都是迭代器,其指向的是 set 容器中删除元素之后的第一个元素。

find()返回一个指向被查找到元素的迭代器返回值该函数返回一个迭代器该迭代器指向在集合容器中搜索的元素如果找不到该元素则迭代器将指向集合中最后一个元素之后的位置end
count()- 查找的bool结果
size()集合中元素的数目

begin();            // 返回指向第一个元素的迭代器
end();              // 返回指向迭代器的最末尾处(即最后一个元素的下一个位置)
clear();            // 清除所有元素
count();            // 返回某个值元素的个数

swap()交换两个集合变量

template <class T, class Compare, class Alloc>
  bool operator== ( const set<T,Compare,Alloc>& lhs,
                    const set<T,Compare,Alloc>& rhs ); // 和map类似的,重载相等判断

set::lower_bound(key)

參數:該函數接受單個強製性參數鍵,該鍵指定要返回其lower_bound的元素。

返回值:該函數返回一個指向容器中元素的迭代器,該迭代器等效於在參數中傳遞的k。如果set容器中不存在k,則該函數返回一個迭代器,該迭代器指向剛好大於k的下一個元素。如果參數中傳遞的鍵超過了容器中的最大值,則返回的迭代器等效於s.end()(特殊的迭代器指向最後一個元素)。

find example

//set.find(key)!=set.end() 的判断一般会比count快
auto p = points.find({x, y});
if (p != points.end()) {
 points.erase(p);
 ……
}

// 检查键30是否存在
if (mp.count(30))
 cout << "键30存在\n";
else
 cout << "键30不存在\n";

unordered_set

auto hash_p = [](const pair<int, int> &p) -> size_t {
  static hash<long long> hash_ll;
  return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
 };
unordered_set<pair<int, int>, decltype(hash_p)> points(0, hash_p); //(0,hash_p)分别为迭代器的开始和结束的标记(数组多为数据源)
//多用于数组 set<int> iset(arr,arr+sizeof(arr)/sizeof(*arr));

类似的例子

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

上面的不是用lambda expression隐函数,而是定义函数的写法

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};
std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

How to use unordered_set with custom types?

https://stackoverflow.com/questions/9729390/how-to-use-unordered-set-with-custom-types/9729747#9729747

set map 的区别

map和set都是C++的关联容器,其底层实现都是红黑树(RB-Tree)。由于 map 和set所开放的各种操作接口,RB-tree 也都提供了,所以几乎所有的 map 和set的操作行为,都只是转调 RB-tree 的操作行为。 map和set区别在于:

(1)map中的元素是key-value(关键字—值)对:关键字起到索引的作用,值则表示与索引相关联的数据;Set与之相对就是关键字的简单集合,set中每个元素只包含一个关键字

(2)set的迭代器是const的,不允许修改元素的值;map允许修改value,但不允许修改key其原因是因为map和set是根据关键字排序来保证其有序性的,如果允许修改key的话,那么首先需要删除该键,然后调节平衡,再插入修改后的键值,调节平衡,如此一来,严重破坏了map和set的结构,导致iterator失效,不知道应该指向改变前的位置,还是指向改变后的位置。所以STL中将set的迭代器设置成const,不允许修改迭代器的值;而map的迭代器则不允许修改key值,允许修改value值。

(3)map支持下标操作,set不支持下标操作。map可以用key做下标,map的下标运算符[ ]将关键码作为下标去执行查找,如果关键码不存在,则插入一个具有该关键码和mapped_type类型默认值的元素至map中,因此下标运算符[ ]在map应用中需要慎用,const_map不能用,只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用,mapped_type类型没有默认值也不应该使用。如果find能解决需要,尽可能用find。

map和multimap的区别

map不允许相同key值存在,multimap则允许相同的key值存在。

set/map 后insert 先输出

由于是有序的,对于int这种能比大小的,默认是输出是从小到大,可以改变。

  • set中存放的为数(整数,浮点数......),在set中会按从小到大排列这些数
  • 存放指针,都会按照地址排序
  • set 中存放的为string,存入的string会按字母表顺序排列
  • 至于存放类的话,还可以自己定义排列规则
  • 存放结构体?没定义大小关系的类?
  • *it 递增的顺序,存储的是指向某元素的指针,则是指针地址递增的顺序。

并差集

核心是

  1. 同一个并查集内的元素会指向同一个parent
  2. 可以维护并查集总个数Rank
  3. 和每个并查集的子集合元素个数
  4. 数据结构用数组和map都行

例子是LeetCode 1020

class UnionFind {
public:
    // 初始化未union的数组
    UnionFind(const vector<vector<int>> & grid) {//初始化遍历
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        //this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n, 0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        //onEdge[index] = true;
                    }
                }
            }
        }
    }

    int find(int i) {
        // 原始版本
        return (parent[i] == i)? i : find(parent[i]);
        // “路径压缩”。在执行Find的过程中,将路径上的所有节点都直接连接到根节点上。
        return (parent[i] == i)? i : (parent[i] = find(parent[i]));
    }

    void uni(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            // "按秩合并"。实际上就是在合并两棵树时,将高度较小的树合并到高度较大的树上。
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
            } else {
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;  
    // 如果带合并的元素表示有负数表示,或者不是连续表示的。可以使用map
    map<int, int> parent;//定义一个并查集
    map<int, int> ranks;//定义树的深
};

对于不确定元素个数来初始化的

class DisjointSet {
  public:
    std::unordered_map<BBLID, BBLID> parent;

    BBLID Find(BBLID l) {
        auto it = parent.find(l);
        if (it == parent.end()) {
            parent[l] = l;
        }
        else {
            while (parent[l] != l) {
                // 路径压缩部分
                parent[l] = parent[parent[l]];
                l = parent[l];
            }
        }
        return l;
    }

    void Union(BBLID m, BBLID n) {
        BBLID x = Find(m);
        BBLID y = Find(n);
        parent[x] = y;
    }
};

emplace VS push

push() adds a copy of an already constructed object into the queue as a parameter, it takes an object of the queue's element type.

emplace() constructs a new object in-place at the end of the queue. It takes as parameters the parameters that the queue's element types constructor takes.

If your usage pattern is one where you create a new object and add it to the container, you shortcut a few steps(creation of a temporary object and copying it) by using emplace().

数组

int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };

数组初始化为0

//直接初始化为0
int a[SIZE]={0};

#include<string.h>
int a[SIZE];
memset(a, 0, sizeof(a));
memset(a, 0, sizeof(int)*1000);//这里的1000是数组大小,需要多少替换下就可以了。 

注意 memset是按照字节进行赋值,即对每一个字节赋相同值。除开0和-1,其他值都是不安全的,不会赋值期望的值。比如int是四个字节。

  • memset(a,127,sizeof(a)),全部初始化为int的较大值,即2139062143(int 最大值为2147483647);
  • memset(a,128,sizeof(a)),全部初始化为一个很小的数,比int最小值略大,为-2139062144。

calloc & malloc

//区分
//calloc() 函数是动态申请内存函数之一,相当于用malloc函数申请并且初始化一样,calloc函数会将申请的内存全部初始化为0。
int *res = (int*)calloc(numsSize, sizeof(int)); 
//方法二:
int *res = (int*)malloc(numsSize * sizeof(int));
memset(res, 0, numsSize * sizeof(int));
//错误写法: memset(res, 0, sizeof(res)); res是指针变量,不管 res 指向什么类型的变量,sizeof( res ) 的值都是 4。

new

int *p = new int();//此时p指向内存的单变量被初始化为0
int *p = new int (5);//此时p指向内存的单变量被初始化为5
int *p = new int[100]()//此时p指向数组首元素,且数组元素被初始化为0
//c++11 允许列表初始化,因此也有了以下几种形式形式
int *p = new int{}//p指向的单变量被初始化为0
int *p = new int{8}//p指向变量被初始化为8
int *p = new int[100]{}//p指向的数组被初始化为0
int *p = new int[100]{1,2,3}//p指向数组的前三个元素被初始化为1,2,3,后边97个元素初始化为0;

new 三维数组

建议老实用vector

int ***array;
// 假定数组第一维为 m, 第二维为 n, 第三维为h
// 动态分配空间
array = new int **[m];
for( int i=0; i<m; i++ )
{
    array[i] = new int *[n];
    for( int j=0; j<n; j++ )
    {
        array[i][j] = new int [h];
    }
}
//释放
for( int i=0; i<m; i++ )
{
    for( int j=0; j<n; j++ )
    {
        delete[] array[i][j];
    }
    delete[] array[i];
}
delete[] array;

Leetcode support VLA

  • The C++ standard does not officially support Variable Length Arrays (VLA), but some compilers, such as g++ and Clang++, may accept it as valid syntax as an extension to the language.
  • leetcode uses g++ 5.4.0 compiler for C++ compilation. It supports variable length array definitions. After ISO C99 specification, arrays with variable length declarations are allowed.
  • The storage is allocated at the point of declaration and deallocated when the block scope containing the declaration exits.
  • And memory consumption differ significantly.
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];

pair

pair<T1, T2> p1;            //创建一个空的pair对象(使用默认构造),它的两个元素分别是T1和T2类型,采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象,它的两个元素分别是T1和T2类型,其中first成员初始化为v1,second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象,其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算,其定义遵循字典次序:如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2                  // 如果两个对象的first和second依次相等,则这两个对象相等;该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

array

array也位于名称空间std中,与数组同样,array对象的长度也是固定的,也使用栈(静态内存分配),而不是自由存储区,所以其效率与数组相同,但更方便,更安全.

array<typeName, nElem> arr;

# include <array>
using namespace std;
array<int, 5> ai;
array<double, 4> ad = {1.1,1.2,1.2,1.3};

//通过如下创建 array 容器的方式,可以将所有的元素初始化为 0 或者和默认元素类型等效的值:
std::array<double, 10> values {};
//使用该语句,容器中所有的元素都会被初始化为 0.0。

//二维
std::array<std::array<int, 2>, 3> m = { {1, 2}, {3, 4}, {5, 6} };

单链表 (自定义)

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

ListNode* head = new ListNode(5);

或者
ListNode* head = new ListNode();
head->val = 5;

while(result != nullptr && result->val == val){
 //多使用nullptr 
 ListNode* tmp_free = result;
 result = result->next;
 delete tmp_free; // 注意释放空间
}

nullptr是一个关键字,可以在所有期望为NULL的地方使用。

  • 与NULL一样,可与任何指针类型相比较。
  • 与NULL不同,只能被赋值给指针类型,它不能隐式转换,也不能与整型相比较。与NULL通常被定义为整数0的宏定义 之间来区分。

list 双向链表

STL list 容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。

  • 特点:
  • 可以看到,list 容器中各个元素的前后顺序是靠指针来维系的,每个元素都配备了 2 个指针,分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null,因为它前面没有元素;同样,尾部元素的后向指针也总为 null。
  • vector是连续的容器,而list是非连续的容器,即vector将元素存储在连续的存储器中,而list存储在不连续的存储器中。
  • 优点
  • list 容器具有一些其它容器(array、vector 和 deque)所不具备的优势,
  • 可以在序列已知的任何位置快速插入或删除元素(时间复杂度为O(1))。
  • 并且在 list 容器中移动元素,也比其它容器的效率高。
  • 缺点
  • 不能像 array 和 vector 那样,通过位置直接访问元素。
    • 举个例子,如果要访问 list 容器中的第 6 个元素,它不支持容器对象名[6]这种语法格式,正确的做法是从容器中第一个元素或最后一个元素开始遍历容器,直到找到该位置。
  • 应用场景:需要对序列进行大量添加或删除元素的操作,而直接访问元素的需求却很少,这种情况建议使用 list 容器存储序列。
list<pair<unordered_set<string>, int>> lst;
unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> nodes;

auto cur = nodes[key], nxt = next(cur); //对迭代器使用next
nodes[key] = lst.emplace(nxt, s, cur->second + 1);

*lst.rbegin()->first.begin(); //链表最后元素的first也就是unordered_set<string>的第一个

emplace & emplace_front

C ++ List emplace()函数在指定位置插入新元素,并且列表的大小增加一。

语法 iterator emplace(iterator pos, value_type val); 参数

pos:它定义了要插入新元素的位置。

val:要在指定位置插入的新值。

返回值

它返回指向新构造元素的迭代器。

vector

构造函数

vector(int nSize)   //创建一个vector,元素个数为nSize

//指定值初始化,ilist5被初始化为包含7个值为3的int
vector(int nSize,const t& t)//创建一个vector,元素个数为nSize,且值均为t
vector<int> ilist5(7,3);
//区分列表初始化, 包含7 和 3两个元素
vector<int> ilist5{7,3};

//改变大小
vals.reserve(cnt.size());

二维vector, 两个维度的长度都未知时:

vector<vector<bool>> name (xSize, vector<bool>(ySize, false));
//leetcode假如写在函数外,class public下,第二维度为空
vector<vector<int>> alphaIndexList{26, vector<int>(0)}; 
//指针使用
vector<int>* todo;
todo= &alphaIndexList[i];
int n = todo->size(); // (*todo).size();
for(auto &x: *todo)

二维vector, 已知某一个维度的大小:

vector<int> alphaIndexList[26];
alphaIndexList[i].push_back(x);

返回表示

vector<int> func() {
    //sth
    return {it->second, i}; //no []
    //or
    return {};
}

元素排序

如果需要元素有序,考虑stable_sort

//默认是从低到高,加入std::greater<int>() 变成从高到低排序
sort(nums.begin(),nums.end(),std::greater<int>());

//vector of pair
vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};

//c++14 
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});

//C++11 using lambdas
sort(arr.begin(), arr.end(), 
 [](const pair<int, char> & p1, const pair<int, char> & p2) {
  return p1.first > p2.first;
 }
);

//origin 
struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};
std::sort(v.begin(), v.end(), sort_pred());

增加函数

void push_back(const T& x)      :向量尾部增加一个元素X
void emplace_back(const T& x)
iterator insert(iterator it,const T& x)   :向量中迭代器指向元素前增加一个元素x
result.insert(result.begin()+p,x);     :在result的index为p的位置插入元素
iterator insert(iterator it,int n,const T& x) :向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

删除函数

iterator erase(iterator it)     :删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back()        :删除向量中最后一个元素
void clear()        :清空向量中所有元素

遍历查找函数

reference at(int pos)  :返回pos位置元素的引用
reference front()   :返回首元素的引用
reference back()   :返回尾元素的引用
iterator begin()   :返回向量头指针指向第一个元素
iterator end()    :返回向量尾指针指向向量最后一个元素的下一个位置
reverse_iterator rbegin() :反向迭代器指向最后一个元素
reverse_iterator rend()  :反向迭代器指向第一个元素之前的位置

upper_bound(prefix_sum.begin(),prefix_sum.end(),a) : 查找满足prefix_sum[i]<=a的最大i

判断函数

bool empty() const   :判断向量是否为空若为空则向量中无元素

大小函数

int size() const  :返回向量中元素的个数
int capacity() const :返回当前向量所能容纳的最大元素值
int max_size() const :返回最大可允许的vector元素数量值

#include <algorithm> 
// C++ vector 容器裡使用 std::max_element 找最大值(或者min_element)的範例,std::max_element 會回傳一個迭代器,這個迭代器會指向該容器範圍內最大值的元素,
vector<int>::iterator result = std::max_element(v.begin(), v.end());
int index = result - v.begin();
int value = (*result)

片段的截取

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素:2,3,4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arrs2(First, Second); // 将值直接初始化到Arrs2

迭代器是指可在容器对象上遍访的对象

或者assign()功能函数实现截取

assign() 功能函数是vector容器的成员函数。原型:

1:void assign(const_iterator first,const_iterator last);//两个指针,分别指向开始和结束的地方 2:void assign(size_type n,const T& x = T()); //n指要构造的vector成员的个数, x指成员的数值,他的类型必须与vector类型一致!

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素:2,3,4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arr2;
Arr2.assign(First,Second); //使用assign() 成员函数将Arrs对应位置的值存入Arrs2数组中

迭代器的使用

#include <algorithm> 
double max = *max_element(vector.begin(), vector.end());
cout<<"Max value: "<<max<<endl;
vector<int>::iterator i;  //定义正向迭代器
for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
    cout << *i << " ";  //*i 就是迭代器i指向的元素
    *i *= 2;  //每个元素变为原来的2倍
}
cout << endl;
//用反向迭代器遍历容器
for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
    cout << *j << " ";

迭代器之间的减法是被允许的,两个迭代器相减返回是它们之间的距离,这个距离是一个符号类整型(signed),意味着两个迭代器之间相减可能是正数、零或者负数。

其他赋值函数

void swap(vector&)    :交换两个同类型向量的数据
void assign(int n,const T& x) :设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

#include <algorithm> //或者#include <bits/stdc++.h>
reverse(a.begin(), a.end());
std::reverse(a,a+5);  //转换0~5下标的元素

fill(ForwardIt first, ForwardIt last, const T& value) //fill函数的作用是:将一个区间的元素都赋予val值。函数参数:fill(first,last,val);//first为容器的首迭代器,last为容器的末迭代器,val为将要替换的值。
fill_n(OutputIt first, Size count, const T& value) //fill_n函数的作用是:给你一个起始点,然后再给你一个数值count和val。把从起始点开始依次赋予count个元素val的值。

vector具体实现

(1)扩容

vector的底层数据结构是数组。

当vector中的可用空间耗尽时,就要动态第扩大内部数组的容量。直接在原有物理空间的基础上追加空间?这不现实。数组特定的地址方式要求,物理空间必须地址连续,而我们无法保证其尾部总是预留了足够空间可供拓展。一种方法是,申请一个容量更大的数组,并将原数组中的成员都搬迁至新空间,再在其后方进行插入操作。新数组的地址由OS分配,与原数据区没有直接的关系。新数组的容量总是取作原数组的两倍。

(2)插入和删除

插入给定值的过程是,先找到要插入的位置,然后将这个位置(包括这个位置)的元素向后整体移动一位,然后将该位置的元素复制为给定值。删除过程则是将该位置以后的所有元素整体前移一位。

(2)vector的size和capacity

size指vector容器当前拥有的元素个数,capacity指容器在必须分配新存储空间之前可以存储的元素总数,capacity总是大于或等于size的。

size() – 返回目前存在的元素数。即: 元素个数
capacity() – 返回容器能存储 数据的个数。 即:容器容量
reserve() --设置 capacity 大小
resize() --设置 size ,重新指定有效元素的个数 ,区别与reserve()指定 容量的大小
clear() --清空所有元素,把size设置成0,capacity不变

针对capacity这个属性,STL中的其他容器,如list map set deque,由于这些容器的内存是散列分布的,因此不会发生类似realloc()的调用情况,因此我们可以认为capacity属性针对这些容器是没有意义的,因此设计时这些容器没有该属性。

在STL中,拥有capacity属性的容器只有vector和string。

为何map和set的插入删除效率比用其他序列容器高?

因为对于关联容器来说,不需要做内存拷贝和内存移动。说对了,确实如此。map和set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。

插入的时候只需要稍做变换,把节点的指针指向新的节点就可以了。删除的时候类似,稍做变换后把指向删除节点的指针指向其他节点就OK了。这里的一切操作就是指针换来换去,和内存移动没有关系。

std::map的优势: 内存池的管理

自己实现的map需要自己去new一些节点,当节点特别多, 而且进行频繁的删除和插入的时候,内存碎片就会存在,而STL采用自己的Allocator分配内存,以内存池的方式来管理这些内存,会大大减少内存碎片,从而会提升系统的整体性能。

为什么有时unordered_map, 性能比map差

注意到很多代码使用 std::unordered_map 因为“哈希表更快”。但是对于小map,具有很高的内存开销。

网上有许多map和unorderd_map的比较,但是都是大例子。

下载一个,比较N比较小时的速度。前面是插入,后面是读取时间。编译g++ -std=c++11 -O3 map.cpp -o main

$ ./main
insert N=15,cost=               9e-06 sec
[] N=15,cost=                   5e-06 sec
insert N=15,cost=               3e-06 sec
getall find not N=15,cost=      1.2e-05 sec
getall find N=15,cost=          1.4e-05 sec
getall find not N=15,cost=      1e-05 sec
getall cout N=15,cost=          1.3e-05 sec
getall cout not N=15,cost=      1.3e-05 sec

insert N=15,cost=               6e-06 sec
[] N=15,cost=                   2e-06 sec
insert N=15,cost=               3e-06 sec
getall find not N=15,cost=      1.9e-05 sec
getall find N=15,cost=          2e-05 sec
getall find not N=15,cost=      1.9e-05 sec
getall cout N=15,cost=          3.7e-05 sec
getall cout not N=15,cost=      2e-05 sec

insert N=15,cost=               3e-06 sec
[] N=15,cost=                   2e-06 sec
insert N=15,cost=               1e-06 sec
getall find not N=15,cost=      2e-05 sec
getall find N=15,cost=          1.8e-05 sec
getall find not N=15,cost=      1.9e-05 sec
getall cout N=15,cost=          1.8e-05 sec
getall cout not N=15,cost=      1.9e-05 sec

insert N=15,cost=               5e-06 sec
[] N=15,cost=                   1e-06 sec
insert N=15,cost=               2e-06 sec
getall find not N=15,cost=      7e-06 sec
getall find N=15,cost=          8e-06 sec
getall find not N=15,cost=      7e-06 sec
getall cout N=15,cost=          8e-06 sec
getall cout not N=15,cost=      1e-05 sec

可见创建 unorderd_map快于map。

map find没命中会很快,差不多unorderd_map。

但是map命中会慢很多。1.2e-05 >> 2e-06

array,vector与数组的区别

共同点

(1.)都和数组相似,都可以使用标准数组的表示方法来访问每个元素(array和vector都对下标运算符[ ]进行了重载)

(2.)三者的存储都是连续的,可以进行随机访问

不同点

(0.)数组是不安全的,array和vector是比较安全的(有效的避免越界等问题)

(1.)array对象和数组存储在相同的内存区域()中,vector对象存储在自由存储区()malloc和new的空间也是在堆上,原因是栈的空间在编译代码的时候就要确定好,堆空间可以运行时分配。

(2.)array可以将一个对象赋值给另一个array对象,但是数组不行

(3.)vector属于变长的容器,即可以根据数据的插入和删除重新构造容器容量;但是array和数组属于定长容器

(4.)vector和array提供了更好的数据访问机制,即可以使用front()和back()以及at()(at()可以避免a[-1]访问越界的问题)访问方式,使得访问更加安全。而数组只能通过下标访问,在写程序中很容易出现越界的错误

(5.)vector和array提供了更好的遍历机制,即有正向迭代器和反向迭代器

(6.)vector和array提供了size()和Empty(),而数组只能通过sizeof()/strlen()以及遍历计数来获取大小和是否为空

(7.)vector和array提供了两个容器对象的内容交换,即swap()的机制,而数组对于交换只能通过遍历的方式逐个交换元素

(8.)array提供了初始化所有成员的方法fill()

(9.)由于vector的动态内存变化的机制,在插入和删除时,需要考虑迭代的是否有效问题

(10.)vector和array在声明变量后,在声明周期完成后,会自动地释放其所占用的内存。对于数组如果用new[ ]/malloc申请的空间,必须用对应的delete[ ]和free来释放内存

vector 存储可变大小类型

  • vector是变长的连续存储,
  • 对于简单的类型,是直接存储
  • 对于复杂的类,存储的是,该元素的信息(比如新构造元素的begin地址,end地址,capacity信息)
vector<vector<int>> v2d(3,vector<int>(0));      // 间隔 6 个int
// vector<set<int>> v2d(3);                     // 间隔 12 个int 
// vector<unordered_set<int>> v2d(3);           // 间隔 14 个int 
// vector<map<int,int>> v2d(3);                 // 间隔 12 个int 
// vector<unordered_map<int,int>> v2d(3);       // 间隔 14 个int 

const int STEP = 6;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
    for(int j=0; j<STEP; j++)
        cout << " " << hex << *(int *)((void *)(&v2d[i])+j*4);
    cout << endl;
}

// add elements to v2d[0]
const int ADDNUM = 10;
for(int i = 0; i<ADDNUM; i++){
    v2d[0].emplace_back(2);
    // v2d[0].insert(i);
    // v2d[0][i]=i*i;
}

// check the space change
cout << "Ele[0] size : " << v2d[0].size() << endl;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
}

//check ele[0] location
cout << endl;
for(int i = 0; i<ADDNUM; i++){
    cout << " " << &v2d[0][i];
}

hash

哈希

#include<functional> 
auto hash_p = [](const pair<int, int> &p) -> size_t {
            static hash<long long> hash_ll;
            return hash_ll(p.first + (static_cast<long long>(p.second) << 32));//64位高低一半存储x和y
        };

static_cast 用于良性类型转换,一般不会导致意外发生,风险很低。

hash <K> 模板专用的算法取决于实现,但是如果它们遵循 C++14 标准的话,需要满足一些具体的要求。这些要求如下:

  • 不能拋出异常
  • 对于相等的键必须产生相等的哈希值
  • 对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

C++11技巧

https://shaojiemike.notion.site/C-11-a94be53ca5a94d34b8c6972339e7538a

map VS unordered_map 时间比较

/**
比较map、hash_map和unordered_map的执行效率以及内存占用情况
**/
#include "parallel-hashmap/parallel_hashmap/phmap.h"
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h> 
#include <iostream>
#include <fstream>
#include <string>
#include <map>
// #include <ext/hash_map>
#include <tr1/unordered_map>
#include <unordered_map>

#include <cstring>

using namespace std;

// using namespace __gnu_cxx;

using namespace std::tr1;

#define N 15  //分别测试N=100,000、N=1,000,000、N=10,000,000以及N=100,000,000
#define LOOP 50

//分别定义MapKey=map<int,int>、hash_map<int,int>、unordered_map<int,int>
typedef map<int,int> MapKey;          //采用map
//typedef hash_map<int,int> MapKey;     //采用hash_map
typedef std::unordered_map<int,int> MapKey1;  //采用unordered_map
typedef tr1::unordered_map<int,int> MapKey2;  //采用unordered_map
typedef phmap::flat_hash_map<int,int> MapKey3;  //采用unordered_map





int GetPidMem(pid_t pid,string& memsize)
{
 char filename[1024];

 snprintf(filename,sizeof(filename),"/proc/%d/status",pid);

 ifstream fin;

 fin.open(filename,ios::in);
 if (! fin.is_open())
 {
  cout<<"open "<<filename<<" error!"<<endl;
  return (-1);
 }

 char buf[1024];
 char size[100];
 char unit[100];

 while(fin.getline(buf,sizeof(buf)-1))
 {
  if (0 != strncmp(buf,"VmRSS:",6))
   continue;

  sscanf(buf+6,"%s%s",size,unit);

  memsize = string(size)+string(unit);
 }

 fin.close();

 return 0;
}


template<typename T>
void testMap(T MyMap){
 struct timeval begin;

 struct timeval end;
 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap.insert(make_pair(i,i));
 }

 gettimeofday(&end,NULL);

 cout<<"insert N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 MyMap.clear();

 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap[i]=i;
 }

 gettimeofday(&end,NULL);

 cout<<"[] N="<<N<<",cost=\t\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 MyMap.clear();

 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap.insert(make_pair(i,i));
 }

 gettimeofday(&end,NULL);

 cout<<"insert N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;


 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=0;i<N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=0;i<N;++i){
  MyMap.count(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall cout N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.count(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall cout not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 cout<<endl;

}

int main(int argc, char *argv[])
{

 MapKey map;
 MapKey1 map1;
 MapKey2 map2;

 MapKey3 map3;

 testMap<MapKey>(map);
 testMap<MapKey1>(map1);
 testMap<MapKey2>(map2);
 testMap<MapKey3>(map3);


 string memsize;

 GetPidMem(getpid(),memsize);

 cout<<memsize<<endl;

 return 0;
}

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

【C++容器】数组和vector、array三者区别和联系 https://blog.51cto.com/liangchaoxi/4056308

https://blog.csdn.net/y601500359/article/details/105297918

———————————————— 版权声明:本文为CSDN博主「stitching」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/qq_40250056/article/details/114681940

———————————————— 版权声明:本文为CSDN博主「FishBear_move_on」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/haluoluo211/article/details/80877558

———————————————— 版权声明:本文为CSDN博主「SOC罗三炮」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/luolaihua2018/article/details/109406092

———————————————— 版权声明:本文为CSDN博主「鱼思故渊」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/yusiguyuan/article/details/40950735

Java

java运行的特点

JVM(java虚拟机)

Just-In-Time (JIT) 编译器

  • JIT编译器是一种动态编译技术,它将程序的一部分或者全部源代码或更常见的字节码在运行时编译成机器码,然后将编译后的代码替换原来的代码。
  • 字节码(英语:Bytecode)通常指的是已经经过编译,但与特定机器代码无关,需要解释器转译后才能成为机器代码的中间代码(多为虚拟机代码)。典型应用为Java虚拟机里的Java bytecode。
  • 主要优点是可以在运行时根据程序的运行情况进行优化,从而提高程序的执行效率。
  • 字节码编译是跨平台的,便于移植的。
  • 主要缺点是编译字节码导致的延迟和空间开销较大,因此只有在程序运行时间较长的情况下才能体现出优势。
  • 是提前编译(AOT)和字节码解释器(python的实现)的结合体,它的执行效率介于两者之间。

区别

  1. Java Virtual Machine (JVM) is an abstract computing machine.
  2. Java Runtime Environment (JRE) is an implementation of the JVM.
  3. Java Development Kit (JDK) contains JRE along with various development tools like Java libraries, Java source compilers, Java debuggers, bundling and deployment tools.
  4. Java SE: Java™ Platform Standard Edition 21 Development Kit - JDK™ 21
  5. Just In Time compiler (JIT) is runs after the program has started executing, on the fly. It has access to runtime information and makes optimizations of the code for better performance.

Install

Intall for topcoder

chinese ref

  1. download from website
  2. But the first download choice java 21 SDK seems not contain Java Control Panel (javacpl.exe), you need to install Java SE Development Kit 8u381 which include JDK 1.8 and JRE 1.8
  3. config Java Control Panel, add https://www.topcoder.com to allowed website (Attention: https)
  4. open ContestAppletProd.jnlp
  5. need 127.0.0.1 proxy and HTTP TUNE 1 to connect to server

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

Python: DataStructure

check if it is empty?

strings, lists, tuples

# Correct:
if not seq:
if seq:

# Wrong:
if len(seq):
if not len(seq):

debug

try:
    # sth
except Exception as e:
    pprint.pprint(list)
    raise e
finally:
    un_set()

for

step

调参需要测试间隔值

for i in range(1, 101, 3):
    print(i)

遍历修改值

  • 使用 enumerate 函数结合 for 循环遍历 list,以修改 list 中的元素。
  • enumerate 函数返回一个包含元组的迭代器,其中每个元组包含当前遍历元素的索引和值。在 for 循环中,我们通过索引 i 修改了列表中的元素。
# 对于 二维list appDataDict
baseline = appDataDict[0][0] # CPU Total
for i, line in enumerate(appDataDict):
    for j, entry in enumerate(line):
        appDataDict[i][j] = round(entry/baseline, 7)

itertools

itertools --- 为高效循环而创建迭代器的函数

for a,b,c in permutations((a,b,c)):

String 字符串

%c  格式化字符及其ASCII码
%s  格式化字符串
%d  格式化整数
%u  格式化无符号整型
%o  格式化无符号八进制数
%x  格式化无符号十六进制数
%X  格式化无符号十六进制数(大写)
%f  格式化浮点数字,可指定小数点后的精度
%e  用科学计数法格式化浮点数
%E  作用同%e,用科学计数法格式化浮点数
%g  %f和%e的简写
%G  %F  %E 的简写
%p  用十六进制数格式化变量的地址
print("My name is %s and weight is %d kg!" % ('Zara', 21))

string <-> list

' '.join(pass_list) and pass_list.split(" ")

对齐"\n".join(["%-10s" % item for item in List_A])

字符串开头判断

text = "Hello, world!"

if text.startswith("Hello"):
    print("The string starts with 'Hello'")
else:
    print("The string does not start with 'Hello'")

format 格式化函数

Python2.6 开始,通过 {}: 来代替以前的 %

>>>"{} {}".format("hello", "world")    # 不设置指定位置,按默认顺序
'hello world'

>>> "{1} {0} {1}".format("hello", "world")  # 设置指定位置
'world hello world'

# 字符串补齐100位,<表示左对齐
variable = "Hello"
padded_variable = "{:<100}".format(variable)

数字处理

print("{:.2f}".format(3.1415926)) # 保留小数点后两位

{:>10d} 右对齐 (默认, 宽度为10)
{:^10d} 中间对齐 (宽度为10)

小数位

x = round(x,3)# 保留小数点后三位

容器:List

https://www.runoob.com/python/python-lists.html

初始化以及访问

list = ['physics', 'chemistry', 1997, 2000]
list = []          ## 空列表
print(list[0])

切片

格式:[start_index:end_index:step]

不包括end_index的元素

二维数组

list_three = [[0 for i in range(3)] for j in range(3)]

//numpy 创建连续的可自动向量化线程并行
import numpy as np
# 创建一个 3x4 的数组且所有值全为 0
x3 = np.zeros((3, 4), dtype=int)
# 创建一个 3x4 的数组,然后将所有元素的值填充为 2
x5 = np.full((3, 4), 2, dtype=int)

size 大小

len(day)

排序

# take second element for sort
def takeSecond(elem):
    return elem[2]

LCData.sort(key=takeSecond)

# [1740, '黄业琦', 392, '第 196 场周赛'],
# [1565, '林坤贤', 458, '第 229 场周赛'],
# [1740, '黄业琦', 458, '第 229 场周赛'],
# [1509, '林坤贤', 460, '第 230 场周赛'],
# [1740, '黄业琦', 460, '第 230 场周赛'],
# [1779, '黄业琦', 558, '第 279 场周赛'],

对应元素相加到一个变量

tmp_list = [[],[],[],[]]
# 注意不需要右值赋值
[x.append(copy.deepcopy(entry)) for x,entry in zip(tmp_list, to_add)]

两个list对应元素相加

对于等长的

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = [x + y for x, y in zip(list1, list2)]
print(result)

如果两个列表的长度不同,你可以使用zip_longest()函数来处理它们。zip_longest()函数可以处理不等长的列表,并使用指定的填充值填充缺失的元素。

from itertools import zip_longest

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8]

result = [x + y for x, y in zip_longest(list1, list2, fillvalue=0)]
print(result)

如果是二维list

list1 = [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]]

list2 = [[10, 11, 12],
         [13, 14, 15]]

rows = max(len(list1), len(list2))
cols = max(len(row) for row in list1 + list2)

result = [[0] * cols for _ in range(rows)]

for i in range(rows):
    for j in range(cols):
        if i < len(list1) and j < len(list1[i]):
            result[i][j] += list1[i][j]
        if i < len(list2) and j < len(list2[i]):
            result[i][j] += list2[i][j]

print(result)

# 将一个二维列表的所有元素除以一个数A
result = [[element / A for element in row] for row in list1]

直接赋值、浅拷贝和深度拷贝

Python append() 与深拷贝、浅拷贝

python赋值只是引用,别名

list.append('Google')   ## 使用 append() 添加元素
alist.append( num ) # 浅拷贝 ,之后修改num 会影响alist内的值

import copy
alist.append( copy.deepcopy( num ) ) # 深拷贝

# delete
del list[2]

for循环迭代的元素 也是 引用

original_list = [1, 2, 3]

for item in original_list:
    item *= 2 # 每个元素是不可变的

print(original_list) 

original_list = [[1,2,3], [2], [3]]

for item in original_list:
    item.append("xxx") # 每个元素是可变的

print(original_list) 

# [1, 2, 3]
# [[1, 2, 3, 'xxx'], [2, 'xxx'], [3, 'xxx']]

函数传参是引用,但是能通过切片来得到类似指针

参数的传递 函数声明时的形参,使用时,等同于函数体内的局部变量。由于Python中一切皆为对象。因此,参数传递时直接传递对象的地址,但具体使用分两种类型: 1.传递不可变对象的引用(起到其他语言值传递的效果) 数字,字符串,元组,function等 2.传递可变对象的引用(起到其他语言引用传递的效果) 字典,列表,集合,自定义的对象等

def fun0(a):
    a = [0,0] # a在修改后,指向的地址发生改变,相当于新建了一个值为[0,0]

def fun(a):
    a[0] = [1,2]

def fun2(a):
    a[:] = [10,20]

b = [3,4]
fun0(b)
print(b)
fun(b)
print(b)
fun2(b)
print(b)

# [3, 4]
# [[1, 2], 4]
# [10, 20]

return 返回值

可变的也是引用

def fun1(l):
    l.append("0")
    return l 

def fun2(l):
    return l

if __name__=="__main__":
    l = [1,2,3,4,5]

    rel2 = fun2(l)
    print(rel2)   
    rel1 = fun1(l)
    print(rel1)   
    print(rel2)   
    l.append("xxx")
    print(rel1)   
    print(rel2)   
    del rel1[2]
    print(rel1)   
    print(rel2)  

# [1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5, '0']
# [1, 2, 3, 4, 5, '0']
# [1, 2, 3, 4, 5, '0', 'xxx']
# [1, 2, 3, 4, 5, '0', 'xxx']
# [1, 2, 4, 5, '0', 'xxx']
# [1, 2, 4, 5, '0', 'xxx']

容器:元组Tuple

  • 元组和列表类似,但是不同的是元组不能修改,但可以对元组进行连接组合,元组使用小括号。
  • 元组中只包含一个元素时,需要在元素后面添加逗号,否则括号会被当作运算符使用。
#创建元组
tup = (1, 2, 3, 4, 5)
tup1 = (23, 78);
tup2 = ('ab', 'cd')
tup3 = tup1 + tup2

容器:Dict

empty dict

a= {}
a=dict()

key 支持tuple元组

类似c++ 的 pair<int,int>

bblHashDict[(tmpHigherHash,tmpLowerHash)]=tmpBBL

但是这样就不支持json.dump, json.dump() 无法序列化 Python 中元组(tuple)作为字典的 key,这会导致 json.dump() 函数在写入此类字典数据时会进入死循环或陷入卡住状态

初始化以及访问

>>> tinydict = {'a': 1, 'b': 2, 'b': '3'}
>>> tinydict['b']
'3'
a_dict = {'color': 'blue'}
for key in a_dict:
 print(key)
# color
for key in a_dict:
    print(key, '->', a_dict[key])
# color -> blue
for item in a_dict.items():
    print(item)
# ('color', 'blue')
for key, value in a_dict.items():
 print(key, '->', value)
# color -> blue

判断key 是否存在

以下是两种常用的方法:

方法一:使用in操作符: in操作符返回一个布尔值,True表示存在,False表示不存在。

Copy code
my_dict = {"key1": "value1", "key2": "value2", "key3": "value3"}

# 判断是否存在指定的键
if "key2" in my_dict:
    print("Key 'key2' exists in the dictionary.")
else:
    print("Key 'key2' does not exist in the dictionary.")

方法二:使用dict.get()方法: dict.get()方法在键存在时返回对应的值,不存在时返回None。根据需要选择适合的方法进行判断。

Copy code
my_dict = {"key1": "value1", "key2": "value2", "key3": "value3"}

# 判断是否存在指定的键
if my_dict.get("key2") is not None:
    print("Key 'key2' exists in the dictionary.")
else:
    print("Key 'key2' does not exist in the dictionary.")

这两种方法都可以用来判断字典中是否存在指定的键。

size 大小

len(day)

修改以及添加

tinydict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

tinydict['Age'] = 8 # 更新
tinydict['School'] = "RUNOOB" # 添加

合并

dict1 = {'a': 10, 'b': 8} 
dict2 = {'d': 6, 'c': 4} 

# dict2保留了合并的结果
dict2.update(dict1)
print(dict2)
{'d': 6, 'c': 4, 'a': 10, 'b': 8}

删除

del tinydict['Name']  # 删除键是'Name'的条目
tinydict.clear()      # 清空字典所有条目
del tinydict          # 删除字典
from pprint import pprint
pprint

容器:set

无序不重复序列

初始化

a=  set() # 空set

thisset = set(("Google", "Runoob", "Taobao"))
>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # 这里演示的是去重功能

list2set

setL=set(listV)

set2list

my_set = {'Geeks', 'for', 'geeks'}

s = list(my_set)
print(s)
# ['Geeks', 'for', 'geeks']

添加

thisset.add("Facebook")

合并

x = {"apple", "banana", "cherry"}
y = {"google", "runoob", "apple"}

z = x.union(y) 

print(z)
# {'cherry', 'runoob', 'google', 'banana', 'apple'}

删除与清空

s.remove( x )
a.clear()

修改原本的值

修改传入参数

在Python中,函数的参数是按值传递的,也就是说在函数内部修改参数不会影响到函数外部的变量。

但是有几种方法可以实现类似修改参数的效果:

  1. 返回修改后的值,在函数外部重新赋值
def func(x):
    x = x + 1 
    return x

a = 10
a = func(a) 
print(a) # 11
  1. 使用可变对象作为参数,修改可变对象的内部值
def func(lst):
    lst.append(1)

lst = [1,2,3]
func(lst)
print(lst) # [1,2,3,1]

这里lst是列表,在func内部修改了lst,由于lst是可变的,所以函数外部的lst也被修改了。

  1. 使用全局变量
count = 0
def func():
    global count
    count += 1

func()
print(count) # 1

通过global关键字声明count为全局变量,这样就可以在函数内部修改全局变量count了。

所以要修改传入参数的值,主要的方法是:

  1. 返回修改后的值并重新赋值
  2. 传入一个可变对象并修改可变对象内部的值
  3. 使用全局变量

这些技巧可以实现模拟修改参数的效果。

修改for循环对象

在Python中,for循环遍历的是一个迭代器,每次循环会将迭代器的下一个元素赋值给循环变量。

如果想在for循环内部修改迭代器中的元素,可以使用以下方法:

  1. 将迭代器转换成列表,然后修改列表中的元素:
all_for_one = ['a', 'b', 'c']

for app_info in list(all_for_one):
    if app_info == 'b':
        all_for_one[1] = 'x' 

print(all_for_one) # ['a', 'x', 'c']

这里通过list()将迭代器转成列表,然后修改列表的元素。

  1. 使用循环的索引而不是直接使用元素:
all_for_one = ['a', 'b', 'c']

for i in range(len(all_for_one)):
    if i == 1:
        all_for_one[i] = 'x'

print(all_for_one) # ['a', 'x', 'c']

通过索引 i 来访问并修改元素。

  1. 使用enumerate()在循环中获取索引:
all_for_one = ['a', 'b', 'c']

for i, app_info in enumerate(all_for_one):
    if i == 1:
        all_for_one[i] = 'x'

print(all_for_one) # ['a', 'x', 'c']

enumerate()可以同时迭代索引和元素。

所以主要思路就是不直接修改循环变量,而是通过索引或临时列表来修改迭代器中的原始元素。

修改for循环的对象 set

对于 set 这样的不可变对象,不能直接通过索引或者 enumerate 来修改,因为 set 对象不支持索引和切片操作。

对于 set,可以使用以下方法在循环内部进行修改:

  1. 将 set 转换成 list,修改后再转换回 set
s = {'a', 'b', 'c'}

for item in list(s):
    if item == 'b':
        s = list(s)
        s[1] = 'x'
        s = set(s)

print(s) # {'a', 'x', 'c'}
  1. 创建一个新的 set,在循环中添加修改后的元素
s = {'a', 'b', 'c'}
new_s = set()

for item in s:
    if item == 'b':
        new_s.add('x')
    else:
        new_s.add(item)

s = new_s

print(s) # {'a', 'x', 'c'}
  1. 使用 set 的discard()和add()方法在循环中修改
s = {'a', 'b', 'c'}

for item in s:
    if item == 'b':
        s.discard(item)
        s.add('x')

print(s) # {'a', 'x', 'c'}

上面这些方法的关键思路都是:

  1. 将不可变对象设置转换成可变类型
  2. 在循环中针对可变类型进行修改
  3. 再转换回不可变 Set 对象

这样就可以实现循环中修改 Set 的效果。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://blog.csdn.net/weixin_63719049/article/details/125680242

PythonRegex

pattern

^   匹配字符串的开头
$   匹配字符串的末尾。
.   匹配任意字符,除了换行符
a| b    匹配a或b
[a-zA-Z0-9] 匹配任何字母及数字
[aeiou] 匹配中括号内的任意一个字母
[^aeiou]    除了aeiou字母以外的所有字符
\w  匹配包括下划线的任何单词字符。等价于'[A-Za-z0-9_]'(\s*) 或者 ([\t ]*)     来匹配任意TAB和空格的混合字符

\s  匹配任何空白字符,包括空格、制表符、换页符等等。等价于 [ \f\n\r\t\v]\S  匹配任何非空白字符。等价于 [^ \f\n\r\t\v]\b  匹配一个单词边界,也就是指单词和空格间的位置。例如, 'er\b' 可以匹配"never" 中的 'er',但不能匹配 "verb" 中的 'er'\B  匹配非单词边界。'er\B' 能匹配 "verb" 中的 'er',但不能匹配 "never" 中的 'er'

重复

re* 匹配0个或多个的表达式。
re+ 匹配1个或多个的表达式。
re? 匹配0个或1个由前面的正则表达式定义的片段,非贪婪方式
re{ n}  精确匹配 n 个前面表达式。
        例如, o{2} 不能匹配 "Bob" 中的 "o",
        但是能匹配 "food" 中的两个 o。
re{ n,} 匹配 n 个前面表达式。
        例如, o{2,} 不能匹配"Bob"中的"o",
        但能匹配 "foooood"中的所有 o。
        "o{1,}" 等价于 "o+"。
        "o{0,}" 则等价于 "o*"。
re{ n, m}   匹配 n 到 m 次由前面的正则表达式定义的片段,贪婪方式

match exactlly str

# find should use \ to represent the (6|12|3)
$ find ~/github/gapbs/ -type f -regex '.*/kron-\(6\|12\|3\).*'
/staff/shaojiemike/github/gapbs/kron-12.wsg
/staff/shaojiemike/github/gapbs/kron-3.sg
/staff/shaojiemike/github/gapbs/kron-3.wsg
/staff/shaojiemike/github/gapbs/kron-6.sg
/staff/shaojiemike/github/gapbs/kron-6.wsg

re.match与re.search的区别

re.match只匹配字符串的开始,如果字符串开始不符合正则表达式,则匹配失败,函数返回None;

而re.search匹配整个字符串,直到找到一个匹配。

re.match函数

从字符串的起始位置匹配

re.match(pattern, string, flags=0)

flags

多个标志可以通过按位 OR(|) 它们来指定。如 re.I | re.M被设置成 I 和 M 标志:

re.I    使匹配对大小写不敏感
re.M    多行匹配,影响 ^ 和 $
re.S    使 . 匹配包括换行在内的所有字符

group

matchObj = re.match( r'(.*) are (.*?) .*', line, re.M|re.I)

if matchObj:
   print "matchObj.group() : ", matchObj.group()
   print "matchObj.group(1) : ", matchObj.group(1)
   print "matchObj.group(2) : ", matchObj.group(2)
else:
   print "No match!!"

打印部分内容

matchObj.group() :  Cats are smarter than dogs
matchObj.group(1) :  Cats
matchObj.group(2) :  smarter

re.sub 替换

findall

返回元组,可以指定开始,与结束位置。

result = re.findall(r'(\w+)=(\d+)', 'set width=20 and height=10')
print(result)
# [('width', '20'), ('height', '10')]

实例:objdump结果只提取汇编的命令

import re      
# 打开x86汇编代码文件
with open(assembly) as f:
        # 读取文件内容
        content = f.read()

# 使用正则表达式匹配所有汇编指令,
pattern = r'\b([a-zA-Z]{3,6})\b.*'
# 匹配pattern,但是只将()内结果保存在matches中
matches = re.findall(pattern, content)

# 输出匹配结果
for match in matches:
        print(match)

re.split

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://blog.csdn.net/weixin_39594191/article/details/111611346

https://www.runoob.com/python/python-reg-expressions.html

Python Class

简介

Python从设计之初就已经是一门面向对象的语言,正因为如此,在Python中创建一个类和对象是很容易的。

面向对象技术简介

  • 类(Class): 用来描述具有相同的属性和方法的对象的集合。它定义了该集合中每个对象所共有的属性和方法。对象是类的实例。

  • 实例化:创建一个类的实例,类的具体对象。

  • 方法:类中定义的函数。
  • 方法重写:如果从父类继承的方法不能满足子类的需求,可以对其进行改写,这个过程叫方法的覆盖(override),也称为方法的重写。
  • 继承:即一个派生类(derived class)继承基类(base class)的字段和方法。继承也允许把一个派生类的对象作为一个基类对象对待。例如,有这样一个设计:一个Dog类型的对象派生自Animal类,这是模拟"是一个(is-a)"关系(例图,Dog是一个Animal)。
  • 对象:通过类定义的数据结构实例。对象包括两个数据成员(类变量和实例变量)和方法。
  • 类变量:类变量在整个实例化的对象中是公用的。类变量定义在类中且在函数体之外。类变量通常不作为实例变量使用。
  • 实例变量:在类的声明中,属性是用变量来表示的。这种变量就称为实例变量,是在类声明的内部但是在类的其他成员方法之外声明的。

何时使用类

  1. 数据与操作紧密相关
  2. 对象有许多状态需要维护,可以使用类中的属性来保存状态。
  3. 需要生成多个仅在部分属性不同的实例,可以使用类作为模板。
  4. 不同对象存在公共parent-child的层次关系,可以使用继承来复用代码。
  5. 隐藏对象的实现细节,只对外公开接口。

类变量 与 实例变量

在Python中,类变量和实例变量是两个不同的概念:

  1. 类变量(Class Variable)

  2. 定义在类内部,但不在任何方法之内

  3. 被该类的所有实例对象所共享
  4. 可以通过类名或实例对象访问
  5. 用于定义与这个类相关的特征或属性

  6. 实例变量(Instance Variable)

  7. 定义在类内部的方法之内

  8. 每个实例对象拥有属于自己的变量副本
  9. 只能通过实例对象访问
  10. 用于定义实例对象的个性化特征或状态

例如:

class Person:

    species = 'Human' # 类变量

    def __init__(self, name):
        self.name = name # 实例变量

p1 = Person('John')
p2 = Person('Mary')

print(p1.species) # Human
print(p2.species) # Human 

print(p1.name) # John 
print(p2.name) # Mary

综上,类变量用于定义类的通用属性,实例变量用于定义实例的独特属性。区分二者是理解Python面向对象的关键。

创建

class Employee:
   '所有员工的基类'
   empCount = 0 # 类变量

   def __init__(self, name, salary):
      self.name = name
      self.salary = salary
      Employee.empCount += 1

   def displayCount(self):
     print "Total Employee %d" % Employee.empCount

   def displayEmployee(self):
      print "Name : ", self.name,  ", Salary: ", self.salary

类函数必有参数 ‘self’

必须有一个额外的第一个参数名称, 按照惯例它的名称是 self,self 不是 python 关键字,换成其他词语也行。

创建实例对象与访问

emp1 = Employee("Zara", 2000)
emp1.displayEmployee()

继承

通过继承创建的新类称为子类或派生类,被继承的类称为基类、父类或超类。

继承语法 class 派生类名(基类名)

调用基类

调用基类的方法时,需要加上基类的类名前缀,且需要带上 self 参数变量。区别在于类中调用普通函数时并不需要带上 self 参数 ,这点在代码上的区别如下:

class Base:
    def base_method(self):
        print("Base method")

class Derived(Base):
    def derived_method(self):
        # 调用基类方法要加类名前缀
        Base.base_method(self)

        # 调用普通函数
        print("Hello")  

d = Derived()
d.derived_method()

# 输出
Base method  
Hello

在Derived类中:

  • 调用Base基类的方法base_method(),需要写成Base.base_method(self)

  • 调用普通函数print(),直接写函数名即可

区别在于:

  • 调用基类方法需要指明方法所属的基类
  • 基类方法需要传入self,指代实例自己

而对于普通函数,只需要直接调用即可,不需要self参数。

这与Python的名称空间和面向对象实现有关,是理解Python类继承的关键点。

运算符重载

__init__ : 构造函数在生成对象时调用
__del__ : 析构函数释放对象时使用
__repr__ : 打印转换
__setitem__ : 按照索引赋值
__getitem__: 按照索引获取值
__len__: 获得长度
__cmp__: 比较运算
__call__: 函数调用
__add__: 加运算
__sub__: 减运算
__mul__: 乘运算
__truediv__: 除运算
__mod__: 求余运算
__pow__: 乘方

+=

在Python中可以通过特殊方法__iadd__来对+=符号进行重载。

__iadd__需要定义在类中,用于指定+=操作时的具体行为。例如:

class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self

v1 = Vector(1, 2)
v2 = Vector(3, 4)

v1 += v2
print(v1.x, v1.y) # 4, 6

这里我们定义了__iadd__方法,用于实现两个Vector对象使用+=时的相加操作。

__iadd__方法的参数是另一个要相加的对象,在方法内部我们实现了两个向量的分量相加,并返回self作为结果。这样就实现了+=的运算符重载。

此外,Python还提供了__add__特殊方法用于重载+符号,但是__iadd__和__add__有以下区别:

  • __add__返回一个新的对象,不改变原有对象。
  • __iadd__在原有对象的基础上进行操作,并返回对原对象的引用。

所以对可变对象进行+=操作时,通常需要实现__iadd__方法。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5,没有进行正确性的交叉校验。

https://www.runoob.com/python/python-object.html

Language

面向过程 VS 面向对象

面向过程

面向过程是一种以事件为中心的编程思想,编程的时候把解决问题的步骤分析出来,然后用函数把这些步骤实现,在一步一步的具体步骤中再按顺序调用函数。

面向对象

在日常生活或编程中,简单的问题可以用面向过程的思路来解决,直接有效,但是当问题的规模变得更大时,用面向过程的思想是远远不够的。所以慢慢就出现了面向对象的编程思想。世界上有很多人和事物,每一个都可以看做一个对象,而每个对象都有自己的属性和行为,对象与对象之间通过方法来交互。面向对象是一种以“对象”为中心的编程思想,把要解决的问题分解成各个对象,建立对象的目的不是为了完成一个步骤,而是为了描叙某个对象在整个解决问题的步骤中的属性和行为。

优缺点

面向过程

优点:

  1. 流程化使得编程任务明确,在开发之前基本考虑了实现方式和最终结果,具体步骤清楚,便于节点分析。
  2. 效率高,面向过程强调代码的短小精悍,善于结合数据结构来开发高效率的程序。

缺点:

  1. 需要深入的思考,耗费精力,代码重用性低,扩展能力差,后期维护难度比较大。
面向对象

优点:

  1. 结构清晰,程序是模块化和结构化,更加符合人类的思维方式;
  2. 易扩展,代码重用率高,可继承,可覆盖,可以设计出低耦合的系统;
  3. 易维护,系统低耦合的特点有利于减少程序的后期维护工作量。

缺点:

  1. 开销大,当要修改对象内部时,对象的属性不允许外部直接存取,所以要增加许多没有其他意义、只负责读或写的行为。这会为编程工作增加负担,增加运行开销,并且使程序显得臃肿。
  2. 性能低,由于面向更高的逻辑抽象层,使得面向对象在实现的时候,不得不做出性能上面的牺牲,计算时间和空间存储大小都开销很大。

静态语言 vs 动态语言

  1. Dynamic Programming Language (动态语言或动态编程语言)
  2. 动态语言,准确地说,是指程序在运行时可以改变其结构:新的函数可以被引进,已有的函数可以被删除等在结构上的变化。
  3. 比如众所周知的ECMAScript(JavaScript)便是一个动态语言。
  4. 除此之外如Ruby、Python等也都属于动态语言,而C、C++等语言则不属于动态语言。
  5. Dynamically Typed Language (动态类型语言)
  6. 动态类型语言:是指在运行期间才去做数据类型检查的语言。
  7. 在用动态语言编程时,不用给变量指定数据类型,该语言会在你第一次赋值给变量时,在内部将数据类型记录下来。
  8. Statically Typed Language (静态类型语言)
  9. 静态类型语言:与动态类型语言刚好相反,它的数据类型检查发生在在编译阶段,也就是说在写程序时要声明变量的数据类型。
  10. C/C++、C#、JAVA都是静态类型语言的典型代表。

两者的优缺点

静态类型语言的

  1. 主要优点在于其结构非常规范,便于调试,方便类型安全;
  2. 缺点是为此需要写更多的类型相关代码,导致不便于阅读、不清晰明了。

动态类型语言的

  1. 优点在于方便阅读,不需要写非常多的类型相关的代码;
  2. 缺点自然就是不方便调试,命名不规范时会造成读不懂,不利于理解等。

runtime

runtime 描述了程序运行时候执行的软件/指令, 在每种语言有着不同的实现。

可大可小,在 C 中,runtime 是库代码, 等同于 C runtime library,一系列 C 程序运行所需的函数。

在 Java 中,runtime 还提供了 Java 程序运行所需的虚拟机等。

总而言之,runtime 是一个通用抽象的术语,指的是计算机程序运行的时候所需要的一切代码库,框架,平台等

Go中的 runtime

在 Go 中, 有一个 runtime 库,其实现了垃圾回收,并发控制, 栈管理以及其他一些 Go 语言的关键特性。 runtime 库是每个 Go 程序的一部分,也就是说编译 Go 代码为机器代码时也会将其也编译进来。所以 Go 官方将其定位偏向类似于 C 语言中的库。

Go 中的 runtime 不像 Java runtime (JRE, java runtime envirement ) 一样,jre 还会提供虚拟机, Java 程序要在 JRE 下 才能运行。

垃圾回收机制(garbage collection,GC)的设计

C/C++语言为什么没有对指针对象的垃圾回收机制

作为支持指针的编程语言,C++将动态管理存储器资源的便利性交给了程序员。在使用指针形式的对象时(请注意,由于引用在初始化后不能更改引用目标 的语言机制的限制,多态性应用大多数情况下依赖于指针进行),程序员必须自己完成存储器的分配、使用和释放,语言本身在此过程中不能提供任何帮助。

某些语言提供了垃圾回收机制,也就是说程序员仅负责分配存储器和使用,而由语言本身负责释放不再使用的存储器,这样程序员就从讨厌的存储器管理的工作中脱身了。

C++的设计者Bjarne Stroustrup对此做出过解释:

“我有意这样设计C++,使它不依赖于自动垃圾回收(通常就直接说垃圾回收)。这是基于自己对垃圾回收系统的经验,我很害怕那种严重的空间和时间开销,也害怕由于实现和移植垃圾回收系统而带来的复杂性。还有,垃圾回收将使C++不适合做许多底层的工作,而这却正是它的一个设计目标。但我喜欢垃圾回收 的思想,它是一种机制,能够简化设计、排除掉许多产生错误的根源。 需要垃圾回收的基本理由是很容易理解的:用户的使用方便以及比用户提供的存储管理模式更可靠。而反对垃圾回收的理由也有很多,但都不是最根本的,而是关于实现和效率方面的。 已经有充分多的论据可以反驳:每个应用在有了垃圾回收之后会做的更好些。类似的,也有充分的论据可以反对:没有应用可能因为有了垃圾回收而做得更好。 并不是每个程序都需要永远无休止的运行下去;并不是所有的代码都是基础性的库代码;对于许多应用而言,出现一点存储流失是可以接受的;许多应用可以管理自己的存储,而不需要垃圾回收或者其他与之相关的技术,如引用计数等。 我的结论是,从原则上和可行性上说,垃圾回收都是需要的。但是对今天的用户以及普遍的使用和硬件而言,我们还无法承受将C++的语义和它的基本库定义在垃圾回收系统之上的负担。”

强类型语言和弱类型语言

1.强类型语言:使之强制数据类型定义的语言。没有强制类型转化前,不允许两种不同类型的变量相互操作。强类型定义语言是类型安全的语言,如Rust, Java、C# 和 Python,比如Java中“int i = 0.0;”是无法通过编译的;

2.弱类型语言:数据类型可以被忽略的语言。与强类型语言相反, 一个变量可以赋不同数据类型的值,允许将一块内存看做多种类型,比如直接将整型变量与字符变量相加。C/C++、PHP都是弱类型语言,比如C++中“int i = 0.0;”是可以编译运行的;

注意,强类型语言在速度上略逊色于弱类型语言,使用弱类型语言可节省很多代码量,有更高的开发效率。而对于构建大型项目,使用强类型语言可能会比使用弱类型更加规范可靠。

ispc

a data-parallel languagedesigned specifically to target Intel’s vector extensions

Intel® Implicit SPMD Program Compiler

An open-source compiler for high-performance SIMD programming on the CPU and GPU

ispc is a compiler for a variant of the C programming language, with extensions for "single program, multiple data" (SPMD) programming.

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://blog.csdn.net/yuanmengong886/article/details/52572533

https://segmentfault.com/a/1190000022715733

Pytorch

(本人是rookie,纯小白~

什么是 PyTorch?

PyTorch 是一个基于 Python 的科学计算包,主要定位两类人群:

  1. NumPy 的替代品,可以利用 GPU 的性能进行计算。
  2. 深度学习研究平台拥有足够的灵活性和速度

Pytorch简介

要介绍PyTorch之前,不得不说一下Torch。

Torch是一个有大量机器学习算法支持的科学计算框架,是一个与Numpy类似的张量(Tensor) 操作库,其特点是特别灵活,但因其采用了小众的编程语言是Lua,所以流行度不高,这也就有了PyTorch的出现。所以其实Torch是 PyTorch的前身,它们的底层语言相同,只是使用了不同的上层包装语言。

PyTorch是一个基于Torch的Python开源机器学习库,用于自然语言处理等应用程序。它主要由Facebookd的人工智能小组开发,不仅能够 实现强大的GPU加速,同时还支持动态神经网络,这一点是现在很多主流框架如TensorFlow都不支持的。 PyTorch提供了两个高级功能:

  • 具有强大的GPU加速的张量计算(如Numpy)
  • 包含自动求导系统的深度神经网络

TensorFlow和Caffe都是命令式的编程语言,而且是静态的,首先必须构建一个神经网络,然后一次又一次使用相同的结构,如果想要改变网络的结构,就必须从头开始。

但是对于PyTorch,通过反向求导技术,可以让你零延迟地任意改变神经网络的行为,而且其实现速度 快。正是这一灵活性是PyTorch对比TensorFlow的最大优势。

所以,总结一下PyTorch的优点:

  • 支持GPU
  • 灵活,支持动态神经网络
  • 底层代码易于理解
  • 命令式体验
  • 自定义扩展

当然,现今任何一个深度学习框架都有其缺点,PyTorch也不例外,对比TensorFlow,其全面性处于劣势,目前PyTorch

  • 还不支持快速傅里 叶、沿维翻转张量和检查无穷与非数值张量;
  • 针对移动端、嵌入式部署以及高性能服务器端的部署其性能表现有待提升;
  • 其次因为这个框 架较新,使得他的社区没有那么强大,在文档方面其C库大多数没有文档。

安装和使用

安装

https://pytorch.org/ 选择对应cuda版本下载即可

使用

from __future__ import print_function
import torch

数据类型和操作

Tensor(张量)

# 构造一个5x3矩阵,不初始化。基本是0,或者+-10^-4之类
x = torch.empty(5, 3)
# 构造一个随机初始化的矩阵:范围[0,1)
x = torch.rand(5, 3)
# 构造一个随机int初始化的矩阵:范围[3,10),大小2*2
torch.randint(3, 10, (2, 2))
tensor([[4, 5],
        [6, 7]])
# 构造一个矩阵全为 0,而且数据类型是 long.
x = torch.zeros(5, 3, dtype=torch.long)
# 直接使用数据 1*2维 
x = torch.tensor([5.5, 3])
# 裁取已有tensor 5*3的元素
x = x.new_ones(5, 3, dtype=torch.double)   
# 已有tensor元素全部随机化
x = torch.randn_like(x, dtype=torch.float) 
# 连接矩阵,不同维度 Concatenates 
>>> x = torch.randn(2, 3)
>>> x
tensor([[ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497]])
>>> torch.cat((x, x, x), 0)
# torch.cat([input]*100)
tensor([[ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497],
        [ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497],
        [ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497]])
# 相同大小对应位置相乘
x = torch.tensor([[5, 6], [1 / 5, 2]])
print(x)
print(torch.prod(x, 0))  # product along 0th axis
tensor([[5.0000, 6.0000],
        [0.2000, 2.0000]])
tensor([ 1., 12.])
# 转置 指定维度transpose() 和 permute()
x.t()   
# 横向纵向复制拓展
>>> x = torch.tensor([[1], [2], [3]])
>>> x.size()
torch.Size([3, 1])
>>> x.expand(3, 4)
tensor([[ 1,  1,  1,  1],
        [ 2,  2,  2,  2],
        [ 3,  3,  3,  3]])
>>> x.expand(-1, 4)   # -1 means not changing the size of that dimension
tensor([[ 1,  1,  1,  1],
        [ 2,  2,  2,  2],
        [ 3,  3,  3,  3]])
# 输出第二列的数据
print(x[:, 1])
# 维度信息 输出是一个元组,所以它支持左右的元组操作。
print(x.size())
# 改变一个 tensor 的大小或者形状
# reshape也行 https://blog.csdn.net/Flag_ing/article/details/109129752
x = torch.randn(4, 4)
y = x.view(16)
z = x.view(-1, 8)  # -1位置的取值是从其他维度推断出来的
print(x.size(), y.size(), z.size()) # torch.Size([4, 4]) torch.Size([16]) torch.Size([2, 8])
# 加法
z=x+y
z=torch.add(x, y)
y.add_(x)  # adds x to y

注意 任何使张量会发生变化的操作都有一个前缀 '_'。例如: x.copy_(y), x.t_(), 将会改变 x

PyTorch 自动微分

autograd 包是 PyTorch 中所有神经网络的核心。

autograd 软件包为 Tensors 上的所有操作提供自动微分。它是一个由运行定义的框架,这意味着以代码运行方式定义你的后向传播,并且每次迭代都可以不同。

TENSOR

torch.Tensor 是包的核心类。

如果将其属性 .requires_grad 设置为 True,则会开始跟踪针对 tensor 的所有操作。.requires_grad_( ... ) 会改变张量的 requires_grad 标记。输入的标记默认为 False ,如果没有提供相应的参数。

完成计算后,您可以调用 .backward() 来自动计算所有梯度。

该张量的梯度将累积到 .grad 属性中。要停止 tensor 历史记录的跟踪,您可以调用 .detach(),它将其与计算历史记录分离,并防止将来的计算被跟踪。要停止跟踪历史记录(和使用内存),您还可以将代码块使用 with torch.no_grad(): 包装起来。

在评估模型时,这是特别有用,因为模型在训练阶段具有 requires_grad = True 的可训练参数有利于调参,但在评估阶段我们不需要梯度。(???)

另一个重要的类是Function。Tensor 和 Function 互相连接并构建一个非循环图,它保存整个完整的计算过程的历史信息。

每个张量都有一个 .grad_fn 属性保存着创建了张量的 Function 的引用,(如果用户自己创建张量,则g rad_fn 是 None )。

计算导数

你可以调用 Tensor.backward()。如果 Tensor 是标量(即它包含一个元素数据),则不需要指定任何参数backward(),但是如果它有更多元素,则需要指定一个gradient 参数来指定张量的形状。

例子1

import torch
# 创建一个张量,设置 requires_grad=True 来跟踪与它相关的计算
x = torch.ones(2, 2, requires_grad=True)
# 操作张量
y = x + 2
z = y * y * 3
out = z.mean()
# 后向传播,因为输出包含了一个标量,out.backward() 等同于out.backward(torch.tensor(1.))。
out.backward()
# 打印梯度 d(out)/dx
print(x.grad)

# tensor([[4.5000, 4.5000],
#        [4.5000, 4.5000]])

原理: 最终Loss的值,网络结构(部分偏导数),当前训练的值。三者共同决定了梯度。这意味着在Batch使用时,假如将网络复制多遍(包括初始训练参数也一样),对于总的Loss来训练得到的参数是完全相同的。

例子2

y 不再是一个标量。torch.autograd 不能够直接计算整个雅可比,但是如果我们只想要雅可比向量积,只需要简单的传递向量给 backward 作为参数。(??? 雅可比向量积有什么用)

v = torch.tensor([0.1, 1.0, 0.0001], dtype=torch.float)
y.backward(v)

print(x.grad)
# tensor([1.0240e+02, 1.0240e+03, 1.0240e-01])

神经网络的训练

定义网络

一个简单的前馈神经网络,它接收输入,让输入一个接着一个的通过一些层,最后给出输出。 通过 torch.nn 包来构建。一个 nn.Module 包括层和一个方法 forward(input) 它会返回输出(output)。

import torch
import torch.nn as nn
import torch.nn.functional as F


class Net(nn.Module):

    def __init__(self):
        # 习惯上,将包含可训练参数的结构,声明在__init__里
        super(Net, self).__init__()
        # 1 input image channel, 6 output channels, 5x5 square convolution
        # kernel
        self.conv1 = nn.Conv2d(1, 6, 5)
        self.conv2 = nn.Conv2d(6, 16, 5)
        # an affine operation: y = Wx + b
        self.fc1 = nn.Linear(16 * 5 * 5, 120)
        self.fc2 = nn.Linear(120, 84)
        self.fc3 = nn.Linear(84, 10)

    def forward(self, x):
        # Max pooling over a (2, 2) window
        x = F.max_pool2d(F.relu(self.conv1(x)), (2, 2))
        # If the size is a square you can only specify a single number
        x = F.max_pool2d(F.relu(self.conv2(x)), 2)
        x = x.view(-1, self.num_flat_features(x))
        x = F.relu(self.fc1(x))
        x = F.relu(self.fc2(x))
        x = self.fc3(x)
        return x

    def num_flat_features(self, x):
        size = x.size()[1:]  # all dimensions except the batch dimension
        num_features = 1
        for s in size:
            num_features *= s
        return num_features


net = Net()
print(net)

一个模型可训练的参数可以通过调用 net.parameters() 返回:

params = list(net.parameters())
print(len(params))
print(params[0].size())  # conv1's .weight

运行一次网络

input = torch.randn(1, 1, 32, 32)
out = net(input)
print(out)

反向传播计算各个位置梯度

把所有参数梯度缓存器置零,用随机的梯度来反向传播

net.zero_grad()
out.backward(torch.randn(1, 10))

损失函数

一个损失函数需要一对输入:模型输出和目标,然后计算一个值来评估输出距离目标有多远。

有一些不同的损失函数在 nn 包中。一个简单的损失函数就是 nn.MSELoss ,这计算了均方误差。

可以调用包,也可以自己设计。

output = net(input)
target = torch.randn(10)  # 随便一个目标
target = target.view(1, -1)  # make it the same shape as output
criterion = nn.MSELoss()

loss = criterion(output, target)

使用loss反向传播更新梯度

查看梯度记录的地方

input -> conv2d -> relu -> maxpool2d -> conv2d -> relu -> maxpool2d
      -> view -> linear -> relu -> linear -> relu -> linear
      -> MSELoss
      -> loss

当我们调用 loss.backward(),整个图都会微分,而且所有的在图中的requires_grad=True 的张量将会让他们的 grad 张量累计梯度。

为了实现反向传播损失,我们所有需要做的事情仅仅是使用 loss.backward()。你需要清空现存的梯度,要不然将会和现存(上一轮)的梯度累计到一起。

net.zero_grad()     # zeroes the gradient buffers of all parameters
loss.backward()

查看某处梯度

print(net.conv1.bias.grad)

使用梯度和各种方法优化器更新参数

最简单的更新规则就是随机梯度下降。

weight = weight - learning_rate * gradient

我们可以使用 python 来实现这个规则:

learning_rate = 0.01
for f in net.parameters():
    f.data.sub_(f.grad.data * learning_rate)

尽管如此,如果你是用神经网络,你想使用不同的更新规则,类似于 SGD, Nesterov-SGD, Adam, RMSProp, 等。为了让这可行,我们建立了一个小包:torch.optim 实现了所有的方法。使用它非常的简单。

import torch.optim as optim

# create your optimizer
optimizer = optim.SGD(net.parameters(), lr=0.01)

# in your training loop:
optimizer.zero_grad()   # zero the gradient buffers
output = net(input)
loss = criterion(output, target)
loss.backward()
optimizer.step()    # Does the update

上面是一次训练

一般是按照一次多少batch训练,训练10次等.

或者考虑loss 稳定后结束,一般不使用loss小于某个值(因为不知道loss阈值是多少)

或许可以考虑K折交叉检验法(k-fold cross validation)

for epoch in range(2):  # loop over the dataset multiple times
    running_loss = 0.0
    for i, data in enumerate(trainloader, 0):
        # get the inputs
        inputs, labels = data

        # zero the parameter gradients
        optimizer.zero_grad()

        # forward + backward + optimize
        outputs = net(inputs)
        loss = criterion(outputs, labels)
        loss.backward()
        optimizer.step()

        # print statistics
        running_loss += loss.item()
        if i % 2000 == 1999:    # print every 2000 mini-batches
            print('[%d, %5d] loss: %.3f' %
                  (epoch + 1, i + 1, running_loss / 2000))
            running_loss = 0.0
print('Finished Training')

测试单个任务

分类任务,取最高的

outputs = net(images)
_, predicted = torch.max(outputs, 1)

测试总误差

correct = 0
total = 0
with torch.no_grad():
    for data in testloader:
        images, labels = data
        outputs = net(images)
        _, predicted = torch.max(outputs.data, 1)
        total += labels.size(0)
        correct += (predicted == labels).sum().item()

print('Accuracy of the network on the 10000 test images: %d %%' % (
    100 * correct / total))

各种初学者问题

In-place 正确性检查

所有的Variable都会记录用在他们身上的 in-place operations。如果pytorch检测到variable在一个Function中已经被保存用来backward,但是之后它又被in-place operations修改。当这种情况发生时,在backward的时候,pytorch就会报错。这种机制保证了,如果你用了in-place operations,但是在backward过程中没有报错,那么梯度的计算就是正确的。

对于不需要自动微分

=不需要计算梯度=手动计算值的

使用 someTensor.detach() 来更新

相关知识

欠拟合和过拟合判断

  1. 训练集和测试集都不好——欠拟合
  2. 训练集好,测试集不好——过拟合

多通道

一般是任务特征很多维度时,拓展描述参数用的。

比如:图像一般包含三个通道/三种原色(红色、绿色和蓝色)。 实际上,图像不是二维张量,而是一个由高度、宽度和颜色组成的三维张量。所以第三维通过通道表示。

https://zh.d2l.ai/chapter_convolutional-neural-networks/channels.html

多通道举例说明

self.conv1 = nn.Conv2d(1, 6, 5) # 输入通道1,输出通道6,卷积核 5*5
\[ 28=32-5+1 \]

初始1通道变6通道,意味着对初始的A数据,有6个初始值不同的5*5卷积核操作,产生6张图。需要参数6*5*5.

初始6通道变16通道,相当于将6通道变1通道,重复16次。6通道变1通道,通过6张图与由6个5*5卷积核组成的卷积核组作用,生成6张图,然后简单相加,变成1张。需要总参数16*6*5*5*5。相当于下图某些数据变成6和16:

BatchSize

https://blog.csdn.net/qq_34886403/article/details/82558399

  1. Batch Size定义:一次训练所选取的样本数。
  2. 由于矩阵操作,增加batch/行号。每行经过同一个网络,引起的就是输出行号增加。只需要对每行单独计算出来的误差进行sum或者mean得到一个误差值,就可以反向传播,训练参数。
  3. 简单来说就是平均了一个batch数据的影响,不会出现离谱的波动,方向比较准确。
  4. Batch Size的大小影响模型的优化程度和速度。同时其直接影响到GPU内存的使用情况,假如你GPU内存不大,该数值最好设置小一点。
  5. 没有Batch Size,梯度准确,只适用于小样本数据库
  6. Batch Size增大,梯度变准确。但是单个epoch的迭代次数减少了,参数的调整也慢了,假如要达到相同的识别精度,需要更多的epoch。
  7. Batch Size再增大,梯度已经非常准确,再增加Batch Size也没有用
  8. 虽然Batch Size增大,一遍的总次数变少,单步计算量增加。但是由于GPU并行操作,单步时间不会增加太多。

BatchNorm

Batch Normalization是将各层的输入进行归一化,使训练过程更快、更稳定的一种技术。在实践中,它是一个额外的层,我们通常添加在计算(卷积)层之后,在非线性(激活函数)之前。也有更先进的,比如layernorm。

BN层只是效果会变好,因为感受到了细节。不是有batch一定有BN层的意思。

各种不同的Loss

交叉熵和加权交叉熵

多用于多分类任务,预测值是每一类各自的概率。label为特定的类别 torch.nn.NLLLOSS通常不被独立当作损失函数,而需要和softmax、log等运算组合当作损失函数。

torch.nn.CrossEntropyLoss相当于softmax + log + nllloss。

预测的概率大于1明显不符合预期,可以使用softmax归一,取log后是交叉熵,取负号是为了符合loss越小,预测概率越大。

# 4类权重是 1, 10, 100, 100 一般是与样本占比成反比
criterion = nn.CrossEntropyLoss(weight=torch.from_numpy(np.array([1,10,100,100])).float() ,reduction='sum')
* size_average(该参数不建议使用,后续版本可能被废弃),该参数指定loss是否在一个Batch内平均,即是否除以N。默认为True * reduce (该参数不建议使用,后续版本可能会废弃),首先说明该参数与size_average冲突,当该参数指定为False时size_average不生效,该参数默认为True。reduce为False时,对batch内的每个样本单独计算loss,loss的返回值Shape为[N],每一个数对应一个样本的loss。reduce为True时,根据size_average决定对N个样本的loss进行求和还是平均,此时返回的loss是一个数。 * reduction 该参数在新版本中是为了取代size_average和reduce参数的。 * 它共有三种选项'mean','sum'和'none'。 * 'mean'为默认情况,表明对N个样本的loss进行求平均之后返回(相当于reduce=True,size_average=True); * 'sum'指对n个样本的loss求和(相当于reduce=True,size_average=False); * 'none'表示直接返回n分样本的loss(相当于reduce=False)

Focal Loss

相对于加权交叉熵不仅权重不需要计算,自动通过概率算,而且gamma=2按照平方缩小了,大样本的影响。

“蓝”线代表交叉熵损失。X轴即“预测为真实标签的概率”(为简单起见,将其称为pt)。举例来说,假设模型预测某物是自行车的概率为0.6,而它确实是自行车, 在这种情况下的pt为0.6。

Y轴是给定pt后Focal loss和CE的loss的值。

从图像中可以看出,当模型预测为真实标签的概率为0.6左右时,交叉熵损失仍在0.5左右。因此,为了在训练过程中减少损失,我们的模型将必须以更高的概率来预测到真实标签。换句话说,交叉熵损失要求模型对自己的预测非常有信心。但这也同样会给模型表现带来负面影响。

深度学习模型会变得过度自信, 因此模型的泛化能力会下降.

当使用γ> 1的Focal Loss可以减少“分类得好的样本”或者说“模型预测正确概率大”的样本的训练损失,而对于“难以分类的示例”,比如预测概率小于0.5的,则不会减小太多损失。因此,在数据类别不平衡的情况下,会让模型的注意力放在稀少的类别上,因为这些类别的样本见过的少,比较难分。

https://cloud.tencent.com/developer/article/1669261

https://blog.csdn.net/qq_34914551/article/details/105393989

https://ptorch.com/news/253.html

Pytorch.nn常用函数

torch.nn.Linear

\[ y=x*A^T+b \]

设置网络中的全连接层的,需要注意在二维图像处理的任务中,全连接层的输入与输出一般都设置为二维张量,形状通常为[batch_size, size],不同于卷积层要求输入输出是四维张量。

in_features指的是输入的二维张量的大小,即输入的[batch_size, size]中的size。

out_features指的是输出的二维张量的大小,即输出的二维张量的形状为[batch_size,output_size],当然,它也代表了该全连接层的神经元个数。

torch.nn.ReLU()

\[ ReLU(x)=(x)^+=max(0,x) \]

torch.nn.Sigmoid

\[ Sigmoid(x)=σ(x)= \frac{1}{1+exp(−x)} \]
  1. torch.nn.Sigmoid()
  2. 是一个类。在定义模型的初始化方法中使用,需要在_init__中定义,然后再使用。
  3. torch.nn.functional.sigmoid():
  4. 可以直接在forward()里使用。eg.A=F.sigmoid(x)

torch.cat

cat是concatnate的意思:拼接,联系在一起。

C = torch.cat( (A,B),0 )  #按维数0拼接(竖着拼)
C = torch.cat( (A,B),1 )  #按维数1拼接(横着拼)

torch.nn.BatchNorm2d

num_features – C from an expected input of size (N, C, H, W)

torch.nn.BatchNorm1d

Input: (N, C) or (N, C, L), where NN is the batch size, C is the number of features or channels, and L is the sequence length

Output: (N, C) or (N, C, L) (same shape as input)

Softmax函数和Sigmoid函数的区别

https://zhuanlan.zhihu.com/p/356976844

保存与读取

Save on GPU, Load on GPU Save:

torch.save(model.state_dict(), PATH)

Load:

device = torch.device("cuda")
model = TheModelClass(*args, **kwargs)
model.load_state_dict(torch.load(PATH))
model.to(device)
# Make sure to call input = input.to(device) on any input tensors that you feed to the model
model.eval()

Remember that you must call model.eval() to set dropout and batch normalization layers to evaluation mode before running inference. Failing to do this will yield inconsistent inference results.

误差的表示

训练参数怎么保存和读取

怎么表示数据

怎么反向梯度法训练

怎么使用GPU,怎么多GPU

在GPU上训练 就像你怎么把一个张量转移到GPU上一样,你要将神经网络转到GPU上。 如果CUDA可以用,让我们首先定义下我们的设备为第一个可见的cuda设备。

device = torch.device("cuda:0" if torch.cuda.is_available() else "cpu")

# Assume that we are on a CUDA machine, then this should print a CUDA device:

print(device) # cuda:0
net=Net()
net.to(device)
outputs = net(inputs)
input = torch.randn(1, 1, 32, 32)
inputs, labels = inputs.to(device), labels.to(device)
out = net(input)

多GPU

如果你想要来看到大规模加速,使用你的所有GPU,请查看:数据并行性(https://pytorch.org/tutorials/beginner/blitz/data_parallel_tutorial.html)。PyTorch 60 分钟入门教程:数据并行处理

http://pytorchchina.com/2018/12/11/optional-data-parallelism/

可视化

网络结构可视化

自动 https://stackoverflow.com/questions/52468956/how-do-i-visualize-a-net-in-pytorch

或者手动drawio

误差实时可视化TensorBoard

https://www.cnblogs.com/sddai/p/14516691.html

原理: 通过读取保存的log文件来可视化数据

标量可视化

记录数据,默认在当前目录下一个名为'runs/'的文件夹中。

from torch.utils.tensorboard import SummaryWriter

# 写log的东西
log_writer = SummaryWriter('./path/to/log')
# 第一个参数是名称,第二个参数是y值,第三个参数是x值。
log_writer.add_scalar('Loss/train', float(loss), epoch)

运行 tensorboard --logdir=runs/ --port 8123 在某端口打开,比如 https://127.0.0.1:6006

网络结构可视化

在tensorboard的基础上使用tensorboardX

from tensorboardX import SummaryWriter

with SummaryWriter(comment='LeNet') as w:
    w.add_graph(net, (net_input, ))

PR曲线

什么是PR曲线

log_writer.add_pr_curve("pr_curve", label_batch, predict, epoch)

x,y轴分别是recall和precision。应该有可能有矛盾的数据,或者网络分不开,对于不同的阈值,可以划分出PR图。

与ROC曲线左上凸不同的是,PR曲线是右上凸效果越好。

怎么分布式并行

需要进一步的研究学习

暂无

遇到的问题

  1. 矩阵或者向量的使用
  2. optimizer.step() # Does the update会自动循环吗?什么误差什么时候训练完毕呢?

开题缘由、总结、反思、吐槽~~

社会计算实验二,关于Meetup数据的预测性问题的解决

参考文献

https://pytorch-cn.readthedocs.io/zh/latest/

https://www.pytorch123.com/

https://zh.d2l.ai/chapter_convolutional-neural-networks/channels.html

Exploring the Impact of Dynamic Mutual Influence on Social Event Participation

Cuda Program Basic

CUDA编程水平高低的不同,会导致几十上百倍的性能差距。但是这篇将聚焦于CUDA的编程语法,编译与运行。