当前位置: 首页 > news >正文

treap使用mt19937会导致问题原因分析

Treap 是一种使用随机数生成器来维护树形结构的数据结构,而 mt19937 是一种常用的伪随机数生成器。虽然 mt19937 可以生成高质量的随机数序列,但是在 Treap 中使用它可能会导致一些问题。

mt19937 返回的是一个 unsigned int

其中一个问题是,mt19937 生成的随机数序列是确定的,也就是说,如果使用相同的种子值,每次生成的随机数序列都是相同的。这就会导致 Treap 在使用相同的种子值时,生成的树形结构也是相同的,这可能会降低 Treap 的性能和安全性。

另一个问题是,mt19937 生成的随机数序列是均匀分布的,而 Treap 中需要的随机数却是符合概率分布的,因此 mt19937 不能很好地满足 Treap 中的需求。

为了解决这些问题,Treap 中通常会使用更高质量的随机数生成器,如 PCGXORSHIFT 等。这些随机数生成器生成的随机数序列更加随机和均匀,可以更好地满足 Treap 的需求。

写下这篇文章,是因为我在写 treap 的时候使用 mt19937 导致代码测试错误,我将其改成 LLLLLL 类型的 valvalval 后可以正常 AC,于是就有了上述的问题,于是就写下这篇文章记录一下!

http://www.lryc.cn/news/27259.html

相关文章:

  • tmux和vim
  • 2023年全国最新保安员精选真题及答案12
  • Hbase的基本概念与架构
  • 颠覆你的认知,业务同事都能开发软件,我简直无地自容……
  • 01 | n2n虚拟局域网
  • MFC界面控件BCGControlBar v33.4 - 支持Win 11 Mica material主题
  • 手把手教你用js实现手机通讯录功能(附源码)
  • 【C/C++】逗号表达式、算术运算符优先级
  • 携禾生物面试总结
  • FPGA纯verilog手写HDMI发送IP 提供源码和技术支持
  • 【知识点】OkHttp 原理 8 连问
  • 【python】深入了解Selenium-PageObject
  • PAT——7-4 简易测谎 (20 分)
  • 【力扣】 面试题 05.02.二进制数转字符串(超过c++100%)
  • 软件质量保证与测试 课堂笔记
  • Costco好市多验厂百问百答
  • Nginx 通过 header 中的标识进行分发
  • 如何实现《电子签名法》要求的可靠电子签名?
  • 工程项目管理软件有哪些?这六款很好用!
  • 多看看spdk代码学习
  • 宾语从句it做形式主语的句子
  • 【C#基础】C# 文件与IO
  • 死锁相关介绍【内含哲学家就餐问题】
  • Java的Groovy执行器内存泄露(MetaSpace)问题分析与解决办法
  • 【linux】进程信号——信号的产生
  • 部署OpenStack
  • Java 运算符与类型转化
  • 《C++ Primer Plus》第18章:探讨 C++ 新标准(2)
  • QML定时器
  • 第三章 opengl之纹理