Cplusplus

模版元编程与函数式

image-20240808230648900

image-20240820160811024

template

image-20240820162244999

image-20240820162358151

std::enable_if 是 C++ 标准库中的一个模板工具,通常用于实现 SFINAE(Substitution Failure Is Not An Error)技术。它位于 <type_traits> 头文件中,用于在模板编程中根据条件启用或禁用模板的实例化。

  • 基本用法

    std::enable_if 的基本结构如下:

    template <bool B, typename T = void>
    struct enable_if {
      using type = T;
    };
    
    template <typename T>
    struct enable_if<false, T> {
      // 这个结构体是未定义的
    };
    
  • 解释

  • std::enable_if 主要有两个模板参数

    • B:一个布尔值(通常是编译时常量表达式),用于决定 type 成员是否有效。
    • T:一个默认类型(默认为 void),当 B 为真时,type 成员将定义为 T
  • B 为真时std::enable_iftype 成员被定义为 T。这意味着我们可以使用 std::enable_iftype 来在模板中进行条件判断。

  • B 为假时std::enable_iftype 成员没有定义。尝试使用这种情况下的 type 成员会导致编译错误,从而使得该模板实例化失败。这样可以用来控制模板的选择和重载。

  • 示例

    以下是一个使用 std::enable_if 的示例,演示如何根据类型的特性来启用或禁用函数模板:

    #include <iostream>
    #include <type_traits>
    
    // 用于启用整数类型的模板函数
    template<typename T>
    typename std::enable_if<std::is_integral<T>::value, void>::type
    printType() {
      std::cout << "Integral type\n";
    }
    
    // 用于启用非整数类型的模板函数
    template<typename T>
    typename std::enable_if<!std::is_integral<T>::value, void>::type
    printType() {
      std::cout << "Non-integral type\n";
    }
    
    int main() {
      printType<int>();    // 输出: Integral type
      printType<double>(); // 输出: Non-integral type
      return 0;
    }
    

    在这个示例中:

  • printType<int>() 会选择第一个模板版本,因为 int 是整数类型。

  • printType<double>() 会选择第二个模板版本,因为 double 不是整数类型。

  • 工作原理

  • 编译时替换std::enable_if 根据布尔表达式 B 的值来决定是否定义 type 成员。

  • 条件启用:在模板参数中使用 std::enable_if 可以有效地启用或禁用某些模板实例化。

  • SFINAE:如果 B 为假,type 成员未定义,尝试实例化使用 type 的模板将导致编译错误,从而引发 SFINAE 机制。

    通过这种方式,std::enable_if 可以帮助实现条件模板选择,使得模板编程更加灵活和强大。

    image-20240820163258259

    模板的参数可以作为编译器常量,可以自动优化

    image-20240820163542636

    image-20240820163702315

    image-20240820163833807

    N变一次,编译器就会重新实例化一遍模版函数,编译就变慢

    模版函数必须定义在同一个文件里才能使用(必须是内联的或者在头文件里的),所以模板函数的定义和实现无法分离,因此除非特殊手段,模板函数的定义和实现必须放到头文件里。

    模板函数太多会导致头文件非常大。

    模板函数内联要加static

    image-20240821074758660{:height 34, :width 232}

    image-20240821075058309

    image-20240821080547610

    image-20240821080851591

    if constexpr 是 C++17 中引入的一种编译时条件语句。它允许在编译时根据条件选择代码路径,从而避免在运行时进行条件判断。与传统的 if 语句不同,if constexpr 在编译时会根据条件是否为 true 来决定是否编译相应的代码块。

    举个例子:

    #include <iostream>
    #include <type_traits>
    
    template <typename T>
    void print_type() {
      if constexpr (std::is_integral<T>::value) {
          std::cout << "Integral type" << std::endl;
      } else {
          std::cout << "Non-integral type" << std::endl;
      }
    }
    
    int main() {
      print_type<int>();    // 输出 "Integral type"
      print_type<double>(); // 输出 "Non-integral type"
    }
    

    在这个例子中,if constexpr 会在编译时检查 std::is_integral<T>::value 是否为 true,然后编译对应的代码块。这使得 print_type 函数的行为在编译时就被确定下来,从而避免了在运行时的类型检查。

    image-20240821081339456

    image-20240821082517892

    image-20240821082721689

    image-20240821090104734

    image-20240821090237051

    image-20240821090714458但是这样要把模板实例化的,每一种 情况都声明

    所以,尽量不要把模板分离

    image-20240821091734245延迟编译:当一个函数定义在头文件里,可能用不到,可以在前面加 template 这个假模板,只有被调用的时候才会被编译

    image-20240821093416355

    可以把函数的信息打印出来

    image-20240821094441153

    image-20240821094522021

    image-20240821094700080

    image-20240821095549768

    c++里的引用(int &)相当于C里面的指针(int*)

    image-20240821145117646引用没有空,指针可以空

    auto & auto const & 也可

    image-20240821150609535

    懒汉单例模式(Lazy Singleton)是一种设计模式,用于确保一个类只有一个实例,并提供一个全局访问点。与饿汉单例模式不同,懒汉单例模式会在需要实例时才进行初始化,因此被称为“懒汉”模式。

  • 懒汉单例模式的特点

    1. 延迟初始化:单例对象只有在第一次被使用时才会创建。
    2. 线程安全问题:在多线程环境下,需要处理线程安全问题,以确保只有一个实例被创建。
  • 懒汉单例模式的实现方式

    下面是一个基本的懒汉单例模式的实现示例(不考虑线程安全):

    class Singleton {
    public:
      // 获取单例实例的静态方法
      static Singleton* getInstance() {
          if (instance == nullptr) {
              instance = new Singleton();
          }
          return instance;
      }
    
      // 禁止拷贝构造函数和赋值操作符
      Singleton(const Singleton&) = delete;
      Singleton& operator=(const Singleton&) = delete;
    
    private:
      // 私有构造函数
      Singleton() {}
    
      // 静态成员变量,用于存储唯一的实例
      static Singleton* instance;
    };
    
    // 静态成员变量的初始化
    Singleton* Singleton::instance = nullptr;
    
  • 线程安全的实现

    在多线程环境下,上述实现可能会导致线程安全问题,因此需要对其进行改进。可以使用互斥锁(mutex)来确保线程安全:

    #include <mutex>
    
    class Singleton {
    public:
      // 获取单例实例的静态方法
      static Singleton* getInstance() {
          if (instance == nullptr) {
              std::lock_guard<std::mutex> lock(mutex);
              if (instance == nullptr) {
                  instance = new Singleton();
              }
          }
          return instance;
      }
    
      // 禁止拷贝构造函数和赋值操作符
      Singleton(const Singleton&) = delete;
      Singleton& operator=(const Singleton&) = delete;
    
    private:
      // 私有构造函数
      Singleton() {}
    
      // 静态成员变量,用于存储唯一的实例
      static Singleton* instance;
      // 互斥锁,用于保证线程安全
      static std::mutex mutex;
    };
    
    // 静态成员变量的初始化
    Singleton* Singleton::instance = nullptr;
    std::mutex Singleton::mutex;
    
  • C++11 及以后的标准

    在C++11及以后的标准中,可以使用std::call_once来确保实例的唯一性,并提高线程安全性:

    #include <mutex>
    
    class Singleton {
    public:
      // 获取单例实例的静态方法
      static Singleton* getInstance() {
          std::call_once(flag, []() {
              instance.reset(new Singleton());
          });
          return instance.get();
      }
    
      // 禁止拷贝构造函数和赋值操作符
      Singleton(const Singleton&) = delete;
      Singleton& operator=(const Singleton&) = delete;
    
    private:
      // 私有构造函数
      Singleton() {}
    
      // 静态成员变量,用于存储唯一的实例
      static std::unique_ptr<Singleton> instance;
      // 静态变量,用于确保单例实例只创建一次
      static std::once_flag flag;
    };
    
    // 静态成员变量的初始化
    std::unique_ptr<Singleton> Singleton::instance;
    std::once_flag Singleton::flag;
    

    在这个实现中,std::call_oncestd::once_flag 确保了即使在多线程环境中,单例对象也只会被创建一次。std::unique_ptr 自动管理内存,避免了手动释放内存的麻烦。

    使用互斥锁(mutex)来确保线程安全时为什么只有锁:std::lock_guardstd::mutex lock(mutex); 没有解锁?

    在使用 std::lock_guard<std::mutex> 时,解锁是由 std::lock_guard 自动处理的,而不需要显式地调用解锁操作。这是因为 std::lock_guard 是一个RAII(Resource Acquisition Is Initialization)风格的类,它的设计目的是简化互斥锁的管理并自动释放资源。

  • RAII 和 std::lock_guard

    RAII 是一种编程习惯,确保资源(如内存、文件句柄、互斥锁等)的生命周期由对象的生命周期来管理。std::lock_guard 利用 RAII 原则来管理互斥锁的锁定和解锁:

    1. 构造函数:当 std::lock_guard 对象被创建时,它会在构造函数中自动锁定传递给它的 std::mutex 对象。
    2. 析构函数:当 std::lock_guard 对象被销毁(即其作用域结束时),它的析构函数会自动释放(解锁)互斥锁。

    这种设计使得你不需要显式地编写解锁代码,降低了因为遗漏解锁操作而导致的潜在错误。

  • 解释

  • std::lock_guard<std::mutex> lock(mutex);

    • 当执行到这行代码时,lock 对象会在构造函数中自动锁定 mutex
    • lock 对象超出作用域(例如,getInstance 方法的执行结束时),lock 的析构函数会被调用,从而自动解锁 mutex
  • 优点

  • 自动解锁:减少了因为忘记解锁导致的死锁问题。

  • 简化代码:不需要显式地管理锁的释放,使代码更加简洁和易于维护。

  • 异常安全:即使在 getInstance 方法中发生异常,std::lock_guard 也会确保互斥锁在 lock 对象被销毁时正确解锁,从而避免死锁。

    通过 std::lock_guard 或其他类似的 RAII 风格的工具,C++ 提供了一种简洁而安全的方式来管理互斥锁,帮助程序员编写更健壮的多线程代码。

    image-20240821154750452

    image-20240821155047037

image-20240822093944038

decltype(auto)和auto的区别

decltype(auto)auto 都用于类型推导,但它们有不同的行为:

  1. auto:

    • 用于自动推导变量的类型。auto 根据表达式的值推导类型,不会保留表达式的引用性(即 auto 不会推导出引用类型,除非显式指定)。
    • 例如,auto x = 5; 中,x 的类型是 int
  2. decltype(auto):

    • 结合 decltypeauto 的特性。它推导出表达式的类型,包括引用(decltype 会保留表达式的原始类型)。
    • 例如,decltype(auto) y = (5); 中,y 的类型是 int&,因为 (5) 是一个左值引用。

总结:

  • 使用 auto 时,结果类型是值类型。
  • 使用 decltype(auto) 时,结果类型保持原表达式的类型,包括引用。

image-20240822094955233

image-20240822095110135

image-20240822095353349T1{}创建一个T1的对象

函数式编程

image-20240822100310129

函数作为参数传入另一个函数,实际传的是这个函数的起始地址

image-20240822100649562

确实相当于函数指针

image-20240822100903926

image-20240822102642020

image-20240822102841702

image-20240822103024352

image-20240822103222797

image-20240822103620126

image-20240822103849124

image-20240822104300564

image-20240822142510370

image-20240822142730386

###避免使用模板参数

image-20240822143331265

类型擦除技术:std::function容器

image-20240822143825237

image-20240822145011740但是没办法做部分特例化

image-20240822145901194

立即调用 Lambda:在 lambda 表达式的定义后面加上 (),立即调用这个匿名函数。 lambda 表达式的返回值可以用于初始化变量或进行其他操作。

image-20240822150515258

可以利用return自带的break效果既实现break又赋值的效果

image-20240822151844264

image-20240822152541777

image-20240822152759758

image-20240822153156878

image-20240822161836536

image-20240822162204007

左值持久,右值短暂,左值有持久的状态,而右值要么是字面常量,要么是在表达式求值过程中创建的临时对象(将要被销毁的对象)。

右值引用的好处是减少右值作为参数传递时的复制开销

使用std::move可以获得绑定到一个左值的右值引用

int intValue = 10;
int &&intValue3 = std::move(intValue);

decltype(auto) 是 C++11 引入的一种类型推断工具,它结合了 decltypeauto 的特性,用于在声明变量时推断其类型。与 auto 不同,decltype(auto) 更精确地推断变量的类型,包括引用性。

  • 用法decltype(auto) 在声明变量时,会推断出表达式的确切类型,包括是否是引用类型。

    int x = 10;
    int& ref = x;
    decltype(auto) y = ref; // y 是 int&,与 ref 类型相同
    
  • 区别auto 只推断值类型,而 decltype(auto) 会保持原有的引用类型或常量性。

    auto a = x;          // a 是 int
    decltype(auto) b = x; // b 是 int,b 不是引用
    decltype(auto) c = ref; // c 是 int&,与 ref 类型相同
    

总结decltype(auto) 在需要精确类型推断,包括引用时非常有用。

但是tuple容器的万能推导由于历史原因,不是decltype(auto),而是auto &&

image-20240825111507625

image-20240825111624413

结构化绑定的基本语法如下:

auto [var1, var2, var3] = expression;

image-20240825112136528

image-20240825154641671

image-20240825155359129

image-20240825155541735

image-20240826130922114optional就像一个更安全的指针

在 C++ 中,union 是一种数据结构,它允许在同一内存位置存储不同的数据类型。union 的所有成员共享同一块内存区域,这意味着在任何给定时刻,union 只能存储一个成员的数据。使用 union 可以节省内存,特别是在需要存储多种不同类型但从不同时存储这些类型时。

union 的基本语法

union UnionName {
    type1 member1;
    type2 member2;
    type3 member3;
    // more members
};

主要特点

  1. 内存共享

    • union 中的所有成员共享同一块内存。因此,union 的大小由其最大成员的大小决定。
  2. 只能存储一个成员

    • 虽然 union 可以定义多个成员,但在任何时刻只能存储一个成员的数据。写入一个成员会覆盖掉之前写入的成员的数据。
  3. 节省内存

    • 因为所有成员共用一块内存,所以 union 可以节省内存,尤其是在只需要存储其中一个成员的数据时。

使用示例

#include <iostream>

union Data {
    int intValue;
    float floatValue;
    char charValue;
};

int main() {
    Data data;

    data.intValue = 5;
    std::cout << "intValue: " << data.intValue << std::endl;

    data.floatValue = 3.14;
    std::cout << "floatValue: " << data.floatValue << std::endl;

    data.charValue = 'A';
    std::cout << "charValue: " << data.charValue << std::endl;

    // 访问数据会输出不确定的结果,因为各个成员共享同一内存
    std::cout << "intValue (after modifying to charValue): " << data.intValue << std::endl;

    return 0;
}

在上面的示例中,union Data 可以存储 int, float, 和 char 三种数据类型,但它们共享同一块内存。当写入 floatValue 后,之前存储的 intValue 的数据会被覆盖,读取 intValue 会得到不可预测的结果。

注意事项

  • 类型安全

    • 使用 union 时要注意类型安全。读取当前未写入的成员数据可能会导致未定义的行为。
  • 构造和析构

    • union 允许只有一个成员的构造和析构。C++11 之后,union 可以包含具有非平凡构造函数、析构函数或拷贝/移动操作符的成员,但这些操作必须在使用 union 的情况下正确处理。
  • std::variant 替代

    • C++17 引入了 std::variant,这是一个更安全的替代 union,提供了类型安全的联合体和更丰富的功能。

总的来说,union 是一个低级数据结构,用于内存优化和处理不同类型的数据,但在实际编程中需谨慎使用。

image-20240826131405785

image-20240826133023527

image-20240826133352602

image-20240826134549406

image-20240826135522792

  • 使用 auto 作为参数类型实际上利用了 C++ 的模板机制,因为 auto 类型推断相当于模板类型参数的自动推导。虽然 lambda 本身不是一个模板,但它的参数使用 auto 实际上是利用了模板的类型推断机制。
  • [&] (auto const &t){} 使用了模板特性中的类型推断机制,通过 auto 使得 lambda 表达式能够处理多种不同类型的参数。这个功能在 C++11 及其后续版本中成为了更灵活、强大的工具,使得代码更加简洁和通用。

image-20240826140520404

image-20240826140928719

从汇编角度看编译器优化

编译器是从源代码生成汇编语言

image-20240826142543763

RIP是当前执行的代码的地址

MMX,XMM,YMM都是用于储存浮点数的寄存器

把局部变量放入寄存器,读写就更快了

rsp代表堆栈: -4(%rsp)其中-代表是堆栈上的某一个地址

image-20240826143356174

image-20240826145632245

image-20240826145948278

eax与rax的低32位是共用的

ax与eax的低16位是通用的

image-20240826162116558

image-20240826162507877%eax :返回值

image-20240826163129510

image-20240826163353133

image-20240826163854896

l代表32位,q代表64位

image-20240826164111288

image-20240826165156571

image-20240826165630808

在 C++ 中,ThreadPool threadPool {};ThreadPool threadPool ; 是两种不同的初始化方式,它们对 ThreadPool 对象的初始化有所不同。

1. ThreadPool threadPool {};

这是 直接初始化(Direct Initialization) 的一种方式,使用了 统一初始化语法(Uniform Initialization Syntax)。具体来说,这种写法会调用 ThreadPool 的默认构造函数,并且初始化所有成员变量为默认值:

  • 如果 ThreadPool 有默认构造函数,它将被调用来创建对象。
  • 如果 ThreadPool 的构造函数没有显式初始化某些成员变量,它们会被自动初始化为其类型的默认值。对于基本数据类型(如 int),这意味着它们会被初始化为 0。对于指针类型,它们会被初始化为 nullptr

2. ThreadPool threadPool ;

这是 默认初始化(Default Initialization) 的一种方式。在这种情况下,ThreadPool 对象的初始化行为依赖于以下几种情况:

  • 如果 ThreadPool 有默认构造函数,它将被调用来创建对象。
  • 如果 ThreadPool 的构造函数没有显式初始化某些成员变量,那么这些成员变量的初始化方式依赖于它们的类型和是否有默认构造函数。基本数据类型(如 int)不会被初始化到任何特定值(它们会是未定义的),指针类型也不会自动初始化(它们的值是不确定的)。

总结

  • **ThreadPool threadPool {};**:使用统一初始化语法,所有成员变量被初始化为其类型的默认值,较为安全。
  • ThreadPool threadPool ;:默认初始化,成员变量的初始值依赖于其类型和构造函数,可能会导致未定义行为(对于基本数据类型)

在实践中,推荐使用 ThreadPool threadPool {}; 以确保对象的成员变量被正确地初始化,避免潜在的未定义行为。

在对象构造时,std::lock_guard 会自动锁定传入的互斥锁,而在对象析构时,它会自动释放锁

std::lock_guard<std::mutex> guard(lock);

当执行 std::lock_guard<std::mutex> guard(lock); 时:

  • 锁定: guard 对象在创建时会自动调用 lock() 方法来锁定传入的互斥锁(lock)。
  • 作用域结束: 当 guard 对象的作用域结束(例如,离开当前的代码块或函数)时,它的析构函数会自动调用 unlock() 方法来解锁互斥锁

要理解 subset 中的这行数据,我们可以将其拆解成几部分来分析:

[[ 0.          1.          2.          3.          4.          5.
   6.          7.          8.         -1.         -1.          9.
  -1.         -1.         10.         11.         12.         -1.
  21.50975911 13.        ]]

1. 关键点索引

  • 前 18 个值 [0, 1, 2, 3, 4, 5, 6, 7, 8, -1, -1, 9, -1, -1, 10, 11, 12, -1] 代表了关键点的索引。
    • 正整数表示该位置有一个有效的关键点索引。
    • -1 表示该位置没有对应的关键点。

2. 总评分

  • 21.50975911 是这个组合的总评分。这个评分是所有有效关键点的评分之和或某种加权评分的结果。

3. 关键点数量

  • 13 是这个组合中的有效关键点数量。这里 13 表示在该组合中共有 13 个有效的关键点索引。

结合信息

这个 subset 行数据表示一个关键点组合,其中包含 13 个有效的关键点,所有这些关键点的索引被列出。组合的总评分为 21.50975911。通过这些信息,你可以了解该组合的结构以及它在某种评分机制下的表现。

详细解读:

  • 有效关键点索引为 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],总共 13 个。
  • 索引为 -1 的位置表示这些位置没有有效的关键点。
  • 总评分 21.50975911 可能是根据这些有效关键点的某些特性(如评分、置信度等)计算出来的。

这样的 subset 数据通常用于在处理关键点检测任务中,选择或评估最佳的关键点组合。

这个是candidate: [[2.19000000e+02 1.18000000e+02 9.45192695e-01 0.00000000e+00] [1.96000000e+02 2.63000000e+02 9.28416848e-01 1.00000000e+00] [8.70000000e+01 2.89000000e+02 8.54923248e-01 2.00000000e+00] [6.60000000e+01 4.49000000e+02 8.24636817e-01 3.00000000e+00] [1.20000000e+02 5.07000000e+02 7.98071980e-01 4.00000000e+00] [3.07000000e+02 2.38000000e+02 8.55016530e-01 5.00000000e+00] [3.64000000e+02 3.76000000e+02 7.69826353e-01 6.00000000e+00] [2.81000000e+02 4.45000000e+02 8.87847126e-01 7.00000000e+00] [1.68000000e+02 5.42000000e+02 4.70188409e-01 8.00000000e+00] [2.98000000e+02 5.27000000e+02 4.78751719e-01 9.00000000e+00] [1.94000000e+02 1.03000000e+02 9.33498561e-01 1.00000000e+01] [2.30000000e+02 1.02000000e+02 9.27351594e-01 1.10000000e+01] [1.35000000e+02 1.22000000e+02 8.83832693e-01 1.20000000e+01]] 这个是subset: [[ 0. 1. 2. 3. 4. 5. 6. 7. 8. -1. -1. 9. -1. -1. 10. 11. 12. -1. 21.50975911 13. ]]

“Stack underflow”和“stack overflow”都是与栈(stack)数据结构相关的错误,但它们的含义和发生的情况不同:

Stack Overflow(栈溢出)

  • 定义:栈溢出发生在栈的大小超过其最大容量时。通常是由于过深的递归调用或在栈上分配了过多的局部变量导致的。
  • 后果:栈溢出通常会导致程序崩溃或异常终止,因为系统无法继续在栈上分配内存。

Stack Underflow(栈下溢出)

  • 定义:栈下溢出发生在试图从空栈中弹出元素时。例如,尝试执行“pop”操作但栈为空。
  • 后果:栈下溢出可能导致访问未定义的内存,程序可能会抛出异常或返回错误。

总结

  • 溢出(overflow):栈容量超出限制。
  • 下溢(underflow):试图从空栈中移除元素。

NULL 是一个预处理宏,通常被定义为 0((void*)0)。它在类型上是一个整数,因此可能导致类型不安全的情况。

  • nullptr 是 C++11 引入的一个关键字,表示空指针。它是一个特定的类型 std::nullptr_t,能更好地支持类型安全。

  • OpenGL 上下文:OpenGL 上下文是一个包含了所有 OpenGL 状态的信息的环境。每个窗口通常会有一个自己的上下文。

gcc -E main.cpp | tail -n 15 是什么意思

gcc -E main.cpp | tail -n 15 是一个命令行指令,具体含义如下:

  • gcc:GNU 编译器集合,用于编译 C 和 C++ 程序。
  • -E:该选项告诉 gcc 只进行预处理,即处理源代码中的宏和包含文件,但不进行编译。
  • main.cpp:要处理的源文件。
  • |:管道符,用于将前一个命令的输出传递给后一个命令。
  • tail -n 15:该命令输出前一个命令的最后 15 行。

因此,整个命令的作用是预处理 main.cpp 文件,并显示预处理后的结果的最后 15 行。这通常用于调试宏和包含的头文件。

constexpr

编译时常量

在编译时计算

结合 if constexpr 根据条件选择性编译代码

__attribute__((inline)) 是 GCC 和 Clang 编译器中的一个扩展,用于建议编译器将某个函数内联。内联函数的目的是减少函数调用的开销,通过将函数代码直接插入到调用处来提高性能。

  1. 性能优化:可以减少函数调用的开销,尤其是在小型函数中。
  2. 不强制:即使使用了 inline 属性,编译器仍然可以选择不内联,具体取决于优化策略和函数的复杂性。
  3. 适用场景:通常用于小的、频繁调用的函数。

把std::string opengl_errno_name(int err)改成static const char *opengl_errno_name(int err)的好处

std::string opengl_errno_name(int err) 改为 static const char *opengl_errno_name(int err) 的好处包括:

  1. 性能提升:使用 const char* 可以减少内存分配和拷贝操作,提高性能,尤其在频繁调用的情况下。
  2. 内存管理const char* 不需要动态分配内存,避免了内存泄漏的风险,使用起来更加安全。
  3. 简单性:直接返回字符串字面量或静态数组,使代码更简洁,减少不必要的复杂性。
  4. 更好地适应 C 风格 API:在与 C 语言库交互时,使用 const char* 更加兼容。

#include <GL/gl.h>#include <GL/glu.h> 是 OpenGL 的头文件,它们用于图形编程。具体来说:

  1. **<GL/gl.h>**:
    • 包含了 OpenGL 的核心函数和常量,提供了绘制图形所需的基本接口,比如渲染点、线、三角形等几何图形,以及设置视图、光照、纹理等功能。
  2. **<GL/glu.h>**:
    • 提供了一些辅助功能和工具,简化了 OpenGL 的使用。例如,它包含了用于生成和操作网格、处理矩阵变换、创建透视和正交投影等的函数。

#include <GLFW/glfw3.h> 是用于包含 GLFW 库的头文件,GLFW 是一个开源的跨平台库,主要用于创建窗口、处理用户输入以及管理 OpenGL 上下文。具体功能包括:

  1. 创建和管理窗口:可以创建多种类型的窗口,并设置其属性。
  2. 处理输入:支持键盘、鼠标和游戏手柄输入,方便处理用户交互。
  3. 上下文管理:简化 OpenGL 上下文的创建和管理,使得在窗口中进行图形渲染更为高效。、

#include <glm/glm.hpp>#include <glm/ext.hpp> 是用于包含 GLM(OpenGL Mathematics)库的头文件。具体功能如下:

  1. **<glm/glm.hpp>**:
    • 提供基础数学类型和操作,例如向量、矩阵、四元数等,支持高效的数学运算,适用于图形编程和物理计算。
  2. **<glm/ext.hpp>**:
    • 包含一些扩展功能,比如矩阵变换、投影、视图等常用数学函数,方便进行更复杂的数学运算。

GLM 常用于 OpenGL 应用程序中,以简化数学计算和数据管理。

❥ 基本
jk / kj / 回到普通模式
q / :wq / ZZ 保存并退出
Q 记录宏
gl / $ 移动到行末尾
gh / ^ 移动到行开头(不包括空格)
3gl / $2l 移动到行末尾倒数第 3 个字符
3gh / ^2h 移动到行开头倒数第 3 个字符
❥ 跳转
gd 跳转到定义
gD 跳转到声明
gy 跳转到变量类型的定义
gY 跳转到虚函数实现
go 头文件和源文件来回跳转
gr 寻找符号引用
gz 罗列所有相关信息(定义、引用等)
gf 打开光标下的文件名
gF 打开光标下的文件名并跳到右侧指定的行号
gx 打开光标下的网页链接
跳转回来
❥ 重构
gcc 注释/取消注释当前选中的代码/行
gn 重命名变量
gw 尝试自动修复问题
g= 自动格式化当前代码
❥ 预览
K 悬浮窗查看文档
gsf 预览函数定义
gsc 预览类定义
gsd 预览语法错误
❥ 开关
gso 打开大纲
gsg 打开 Git 面板
gsp 打开项目文件树
gss 查看所有静态语法错误
gsl 查看所有编译器报错
gsi 开关 Inlay Hint
打开/关闭终端
❥ 标签页
一键保存所有打开的文件
切换到下一个标签页
切换到上一个标签页
将当前标签页固定在最前
将当前标签页右移一位
将当前标签页左移一位
关闭当前标签页
关闭右侧所有标签页
关闭左侧所有标签页
关闭除当前标签页外所有
g 选择跳转到一个标签页
❥ 文本查找
,, 当前文件中模糊查找
,k 当前项目中正则表达式查找
,l 当前项目中的所有文件
,b 当前 Vim 已打开文件
,o 最近打开过的历史文件
,i 当前所有加入 Git 仓库的文件
,p 当前 Git 有未提交修改的文件
,c 所有 Git 提交历史
,v 所有 Git 分支
❥ 选择
vac 选中当前类
vic 选中当前类体内
vaf 选中当前函数
vif 选中当前函数体
vab 选中当前块
vib 选中当前块中内容
vai 选中当前函数调用语句
vii 选中当前函数调用语句的参数列表
vap 选中当前参数(包括逗号)
vip 选中当前参数(不包括逗号)
vin 选中当前数字
vat 选中当前注释块

  • 扩大选择

ALT+shift+左右箭头 跳转

pendulum:
    joint_state_controller:
        publish_rate: 100
        type: joint_state_controller/JointStateController
    x_controller:
        joint: base_to_plat
        type: effort_controllers/JointEffortController

其中joint_state_controller和x_controller是什么意思 这个文件的作用是什么

1. joint_state_controller

  • 用途:这个控制器用于发布机器人的关节状态(例如位置、速度和加速度)到 ROS 主题。它通常是机器人系统中的基础控制器,负责获取各个关节的状态信息并将其传递给其他组件。
  • 类型joint_state_controller/JointStateController 是一个标准的控制器类型,用于处理关节状态的更新。
  • joint_state_controller 是用于发布所有关节状态信息的控制器。它会收集机器人的所有关节(如位置、速度和加速度)的状态,并将这些信息发布到 ROS 主题上,通常是 /joint_states 主题。
  • publish_rate:表示发布关节状态的频率,这里设置为 100 Hz。

2. x_controller

  • 用途:这个控制器用于控制名为 base_to_plat 的关节的努力(力或扭矩)。通常用于执行某种运动控制任务,比如驱动一个关节以实现预期的动态行为。
  • 类型effort_controllers/JointEffortController 是一个控制器类型,专注于控制关节施加的力或扭矩。

文件的作用

这个文件主要是用于配置 ROS 控制器管理器,定义机器人各个关节的控制方式及其参数。通过这个配置,您可以在启动时自动加载和初始化这些控制器,使得机器人能够实时进行关节状态的监测和控制。

总结

  • joint_state_controller 负责关节状态的信息发布。
  • x_controller 则用于具体关节的力量控制。
  • 整个 YAML 文件用于配置和管理这些控制器,使机器人能够有效地执行控制任务。

##并发

image-20240928131042017

###0.时间 time

image-20241005183555504

###1.线程 thread

image-20241005183759412

join汇合加入,把子线程加到主线程里,这样主线程只有在子线程结束后才会退出

image-20241005185354229

当想要对线程进行封装时,会发现线程会随着封装函数执行过去而被销毁(因为thread的析构函数):

image-20241005190729501

使用detach(),还是不行(因为没用join,主线程不会等子线程):

image-20241005190842874

全局变量,生命周期会大于封装函数,join,等待子线程:
image-20241005191516568

利用析构函数简化:
image-20241005191923023

再简化,标准函数帮你把析构函数写了:

image-20241005183933864

2.异步async

异步相当于thread的帮手函数,专注于任务本身而不是底层的线程管理,不用那么底层了,使用简单了,但是能力也就下降了。

std::asyncstd::thread 都是 C++11 引入的用于处理并发和多线程编程的工具,但它们在设计目的、使用方式和抽象级别上存在一些关键的关系与区别。以下是它们之间的详细比较:

关系

  • 都属于 C++ 标准库:两者都是 C++11 提供的并发支持的一部分,旨在简化多线程编程。
  • 功能互补:尽管各自的设计有不同侧重点,但它们可以一起使用。例如,可以在 std::async 中使用 std::thread,或者在创建线程时使用 std::async 来管理结果。

区别

特性 std::thread std::async
抽象级别 更低级别的线程管理 更高层次的异步任务管理
线程控制 开发者需要手动管理线程的生命周期(启动、加入、分离) 自动管理线程的生命周期,返回 std::future
执行策略 一般立即启动新线程 可选择立即执行或延迟执行(std::launch::asyncstd::launch::deferred
结果处理 返回值需要通过共享数据或其他同步机制来获取 通过 std::future 对象直接获取结果
异常处理 异常不会传播到主线程,需要手动管理 异常会被捕获并在调用 future.get() 时重新抛出
适用场景 需要细致控制线程行为的场景,如实时系统、服务器等 简单的异步任务、并行计算、提高程序响应性

使用示例

使用 std::thread 的示例:

#include <iostream>
#include <thread>

void task() {
    std::cout << "Task is running in a separate thread.\n";
}

int main() {
    std::thread t(task);
    t.join();  // 等待线程完成
    return 0;
}

使用 std::async 的示例:

#include <iostream>
#include <future>

int task() {
    return 42;  // 返回结果
}

int main() {
    std::future<int> result = std::async(task);
    std::cout << "Result from async task: " << result.get() << '\n';  // 获取结果
    return 0;
}

总结

  • **选择使用 std::thread**:当你需要更细粒度的线程控制,或者需要实现复杂的线程交互时。
  • **选择使用 std::async**:当你希望简化异步任务的管理,并专注于任务本身而不是底层的线程管理时。

根据具体的需求和场景,开发者可以灵活选择这两者中的一种或结合使用。

image-20241005185145651

image-20241005202136786

image-20241005202235380

std::async相当于在后台开一个线程偷偷执行,如果不想用线程的话,可以用假线程:

image-20241005203007249

std::async的底层实现:(应该用不到吧)

image-20241005204852974

3.互斥量

image-20241005211544279

std::lock_guard grd(mtx); // 创建 lock_guard 对象 grd,锁定 mtx

这个有个弊端:不能提前unlock,可以用std::unique_lock:

image-20241005213525208

如果你即想使用unique_lock的自动解锁,又想手动lock:

image-20241006100018130

这个是已经上锁了,又想使用自动解锁:
image-20241006100334056

4.死锁

问题一:

image-20241005182028304

不要同时锁两个

image-20241005182958030

保证线程里上锁的顺序一样

image-20241005183050653

使用标准库里的std::lock

image-20241005183311794

同样,为了避免忘记解锁,有了一个RALL版本的std::lock
image-20241006100806745

问题二:

image-20241006101009888

std::recursive_mutex

image-20241006101432670

5.数据结构

image-20241006101750387

封装一下:

image-20241006102058522

因为mutex::lock()不是const的 ,那么使用mutable修饰一下:

image-20241006102636082

####读写锁:

image-20241006102823718

std::shared_mutex
image-20241006103549484

lock()的RAII是std::unique_lock

lock_shared()的RAII是std::shared_lock

image-20241006104139107

image-20241006105913707

6.条件变量

image-20241006110451776

image-20241006110619094

image-20241006111315559

image-20241006115747920

image-20241006120359417

image-20241006120454654

###7.原子操作(硬件层面)

前面的都是操作系统层面的

硬件解释:

image-20241006123756588

image-20241006123820764

image-20241006124016522

原子变量:

image-20241006125728044

image-20241006125817277

image-20241006130153788

image-20241006144356518

image-20241006144621864

image-20241006145302292

并行

###——TBB开启的并行编程之旅(Intel TBB并行编程框架)

###0.从并发到并行

image-20241006150631389

image-20241006150757093

image-20241006151002766

不需要手动创建线程池:

image-20241006180452099

std::thread是操作系统意义上的线程,TBB的一个任务不一定代表一个线程,把任务分配到线程上去, TBB可视为一个高效调度器

ubuntu20.04蓝牙耳机连上了,但是声音还是输出在内置扬声器上,使用 pactl load-module module-bluetooth-discover 时遇到“模块初始化失败”的错误.

  1. 检查 Bluetooth 服务
    确保 Bluetooth 服务正在运行。可以使用以下命令启动服务:

    sudo systemctl start bluetooth
    
  2. 安装必要的包
    确保已安装 PulseAudio 和 Bluetooth 支持。运行以下命令安装相关组件:

    sudo apt install pulseaudio pulseaudio-module-bluetooth pavucontrol
    
  3. 重启 PulseAudio
    有时重启 PulseAudio 可以解决问题。可以使用以下命令:

    pulseaudio -k
    pulseaudio --start
    

当然可以。根据你提供的代码,系统的状态空间方程可以表示为以下形式:
状态方程:
$$[
\begin{align*}
\dot{x}_1 &= x_2 \
\dot{x}_2 &= \frac{-b \cdot (I + m \cdot l^2)}{P} \cdot x_2 + \frac{m \cdot m \cdot g \cdot l^2}{P} \cdot x_3 \
\dot{x}_3 &= x_4 \
\dot{x}_4 &= \frac{-b \cdot m \cdot l}{P} \cdot x_2 + \frac{m \cdot g \cdot l \cdot (M + m)}{P} \cdot x_3 + \frac{1}{P} \cdot u
\end{align*}
]$$
其中,( x_1 ) 和 ( x_2 ) 可能表示倒立摆的位移和速度,而 ( x_3 ) 和 ( x_4 ) 可能表示摆角和角速度。控制输入 ( u ) 是作用在倒立摆上的力。
输入方程:
$$[
u = 0 \cdot x_1 + \frac{(I + m \cdot l^2)}{P} \cdot x_2 + 0 \cdot x_3 + \frac{m \cdot l}{P} \cdot x_4
]$$
但实际上,控制输入 ( u ) 是由控制器决定的,所以输入方程应该表示控制律,而不是状态变量直接映射到控制输入。
根据你的代码,状态空间方程的矩阵形式是:
$$[
\begin{align*}
\dot{\mathbf{x}} &= \mathbf{A} \mathbf{x} + \mathbf{B} u \
y &= \mathbf{C} \mathbf{x} + \mathbf{D} u
\end{align*}
]$$
其中,(\mathbf{x}) 是状态向量,(u) 是控制输入,(y) 是系统输出。在你的代码中,并没有明确给出输出矩阵 (\mathbf{C}) 和直接馈通矩阵 (\mathbf{D}),所以我们假设它们是:
$$[
\mathbf{C} = \begin{bmatrix}
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0
\end{bmatrix}, \quad
\mathbf{D} = \begin{bmatrix}
0 \
0
\end{bmatrix}
]$$
这意味着系统的输出是状态向量 (\mathbf{x}) 的前两个元素。
因此,状态空间方程的矩阵形式为:
$[
\mathbf{A} = \begin{bmatrix}
0 & 1 & 0 & 0 \
0 & -\frac{b \cdot (I + m \cdot l^2)}{P} & \frac{m \cdot m \cdot g \cdot l^2}{P} & 0 \
0 & 0 & 0 & 1 \
0 & -\frac{b \cdot m \cdot l}{P} & \frac{m \cdot g \cdot l \cdot (M + m)}{P} & 0
\end{bmatrix}
]$
$$[
\mathbf{B} = \begin{bmatrix}
0 \
\frac{(I + m \cdot l^2)}{P} \
0 \
\frac{m \cdot l}{P}
\end{bmatrix}
]$$
请注意,这里的 $(\mathbf{A})$ 和 $(\mathbf{B})$ 矩阵与你代码中定义的矩阵相匹配,但是根据你的系统定义,你可能需要调整 $(\mathbf{C})$ 和 $(\mathbf{D}) $矩阵以反映实际的系统输出。

image-20241006163519590

image-20241006171703693

image-20241006171811928

image-20241006181422178

image-20241006181816664

1.并行循环

并行的for循环 image-20241006194116633

image-20241006195247291

简单,但是有代价,无法被编译器优化了image-20241006195533798

这个是不需要索引的时候可以用

image-20241006195955333

二维

image-20241006200235271

三维

2,缩并与扫描

并行缩并

image-20241006201321218

image-20241006201514955

image-20241006202300112

但是,任务是动态分配到线程上,也就是range会变化,精度就会变,为了性能结果会有不同。所以:

image-20241006202538659

并行缩并的好处,相比于普通的串行缩并:

image-20241006205437392

串行相加,很大的e指数加上一个很小的float数,误差很大(浮点数不能大加小(等于没加))

3.并行扫描

image-20241006210256789

通常用于生成直方图

image-20241006211843354

image-20241006212155394

image-20241006212546708

image-20241006214913619

考试比较喜欢的考法是将这三种校正与“PID校正”校正结合起来,他们喜欢说PID校正,毕竟PD、PI、PID校正分别是超前、滞后、和滞后-超前校正的特殊情况。

$\text{最大超前角}\\varphi_m=\gamma^{\prime\prime}-\gamma+5°=45°-0°+5°=50°\a=\frac{1+\mathrm{sin}\varphi_m}{1-\mathrm{sin}\varphi_m}\approx8:,\quad10\mathrm{lg}a\approx9\mathrm{dB}$

img

img

文件扩展名 .tpp 通常表示 C++ 模板实现文件。它与 C++ 模板相关,主要用于存放模板类或函数的实现。

具体用途

  1. 模板定义分离:在 C++ 中,通常将模板的声明和实现分开。在头文件(.hpp.h)中,你可以声明一个模板,而在 .tpp 文件中实现该模板。这种做法有助于保持代码的组织性和可读性。

  2. 包含在头文件中:为了使用 .tpp 文件中的实现,通常会在相应的头文件中通过 #include 指令将其包含进来。

示例

假设你有一个简单的模板类 MyClass,可以这样组织文件:

MyClass.hpp

#ifndef MYCLASS_HPP
#define MYCLASS_HPP

template <typename T>
class MyClass {
public:
    MyClass(T value);
    void display();

private:
    T data;
};

#include "MyClass.tpp" // 包含实现文件

#endif // MYCLASS_HPP

MyClass.tpp

#include "MyClass.hpp"
#include <iostream>

template <typename T>
MyClass<T>::MyClass(T value) : data(value) {}

template <typename T>
void MyClass<T>::display() {
    std::cout << data << std::endl;
}

debug生成的代码没有经过优化

4.TBB的任务域与for循环的嵌套

image-20241011101745036

指定任务域里使用的线程

并行嵌套for循环

image-20241011102146940

但是嵌套for循环会出现死锁问题:

image-20241011102321351

为啥:(性能优化:线程里的任务做完了,会去其他线程里取任务帮忙)

image-20241011102603422

解决办法:

image-20241011103110746

image-20241011103358416

image-20241011110039932

5.任务分配

并行的时候怎样把一个任务均匀的分配到每个线程/核心(因为通常几个核心就开几个线程)呢:(线程和任务都不动)

image-20241011111101669

效果不太好,不能让核心闲着,让核心上一直有线程在运行

解决:让线程数大于核心数(让线程动起来)

image-20241011112225107

但是操作系统轮换是有开销(overhead)的,而且有可能破坏缓存一致性

解决:线程池(让任务动起来)

image-20241011114443951

TBB的工作窃取法:

image-20241011115732981

image-20241011120205530

tbb::static_partitioner的线程与任务数量一致

image-20241011120455377

image-20241011120545985

默认粒度(一个任务里的元素)是1

image-20241011120835292

image-20241011135601948image-20241011135646042

tbb::static_partitioner

  • 描述:将任务静态地分配给线程。

  • 特性

    • 在任务开始时就确定每个线程将处理哪些任务。
    • 适合于任务量相对均匀且已知的情况。
    • 不会在运行时重新平衡负载,因此可能导致某些线程空闲而其他线程忙碌。

2. tbb::simple_partitioner

  • 描述:提供一个简单的分区策略。

  • 特性

    • 任务被划分为较小的块,并且每个线程可以从待处理任务中获取一个块。
    • 相对于 static_partitionersimple_partitioner 允许更好的负载平衡。
    • 适用于任务量不均或动态变化的情况。

3. tbb::auto_partitioner

  • 描述:动态调整任务分配以优化性能。

  • 特性

    • 在运行时监控线程的工作负载,并根据需要进行任务重新分配。
    • 可以实现更好的负载均衡,特别是在任务执行时间不均匀的情况下。
    • 适用于复杂的并行任务,能自动适应系统负载。

总结

  • 静态分配static_partitioner)适用于可预测且均匀的任务;不适合动态负载。
  • 简单分配simple_partitioner)在一定程度上改进了负载平衡,但仍然保持简单的结构。
  • 自动分配auto_partitioner)最灵活,适合于动态和不均匀的工作负载,通过实时监测和调整提高整体性能。

tbb::static_partitioner对循环体不均匀的情况效果不如tbb::simple_partitioner(操作系统调度)

越来越快

image-20241011140440217

image-20241011140721127

但是auto_partitioner一定比simple_partitioner快吗

image-20241011144432532

image-20241011154029009

6.并发容器

问题:

image-20241011155237153

解决:

image-20241011155440540

image-20241011160119354

push_back()返回的是一个迭代器

用*获取迭代器指向的元素的引用,再用and(&)获取这个元素的指针

image-20241011160927535

tbb::concurrent_vector还是一个多线程安全的容器

image-20241011161401578

访问:随机访问效率不高

image-20241011162020029

推荐顺序访问:

image-20241011162546845

image-20241011164325073

image-20241011164827207

这些STL容器前加上concurrent就变成了多线程安全版

vector/concurrent_vector有一个常见的用法:用于并行筛选数据:

7.并行筛选

image-20241021101434094

image-20241021101859492

image-20241021102554406

image-20241021103037177

但需要连续数据时,还是需要std::vetor

image-20241021103348500

image-20241021104040889

image-20241021105118738

8.分治与排序

image-20241021111447378

反而变慢了:

image-20241021111303257

image-20241021111344357

分治

image-20241021111634419

image-20241021111951889

image-20241021112626978

9.流水线并行

CUDA开启的GPU编程

image-20241021114316913

image-20241021114756000

类对象的声明

ThreadPool threadPool {};ThreadPool threadPool; 的主要区别在于初始化方式:

1. ThreadPool threadPool {};

  • 列表初始化:使用了列表初始化(uniform initialization),这是 C++11 引入的一种语法。
  • 安全性:这种方式可以防止窄化转换(例如,浮点数到整数的转换),因此更安全。
  • 调用构造函数:会调用 ThreadPool 类的默认构造函数。

2. ThreadPool threadPool;

  • 默认构造:这是经典的对象定义语法,直接调用默认构造函数。
  • 行为:如果 ThreadPool 类没有定义任何构造函数,编译器会自动生成一个默认构造函数。
  • 窄化问题:没有列表初始化的安全性,如果初始化涉及类型转换,可能会导致窄化。

总结

  • 功能上:两者都用于创建 ThreadPool 对象并调用默认构造函数。
  • 安全性ThreadPool threadPool {}; 更安全,适用于需要避免潜在类型转换问题的场景。

不存在这样的写法:ThreadPool threadPool ();

加括号是错的,加花括号是安全的,推荐花括号

变量的声明

std::atomic_flag flag;std::atomic_flag flag {}; 的效果是相同的,都会将 flag 初始化为未设置状态。不过,使用 {} 的形式更加显式,可能更符合现代C++的最佳实践。

new SimpleTask()new SimpleTask 在功能上是等价的,都是创建一个 SimpleTask 对象并返回指向该对象的指针。

非常量左值引用问题

常量引用(const T&)可以绑定到临时对象,而非常量左值引用(T&)则不能。

glm::vec3 setPixel(size_t x,size_t y,glm::vec3 &pixel){
        return pixels[width*y+x]=pixel;
    }
film.setPixel(y,x,glm::vec3(0.5,0.4,0.3));

Non-const lvalue reference to type 'vec<...>' cannot bind to a temporary of type 'vec<...>'

或者

film.setPixel(y,x,{0.5,0.4,0.3});

Non-const lvalue reference to type 'glm::vec3' (aka 'vec<3, float, defaultp>') cannot bind to an initializer list temporary

改为:

    glm::vec3 setPixel(size_t x,size_t y,const glm::vec3 &pixel){
        return pixels[width*y+x]=pixel;
    }

``

Qt

QWidgetQMainWindow 是 Qt 框架中的两个重要类,它们都用于创建图形用户界面(GUI),但有一些关键的区别:

QWidget

  • 基础类: QWidget 是 Qt 中所有用户界面对象的基类。它提供了一个基础的窗口部件,其他窗口部件(如按钮、文本框)都是从 QWidget 继承而来的。
  • 功能: QWidget 本身是一个通用的窗口部件,没有特别的窗口管理功能。它可以作为窗口的基础组件,也可以作为其他复杂组件的容器。
  • 布局管理: QWidget 提供了布局管理功能,可以使用布局管理器来控制其子部件的位置和大小。
  • 使用场景: 你可以将 QWidget 用作对话框、工具条、或是任何其他需要的窗口部件。如果你只需要一个简单的窗口,QWidget 是一个合适的选择。

QMainWindow

  • 派生类: QMainWindowQWidget 的子类,提供了更丰富的窗口功能和特性。
  • 功能: QMainWindow 是设计用于主窗口的类,它提供了菜单栏、工具栏、状态栏和中央窗口区域的支持。这使得它特别适合用于主应用窗口的设计。
  • 布局管理: QMainWindow 提供了特定的布局区域,如菜单栏、工具栏、状态栏和中央部件区域。你可以使用这些功能来创建更复杂的应用程序界面。
  • 使用场景: 当你需要一个具有菜单栏、工具栏和状态栏的主窗口时,QMainWindow 是一个理想的选择。它适合用于具有复杂界面的桌面应用程序。

主要区别总结

  1. 功能扩展:
    • QWidget: 基础窗口部件,功能较少,适合用于创建简单的窗口或部件。
    • QMainWindow: 提供额外的功能,如菜单栏、工具栏和状态栏,适合用于主应用窗口。
  2. 使用场景:
    • QWidget: 适合用作对话框、工具条、或简单的窗口部件。
    • QMainWindow: 适合用于需要复杂用户界面的主窗口。
  3. 布局支持:
    • QWidget: 你需要手动设置布局。
    • QMainWindow: 提供了内置的菜单栏、工具栏、状态栏和中央部件区域,可以直接使用这些功能来设计主窗口界面。

connect(menu, &QMenu::triggered, this, &Widget::onMenuTriggered); 为什么QMenu* menu;时不报错 当QMenu menu;时报错:No matching member function for call to ‘connect’

在 Qt 中,connect 函数的作用是将一个信号与一个槽函数连接起来。它依赖于信号发射的对象和槽函数的对象都是有效的,并且能够正确识别和匹配。

使用 QMenu* menu

cpp
QMenu* menu = new QMenu();
connect(menu, &QMenu::triggered, this, &Widget::onMenuTriggered);
  • 这里,menu 是一个指向 QMenu 对象的指针。
  • connect 函数可以使用 menu 指针来连接信号和槽,因为 QMenu 对象在堆上分配,并且其生命周期由指针管理。
  • QMenu 的实例通过指针能够正确地传递给 connect,并且 QMenu 的成员函数和信号可以被正确识别。

使用 QMenu menu

cpp
QMenu menu;
connect(menu, &QMenu::triggered, this, &Widget::onMenuTriggered);
  • 这里,menu 是一个栈上的 QMenu 对象。
  • 栈上的对象在 connect 时会导致问题,因为 connect 期望信号发射对象在其生命周期内有效。栈上的对象会在超出作用域时被销毁。
  • 在这个情况下,menu 可能在连接信号和槽时已经过早销毁,导致 connect 函数找不到有效的信号源。

总结

  • QMenu* menu:指针允许动态管理对象的生命周期,connect 可以正常工作。
  • QMenu menu:栈上的对象在超出作用域时可能被销毁,导致 connect 函数不能正确地处理信号和槽。

因此,使用指针确保 QMenu 对象在 connect 调用期间有效。

image-20240823104744847

image-20240823104804653

定义对象的指针,让widght来管理对象的生命周期,要是直接定义对象,可能不知道什么时候对象就被销毁了,有些用到这些对象的函数就可能报错,因为在栈上找不到他了

risc_v

image-20240618123232143

在RISC-V架构中,IF_ID和ID_EX是两个流水线寄存器,用于在指令执行过程中传递数据。

  1. IF_ID(Instruction Fetch to Instruction Decode):IF_ID流水线寄存器用于在指令提取阶段(Instruction Fetch)和指令解码阶段(Instruction Decode)之间传递数据。它保存了从指令缓存中提取的指令,并将其传递给下一个阶段进行解码。
  2. ID_EX(Instruction Decode to Execute):ID_EX流水线寄存器用于在指令解码阶段(Instruction Decode)和指令执行阶段(Execute)之间传递数据。它保存了从IF_ID寄存器中解码得到的指令信息,包括操作码、寄存器地址等,并将这些信息传递给下一个阶段进行执行。

通过使用这些流水线寄存器,RISC-V架构可以实现指令流水线的并行执行,提高指令的执行效率。

  1. IF (Instruction Fetch) 取指
    • 这一阶段的主要任务是从内存中的指令缓存或主存中取回当前要执行的指令。
    • 在这个阶段,程序计数器(PC,Program Counter)会指向当前要取的指令地址。
    • CPU将该地址发给指令缓存,读取该地址处的指令,并将其存储到流水线寄存器(如IF/ID寄存器)中,以便在下一阶段使用。
  2. ID (Instruction Decode) 译码
    • 这一阶段的主要任务是对取回的指令进行解码,即解析指令的操作码和操作数。
    • 具体来说,CPU会读取并识别指令的操作码(Opcode),确定这条指令的类型和需要执行的操作。
    • 同时,CPU还会确定指令所涉及的源操作数和目标寄存器。如果需要从寄存器文件中读取操作数,这一阶段也会执行这些操作。
    • 解码后的信息会存储在流水线寄存器(如ID/EX寄存器)中,以便在后续的执行阶段使用。

raytracing

在 C++ 中,冒号(:)用于初始化类的成员变量或调用父类的构造函数。这种语法称为成员初始化列表(member initialization list),它允许在构造函数体执行之前对成员变量进行初始化。

在这里,vec3() : e{0,0,0} {} 中的冒号后面就是成员初始化列表。: e{0,0,0} 表示对类的成员变量 e 进行初始化,其中 {0,0,0} 是对数组 e 的初始化值。

txt
double& operator[](int i) { return e[i]; }

double&:

  • 返回类型是 double&,即返回一个 double 类型的左值引用。
  • 左值引用允许函数返回一个可修改的元素,这样调用者可以直接修改这个元素。

左值和右值的定义

  • 左值(lvalue): 可以取地址的值,通常表示内存中的一个位置。例如,变量、数组元素、对象成员等都是左值。
  • 右值(rvalue): 不存在明确地址的临时值,通常是表达式的结果或者字面量。例如,字面量、临时对象、运算结果等。

引用和原变量本质上是同一个东西,对引用的修改就是对原变量的修改

double& 表示引用

inline 关键字在C++中用于建议编译器将某个函数的代码在每次调用时直接插入到调用处,而不是进行常规的函数调用。从而可以减少函数调用的开销,尤其是当函数体非常小、调用频繁时,这种优化可能会带来性能提升。

using color = vec3; 这行代码是一个类型别名(type alias)的定义,将 vec3 类型重命名为 color 类型。也就是说,使用 color 关键字可以代替 vec3 类型的使用。

FOC

可以看出,我们只需要像步进电机那样不断的重复这六部换向就可以让BLDC转动起来,甚至会产生一种错觉,是不是我们换向越快电机转的越快呢?答案是:否,这里我们一定要认识到,是当转子处于特定位置时才去触发换向操作,换向是被动换向,想要提高转速一定是要提高电流,让定子产生的磁场更强,让转子更快的达到目标点然后触发换向

如何获得转子角度?
我们已经知道了要先检测角度再去换向,那么如何检测当前角度呢?,有以下三种方式。
1.通过安装编码器来计算出当前角度。
2.通过安装霍尔元件计算当前角度。
3.通过检测电流来计算当前角度

编码器方式获取电机当前角度
编码器方式分为两种,增量式编码器和绝对式编码器。
增量式编码器:
每次启动之气都需要做一次校准,而且为了防止单片机性能问题导致脉冲丢失,还需要对编码器每圈校准一次。因此经常使用ABZ三轴编码器,AB输出正交信号,Z轴输出中断。
绝对式编码器:
只需要在出厂之前做一次校准,之后如果没有拆机便不需要校准,通讯方式一般是SPI和IIC,需要考虑通讯时间对系统的影响。
为什么要对编码器进行校准?
因为我们无法保证在安装的时候让编码器的0°(机械角度)刚好对应电机绕组的0°(电气角度)

img

伸开左手,使拇指与其他四指垂直且在一个平面内,让磁感线从手心流入,四指指向电流方向,大拇指指向的就是安培力方向(即导体受力方向)

img

右手平展,使大拇指与其余四指垂直,并且都跟手掌在一个平面内。把右手放入磁场中,让磁感线从掌心进入(当磁感线为直线时,相当于手心面向N极),大拇指指向导线运动方向,则四指所指方向为导线中感应电流(动生电动势)的方向。

image-20240529094507089

根据想得到的电流矢量到u1,u2,u3上投影的正负,来判断在哪个扇区里,u1,u2,u3可由u_alpha,u_beta表示出

image-20240529130329149

image-20240529130513189

image-20240529144317410

image-20240529144120858

image-20240529144220989

image-20240530115230681

从定子来计算

image-20240530115639643可以计算出反电动势,进而计算转子的速度和位置(无感)

当变压器的初级绕组通电后,线圈所产生的磁通在铁心流动,因为铁心本身也是导体(由硅钢片制成),在垂直于磁力线的平面上就会感应电势,这个电势在铁心的断面上形成闭合回路并产生电流,好象一个旋涡所以称为“涡流”。这个“涡流”使变压器的损耗增加,并且使变压器的铁心发热变压器的温升增加。由“涡流”所产生的损耗我们称为“铁损”。
另外要绕制变压器需要用大量的铜线,这些铜导线存在着电阻,电流流过时这电阻会消耗一定的功率,这部分损耗往往变成热量而消耗,我们称这种损耗为“铜损”。
铁损等于铜损时,变压器效率最高。大概就是变压器额定负荷的0.65倍左右。

从绕组来计算(d,q,轴的电压方程)

image-20240530130008389

由于定子自感的属性,电流会滞后电压90度

image-20240530180512850

image-20240530180534254

要等幅变换,所以要乘(2/3)

如果遇到乘(根号下2/3),是等功率变换

image-20240530181152049

image-20240530193807755

image-20240530193832651

反帕克变换就是对帕克变换旋转矩阵求逆

MOS管是电压驱动型,三极管是电流驱动型

image-20240531080240566

image-20240531102816686

电角度=极对数(或者级数/2)*机械角度

image-20240531110753146

OpenGL

image-20240517165248939

image-20240517165400128

https://www.cnblogs.com/jiujiubashiyi/p/16429717.html

GLFW,GLAD,opengl是什么,有什么联系

GLFW、GLAD和OpenGL是计算机图形学中常用的三个库,它们之间存在着紧密的联系:

  1. OpenGL:是一个跨语言、跨平台的编程接口,用于渲染2D、3D向量图形。它是由硅谷图形公司(Silicon Graphics, SGI)在1992年开发的。OpenGL是图形硬件制造商的标准,也是创作高质量计算机图形的基本工具。OpenGL提供了一个非常灵活的编程接口,让开发者能够利用它来渲染图形。
  2. GLFW:是一个跨平台的OpenGL应用程序接口(API)的多线程窗口和输入管理器。简单来说,GLFW用来创建窗口、处理输入事件(如键盘、鼠标点击等),并管理OpenGL上下文。它使得开发者可以比较容易地创建一个OpenGL环境,因为它简化了OpenGL程序中许多繁琐的设置步骤。
  3. GLAD:是一个自动生成OpenGL函数指针的库。在OpenGL中,许多操作需要通过指针来调用函数,而在不同的操作系统和硬件平台上,这些函数指针的位置可能会有所不同。GLAD就是用来处理这些函数指针的,它会根据当前的平台和OpenGL的版本自动生成对应的函数指针。这为开发者减少了处理这些底层细节的麻烦。

它们之间的联系

  • 使用OpenGL之前,需要创建一个OpenGL环境,这个环境包括一个窗口以及一个上下文,这是通过GLFW来完成的。
  • GLAD用来确保所有的OpenGL函数调用都能够正确地指向相应的函数,这样开发者就不需要手动查找和设置这些函数指针了。
  • 通常,一个OpenGL程序的设置流程是这样的:首先初始化GLFW,然后使用GLFW创建一个窗口和OpenGL上下文,接着使用GLAD自动加载OpenGL函数,最后就可以开始使用OpenGL进行绘图了。

综上,GLFW和GLAD都是帮助开发者更简单、更有效地使用OpenGL的辅助工具。通过它们,开发者可以专注于图形内容的创作,而不必担心底层的细节问题。

glfwMakeContextCurrent(window);是什么意思

glfwMakeContextCurrent(window); 是一行来自 GLFW(OpenGL Framework)库的代码。GLFW 是一个跨平台的库,用于窗口和输入处理,它使得创建 OpenGL 应用程序变得更加容易。

这句代码的作用是将 OpenGL 渲染上下文关联到由 window 参数指定的窗口。在 OpenGL 中,渲染上下文是用来进行图形绘制的环境,它定义了一系列可以用来配置和控制渲染行为的设置。

在创建窗口之后,必须调用 glfwMakeContextCurrent 函数来指定哪个窗口的上下文将被当前的线程使用。只有当前上下文中的 OpenGL 调用才会对指定的窗口产生影响。如果没有激活任何上下文,任何 OpenGL 调用都会导致错误。

简单来说,当你想要在特定的窗口上绘制图形时,你需要确保该窗口的 OpenGL 上下文被设置为当前上下文。这就是 glfwMakeContextCurrent(window); 这行代码的目的。

gladLoadGLLoader((GLADloadproc)glfwGetProcAddress) 是什么意思

gladLoadGLLoader 是一个函数,通常在 C 或 C++ 程序中使用,用于初始化 OpenGL 函数指针。OpenGL 是一个用于渲染2D和3D矢量图形的跨语言、跨平台的应用程序编程接口(API)。gladLoadGLLoader 函数是 GLAD 库的一部分,GLAD 是一个小型且易于使用的库,它负责在每次调用 OpenGL 函数之前,动态地加载和绑定正确的 OpenGL 函数指针。

glfwGetProcAddress 是另一个函数,属于 GLFW 库(一个用于创建窗口、输入处理等的前端库,常与OpenGL一起使用)。glfwGetProcAddress 的作用是获取指向特定OpenGL函数的指针,该函数在OpenGL核心或者扩展中定义。

gladLoadGLLoader((GLADloadproc)glfwGetProcAddress)

这表示在初始化GLAD库时,它将使用GLFW库提供的函数指针来加载OpenGL函数。这允许应用程序使用OpenGL函数,而不需要关心底层的具体实现细节。

这种机制的好处是,应用程序只需要链接到一个库(比如GLFW),而GLFW会负责查找和加载正确的OpenGL函数。这样做可以简化应用程序的编写和维护工作,同时也确保了应用程序可以轻松地与不同平台的OpenGL版本兼容。

双缓冲(Double Buffer)

应用程序使用单缓冲绘图时可能会存在图像闪烁的问题。 这是因为生成的图像不是一下子被绘制出来的,而是按照从左到右,由上而下逐像素地绘制而成的。最终图像不是在瞬间显示给用户,而是通过一步一步生成的,这会导致渲染的结果很不真实。为了规避这些问题,我们应用双缓冲渲染窗口应用程序。缓冲保存着最终输出的图像,它会在屏幕上显示;而所有的的渲染指令都会在缓冲上绘制。当所有的渲染指令执行完毕后,我们交换(Swap)前缓冲和后缓冲,这样图像就立即呈显出来,之前提到的不真实感就消除了。

  • 顶点数组对象:Vertex Array Object,VAO
  • 顶点缓冲对象:Vertex Buffer Object,VBO
  • 元素缓冲对象:Element Buffer Object,EBO 或 索引缓冲对象 Index Buffer Object,IBO

在OpenGL中,任何事物都在3D空间中,而屏幕和窗口却是2D像素数组,这导致OpenGL的大部分工作都是关于把3D坐标转变为适应你屏幕的2D像素.3D坐标转为2D坐标的处理过程是由OpenGL的图形渲染管线(Graphics Pipeline,大多译为管线,实际上指的是一堆原始图形数据途经一个输送管道,期间经过各种变化处理最终出现在屏幕的过程)管理的。图形渲染管线可以被划分为两个主要部分:第一部分把你的3D坐标转换为2D坐标,第二部分是把2D坐标转变为实际的有颜色的像素。(图形渲染管线接受一组3D坐标,然后把它们转变为你屏幕上的有色2D像素输出)

图形渲染管线可以被划分为几个阶段,每个阶段将会把前一个阶段的输出作为输入。所有这些阶段都是高度专门化的(它们都有一个特定的函数),并且很容易并行执行。正是由于它们具有并行执行的特性,当今大多数显卡都有成千上万的小处理核心,它们在GPU上为每一个(渲染管线)阶段运行各自的小程序,从而在图形渲染管线中快速处理你的数据。这些小程序叫做着色器(Shader)。

OpenGL着色器是用OpenGL着色器语言(OpenGL Shading Language, GLSL)写成的

img

为了让OpenGL知道我们的坐标和颜色值构成的到底是什么,OpenGL需要你去指定这些数据所表示的渲染类型。我们是希望把这些数据渲染成一系列的点?一系列的三角形?还是仅仅是一个长长的线?做出的这些提示叫做**图元(Primitive)**,任何一个绘制指令的调用都将把图元传递给OpenGL。这是其中的几个:GL_POINTS、GL_TRIANGLES、GL_LINE_STRIP。

图形渲染管线的第一个部分—-顶点着色器

把3D坐标转为另一种3D坐标

几何着色器

一组顶点作为输入,这些顶点形成图元,并且能够通过发出新的顶点来形成新的(或其他)图元来生成其他形状

图元装配

将顶点着色器(或几何着色器)输出的所有顶点作为输入(如果是GL_POINTS,那么就是一个顶点),并将所有的点装配成指定图元的形状

光栅化阶段

把图元映射为最终屏幕上相应的像素,生成供片段着色器(Fragment Shader)使用的**片段(Fragment)**。在片段着色器运行之前会执行裁切(Clipping)。裁切会丢弃超出你的视图以外的所有像素,用来提升执行效率。

OpenGL中的一个片段是OpenGL渲染一个像素所需的所有数据

片段着色器

片段着色器的主要目的是计算一个像素的最终颜色

Alpha测试和混合(Blending)阶段

这个阶段检测片段的对应的深度(和模板(Stencil))值(后面会讲),用它们来判断这个像素是其它物体的前面还是后面,决定是否应该丢弃。这个阶段也会检查alpha值(alpha值定义了一个物体的透明度)并对物体进行混合(Blend)。所以,即使在片段着色器中计算出来了一个像素输出的颜色,在渲染多个三角形的时候最后的像素颜色也可能完全不同

GL_ARRAY_BUFFER目标用于表示顶点属性数据的缓冲区对象

在OpenGL中,VAO(Vertex Array Object)和VBO(Vertex Buffer Object)是用于管理顶点数据的重要概念,并且它们之间存在一定的关系。

  1. VAO(Vertex Array Object):
    • VAO是OpenGL中用于存储顶点属性状态的对象。它包含了多个指向VBO的指针,用于指定顶点属性数据的格式、排列方式等。
    • VAO可以看作是对VBO的管理器,它记录了OpenGL如何解释顶点数据,包括顶点的位置、颜色、法线等信息。通过绑定VAO,可以轻松地切换顶点属性的设置,从而简化渲染流程。
  2. VBO(Vertex Buffer Object):
    • VBO是用于存储顶点数据的缓冲区对象。它可以存储顶点的位置、颜色、纹理坐标等信息。
    • 通过将顶点数据存储在VBO中,可以有效地管理和传输大量的顶点数据,而不必反复传输到GPU。

关系:

  • VBO存储了实际的顶点数据,例如顶点的位置、颜色、纹理坐标等。
  • VAO描述了顶点数据的格式和布局,它指明了如何从VBO中读取顶点数据以供渲染使用。
  • 通常情况下,我们先创建和绑定VAO,然后配置相应的VBO,并将VBO与VAO关联。这样,在渲染时只需绑定相应的VAO即可,OpenGL就会根据VAO中的配置自动获取正确的顶点数据进行渲染。

总结来说,VAO用于管理顶点属性状态,而VBO用于存储实际的顶点数据。它们共同协作,使得在OpenGL中管理和使用顶点数据变得更加灵活和高效。

我们可以绘制两个三角形来组成一个矩形(OpenGL主要处理三角形)

着色器(Shader)是运行在GPU上的小程序。这些小程序为图形渲染管线的某个特定部分而运行。从基本意义上来说,着色器只是一种把输入转化为输出的程序。着色器也是一种非常独立的程序,因为它们之间不能相互通信;它们之间唯一的沟通只有通过输入和输出。

Uniform是另一种从我们的应用程序在 CPU 上传递数据到 GPU 上的着色器的方式,但uniform和顶点属性有些不同。首先,uniform是全局的(Global)。全局意味着uniform变量必须在每个着色器程序对象中都是独一无二的,而且它可以被着色器程序的任意着色器在任意阶段访问。第二,无论你把uniform值设置成什么,uniform会一直保存它们的数据,直到它们被重置或更新。

在OpenGL中,VBO(Vertex Buffer Object)和VAO(Vertex Array Object)都是用于管理顶点数据的对象。它们之间的联系和区别如下:

联系:

  • VBO和VAO都是用于管理顶点属性数据的对象。
  • 它们都可以通过OpenGL API进行创建、绑定、更新和删除等操作。
  • VAO可以保存多个VBO的绑定状态,使得我们在绘制时只需绑定VAO即可同时启用多个顶点属性数组。

区别:

  • VBO是用于存储和管理顶点数据的缓冲对象,包括顶点位置、法线、颜色、纹理坐标等属性数据。它能够提高渲染效率,因为可以将这些数据上传到显卡内存中,而不需要每次绘制时都从系统内存中获取。
  • VAO是用于管理VBO的绑定状态的对象,它记录了VBO的绑定状态以及每个属性在VBO中的偏移量、类型等信息。VAO可以看作是一组VBO的绑定描述符,它规定了如何从VBO中获取顶点属性数据。

总体来说,VBO和VAO在OpenGL中都扮演着非常重要的角色,它们都可以提高渲染效率,使得开发者可以更加方便地管理和操作顶点属性数据。其中,VBO主要用于存储和管理顶点数据,而VAO则是用于在绘制时快速激活和绑定多个顶点属性数组。

把两个角度都发送

试一下发后两个数据,看看是不是数据的问题

试试发5个

image-202406031552098552024.6.3.15.52Matlab报错,遂改,无用!!!!

艺术家和程序员更喜欢使用纹理(Texture)。纹理是一个2D图片(甚至也有1D和3D的纹理),它可以用来添加物体的细节.这样就可以让物体非常精细而不用指定额外的顶点

为了能够把纹理映射(Map)到三角形上,我们需要指定三角形的每个顶点各自对应纹理的哪个部分。这样每个顶点就会关联着一个纹理坐标(Texture Coordinate),用来标明该从纹理图像的哪个部分采样(译注:采集片段颜色)。之后在图形的其它片段上进行片段插值(Fragment Interpolation)。

使用 Xlib 来获取窗口大小需要一些底层的操作,但可以通过以下步骤来实现:

首先,你需要安装 python-xlib 库。你可以使用以下命令在 Ubuntu 上安装:

sudo apt-get install python-xlib

然后,你可以使用下面的代码来获取当前活动窗口的大小:

from Xlib import display

def get_screen_size():
    disp = display.Display()
    screen = disp.screen()
    root_win = screen.root
    windowID = root_win.get_full_property(disp.intern_atom('_NET_ACTIVE_WINDOW'), 0).value[0]
    window = disp.create_resource_object('window', windowID)
    geometry = window.get_geometry()
    return geometry.width, geometry.height

width, height = get_screen_size()
print("Window size: {} x {}".format(width, height))

这段代码中,我们首先创建了一个 Display 对象,然后获取了当前活动窗口的 ID。接着,我们使用这个窗口 ID 创建了一个 window 对象,并通过这个对象的 get_geometry 方法获取了窗口的宽度和高度。

请注意,使用 Xlib 需要对 X 窗口系统有一定的了解,因为它是一个底层的库,直接和 X 服务器进行交互。希望这个示例能够帮助你开始使用 Xlib 来获取窗口大小。

  • layout(location=0): 这是一个着色器布局限定符(layout qualifier),用于指定顶点属性在输入阶段的位置。在这里,location=0 表示顶点属性的位置索引为 0。这个位置索引将与顶点数组对象(VAO)中的对应属性绑定,以确保正确地将顶点数据传递给顶点着色器。
  • in: 这是一个输入变量修饰符,用于指示这个变量是从外部传递给顶点着色器的。
  • vec3: 这是指定变量类型的关键字,表示这个变量是一个三维向量。
  • in_position: 这是变量的名称,用于在顶点着色器中引用这个输入变量。在这里,in_position 可能表示顶点的位置信息。

在OpenGL中,gl_Position是一个内置的变量,用于表示顶点着色器(Vertex Shader)输出的顶点位置。它是一个四维向量(vec4),表示顶点的齐次坐标(Homogeneous Coordinates),通常用于表示三维空间中的点。齐次坐标是四维的,其中前三个分量表示点的位置,而第四个分量通常被用于表示点的类型或者进行透视除法(Perspective Division)。在顶点着色器中,对 gl_Position 的设置将影响后续的图元装配(Primitive Assembly)和光栅化(Rasterization)阶段,最终确定绘制的像素位置。因此,正确设置 gl_Position 是绘制正确图形的关键。

[[ 0.5 0.5 0. 0. 1. 0. ]
[-0.5 0.5 0. 1. 0. 0. ]
[-0.5 -0.5 0. 0. 0. 1. ]
[ 0.5 0.5 0. 0. 1. 0. ]
[-0.5 -0.5 0. 0. 0. 1. ]
[ 0.5 -0.5 0. 1. 0. 0. ]]

layout(location=0) in vec3 in_position;
layout(location=1) in vec3 in_color;
self.vbo_format = '3f 3f'
self.attrs = ('in_position', 'in_color')
vertex_data = np.hstack([vertices_array, colors_array])

缩放

image-20240608192337289

位移

image-20240608192358635

大多数旋转函数需要用弧度制的角,但幸运的是角度制的角也可以很容易地转化为弧度制的:

  • 弧度转角度:角度 = 弧度 * (180.0f / PI)
  • 角度转弧度:弧度 = 角度 * (PI / 180.0f)

image-20240608192525938

我这一辈子,抠抠搜搜的花了很多钱,精精明明的上了很多当。骂骂咧咧的干了很多活,小心翼翼的闯了很多祸。精打细算的欠了一屁股帐。认认真真的范了很多错。掏心掏肺的结了很多仇。不明不白的吃了很多亏。窝窝囊囊的活了几十年。

  1. glm::mat4 trans;:首先声明了一个4x4的矩阵trans,用于表示变换矩阵。
  2. trans = glm::rotate(trans, glm::radians(90.0f), glm::vec3(0.0, 0.0, 1.0));:这一行代码对trans进行了旋转变换。使用了glm库中的rotate函数,将trans矩阵绕Z轴旋转90度(使用radians函数将角度转换为弧度),并将结果赋值给trans本身。
  3. trans = glm::scale(trans, glm::vec3(0.5, 0.5, 0.5));:接着对trans进行了缩放变换。使用了glm库中的scale函数,将trans矩阵沿着X、Y、Z三个轴分别缩放0.5倍,并将结果再次赋值给trans本身。
  • 局部空间(Local Space,或者称为物体空间(Object Space))
  • 世界空间(World Space)
  • 观察空间(View Space,或者称为视觉空间(Eye Space))
  • 裁剪空间(Clip Space)
  • 屏幕空间(Screen Space)

为了将坐标从一个坐标系变换到另一个坐标系,我们需要用到几个变换矩阵,最重要的几个分别是模型(Model)、观察(View)、投影(Projection)三个矩阵。我们的顶点坐标起始于局部空间(Local Space),在这里它称为局部坐标(Local Coordinate),它在之后会变为世界坐标(World Coordinate),观察坐标(View Coordinate),裁剪坐标(Clip Coordinate),并最后以屏幕

坐标(Screen Coordinate)的形式结束。下面的这张图展示了整个流程以及各个变换过程做了什么:

coordinate_systems

  1. 局部坐标是对象相对于局部原点的坐标,也是物体起始的坐标。
  2. 下一步是将局部坐标变换为世界空间坐标,世界空间坐标是处于一个更大的空间范围的。这些坐标相对于世界的全局原点,它们会和其它物体一起相对于世界的原点进行摆放。
  3. 接下来我们将世界坐标变换为观察空间坐标,使得每个坐标都是从摄像机或者说观察者的角度进行观察的。
  4. 坐标到达观察空间之后,我们需要将其投影到裁剪坐标。裁剪坐标会被处理至-1.0到1.0的范围内,并判断哪些顶点将会出现在屏幕上。
  5. 最后,我们将裁剪坐标变换为屏幕坐标,我们将使用一个叫做视口变换(Viewport Transform)的过程。视口变换将位于-1.0到1.0范围的坐标变换到由glViewport函数所定义的坐标范围内。最后变换出来的坐标将会送到光栅器,将其转化为片段。

你可能已经大致了解了每个坐标空间的作用。我们之所以将顶点变换到各个不同的空间的原因是有些操作在特定的坐标系统中才有意义且更方便。例如,当需要对物体进行修改的时候,在局部空间中来操作会更说得通;如果要对一个物体做出一个相对于其它物体位置的操作时,在世界坐标系中来做这个才更说得通,等等。如果我们愿意,我们也可以定义一个直接从局部空间变换到裁剪空间的变换矩阵,但那样会失去很多灵活性。

局部空间——–模型矩阵——–世界空间———观察矩阵———-观察空间(摄像机空间)———–投影矩阵————–裁剪空间————–视口变换————-屏幕空间

image-20240609164419389

image-20240609164929887

image-20240609165058873

image-20240609211854570

image-20240609212927721

image-20240609213514370

glm::LookAt函数需要一个位置、目标和上向量。它会创建一个观察矩阵。

为了改变摄像机方向

image-20240609221012736

self.m_projection=glm.perspective(V_FOV,ASPECT_RATIO,NEARPLANE,FARPLANE)

使用 GLM 库中的 glm::perspective() 函数创建了一个投影矩阵(projection matrix).会根据给定的参数创建一个透视投影矩阵,并返回这个矩阵。这个投影矩阵描述了从摄像机位置观察场景时的投影效果,将三维场景转换为二维屏幕空间

image-20240610000155256

对连续时间正弦信号考虑下面表示式:
x ( t ) = s i n ( 2 π f 0 t + φ )
可以按抽样频率 fs=1/Ts对 x(t)抽样来获得离散时间信号
x [ n ] = x ( t )|t =nTs = x ( t ) |t=n / fs = s i n ( 2 πf0 /fsn + φ ),
f0 =500Hz, fs 取 100Hz, 绘出 x[n]及其 DTFT

image-20240611133720092

image-20240611133805550

image-20240611133838091

image-20240611140046801

以 5000HZ 和 1000HZ 分别对其采样得到 x1(n), x2(n);画出它们的 DTFT 并比较

image-20240611140651535

image-20240611141635271

我们可以从第一个方程中直接得到 A 和 φ 的关系:

image-20240611141659727

φ !=π/2+kπ

x(t)=2cos(π/3 *t)

image-20240611143342649

image-20240611143614094

image-20240611144943071

image-20240611145404898

现实中无法实现理想低通滤波器。然而,可以按下面的方法计算由理想低通滤波器产生的
波形:理想低通运算相当于信号频谱与频域的矩形函数相乘,这对应于信号与通过傅里叶逆变
换得到的时域 sinc 函数的卷积。当其应用于点样本时,卷积和为 sinc 函数内插:

xa(t)=sum_{n=-无穷}^{正无穷} [xa(nt) sin(π(t-nTs)/Ts)/(π(t-nTs)/Ts)]

(3.18)
其中,样本 xa(nt)取自 t= nTs处。
a. 假设只有有限数量的信号样本是非零值,且只需在有限时间区间上进行信号重建,写出
基于(3.18)式的 sinc 内插表示式。

syms t n Ts xa;

xa_t = symsum(xa * sin(pi*(t-n*Ts)/Ts)/(pi*(t-n*Ts)/Ts), n, -inf, inf);

image-20240611153315884

C:
image-20240611155005492

根据奈奎斯特采样定理,要求 fs≥2fbfs≥2fb 以避免混叠现象。因此,fb<fs2fb<2fs 是满足采样定理的条件。

image-20240613162635475

45HZ,基本周期 T是 1/45

image-20240613160828062

结果分析与总结

  1. 分析长度 ( 0.5T_p = 0.1 ) 秒:
    • 频谱图中的频率分辨率较低,频率成分不清晰,可能会导致频率混淆。
    • 由于分析长度小于一个周期,频谱分析结果可能包含较多的谐波失真和旁瓣效应。
  2. 分析长度 ( 1.5T_p = 0.3 ) 秒:
    • 频谱图中的频率分辨率有所提高,主要频率成分变得更加明显。
    • 由于分析长度超过一个周期,频谱分析结果更加准确,频率成分容易识别。
  3. 分析长度 ( 2T_p = 0.4 ) 秒:
    • 频谱图中的频率分辨率进一步提高,主要频率成分非常清晰。
    • 更长的分析长度提供了更好的频率分辨率,但同时也增加了计算时间和资源需求。

总结

  • 选择合适的分析长度:分析长度可以通过基本周期 ( T_p ) 的整数倍来选择。一般来说,分析长度至少应等于或大于一个周期 ( T_p ),这样可以确保频谱分析结果的准确性。
  • 平衡分辨率和计算复杂度:较长的分析长度提供更好的频率分辨率,但也会增加计算时间和资源。在实际应用中,需要在频率分辨率和计算复杂度之间取得平衡。
  • 避免过短的分析长度:过短的分析长度(例如小于一个周期)可能导致频谱结果混乱,难以准确识别主要频率成分

image-20240613161203147

你可以看到,白色的阳光实际上是所有可见颜色的集合,物体吸收了其中的大部分颜色。它仅反射了代表物体颜色的部分,被反射颜色的组合就是我们所感知到的颜色(此例中为珊瑚红)。

这些颜色反射的定律被直接地运用在图形领域。当我们在OpenGL中创建一个光源时,我们希望给光源一个颜色。在上一段中我们有一个白色的太阳,所以我们也将光源设置为白色。当我们把光源的颜色与物体的颜色值相乘,所得到的就是这个物体所反射的颜色(也就是我们所感知到的颜色)。让我们再次审视我们的玩具(这一次它还是珊瑚红),看看如何在图形学中计算出它的反射颜色。我们将这两个颜色向量作分量相乘,结果就是最终的颜色向量了:

glm::vec3 lightColor(1.0f, 1.0f, 1.0f);
glm::vec3 toyColor(1.0f, 0.5f, 0.31f);
glm::vec3 result = lightColor * toyColor; // = (1.0f, 0.5f, 0.31f);

我们可以看到玩具的颜色吸收了白色光源中很大一部分的颜色,但它根据自身的颜色值对红、绿、蓝三个分量都做出了一定的反射。这也表现了现实中颜色的工作原理。由此,我们可以定义物体的颜色为==物体从一个光源反射各个颜色分量的大小。==

**现实世界的光照是极其复杂的,而且会受到诸多因素的影响,这是我们有限的计算能力所无法模拟的。因此OpenGL的光照使用的是简化的模型,对现实的情况进行近似,这样处理起来会更容易一些,而且看起来也差不多一样。这些光照模型都是基于我们对光的物理特性的理解。其中一个模型被称为冯氏光照模型(Phong Lighting Model)。冯氏光照模型的主要结构由3个分量组成:环境(Ambient)、漫反射(Diffuse)和镜面(Specular)光照。下面这张图展示了这些光照分量看起来的样子:

img

  • 环境光照(Ambient Lighting):即使在黑暗的情况下,世界上通常也仍然有一些光亮(月亮、远处的光),所以物体几乎永远不会是完全黑暗的。为了模拟这个,我们会使用一个环境光照常量,它永远会给物体一些颜色。
  • 漫反射光照(Diffuse Lighting):模拟光源对物体的方向性影响(Directional Impact)。它是冯氏光照模型中视觉上最显著的分量。物体的某一部分越是正对着光源,它就会越亮。
  • 镜面光照(Specular Lighting):模拟有光泽物体上面出现的亮点。镜面光照的颜色相比于物体的颜色会更倾向于光的颜色。

在漫反射光照部分,光照表现并没有问题,这是因为我们没有对物体进行任何缩放操作,所以我们并不真的需要使用一个法线矩阵,而是仅以模型矩阵乘以法线就可以。但是如果你会进行不等比缩放,使用法线矩阵去乘以法向量就是必须的了。

image-20240618134143162

image-20240618134913056

image-20240618135228887

image-20240618135413787

已知周期信号 x(t) = 0.75 + 3.4 cos 2πft + 2.7 cos 4π ft +1.5sin 3.5π ft + 2.5sin 7π ft ,其
中 25/16Hz,若截断时间长度分别为信号周期的 0.9 和 1.1 倍,试分别绘制这八种窗函数
提取的 x(t)的频谱。

image-20240618141855717

根据下列指标采用窗函数法设计低通数字滤波器, 通带截止频率wp= 0.2π ,阻带截止频率

ws = 0.3π,通带最大衰减 0.25dB,阻带最小衰减 50dB。

(1) 分别利用汉明窗、布莱克曼窗和凯泽窗设计该滤波器,且滤波器具有线性相位。绘出脉冲响应 h(n)及滤波器的频率响应;

(2) 增加 N,观察过渡带和最大肩峰值的变化。

利用汉明窗设计数字微分器

Hd(e^jw)=

jw,0<w<π;

-jw,-π<w<0.

要求 N = 21,且滤波器具有线性相位。

CUDA

image-20240514124728144

PCIe传输速率比较慢

image-20240514125248067

image-20240514134619194

image-20240514163840122

image-20240514164819180

CPU启动核函数之后,由这个核函数在GPU设备里产生的所有的线程构成了一个grid(网格)

而一个grid又由多个线程块(block)组成,一个线程块里包含一组线程(thread)

进行CUDA编程时,要做的就是减少计算核心空闲的时间,让计算核心一直处于计算中

CPU,GPU在进行内存相互访问的时候,会很耗时

image-20240514170821304

image-20240514200242464

image-20240514200453776

一维:

image-20240514215215578

image-20240514214149999

二维:

image-20240514214513695

三维:
image-20240515094438706

image-20240515094525884

image-20240515095616319

-arch和-code 都与GPU的兼容性有关,在指定计算能力的时候,GPU的真实架构计算能力一定要大于虚拟架构计算能力的

image-20240515100052890

image-20240515100901251

image-20240515101949472

image-20240515102254655

image-20240515104802323

即时编译,增加兼容性:

image-20240515104350368

两个都是compute_XY(虚拟)

image-20240518093831448

image-20240518094156107

在C++中,exit(-1)return -1 都可以用来表示程序的异常退出或者返回一个错误码,但它们之间有一些重要的区别:

  1. exit(-1) 是一个系统调用,它会立即终止整个程序的执行,并返回一个指定的退出码给操作系统。这会终止程序的执行并进行清理工作(如关闭文件、释放内存等),然后返回退出码。exit 函数是C标准库中的函数,定义在 <cstdlib> 头文件中。
  2. return -1 通常出现在函数中,用于从当前函数中返回一个指定的值。当函数的返回类型是整型时,return -1 将会将 -1 这个值返回给调用该函数的地方。如果 -1main 函数的返回值,那么它会被返回给操作系统作为程序的退出码。

因此,exit(-1) 会立即终止整个程序的执行,而 return -1 只是从当前函数中返回一个值。

image-20240518101534052

image-20240518102522434双指针

image-20240518102902454

image-20240518103123516

image-20240518103306357

cudaDeviceReset()函数用于重置当前设备上的所有状态信息。它会清除当前设备上的所有内存分配和设备端的运行时状态,释放所有CUDA资源,并将设备状态恢复到初始化时的状态。这个函数通常在程序结束前被调用,以确保释放所有CUDA资源并将GPU状态还原到初始状态。

调用cudaDeviceReset()函数可以帮助确保程序结束时释放了所有CUDA资源,从而避免内存泄漏和其他问题。

在CUDA中,核函数(kernel function)和设备函数(device function)是两个不同的概念。

  1. 核函数(Kernel Function):
    • 核函数是在GPU上执行的并行函数,由关键字__global__声明。它们可以被从CPU代码调用,并在GPU上并行执行。在CUDA中,核函数通常用于执行大规模数据并行计算。
  2. 设备函数(Device Function):
    • 设备函数是在GPU上执行的函数,但它们只能被其他设备函数调用,不能从CPU代码中直接调用。设备函数通常用于封装重复使用的代码逻辑,以便在核函数中进行调用,以提高代码复用性和可读性。

虽然它们都是在GPU上执行的函数,但核函数和设备函数在调用方式、用途和作用域上有明显的区别。核函数是CUDA程序中由CPU代码调用的入口点,而设备函数是为了在核函数内部使用而设计的。

image-20240518143353274

image-20240518145238232

image-20240518145441046

__FILE____LINE__ 是C/C++中的预定义宏,它们分别代表当前源文件的文件名和行号

image-20240518152527144

image-20240524144504885

%g 是 C++ 语言中的格式化输出控制符之一,用于打印浮点数。它根据浮点数的值自动选择 %f%e 中较短的一个输出形式来打印。

具体来说:

  • 如果浮点数的绝对值小于 0.0001 或者大于等于 10^6,%g 就会采用 %e 的输出形式,用科学计数法表示浮点数。
  • 否则,%g 会采用 %f 的输出形式,用普通的小数形式表示浮点数。

在 CUDA 编程中,cudaEventQuery(start) 表示查询事件 start 的状态。具体来说,它用于检查事件是否已经被记录。如果事件已经被记录,那么 cudaEventQuery 将立即返回。如果事件还没有被记录,那么 cudaEventQuery 将等待事件被记录后才返回。

在上述代码中,cudaEventQuery(start) 的目的可能是为了确保在记录 stop 事件之前,start 事件已经被成功记录。这样可以确保测量的时间间隔准确,避免了 start 事件尚未记录就立即记录 stop 事件的情况。

image-20240524163028697

Algo

由于实际测试具有较大的局限性,因此我们考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析(asymptotic complexity analysis),简称复杂度分析。

  • “时间和空间资源”分别对应时间复杂度(time complexity)和空间复杂度(space complexity)。
  • “随着输入数据大小的增加”意味着复杂度反映了算法运行效率与输入数据体量之间的关系。
  • “时间和空间的增长趋势”表示复杂度分析关注的不是运行时间或占用空间的具体值,而是时间或空间增长的“快慢”。

迭代(iteration)

递归(recursion),通过函数调用自身来解决问题:(“将问题分解为更小子问题”)

  1. :程序不断深入地调用自身,通常传入更小或更简化的参数,直到达到“终止条件”。
  2. :触发“终止条件”后,程序从最深层的递归函数开始逐层返回,汇聚每一层的结果。

而从实现的角度看,递归代码主要包含三个要素。

  1. 终止条件:用于决定什么时候由“递”转“归”。
  2. 递归调用:对应“递”,函数调用自身,通常输入更小或更简化的参数。
  3. 返回结果:对应“归”,将当前递归层级的结果返回至上一层。

虽然从计算角度看,迭代与递归可以得到相同的结果,但它们代表了两种完全不同的思考和解决问题的范式

  • 迭代:“自下而上”地解决问题。从最基础的步骤开始,然后不断重复或累加这些步骤,直到任务完成。
  • 递归:“自上而下”地解决问题。将原问题分解为更小的子问题,这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题,直到基本情况时停止(基本情况的解是已知的)。

过深的递归可能导致栈溢出错误

尾递归

有趣的是,如果函数在返回前的最后一步才进行递归调用,则该函数可以被编译器或解释器优化,使其在空间效率上与迭代相当。这种情况被称为尾递归(tail recursion)。

  • 普通递归:当函数返回到上一层级的函数后,需要继续执行代码,因此系统需要保存上一层调用的上下文。

  • 尾递归:递归调用是函数返回前的最后一个操作,这意味着函数返回到上一层级后,无须继续执行其他操作,因此系统无须保存上一层函数的上下文。

    例如:

    /* 尾递归 */
    int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
    return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
    }

普通递归

txt
python
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

在普通递归中,递归调用 factorial(n - 1) 发生在函数的末尾,并且返回值被乘以 n 后再返回。

尾递归

txt
python
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    else:
        return factorial_tail(n - 1, accumulator * n)

以上述递归函数为例,求和操作在递归的“归”阶段进行。这意味着最初被调用的函数实际上是最后完成其求和操作的,这种工作机制与栈的“先入后出”原则异曲同工

事实上,“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。

  1. :当函数被调用时,系统会在“调用栈”上为该函数分配新的栈帧,用于存储函数的局部变量、参数、返回地址等数据。
  2. :当函数完成执行并返回时,对应的栈帧会被从“调用栈”上移除,恢复之前函数的执行环境。

时间复杂度分析统计的不是算法运行时间,而是算法运行时间随着数据量变大时的增长趋势

img

image-20240426102948646

在计算机科学中,”渐近上界” 是一种用于分析算法性能的概念,特别是与时间复杂度和空间复杂度相关。在时间复杂度分析中,渐近上界的目的在于确定算法在数据规模趋于无穷大时的最坏性能表现。为了更好地理解这一概念,可以从几个角度来探讨:

1. 什么是渐近上界?

渐近上界指的是某个函数在趋于某个极限(例如,无限大)时,其增长速率的上限。它通常用于描述算法的最坏情况性能,表示随着输入规模增加,算法的运行时间或使用的资源上限。

2. 大-O 表示法

在算法分析中,渐近上界最常用的表示法是大-O 表示法。用 O(f(n)) 表示某个算法的时间复杂度,意味着这个算法的运行时间在最坏情况下不会超过某个函数 f(n) 的增长速率。

例如,若算法的时间复杂度是 O(n^2),表示无论最坏情况下发生了什么,这个算法的运行时间最多是某个常数与 n^2 的乘积。这里 n 是输入数据的规模。

3. 用途

渐近上界有助于比较不同算法的性能,并帮助工程师选择适当的算法。在设计和优化算法时,了解渐近上界也有助于避免性能陷阱。

4. 如何理解渐近上界?

渐近上界在数学上是严格定义的。函数 T(n) 的渐近上界是 f(n),如果存在常数 cn_0 使得对于所有 n ≥ n_0,都有 T(n) ≤ c * f(n)。这意味着当 n 足够大时,T(n) 不会超过 c * f(n),即使在最坏情况下。

5. 示例

考虑一个算法的时间复杂度是 3n^2 + 2n + 7。这个算法的渐近上界是 O(n^2),因为当 n 足够大时,3n^2 是增长最快的项,其他项的影响可以忽略。

image-20240426103209429

txt
/* 指数阶(递归实现) */
int expRecur(int n) {
    if (n == 1)
        return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}
txt
/*对数阶*/
int linearLogRecur(int n) {
    if (n <= 1)
        return 1;
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);

    return count;
}
txt
/* 线性对数阶 */
int linearLogRecur(int n) {
    if (n <= 1)
        return 1;
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
    for (int i = 0; i < n; i++) {
        count++;
    }
    return count;
}

image-20240426120004603

算法在运行过程中使用的内存空间主要包括以下几种。

  • 输入空间:用于存储算法的输入数据。
  • 暂存空间:用于存储算法在运行过程中的变量、对象、函数上下文等数据。
  • 输出空间:用于存储算法的输出数据。

一般情况下,空间复杂度的统计范围是“暂存空间”加上“输出空间”。

txt
struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(nullptr) {}
};

Node(int x) : val(x), next(nullptr) 是一个构造函数的定义

txt
int func() {
    // 执行某些操作
    return 0;
}
/* 循环的空间复杂度为 O(1) */
void loop(int n) {
    for (int i = 0; i < n; i++) {
        func();
    }
}
/* 递归的空间复杂度为 O(n) */
void recur(int n) {
    if (n == 1) return;
    return recur(n - 1);
}

函数 loop()recur() 的时间复杂度都为

,但空间复杂度不同。

  • 函数 loop() 在循环中调用了

function() ,每轮中的 function() 都返回并释放了栈帧空间,因此空间复杂度仍为

递归函数 recur() 在运行过程中会同时存在

个未返回的 recur() ,从而占用 的栈帧空间。

txt
/* 线性阶 */
void linear(int n) {
    // 长度为 n 的数组占用 O(n) 空间
    vector<int> nums(n);
    // 长度为 n 的列表占用 O(n) 空间
    vector<ListNode> nodes;
    for (int i = 0; i < n; i++) {
        nodes.push_back(ListNode(i));
    }
    // 长度为 n 的哈希表占用 O(n) 空间
    unordered_map<int, string> map;
    for (int i = 0; i < n; i++) {
        map[i] = to_string(i);
    }
}

/* 线性阶(递归实现) */
void linearRecur(int n) {
    cout << "递归 n = " << n << endl;
    if (n == 1)
        return;
    linearRecur(n - 1);
}

Q:函数和方法这两个术语的区别是什么?

函数(function)可以被独立执行,所有参数都以显式传递。方法(method)与一个对象关联,被隐式传递给调用它的对象,能够对类的实例中包含的数据进行操作。

下面以几种常见的编程语言为例来说明。

  • C 语言是过程式编程语言,没有面向对象的概念,所以只有函数。但我们可以通过创建结构体(struct)来模拟面向对象编程,与结构体相关联的函数就相当于其他编程语言中的方法。
  • Java 和 C# 是面向对象的编程语言,代码块(方法)通常作为某个类的一部分。静态方法的行为类似于函数,因为它被绑定在类上,不能访问特定的实例变量。
  • C++ 和 Python 既支持过程式编程(函数),也支持面向对象编程(方法)。

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图,它们可以从“逻辑结构”和“物理结构”两个维度进行分类。

逻辑结构:线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中,数据按照一定顺序排列,体现了数据之间的线性关系;而在树中,数据从顶部向下按层次排列,表现出“祖先”与“后代”之间的派生关系;图则由节点和边构成,反映了复杂的网络关系。

如图 3-1 所示,逻辑结构可分为“线性”和“非线性”两大类。线性结构比较直观,指数据在逻辑关系上呈线性排列;非线性结构则相反,呈非线性排列。

  • 线性数据结构:数组、链表、栈、队列、哈希表,元素之间是一对一的顺序关系。
  • 非线性数据结构:树、堆、图、哈希表。

非线性数据结构可以进一步划分为树形结构和网状结构。

  • 树形结构:树、堆、哈希表,元素之间是一对多的关系。
  • 网状结构:图,元素之间是多对多的关系。

内存是所有程序的共享资源,当某块内存被某个程序占用时,则无法被其他程序同时使用了。因此在数据结构与算法的设计中,内存资源是一个重要的考虑因素。比如,算法所占用的内存峰值不应超过系统剩余空闲内存;如果缺少连续大块的内存空间,那么所选用的数据结构必须能够存储在分散的内存空间内。

如图 3-3 所示,物理结构反映了数据在计算机内存中的存储方式,可分为连续空间存储(数组)和分散空间存储(链表)。物理结构从底层决定了数据的访问、更新、增删等操作方法,两种物理结构在时间效率和空间效率方面呈现出互补的特点。

连续空间存储与分散空间存储

值得说明的是,所有数据结构都是基于数组、链表或二者的组合实现的。例如,栈和队列既可以使用数组实现,也可以使用链表实现;而哈希表的实现可能同时包含数组和链表。

链表在初始化后,仍可以在程序运行过程中对其长度进行调整,因此也称“动态数据结构”。数组在初始化后长度不可变,因此也称“静态数据结构”。值得注意的是,数组可通过重新分配内存实现长度变化,从而具备一定的“动态性”。

基本数据类型是 CPU 可以直接进行运算的类型,在算法中直接被使用,主要包括以下几种。

  • 整数类型 byteshortintlong
  • 浮点数类型 floatdouble ,用于表示小数。
  • 字符类型 char ,用于表示各种语言的字母、标点符号甚至表情符号等。
  • 布尔类型 bool ,用于表示“是”与“否”判断。

基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1比特。在绝大多数现代操作系统中,1字节(byte)由 8比特(bit)组成。

txt

/* 初始化数组 */
// 存储在栈上
int arr[5];
int nums[5] = { 1, 3, 2, 5, 4 };
// 存储在堆上(需要手动释放空间)
int* arr1 = new int[5];
int* nums1 = new int[5] { 1, 3, 2, 5, 4 };

在C++中,将数据存储在栈上和堆上有以下区别:

  1. 存储位置
    • 栈上:栈上的数据存储在程序的栈内存中,它们的分配和释放由编译器自动管理。栈上的数据通常具有较短的生命周期,当函数执行结束时,其内部的局部变量就会被自动释放。
    • 堆上:堆上的数据存储在程序的堆内存中,它们的分配和释放通常由程序员手动管理。堆上的数据可以具有较长的生命周期,直到显式释放内存或程序终止时才会被释放。
  2. 动态性
    • 栈上:栈上的内存分配是静态的,大小在编译时确定,并且通常比较有限。由于栈上的内存分配由编译器管理,所以分配和释放速度较快。
    • 堆上:堆上的内存分配是动态的,大小可以在运行时确定,并且可以根据需要动态增长。由于堆上的内存分配由程序员管理,因此可能会产生内存泄漏或内存碎片等问题。
  3. 访问方式
    • 栈上:栈上的数据访问速度通常比较快,因为它们存储在内存中的连续位置上,并且可以直接通过指针或引用进行访问。
    • 堆上:堆上的数据访问速度可能比较慢,因为它们存储在内存中的不同位置上,并且需要通过指针间接访问。

在实际编程中,选择栈上或堆上的存储方式取决于数据的生命周期、大小和访问方式等因素。

Q:把数组存储在堆,栈上,那堆栈是什么

A:在计算机科学中,”堆栈”通常指的是”栈”和”堆”这两种不同的内存分配区域,它们用于存储程序运行时所需的数据和内存。这两者虽然名字相似,但是在内存管理和使用方面有着不同的作用和特点:

  1. 栈(Stack)
    • 栈是一种内存分配区域,用于存储函数调用时的局部变量、函数参数、函数返回地址等信息。
    • 栈上的内存分配由编译器自动管理,通常采用后进先出(LIFO)的方式进行操作。函数调用时,会将局部变量等信息压入栈中,函数返回时则将其弹出。
    • 栈上的内存分配速度快,但是空间有限,通常用于存储函数调用时所需的临时数据。
  2. 堆(Heap)
    • 堆是另一种内存分配区域,用于存储程序运行时动态分配的内存,例如使用newdelete操作符创建和释放的对象。
    • 堆上的内存分配由程序员手动管理,它的大小和生命周期可以动态确定。堆上的内存通常用于存储程序运行时动态产生的数据结构、对象等。
    • 堆上的内存分配速度相对较慢,因为需要进行动态分配和释放,并且可能产生内存碎片等问题。

总的来说,栈和堆是程序运行时两种不同的内存分配区域,它们有着不同的管理方式、分配速度和用途,程序员可以根据需要选择合适的内存分配方式来管理程序的数据和内存。

Q :存储在堆上,是要求定义为指针吗

A : 在C++中,使用new操作符分配内存时,返回的是指向分配内存的指针。因此,存储在堆上的数据需要定义为指针类型,以便程序员能够通过指针来访问和操作这些数据,并在适当的时候手动释放内存空间,以避免内存泄漏。

以下是一个简单的示例,演示如何声明和使用函数指针:

txt
cpp
#include <iostream>

// 声明一个接受两个整数参数并返回它们之和的函数
int add(int a, int b) {
    return a + b;
}

// 声明一个接受两个整数参数并返回它们之差的函数
int subtract(int a, int b) {
    return a - b;
}

int main() {
    // 声明一个指向函数的指针,该函数接受两个整数参数并返回一个整数
    int (*operation)(int, int);

    // 将函数 add 的地址赋值给指针变量 operation
    operation = add;

    // 使用指针调用函数 add
    int result1 = operation(10, 5);
    std::cout << "Result of add: " << result1 << std::endl;

    // 将函数 subtract 的地址赋值给指针变量 operation
    operation = subtract;

    // 使用指针调用函数 subtract
    int result2 = operation(10, 5);
    std::cout << "Result of subtract: " << result2 << std::endl;

    return 0;
}

在这个示例中,int (*operation)(int, int); 声明了一个名为 operation 的函数指针,它指向一个接受两个整数参数并返回一个整数的函数。然后,通过将函数的地址赋值给指针变量 operation,可以使用该指针来调用不同的函数。

txt
/* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {
    // 初始化一个扩展长度后的数组
    int *res = new int[size + enlarge];
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < size; i++) {
        res[i] = nums[i];
    }
    // 释放内存
    delete[] nums;
    // 返回扩展后的新数组
    return res;
}

返回类型为 int *,意味着该函数返回的是一个指向整数类型的指针,即指向数组的指针。

数组的优点与局限性

数组存储在连续的内存空间内,且元素类型相同。这种做法包含丰富的先验信息,系统可以利用这些信息来优化数据结构的操作效率。

  • 空间效率高:数组为数据分配了连续的内存块,无须额外的结构开销。

  • 支持随机访问:数组允许在

  • 时间内访问任何元素。

  • 缓存局部性:当访问数组元素时,计算机不仅会加载它,还会缓存其周围的其他数据,从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑,其存在以下局限性。

  • 插入与删除效率低:当数组中元素较多时,插入与删除操作需要移动大量的元素。

  • 长度不可变:数组在初始化后长度就固定了,扩容数组需要将所有数据复制到新数组,开销很大。

  • 空间浪费:如果数组分配的大小超过实际所需,那么多余的空间就被浪费了。

  • delete 用于释放通过 new 分配的单个对象的内存。

  • delete[] 用于释放通过 new[] 分配的数组的内存。

数组典型应用

数组是一种基础且常见的数据结构,既频繁应用在各类算法之中,也可用于实现各种复杂数据结构。

  • 随机访问:如果我们想随机抽取一些样本,那么可以用数组存储,并生成一个随机序列,根据索引实现随机抽样。
  • 排序和搜索:数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
  • 查找表:当需要快速查找一个元素或其对应关系时,可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射,则可以将字符的 ASCII 码值作为索引,对应的元素存放在数组中的对应位置。
  • 机器学习:神经网络中大量使用了向量、矩阵、张量之间的线性代数运算,这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
  • 数据结构实现:数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如,图的邻接矩阵表示实际上是一个二维数组。

存储数组的内存空间必须是连续的

链表的组成单位是节点(node)对象。每个节点都包含两项数据:节点的“值”和指向下一节点的“引用”。

  • 链表的首个节点被称为“头节点”,最后一个节点被称为“尾节点”。
  • 尾节点指向的是“空”,它在 Java、C++ 和 Python 中分别被记为 nullnullptrNone
  • 在 C、C++、Go 和 Rust 等支持指针的语言中,上述“引用”应被替换为“指针”。
txt
/* 链表节点结构体 */
struct ListNode {
    int val;         // 节点值
    ListNode *next;  // 指向下一节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

为什么结构体也有构造函数:

在C++中,结构体(struct)和类(class)都可以拥有构造函数。构造函数用于初始化对象的数据成员,在创建对象时自动调用。

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

  • 栈与队列:当插入和删除操作都在链表的一端进行时,它表现出先进后出的特性,对应栈;当插入操作在链表的一端进行,删除操作在链表的另一端进行,它表现出先进先出的特性,对应队列。
  • 哈希表:链式地址是解决哈希冲突的主流方案之一,在该方案中,所有冲突的元素都会被放到一个链表中。
  • :邻接表是表示图的一种常用方式,其中图的每个顶点都与一个链表相关联,链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景。

  • 高级数据结构:比如在红黑树、B 树中,我们需要访问节点的父节点,这可以通过在节点中保存一个指向父节点的引用来实现,类似于双向链表。
  • 浏览器历史:在网页浏览器中,当用户点击前进或后退按钮时,浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
  • LRU 算法:在缓存淘汰(LRU)算法中,我们需要快速找到最近最少使用的数据,以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景,比如操作系统的资源调度。

  • 时间片轮转调度算法:在操作系统中,时间片轮转调度算法是一种常见的 CPU 调度算法,它需要对一组进程进行循环。每个进程被赋予一个时间片,当时间片用完时,CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
  • 数据缓冲区:在某些数据缓冲区的实现中,也可能会使用环形链表。比如在音频、视频播放器中,数据流可能会被分成多个缓冲块并放入一个环形链表,以便实现无缝播放。

可以使用动态数组(dynamic array)来实现列表。它继承了数组的各项优点,并且可以在程序运行过程中进行动态扩容。

实际上,许多编程语言中的标准库提供的列表是基于动态数组实现的,例如 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List 等。接下来,我们将把“列表”和“动态数组”视为等同的概念。

数据结构的缓存效率

缓存虽然在空间容量上远小于内存,但它比内存快得多,在程序执行速度上起着至关重要的作用。由于缓存的容量有限,只能存储一小部分频繁访问的数据,因此当 CPU 尝试访问的数据不在缓存中时,就会发生缓存未命中(cache miss),此时 CPU 不得不从速度较慢的内存中加载所需数据。

为了尽可能达到更高的效率,缓存会采取以下数据加载机制。

  • 缓存行:缓存不是单个字节地存储与加载数据,而是以缓存行为单位。相比于单个字节的传输,缓存行的传输形式更加高效。
  • 预取机制:处理器会尝试预测数据访问模式(例如顺序访问、固定步长跳跃访问等),并根据特定模式将数据加载至缓存之中,从而提升命中率。
  • 空间局部性:如果一个数据被访问,那么它附近的数据可能近期也会被访问。因此,缓存在加载某一数据时,也会加载其附近的数据,以提高命中率。
  • 时间局部性:如果一个数据被访问,那么它在不久的将来很可能再次被访问。缓存利用这一原理,通过保留最近访问过的数据来提高命中率。

栈(stack)是一种遵循先入后出逻辑的线性数据结构。

如图 5-1 所示,我们把堆叠元素的顶部称为“栈顶”,底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”,删除栈顶元素的操作叫作“出栈”。因此我们只能在栈顶添加或删除元素,然而,数组和链表都可以在任意位置添加和删除元素,因此栈可以视为一种受限制的数组或链表

txt
基于数组实现的栈
vector<int> stack;
/* 获取栈的长度 */
stack.size()
入栈
stack.push_back(num);
出栈
stack.pop_back();
访问栈顶元素
stack.back();

back就是栈顶的位置
txt
有专用的栈方法
stack<int> stack;

/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* 访问栈顶元素 */
int top = stack.top();

/* 元素出栈 */
stack.pop(); // 无返回值

/* 获取栈的长度 */
int size = stack.size();

/* 判断是否为空 */
bool empty = stack.empty();

队列(queue)是一种遵循先入先出规则的线性数据结构。顾名思义,队列模拟了排队现象,即新来的人不断加入队列尾部,而位于队列头部的人逐个离开。

txt
/* 初始化队列 */
queue<int> queue;

/* 元素入队 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

/* 访问队首元素 */
int front = queue.front();

/* 元素出队 */
queue.pop();

/* 获取队列的长度 */
int size = queue.size();

/* 判断队列是否为空 */
bool empty = queue.empty();

添加队尾,删除队首—–先来后到

双向队列

txt
/* 初始化双向队列 */
deque<int> deque;

/* 元素入队 */
deque.push_back(2);   // 添加至队尾
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);  // 添加至队首
deque.push_front(1);

/* 访问元素 */
int front = deque.front(); // 队首元素
int back = deque.back();   // 队尾元素

/* 元素出队 */
deque.pop_front();  // 队首元素出队
deque.pop_back();   // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
bool empty = deque.empty();

DoublyListNode *pre, *cur = front; 确实是一个比较容易产生误解的地方,但实际上这行代码并不是同时给 precur 赋值为 front。这行代码实际上相当于两行分开的声明和初始化:

txt
cpp
DoublyListNode *pre; // 声明一个指向 DoublyListNode 类型的指针 pre
DoublyListNode *cur = front; // 声明一个指向 DoublyListNode 类型的指针 cur,并将其初始化为 front

这里的 pre 只是声明了一个指针,但并没有初始化,所以它的值是未定义的,你需要在后续代码中对其进行初始化。而 cur 在声明时已经被初始化为 front

哈希表(hash table),又称散列表,它通过建立键 key 与值 value 之间的映射,实现高效的元素查询。具体而言,我们向哈希表中输入一个键 key ,则可以在 O(1)时间内获取对应的值 value

unordered_map 是 C++ 标准库中的一种关联容器(Associative Container),它提供了快速的键值对存储和检索功能。它是通过哈希表实现的,因此提供了高效的插入、删除和查找操作。

txt
/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";

/* 查询操作 */
// 向哈希表中输入键 key ,得到值 value
string name = map[15937];

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);

/* 遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
    cout << kv.first << " -> " << kv.second << endl;
}
// 使用迭代器遍历 key->value
for (auto iter = map.begin(); iter != map.end(); iter++) {
    cout << iter->first << "->" << iter->second << endl;
}

我们先考虑最简单的情况,仅用一个数组来实现哈希表。在哈希表中,我们将数组中的每个空位称为桶(bucket),每个桶可存储一个键值对。因此,查询操作就是找到 key 对应的桶,并在桶中获取 value

那么,如何基于 key 定位对应的桶呢?这是通过哈希函数(hash function)实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中,输入空间是所有 key ,输出空间是所有桶(数组索引)。换句话说,输入一个 key我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置

输入一个 key ,哈希函数的计算过程分为以下两步。

  1. 通过某种哈希算法 hash() 计算得到哈希值。
  2. 将哈希值对桶数量(数组长度)capacity 取模,从而获取该 key 对应的数组索引 index
txt
index = hash(key) % capacity

<Pair *> 表示这个 vector 存储的是指向 Pair 类型对象的指针。

vector<Pair *> 创建了一个存储指向 Pair 结构的指针的动态数组,即每个元素都是指向 Pair 结构的指针。

我们将多个输入对应同一输出的情况称为哈希冲突(hash collision)。

我们可以通过扩容哈希表来减少哈希冲突。类似于数组扩容,哈希表扩容需将所有键值对从原哈希表迁移至新哈希表,非常耗时;并且由于哈希表容量 capacity 改变,我们需要通过哈希函数来重新计算所有键值对的存储位置,这进一步增加了扩容过程的计算开销。为此,编程语言通常会预留足够大的哈希表容量,防止频繁扩容。

负载因子(load factor)是哈希表的一个重要概念,其定义为哈希表的元素数量除以桶数量,用于衡量哈希冲突的严重程度,也常作为哈希表扩容的触发条件。例如在 Java 中,当负载因子超过 时,系统会将哈希表扩容至原先的 2倍。

但此方法简单粗暴且有效,但效率太低,因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率,我们可以采用以下策略。

  1. 改良哈希表数据结构,使得哈希表可以在出现哈希冲突时正常工作
  2. 仅在必要时,即当哈希冲突比较严重时,才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

链式地址

在原始哈希表中,每个桶仅能存储一个键值对。链式地址(separate chaining)将单个元素转换为链表,将键值对作为链表节点,将所有发生冲突的键值对都存储在同一链表中。图 6-5 展示了一个链式地址哈希表的例子。

链式地址哈希表

图 6-5 链式地址哈希表

基于链式地址实现的哈希表的操作方法发生了以下变化。

  • 查询元素:输入 key ,经过哈希函数得到桶索引,即可访问链表头节点,然后遍历链表并对比 key 以查找目标键值对。
  • 添加元素:首先通过哈希函数访问链表头节点,然后将节点(键值对)添加到链表中。
  • 删除元素:根据哈希函数的结果访问链表头部,接着遍历链表以查找目标节点并将其删除。

链式地址存在以下局限性。

  • 占用空间增大:链表包含节点指针,它相比数组更加耗费内存空间。
  • 查询效率降低:因为需要线性遍历链表来查找对应元素。

开放寻址

开放寻址(open addressing)不引入额外的数据结构,而是通过“多次探测”来处理哈希冲突,探测方式主要包括线性探测、平方探测和多次哈希等。

线性探测采用固定步长的线性搜索来进行探测,其操作方法与普通哈希表有所不同。

  • 插入元素:通过哈希函数计算桶索引,若发现桶内已有元素,则从冲突位置向后线性遍历(步长通常为

  • ),直至找到空桶,将元素插入其中。

  • 查找元素:若发现哈希冲突,则使用相同步长向后进行线性遍历,直到找到对应元素,返回 value 即可;如果遇到空桶,说明目标元素不在哈希表中,返回 None

图 6-6 展示了开放寻址(线性探测)哈希表的键值对分布。根据此哈希函数,最后两位相同的 key 都会被映射到相同的桶。而通过线性探测,它们被依次存储在该桶以及之下的桶中。

开放寻址(线性探测)哈希表的键值对分布

值得注意的是,我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None ,而当查询元素时,线性探测到该空桶就会返回,因此在该空桶之下的元素都无法再被访问到,程序可能误判这些元素不存在

为了解决该问题,我们可以采用懒删除(lazy deletion)机制:它不直接从哈希表中移除元素,而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下,NoneTOMBSTONE 都代表空桶,都可以放置键值对。但不同的是,线性探测到 TOMBSTONE 时应该继续遍历,因为其之下可能还存在键值对。

然而,懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记,随着 TOMBSTONE 的增加,搜索时间也会增加,因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素。

为此,考虑在线性探测中记录遇到的首个 TOMBSTONE 的索引,并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样做的好处是当每次查询或添加元素时,元素会被移动至距离理想位置(探测起始点)更近的桶,从而优化查询效率。

平方探测

平方探测与线性探测类似,都是开放寻址的常见策略之一。当发生冲突时,平方探测不是简单地跳过一个固定的步数,而是跳过“探测次数的平方”的步数,即

步。

平方探测主要具有以下优势。

  • 平方探测通过跳过探测次数平方的距离,试图缓解线性探测的聚集效应。
  • 平方探测会跳过更大的距离来寻找空位置,有助于数据分布得更加均匀。

然而,平方探测并不是完美的。

  • 仍然存在聚集现象,即某些位置比其他位置更容易被占用。
  • 由于平方的增长,平方探测可能不会探测整个哈希表,这意味着即使哈希表中有空桶,平方探测也可能无法访问到它。

image-20240428082152341

二叉树的常用术语如图所示。

  • 根节点(root node):位于二叉树顶层的节点,没有父节点。
  • 叶节点(leaf node):没有子节点的节点,其两个指针均指向 None
  • 边(edge):连接两个节点的线段,即节点引用(指针)。
  • 节点所在的层(level):从顶至底递增,根节点所在层为 1 。
  • 节点的度(degree):节点的子节点的数量。在二叉树中,度的取值范围是 0、1、2 。
  • 二叉树的高度(height):从根节点到最远叶节点所经过的边的数量。
  • 节点的深度(depth):从根节点到该节点所经过的边的数量。
  • 节点的高度(height):从距离该节点最远的叶节点到该节点所经过的边的数量。

img

常见二叉树类型

完美二叉树

所有层的节点都被完全填满。

img

完全二叉树

只有最底层的节点未被填满,且最底层节点尽量靠左填充。

img

完满二叉树

除了叶节点之外,其余所有节点都有两个子节点。

img

平衡二叉树

任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

[平衡二叉树

理想结构与退化结构

二叉树的每层节点都被填满时,达到“完美二叉树”;而当所有节点都偏向一侧时,二叉树退化为“链表”。

完美二叉树是理想情况,可以充分发挥二叉树“分治”的优势。

链表则是另一个极端,各项操作都变为线性操作,时间复杂度退化至 O(n)

img

二叉树遍历

从物理结构的角度来看,树是一种基于链表的数据结构,因此其遍历方式是通过指针逐个访问节点。然而,树是一种非线性数据结构,这使得遍历树比遍历链表更加复杂,需要借助搜索算法来实现。

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历

从顶部到底部逐层遍历二叉树,并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于广度优先遍历(breadth-first traversal),也称广度优先搜索(breadth-first search, BFS),它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

img

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则,而广度优先遍历则遵循“逐层推进”的规则,两者背后的思想是一致的。

txt
/* 层序遍历 */
vector<int> levelOrder(TreeNode *root) {
    // 初始化队列,加入根节点
    queue<TreeNode *> queue;
    queue.push(root);
    // 初始化一个列表,用于保存遍历序列
    vector<int> vec;
    while (!queue.empty()) {
        TreeNode *node = queue.front();
        queue.pop();              // 队列出队
        vec.push_back(node->val); // 保存节点值
        if (node->left != nullptr)
            queue.push(node->left); // 左子节点入队
        if (node->right != nullptr)
            queue.push(node->right); // 右子节点入队
    }
    return vec;
}

image-20240429132637500

前序、中序和后序遍历都属于深度优先遍历(depth-first traversal),也称深度优先搜索(depth-first search, DFS),它体现了一种“先走到尽头,再回溯继续”的遍历方式。

img

前序、中序和后序遍历是针对二叉树的三种不同的遍历方式,它们的区别在于遍历节点的顺序:

  1. 前序遍历(Preorder Traversal)
    • 遍历顺序:根节点 -> 左子树 -> 右子树
    • 具体操作:先访问根节点,然后递归地对左子树进行前序遍历,最后递归地对右子树进行前序遍历。
  2. 中序遍历(Inorder Traversal)
    • 遍历顺序:左子树 -> 根节点 -> 右子树
    • 具体操作:先递归地对左子树进行中序遍历,然后访问根节点,最后递归地对右子树进行中序遍历。
  3. 后序遍历(Postorder Traversal)
    • 遍历顺序:左子树 -> 右子树 -> 根节点
    • 具体操作:先递归地对左子树进行后序遍历,然后递归地对右子树进行后序遍历,最后访问根节点。

总的来说,这三种遍历方式主要区别在于根节点的访问顺序与左右子树的递归顺序。

深度优先搜索通常基于递归实现:

txt
/* 前序遍历 */
void preOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级:根节点 -> 左子树 -> 右子树
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

/* 中序遍历 */
void inOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级:左子树 -> 根节点 -> 右子树
    inOrder(root->left);
    vec.push_back(root->val);
    inOrder(root->right);
}

/* 后序遍历 */
void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 访问优先级:左子树 -> 右子树 -> 根节点
    postOrder(root->left);
    postOrder(root->right);
    vec.push_back(root->val);
}
  1. “递”表示开启新方法,程序在此过程中访问下一个节点。
  2. “归”表示函数返回,代表当前节点已经访问完毕。

image-20240429134503523

二叉树数组表示

用数组来表示二叉树

表示完美二叉树

给定一棵完美二叉树,我们将所有节点按照层序遍历的顺序存储在一个数组中,则每个节点都对应唯一的数组索引。

根据层序遍历的特性,我们可以推导出父节点索引与子节点索引之间的“映射公式”:若某节点的索引为i ,则该节点的左子节点索引为2i+1 ,右子节点索引为2i+2

img映射公式的角色相当于链表中的节点引用(指针)。给定数组中的任意一个节点,我们都可以通过映射公式来访问它的左(右)子节点。

表示任意二叉树

完美二叉树是一个特例,在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None ,因此我们无法仅凭该序列来推测 None 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列

img

为了解决此问题,我们可以考虑在层序遍历序列中显式地写出所有 None 。如图 7-14 所示,这样处理后,层序遍历序列就可以唯一表示二叉树了

txt
/* 二叉树的数组表示 */
// 使用 int 最大值 INT_MAX 标记空位
vector<int> tree = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};

img

完全二叉树:只有最底层的节点未被填满,且最底层节点尽量靠左填充。

完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义,None 只出现在最底层且靠右的位置,因此所有 None 一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时,可以省略存储所有 None ,非常方便.

img

优点与局限性

二叉树的数组表示主要有以下优点。

  • 数组存储在连续的内存空间中,对缓存友好,访问与遍历速度较快。
  • 不需要存储指针,比较节省空间。
  • 允许随机访问节点。

然而,数组表示也存在一些局限性。

  • 数组存储需要连续内存空间,因此不适合存储数据量过大的树。
  • 增删节点需要通过数组插入与删除操作实现,效率较低。
  • 当二叉树中存在大量 None 时,数组中包含的节点数据比重较低,空间利用率较低。

二叉搜索树

二叉搜索树(binary search tree)满足以下条件:

1.对于根节点,左子树中所有节点的值<根节点的值<右子树中所有节点的值。

2,任意节点的左、右子树也是二叉搜索树,即同样满足条件 1.

img

插入节点

给定一个待插入元素 num ,为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质,

  1. 查找插入位置:与查找操作相似,从根节点出发,根据当前节点值和 num 的大小关系循环向下搜索,直到越过叶节点(遍历至 None )时跳出循环。
  2. 在该位置插入节点:初始化节点 num ,将该节点置于 None 的位置。

img

只能插在NONE节点处,即*pre = nullptr

  • 二叉搜索树不允许存在重复节点,否则将违反其定义。因此,若待插入节点在树中已存在,则不执行插入,直接返回。
  • 为了实现插入节点,我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时,我们可以获取到其父节点,从而完成节点插入操作。

删除节点

当待删除节点的度为2时,我们无法直接删除它,而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 <根节点 <右子树”的性质,因此这个节点可以是右子树的最小节点或左子树的最大节点

  1. 找到待删除节点在“中序遍历序列”中的下一个节点,记为 tmp
  2. tmp 的值覆盖待删除节点的值,并在树中递归删除节点 tmp

img

img

img

二叉树的中序遍历遵循“左 根 右”的遍历顺序,而二叉搜索树满足“左子节点 根节点 右子节点”的大小关系。

这意味着在二叉搜索树中进行中序遍历时,总是会优先遍历下一个最小节点,从而得出一个重要性质:二叉搜索树的中序遍历序列是升序的

利用中序遍历升序的性质,我们在二叉搜索树中获取有序数据仅需O(n)时间,无须进行额外的排序操作,非常高效。

img

int val{}; 是C++中的变量声明语句,其中 int 表示变量的类型为整数类型,val 是变量名,{} 表示进行了值初始化。

在C++11及其之后的标准中,使用 {} 进行初始化被称为列表初始化或者统一初始化。对于内置类型(如 intfloatdouble 等),使用 {} 进行初始化时,如果未提供初始值,则会将变量初始化为零值,即 0。这种初始化方式也可以保证初始化的一致性,并且在某些情况下可以避免隐式类型转换带来的问题。

AVL 树

在多次插入和删除操作后,二叉搜索树可能退化为链表。在这种情况下,所有操作的时间复杂度将从

O(log n)劣化成O(n)

AVL 树既是二叉搜索树,也是平衡二叉树,同时满足这两类二叉树的所有性质,因此是一种平衡二叉搜索树(balanced binary search tree)。

节点的平衡因子(balance factor)定义为节点左子树的高度减去右子树的高度,同时规定空节点的平衡因子为0 。

AVL 树旋转

AVL 树的特点在于“旋转”操作,它能够在不影响二叉树的中序遍历序列的前提下,使失衡节点重新恢复平衡。换句话说,旋转操作既能保持“二叉搜索树”的性质,也能使树重新变为“平衡二叉树”

我们将平衡因子绝对值>1的节点称为“失衡节点”。根据节点失衡情况的不同,旋转操作分为四种:右旋、左旋、先右旋后左旋、先左旋后右旋。

1. 右旋

imgavltree_right_rotate_step3

avltree_right_rotate_step4

当节点 child 有右子节点(记为 grand_child )时,需要在右旋中添加一步:将 grand_child 作为 node 的左子节点。

有 grand_child 的右旋操作

右旋和左旋操作在逻辑上是镜像对称的,它们分别解决的两种失衡情况也是对称的。基于对称性,我们只需将右旋的实现代码中的所有的 left 替换为 right ,将所有的 right 替换为 left ,即可得到左旋的实现代码

先左旋后右旋

先左旋后右旋

先右旋后左旋

先右旋后左旋

AVL 树的四种旋转情况image-20240430092611363

DFS(深度优先搜索)遍历二叉树是一种遍历或搜索算法,用来访问二叉树中的所有节点,其目的是尽可能深地访问树的分支。DFS在二叉树中常用的有三种遍历方式:前序遍历(Pre-order)、中序遍历(In-order)和后序遍历(Post-order)。下面详细解释这三种遍历方式:

  1. 前序遍历(Pre-order Traversal)
    • 访问顺序:先访问根节点,然后递归地进行前序遍历左子树,接着递归地进行前序遍历右子树。
    • 应用:前序遍历常用于打印树的结构,复制树结构。
  2. 中序遍历(In-order Traversal)
    • 访问顺序:先递归地进行中序遍历左子树,然后访问根节点,最后递归地进行中序遍历右子树。
    • 应用:对于二叉搜索树(BST),中序遍历可以得到一个有序的数据序列。
  3. 后序遍历(Post-order Traversal)
    • 访问顺序:先递归地进行后序遍历左子树,然后递归地进行后序遍历右子树,最后访问根节点。
    • 应用:后序遍历常用于访问节点后再执行操作的场景,如计算一个文件夹的总大小时。

DFS 遍历的核心在于使用递归(或显式使用栈)来实现持续深入每个分支直到达到叶子节点或满足某些条件后回溯到上一节点。这种方式非常适合处理具有层级关系的数据,如文件系统的目录结构、组织结构等。在二叉树的上下文中,DFS遍历可以帮助理解和操作树的结构。

txt
visited.count(adjVet)

countunordered_set 提供的的一个成员函数,它返回集合中指定元素的数量。如果 adjVet 是指向图中的一个顶点的指针,并且这个顶点已经被添加到 visited 集合中,那么 visited.count(adjVet) 将返回 1,表示该顶点已经被访问过。如果 adjVet 不在 visited 集合中,那么返回 0,表示该顶点还没有被访问过。

txt
visited.emplace(adjVet);

emplace 是一个函数,它用于在容器中直接构造并插入元素,而不需要创建元素的副本

FPGA

assign 关键字用于对线网(wire)或变量(var)进行连续赋值。连续赋值意味着一旦右侧的表达式发生变化,赋值就会立即更新左侧的值,这与过程赋值(在always块中)不同,后者在某种事件或条件发生时才更新值。

assign temp2 = {32{1’b0}}; 是什么意思?

在Verilog中,assign temp2 = {32{1'b0}}; 这行代码声明了一个连续赋值,将 temp2 这个线网的值设置为一个32位的全0值。

这里的 {32{1'b0}} 是一个重复拼接操作,含义如下:

  • 1'b0 是一个二进制数,表示一个位宽为1的数值,值为0。
  • {32{1'b0}} 表示将 1'b0 这个值重复32次。
Verilog 数据类型

Verilog 最常用的 2 种数据类型就是线网(wire)与寄存器(reg),其余类型可以理解为这两种数据类型的扩展或辅助。

整数(integer) reg 型变量为无符号数,而 integer 型变量为有符号数

实数(real)

在Verilog中,realinteger 是数据类型关键字,分别用于声明实数类型和整数类型的变量。

txt
real data1;
integer temp;
initial begin
    data1 = 2e3;
    data1 = 3.75;
end

initial begin
    temp = data1; //temp 值的大小为3
end

这段代码包含两个 initial 块,它们在仿真开始时执行一次。

第一个 initial 块中:

  1. data1 被初始化为实数类型 real
  2. data1 被赋值为 2e3,这意味着 data1 现在的值是2000.0。
  3. 随后,data1 被更新为 3.75

第二个 initial 块中:

  1. temp 被初始化为整数类型 integer
  2. temp 被赋值为 data1 的值。由于 data1 当前是 3.75,这个赋值会将实数转换为整数。在Verilog中,实数赋值给整数时,会进行取整操作,保留数值的整数部分,忽略小数部分。因此,temp 的值将是3。

需要注意的是,您的注释 //temp 值的大小为3 是正确的,因为 data1 的值 3.75 在赋值给 temp 时会被取整为3。

时间(time)

Verilog 使用特殊的时间寄存器 time 型变量,对仿真时间进行保存。其宽度一般为 64 bit,通过调用系统函数 $time 获取当前仿真时间。例如:

txt
time current_time;
initial begin
    #100;
    current_time = $time; //current_time 的大小为 100
end

这段代码包含一个 initial 块,它在仿真开始时执行一次。

initial 块中:

  1. current_time 被初始化为时间类型 time
  2. #100; 是一个延迟语句,它会使仿真暂停100个时间单位。在Verilog中,# 后面跟一个数字表示延迟的时间量。

数组

存储器

参数 参数用来表示常量,用关键字 parameter 声明,只能赋值一次

parameter data_width = 10’d32 ;

字符串

字符串保存在 reg 类型的变量中,每个字符占用一个字节(8bit)。因此寄存器变量的宽度应该足够大,以保证不会溢出。

字符串不能多行书写,即字符串中不能包含回车符。如果寄存器变量的宽度大于字符串的大小,则使用 0 来填充左边的空余位;如果寄存器变量的宽度小于字符串大小,则会截去字符串左边多余的数据。例如,为存储字符串 “run.runoob.com”, 需要 14*8bit 的存储单元:

reg [0: 14*8-1] str ;
initial begin
str = “run.runoob.com”;
end

IMG_20240424_115210

IMG_20240424_115158

IMG_20240424_115542

IMG_20240424_115525

IMG_20240424_115506

2.4 Verilog 表达式

表达式由操作符和操作数构成,其目的是根据操作符的意义得到一个计算结果。

a^b ; //a与b进行异或操作
address[9:0] + 10’b1 ; //地址累加
flag1 && flag2 ; //逻辑与操作

always块里赋值对象不能是wire型

同类型操作符之间,除条件操作符从右往左关联,其余操作符都是自左向右关联。圆括号内表达式优先执行

txt
//自右向左关联,两种写法等价
A+B-C ;
(A+B)-C ;

//自右向左关联,两种写法等价,结果为 B、D 或 F
A ? B : C ? D : F ;
A ? B : (C ? D : F) ;

求幂(**)、取模(%)

txt
b = 4'b100x;

x 是一个表示未知或不可确定状态的字符。它用于在仿真中表示一个位的值是未知的,这通常发生在综合过程中,当某些逻辑路径没有被明确赋值时,或者在设计中的某些部分还没有完全定义时。

无符号数乘法时,结果变量位宽应该为 2 个操作数位宽之和

reg [3:0] mula ;
reg [1:0] mulb;
reg [5:0] res ;
mula = 4’he ;
mulb = 2’h3 ;
res = mula * mulb ; //结果为res=6’h2a, 数据结果没有丢失位数

逻辑操作符主要有 3 个:&&(逻辑与), ||(逻辑或),!(逻辑非)

按位操作符包括:取反(),与(&),或(|),异或(^),同或(^)

按位操作符对 2 个操作数的每 1bit 数据进行按位操作,如果 2 个操作数位宽不相等,则用 0 向左扩展补充较短的操作数。

归约操作符

归约操作符包括:归约与(&),归约与非(&),归约或(|),归约或非(|),归约异或(^),归约同或(~^)。

归约操作符只有一个操作数,它对这个向量操作数逐位进行操作,最终产生一个 1bit 结果。

逻辑操作符、按位操作符和归约操作符都使用相同的符号表示,因此有时候容易混淆。区分这些操作符的关键是分清操作数的数目,和计算结果的规则。

txt
A = 4'b1010 ;
&A ;      //结果为 1 & 0 & 1 & 0 = 1'b0,可用来判断变量A是否全1
~|A ;     //结果为 ~(1 | 0 | 1 | 0) = 1'b0, 可用来判断变量A是否为全0
^A ;      //结果为 1 ^ 0 ^ 1 ^ 0 = 1'b0

移位操作符

移位操作符包括左移(<<),右移(>>),算术左移(<<<),算术右移(>>>)。

移位操作符是双目操作符,两个操作数分别表示要进行移位的向量信号(操作符左侧)与移动的位数(操作符右侧)。

算术左移和逻辑左移时,右边低位会补 0。

逻辑右移时,左边高位会补 0;而算术右移时,左边高位会补充符号位,以保证数据缩小后值的正确性。

实例

A = 4’b1100 ;
B = 4’b0010 ;
A = A >> 2 ; //结果为 4’b0011
A = A << 1; *//结果为 4’b1000*
A = A <<< 1 ; *//结果为 4’b1000*
C = B + (A>>>2); //结果为 2 + (-4/4) = 1, 4’b0001

define, undef

在编译阶段,`define 用于文本替换,类似于 C 语言中的 #define

`undef 用来取消之前的宏定义

txt
`ifdef       MCU51
    parameter DATA_DW = 8   ;
`elsif       WINDOW
    parameter DATA_DW = 64  ;
`else
    parameter DATA_DW = 32  ;
`endif

`include

使用 `include 可以在编译时将一个 Verilog 文件内嵌到另一个 Verilog 文件中,作用类似于 C 语言中的 #include 结构。

timescale

在 Verilog 模型中,时延有具体的单位时间表述,并用 `timescale 编译指令将时间单位与实际时间相关联。

该指令用于定义时延、仿真的单位和精度,格式为:

txt
`timescale      time_unit / time_precision

time_unit 表示时间单位,time_precision 表示时间精度,它们均是由数字以及单位 s(秒),ms(毫秒),us(微妙),ns(纳秒),ps(皮秒)和 fs(飞秒)组成。时间精度可以和时间单位一样,但是时间精度大小不能超过时间单位大小,例如下面例子中,输出端 Z 会延迟 5.21ns 输出 A&B 的结果。

实例

timescale 1ns/100ps *//时间单位为1ns,精度为100ps,合法* *//timescale 100ps/1ns //不合法*
module AndFunc(Z, A, B);
output Z;
input A, B ;
assign #5.207 Z = A & B
endmodule

在编译过程中,timescale 指令会影响后面所有模块中的时延值,直至遇到另一个 timescale 指令或 `resetall 指令。

由于在 Verilog 中没有默认的 timescale,如果没有指定 timescale,Verilog 模块就有会继承前面编译模块的 `timescale 参数。有可能导致设计出错。

如果一个设计中的多个模块都带有 `timescale 时,模拟器总是定位在所有模块的最小时延精度上,并且所有时延都相应地换算为最小时延精度

`default_nettype

该指令用于为隐式的线网变量指定为线网类型,即将没有被声明的连线定义为线网类型。

txt
`default_nettype wand 

该实例定义的缺省的线网为线与类型。因此,如果在此指令后面的任何模块中的连线没有说明,那么该线网被假定为线与类型。

txt
`default_nettype none

该实例定义后,将不再自动产生 wire 型变量。

celldefine, endcelldefine

这两个程序指令用于将模块标记为单元模块,他们包含模块的定义。例如一些与、或、非门,一些 PLL 单元,PAD 模型,以及一些 Analog IP 等。

实例

celldefine **module** ( **input** clk, **input** rst, **output** clk_pll, **output** flag); …… **endmodule** endcelldefine

unconnected_drive, nounconnected_drive

在模块实例化中,出现在这两个编译指令间的任何未连接的输入端口,为正偏电路状态或者为反偏电路状态。

txt
assign

用于对 wire 型变量进行赋值,不对寄存器赋值

进位输出(Carry out,通常表示为Co或Cout)是全加器的一个输出,它表示在两个二进制位相加时是否产生了进位。在二进制加法中,当两个加数位(A和B)的和大于或等于2时,就会产生进位,因为二进制中的每一位只能表示0或1。进位输出就是用来表示这个进位的。

module full_adder1(
input Ai, Bi, Ci,
output So, Co);

assign So = Ai ^ Bi ^ Ci ;
assign Co = (Ai & Bi) | (Ci & (Ai | Bi));
endmodule

更简单的:

txt
module full_adder1(
    input Ai, Bi, Ci,
    output So, Co);
    
    assign {Co, So} = Ai + Bi + Ci;
endmodule

//普通时延,A&B计算结果延时10个时间单位赋值给Z
wire Z, A, B ;
assign #10 Z = A & B ;

//隐式时延,声明一个wire型变量时对其进行包含一定时延的连续赋值。
wire A, B;
wire #10 Z = A & B;

//声明时延,声明一个wire型变量是指定一个时延。因此对该变量所有的连续赋值都会被推迟到指定的时间。除非门级建模中,一般不推荐使用此类方法建模。
wire A, B;
wire #10 Z ;
assign Z =A & B

Verilog 过程结构

过程结构语句有 2 种,initial 与 always 语句

一个模块中可以包含多个 initial 和 always 语句,但 2 种语句不能嵌套使用。

但是 initial 语句或 always 语句内部可以理解为是顺序执行的(非阻塞赋值除外)。

initial语句

initial 语句从 0 时刻开始执行,只执行一次,多个 initial 块之间是相互独立的。

如果 initial 块内包含多个语句,需要使用关键字 begin 和 end 组成一个块语句。

如果 initial 块内只要一条语句,关键字 begin 和 end 可使用也可不使用。

initial 理论上来讲是不可综合的,多用于初始化、信号检测等。

这些语句在模块间并行执行,与其在模块的前后顺序没有关系

always 语句

与 initial 语句相反,always 语句是重复执行的。always 语句块从 0 时刻开始执行其中的行为语句;当执行完最后一条语句后,便再次执行语句块中的第一条语句,如此循环反复。

由于循环执行的特点,always 语句多用于仿真时钟的产生,信号行为的检测等。

parameter 关键字用于定义模块的参数。参数是一种可以在模块实例化时或在模块内部使用,但不一定要在模块的所有复制中传递的常数。简单地说,参数类似于函数或算法中的变量,它们在模块的复制品之间共享。

连续性赋值使用assign语句,而过程性赋值使用always块。

阻塞赋值属于顺序执行,即下一条语句执行前,当前语句一定会执行完毕。

阻塞赋值语句使用等号 = 作为赋值符。

非阻塞赋值属于并行执行语句,即下一条语句的执行和当前语句的执行是同时进行的,它不会阻塞位于同一个语句块中后面语句的执行。

非阻塞赋值语句使用小于等于号 <= 作为赋值符。

如下所示,2 个 always 块中语句并行执行,赋值操作右端操作数使用的是上一个时钟周期的旧值,此时 a<=b 与 b<=a 就可以相互不干扰的执行,达到交换寄存器值的目的。

实例

always @(posedge clk) begin
a <= b ;
end

always @(posedge clk) begin
b <= a;
end

Verilog 时序控制

Verilog 提供了 2 大类时序控制方法:时延控制和事件控制。事件控制主要分为边沿触发事件控制与电平敏感事件控制

时延控制:根据在表达式中的位置差异,时延控制又可以分为常规时延与内嵌时延。

常规时延

txt
reg  value_test ;
reg  value_general ;
#10  value_general    = value_test ;

或:

txt
#10 ;
value_ single         = value_test ;

内嵌时延

遇到内嵌延时时,该语句先将计算结果保存,然后等待一定的时间后赋值给目标信号。

内嵌时延控制加在赋值号之后。例如:

txt
reg  value_test ;
reg  value_embed ;
value_embed        = #10 value_test ;

需要说明的是,这 2 种时延控制方式的效果是有所不同的。

当延时语句的赋值符号右端是常量时,2 种时延控制都能达到相同的延时赋值效果。

当延时语句的赋值符号右端是变量时,2 种时延控制可能会产生不同的延时赋值效果。

边沿触发事件控制

在 Verilog 中,事件是指某一个 reg 或 wire 型变量发生了值的变化。事件控制用符号 @ 表示。

设计:根据需求编写硬件描述语言(如Verilog或VHDL)代码来描述设计的功能和行为

synthesize综合,合成:综合代码,检查语法是否有错误,将高级的逻辑描述代码转换为逻辑门级别的网表或等效的门级电路

FloorPlanner 是 FPGA 设计流程中的一个重要工具,用于执行布局(Place)阶段的子任务,即对设计中的逻辑电路进行布局安置。在 FPGA 设计流程中,FloorPlanner 的地位如下:

  1. 布局规划:FloorPlanner 负责规划 FPGA 芯片上各个逻辑模块的布局位置,以最大程度地满足设计的性能和资源利用率要求。它会考虑逻辑模块之间的布线延迟、信号传输路径长度等因素,以优化整体的布局结构。
  2. 资源分配:FloorPlanner 还负责将设计中的逻辑模块分配到 FPGA 芯片的不同区域,并且合理利用芯片上的资源(如片上存储器、DSP模块等),以满足设计对资源的需求。
  3. 时序约束:在布局过程中,FloorPlanner 还会考虑时序约束,确保设计中的时序要求能够得到满足。它会尽可能减少逻辑模块之间的传输延迟,以确保时序性能。
  4. 优化布局:FloorPlanner 通过对设计进行优化布局,以降低布线延迟、减少时序问题和功耗等方面的优化。这可以提高设计的性能、可靠性和功耗效率。

在 FPGA 设计流程中,FloorPlanner 位于布局(Place)阶段之前,它为后续的布线(Route)阶段提供了优化的布局结果,从而帮助实现设计的最终映射和部署。

Place&Route

开发流程中的 Place & Route 是指在将设计映射到 FPGA 芯片时的一个重要步骤。下面解释一下它的含义和作用:

  1. Place(放置):Place 指的是将设计中的逻辑元素(如逻辑门、寄存器等)放置到 FPGA 芯片的物理位置上。这一步骤考虑了芯片内部的布局和连接资源,以尽可能地优化性能和资源利用率。放置的目标是最小化延迟、最大化时序性能,并且尽量减少芯片内的布线冲突。
  2. Route(布线):Route 是指将设计中的逻辑元素之间的连接关系转化为芯片内部的实际物理连线。这一步骤考虑了芯片内部的连线资源、信号传输延迟等因素,以确保逻辑元素之间的连接能够有效地建立并满足时序要求。布线的目标是尽可能地降低信号传输延迟、最小化信号干扰,同时满足设计的时序约束。

在 Verilog 中,reg 类型通常用于表示存储元素(如寄存器),而不是直接连接到模块的输出端口。输出端口通常使用 outputinout 声明,并且通常需要与 wire 类型一起使用。

reg 类型在 Verilog 中表示的是寄存器类型,它在 always 块中使用,存储状态或信号。而 output 端口应该使用 wire 类型来表示,因为它们不会存储状态,只是将信号传递给其他部件。

因此,你在模块顶层中使用 output reg 是不符合常规的 Verilog 设计习惯的,通常应该使用 output wire

image-20240427142422285

半加器(Half Adder)和全加器(Full Adder)是数字电路中用于执行二进制加法的基本组件。它们的主要区别在于它们处理的输入数量和功能。

半加器: 半加器是一个组合逻辑电路,它接受两个二进制位作为输入,并产生两个输出:和(Sum)和进位(Carry)。半加器只处理两个输入位的加法,不考虑来自较低位的进位。半加器的输出进位只能表示当前两个输入位相加是否产生了进位。

半加器的逻辑可以表示为:

  • 和(Sum) = A XOR B

  • 进位(Carry) = A AND B

其中,A和B是两个输入位,XOR表示异或门,AND表示与门。

全加器: 全加器也是一个组合逻辑电路,它接受三个二进制位作为输入,并产生两个输出:和(Sum)和进位(Carry)。全加器的三个输入包括两个加数位(A和B)以及来自较低位的进位(Carry-in)。全加器能够处理包括进位在内的三个位的加法。

全加器的逻辑可以表示为:

  • 和(Sum) = (A XOR B) XOR Carry-in

  • 进位(Carry) = (A AND B) OR (Carry-in AND (A XOR B))

其中,Carry-in是来自较低位的进位,OR表示或门。

区别:

输入数量:半加器有两个输入,全加器有三个输入。

功能:半加器只计算两个输入位的和和进位,而全加器计算三个输入位(包括来自较低位的进位)的和和进位。

应用:半加器通常用于构建更复杂的加法器电路,如全加器。全加器则用于实现多位二进制数的加法,因为它能够处理进位。

在实际的数字电路设计中,全加器更为常用,因为它可以级联(Cascade)起来构成多位加法器,如4位、8位、16位等,从而实现更复杂的算术运算。

在Verilog中,parameter是一个关键字,用于定义模块(module)的参数

parameter定义的值在模块的整个实例化过程中都是固定的,不能被重新赋值。这意味着一旦定义了parameter,它的值在整个模块中都是不变的。

Assignment 赋值

SP代表single port单端口模式,即同一时钟控制读写,同一时间只能写或者度

在您提供的 Verilog 代码片段中,ram_inst 是一个实例化语句,用于创建一个 RAM 模块的实例。这个实例使用了多个引脚(pins),这些引脚定义了模块的输入和输出接口。下面是每个引脚的详细解释:

  • .dout(dout_o):这是 RAM 模块的输出引脚,名为 dout,它是一个 8 位宽度的输出信号。在这个实例中,它被连接到了一个名为 dout_o 的信号。

  • .clk(clk):这是 RAM 模块的时钟输入引脚,用于同步数据写入和读取操作。它被连接到了一个名为 clk 的信号。

  • .oce(oce_i):这是 RAM 模块的输出使能输入引脚,用于控制 dout 信号是否输出数据。它被连接到了一个名为 oce_i 的信号。

  • .ce(ce_i):这是 RAM 模块的芯片使能输入引脚,用于控制 RAM 是否可以进行读写操作。它被连接到了一个名为 ce_i 的信号。

  • .reset(reset_i):这是 RAM 模块的复位输入引脚,用于将 RAM 恢复到初始状态。它被连接到了一个名为 reset_i 的信号。

  • .wre(wre_i):这是 RAM 模块的写使能输入引脚,用于控制是否可以写入数据到 RAM。它被连接到了一个名为 wre_i 的信号。

  • .ad(addr):这是 RAM 模块的地址输入引脚,用于指定要读取或写入的 RAM 单元的地址。它被连接到了一个名为 addr 的信号,该信号是 11 位宽度的。

  • .din(data_i):这是 RAM 模块的数据输入引脚,用于写入数据到 RAM。它被连接到了一个名为 data_i 的信号,该信号是 8 位宽度的。

每个引脚都是 RAM 模块与其外部接口之间的连接点,它们定义了模块如何与外部信号交互。在实际的设计中,您需要确保这些引脚被正确地连接到相应的信号,并且信号的类型和宽度与 RAM 模块的要求相匹配。

FPGA中BRAM和DRAM的区别

FPGA(现场可编程门阵列)中的BRAM(块RAM)和DRAM(动态RAM)是两种不同类型的存储器,它们在设计和使用上有着显著的区别:

  1. 类型和用途
  • BRAM:是静态RAM(SRAM)的一种形式,通常集成在FPGA芯片内部。它提供快速的存储解决方案,适用于需要高速、小容量存储的应用,如缓存、缓冲区或FPGA内部的数据存储。
  • DRAM:是一种动态RAM,与FPGA芯片外部连接。它具有更高的存储密度,但速度较BRAM慢。DRAM适用于需要大容量存储的应用,如图像处理、视频缓冲和大量数据存储。
  1. 存储机制
  • BRAM:作为静态RAM,它不需要刷新电路来维持数据。每个存储单元都使用六晶体管(6T)的SRAM细胞结构,这意味着它可以无限期地保持数据,直到被写入新数据。
  • DRAM:作为动态RAM,它需要定期刷新来维持数据。每个存储单元通常由一个电容器和一个晶体管组成,因此它的密度可以更高,但速度较慢,并且需要更复杂的控制逻辑。
  1. 性能特点
  • BRAM:提供单周期访问时间,这意味着访问数据几乎立即完成,适用于要求严格实时性能的应用。
  • DRAM:由于其刷新要求,访问速度较慢,通常需要多个时钟周期来访问数据。
  1. 集成度
  • BRAM:在FPGA芯片内部,与逻辑元素紧密集成,可以提供非常低的延迟访问。
  • DRAM:通常作为外部组件连接到FPGA,通过内存接口(如DDR)进行通信。
  1. 功耗
  • BRAM:由于其简单性和快速访问能力,通常功耗较低。
  • DRAM:由于需要刷新和复杂的控制逻辑,功耗通常更高。

在选择使用BRAM还是DRAM时,设计者需要根据应用需求、性能要求、成本考虑和功耗限制来做出决策。对于需要高速、小容量存储的应用,BRAM通常是更好的选择;而对于需要大容量存储的应用,DRAM可能是更合适的选择。

在FPGA中,BRAM(块RAM)可以被配置为单端口模式或双端口模式,这两种模式在数据访问方式上有所不同:

  1. 单端口模式
  • 在单端口模式下,BRAM有一个数据访问端口,即地址和数据线是共用的。
  • 在任何给定的时间,单端口BRAM只能进行一次读操作或写操作。如果在一个时钟周期内同时尝试进行读和写操作,通常会发生冲突,除非特定的FPGA具有特殊的管理机制。
  • 单端口模式适用于那些不需要同时进行读写操作的应用场景,或者那些可以接受顺序访问的应用场景。
  1. 双端口模式
  • 双端口模式允许BRAM同时通过两个独立的端口进行访问,每个端口都有自己的地址线、数据线和控制线。
  • 这意味着双端口BRAM可以在同一时钟周期内进行一次读操作和一次写操作,或者同时进行两次读操作,访问不同的地址。
  • 双端口模式适用于需要同时或并行访问存储器中不同位置的应用场景,如图像处理、缓存和乒乓缓冲等。

在某些FPGA中,BRAM还可以配置为更高级的端口模式,如四端口模式,这允许更多的并行访问。设计者根据具体应用的需求来选择最合适的端口模式,以优化性能和资源利用。

十六进制数系统中的每个数字代表4位二进制数

在Verilog中,defparam是一个编译器指令,用于在模块实例化时重定义参数的值。这条指令可以用来改变模块实例化时参数的默认值。

在Verilog中,localparam关键字用于声明一个模块内部的参数,这个参数在模块的整个作用域内都是常量。localparam声明的参数是不可变的,它们的值在编译时就已经确定了。