无序度编程

‘壹’ 极智编程 | 谈谈 C++ 中容器 map 和 unordered_map 的区别

C++中容器map和unordered_map的主要区别如下：

1. 引入标准：

   • map：是C++98标准就引入的容器。
   • unordered_map：是C++11标准后引入的容器，使用时需确保编译器支持C++11或更高版本。

2. 存储方式：

   • map：按照键的排序进行存储，因此查询结果是有序的。
   • unordered_map：不保证键的顺序，存储方式是散列表，因此查询、插入、删除操作通常较快，但查询结果无序。

3. 性能：

   • map：由于需要维护键的排序，查找、插入、删除操作的平均时间复杂度为O。
   • unordered_map：基于散列表实现，查找、插入、删除操作的平均时间复杂度为O，但在最坏情况下可能退化为O。

4. 使用场景：

   • map：适用于需要保持键有序的场景，如需要按键的顺序进行遍历或查找。
   • unordered_map：适用于对查询速度要求较高，但不关心键顺序的场景。

综上所述，C++中的map和unordered_map各有优缺点，选择哪个容器取决于具体的应用场景和需求。

‘贰’ 信息论系列：1 - 信息熵和香农熵

信息熵和香农熵

一、信息熵

信息熵是衡量信息不确定性的一个概念，源自物理学中的熵，用于描述系统的无序程度。在信息论中，信息熵衡量的是信息内容的不确定性或随机性。信息的熵越高，意味着它包含的信息量越大，消除不确定性的能力就越强。

• 定义：信息熵是一个数学定义，用来描述一个信息源可能产生的所有信息的平均不确定性。假设有一个随机变量 X，它有多个可能的结果，每个结果发生的概率分别为 p(x)。信息熵 H(X) 定义为：H(X) = -Σ p(x) log p(x)。这里的 log 表示对数，通常使用二进制对数（底数为2），这样熵的单位是比特（bit）。
• 意义：每个结果的熵值乘以其发生概率的和代表了这个信息源的平均不确定性。信息熵可以理解为信息的“惊喜度”。如果一个事件的结果非常出乎意料，它提供的信息就更多，相应的熵就更高。
• 应用：信息熵不仅在理论上重要，也是实际应用中数据编码、存储和传输优化的关键。了解和计算信息熵，可以帮助我们更有效地设计通信系统和数据存储方案。

二、香农熵

香农熵是信息熵概念的一个特定应用，在信息度量和通信理论中至关重要。实际上，“信息熵”和“香农熵”是指同一个数学概念，只是叫法不同。

• 定义与公式：香农熵也通过公式 H(X) = -Σ p(x) log2 p(x) 来计算，这里的 H(X) 表示熵，p(x) 是某个事件发生的概率，而 log2 是以2为底的对数。
• 概念：香农熵用于描述和量化信息的不确定性，这种度量对于理解和优化信息处理、存储和传输至关重要。
• 叫法的由来：

  香农熵：术语“香农熵”是为了纪念信息论之父克劳德·香农而命名的。香农在1948年的开创性论文中首次提出了这个概念，从而奠定了现代信息论的基础。

  信息熵：而“信息熵”这个名字则更侧重于概念本身，强调其作为信息理论中的一个基本量度。

• 实际应用：

  数据压缩：香农熵帮助我们确定了理论上的最佳数据压缩限度。通过减少信息的冗余来降低信息的熵，从而实现更高效的数据存储和传输。现代数据压缩技术，如ZIP和JPEG格式，都是基于理解香农熵原理设计的。

  通信系统：在通信系统设计中，香农熵用于评估信息的传输效率。它可以帮助设计更有效的编码方案，从而在有限的带宽内传输尽可能多的信息。此外，香农熵还与信道容量的概念密切相关，后者指的是在特定的通信信道中，能够可靠传输数据的最大速率。

  密码学：在密码学中，香农熵用于评估加密系统的强度。一个高熵的加密密钥意味着攻击者更难猜测，从而使加密系统更加安全。同时，香农熵还被用来评估密码系统可能面临的风险，帮助加密专家设计出更安全的加密协议。

  决策和机器学习：在决策树算法中，香农熵用于计算信息增益，帮助确定在哪个属性上分割数据可以最大化信息的提取。在机器学习中，通过分析数据的熵，可以更好地理解和预测数据模式。

三、总结

信息熵和香农熵为我们理解信息的本质提供了数学工具，使我们能够量化信息的不确定性和复杂性。在实际应用中，这些概念帮助我们优化数据处理流程，提高通信效率，增强密码系统的安全性，以及在机器学习领域实现更有效的数据分析和决策。随着技术的进步和新的应用需求的出现，信息熵和香农熵的理论将继续在新的领域中发挥作用。

‘叁’ 怎样理解混乱度为什么熵可以表示混乱度

混乱度是指系统状态的丰富度，反映了系统的无序程度；熵是混乱度的数学表示，可以量化系统的无序状态。

关于混乱度的理解： 状态数增多即混乱度升高：混乱度与系统可能的状态数密切相关。当系统的状态数越多，意味着系统的可能性越多，混乱度也就越高。 粒子自由穿梭体现混乱：在物理学中，可以想象无数粒子在空间中自由穿梭，这种状态就代表了较高的混乱度。

熵作为混乱度的表示： 熵的数学表达：熵是一个数学量，通过特定的公式来计算，能够量化系统的混乱度。 掷骰子示例：以掷骰子为例，每一个可能的结果都对应一个状态，熵就是这些状态的总和，揭示了系统的不确定性和无序性。 系统内部自然趋势：在稳定系统中，如气体分子的无序分布，熵的增加反映了系统内部倾向于无序化的自然趋势。

熵与混乱度的关系： 熵增加与无序化：熵的增加通常意味着系统无序程度的增加，如两个温度相同的气团合并，虽然粒子全同，但状态数的增多导致熵增加，反映了系统内部的自然无序化趋势。 信息熵的例外：虽然熵通常与混乱度同向，但信息熵是一个例外。信息熵是系统状态概率的平均，当所有状态概率相等时，熵最大，表现出最大的无序；相反，当概率高度集中时，熵则最小，系统呈现有序状态。