只是为了练习(而不是作业作业),我一直在试图解决这个问题(Clrs,第3版,练习11.2-6):

Suppose we have stored n keys in a hash table of size m,with
collisions resolved by chaining,and that we kNow the length of each
chain,including the length L of the longest chain. Describe a
procedure that selects a key uniformly at random from among the keys
in the hash table and returns it in expected time O(L * (1 + m/n)).

到目前为止,我认为每个键的返回概率是1 / n.如果我们尝试得到1到n之间的随机值x,并尝试按顺序首先按桶排序,然后沿着桶中的链排列找到第x个密钥,那么将通过进行O(m)找到合适的桶通过桶逐个和O(L)时间获得链中的正确键.

解决方法

重复以下步骤,直到返回一个元素:

>随机选择一个桶.令k是桶中元素的数量.
>从1 … L随机选择p均匀.如果p <= k则返回桶中的第p个元素.
应该清楚的是,该过程会随机均匀地返回一个元素.我们对排列在2D阵列中的元素应用拒绝采样.

每桶的预期数量为n / m.采样尝试成功的概率为(n / m)/ L.因此,找到一个存储桶所需的尝试次数为L * m / n.与从桶中检索元素的O(L)成本一起,预期运行时间为O(L *(1 m / n)).

算法 – 有效地从链接哈希表中挑选一个随机元素?的更多相关文章

  1. swift算法实践2

    字符串hash算法Time33在效率和随机性两方面上俱佳。对于一个Hash函数,评价其优劣的标准应为随机性,即对任意一组标本,进入Hash表每一个单元之概率的平均程度,因为这个概率越平均,数据在表中的分布就越平均,表的空间利用率就越高。Times33的算法很简单,就是不断的乘33,见下面算法原型。

  2. 深度学习中的五大正则化方法和七大优化策略

    utm_source=tuicool&utm_medium=referral深度学习中的正则化与优化策略一直是非常重要的部分,它们很大程度上决定了模型的泛化与收敛等性能。本文主要以深度卷积网络为例,探讨了深度学习中的五项正则化与七项优化策略,并重点解释了当前最为流行的Adam优化算法。为了解决这些问题,近年来研究者开发了多种正则化和优化策略。机器学习中最常用的正则化方法是对权重施加L2范数约束。

  3. php – 如何生成这种随机曲线?

    是否有可能产生这种随机曲线?

  4. Java(或任何语言)中的随机混乱概率

    虽然我理解算法,但我不理解他的概率计算.他说,因为Random使用32位种子,这仅限于2^32种不同的排列.他还说knuth的算法更好,因为它给你N!排列.我同意knuth的算法计算.但我认为在第一个上应该有N^N个不同的排列.塞奇威克错了还是我错过了一个事实?

  5. Java 8:IntStream到Integer []

    我正在编写简单的程序,它最终会绘制用Java编写的各种排序算法的运行时间.排序算法的一般接口是通过一种方法:publicvoidsort我试图使用Java8的流机制生成以下几行的随机测试用例:我的问题是,如何将IntStream类型的对象转换为Integer[]?解决方法您应该将IntStreambox转换为流,然后调用toArray来生成它的数组:

  6. c – random_shuffle算法 – 是否产生了没有随机生成函数的相同结果?

    如果没有为标准库中的random_shuffle算法提供随机生成器函数,如果提供相同的数据,程序的连续运行是否会生成相同的随机序列?解决方法25.2.11只是说元素是均匀分布的.它不能保证在幕后使用哪个RNG,因此您不能依赖任何此类行为.为了保证相同的洗牌结果,您需要提供自己的RNG来提供这些保证,但我怀疑即使这样,如果您更新标准库,random_shuffle算法本身也可以改变效果.

  7. delphi – 随机化StringList

    如何在StringList中随机化String,同样地,这个在线工具如何工作.如果有人熟悉它,请检查:http://textmechanic.co/Randomize-List.html解决方法执行随机播放的一个常见算法是Fisher-Yatesshuffle.这产生均匀分布的排列.要在DelphiTStrings对象上实现,可以使用:现在,理论上,这将产生均匀分布的排列,实际的性能在很大程度上取

  8. 算法 – 有效地从链接哈希表中挑选一个随机元素?

    L随机选择p均匀.如果p

  9. C tr1 unordered_set随机唯一子集的最快方法

    这个问题与此有关thisone,更确切地说是this回答它.这里是:我有一个无符号整数的C/TR1unordered_setU(粗基数100-50000,粗略值范围0到10^6).给定基数N,我希望尽可能快地迭代N随机但是U的独特成员.N没有典型值,但它应该为小N快速工作.更详细地说,这里的“随机性”的概念是两个调用应该产生一些不同的子集–越不同,越好,但这不是太关键.我会…对连续感到高兴(或缠绕

  10. Perlin / Simplex噪声算法的随机性质是什么?

    PerlinNoise算法和Simplex噪声算法的随机性质是什么?哪两种算法具有更好的随机性?与标准伪随机生成器相比,使用Perlin/Simplex作为随机数生成器是否有意义?

随机推荐

  1. 基于EJB技术的商务预订系统的开发

    用EJB结构开发的应用程序是可伸缩的、事务型的、多用户安全的。总的来说,EJB是一个组件事务监控的标准服务器端的组件模型。基于EJB技术的系统结构模型EJB结构是一个服务端组件结构,是一个层次性结构,其结构模型如图1所示。图2:商务预订系统的构架EntityBean是为了现实世界的对象建造的模型,这些对象通常是数据库的一些持久记录。

  2. Java利用POI实现导入导出Excel表格

    这篇文章主要为大家详细介绍了Java利用POI实现导入导出Excel表格,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

  3. Mybatis分页插件PageHelper手写实现示例

    这篇文章主要为大家介绍了Mybatis分页插件PageHelper手写实现示例,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪

  4. (jsp/html)网页上嵌入播放器(常用播放器代码整理)

    网页上嵌入播放器,只要在HTML上添加以上代码就OK了,下面整理了一些常用的播放器代码,总有一款适合你,感兴趣的朋友可以参考下哈,希望对你有所帮助

  5. Java 阻塞队列BlockingQueue详解

    本文详细介绍了BlockingQueue家庭中的所有成员,包括他们各自的功能以及常见使用场景,通过实例代码介绍了Java 阻塞队列BlockingQueue的相关知识,需要的朋友可以参考下

  6. Java异常Exception详细讲解

    异常就是不正常,比如当我们身体出现了异常我们会根据身体情况选择喝开水、吃药、看病、等 异常处理方法。 java异常处理机制是我们java语言使用异常处理机制为程序提供了错误处理的能力,程序出现的错误,程序可以安全的退出,以保证程序正常的运行等

  7. Java Bean 作用域及它的几种类型介绍

    这篇文章主要介绍了Java Bean作用域及它的几种类型介绍,Spring框架作为一个管理Bean的IoC容器,那么Bean自然是Spring中的重要资源了,那Bean的作用域又是什么,接下来我们一起进入文章详细学习吧

  8. 面试突击之跨域问题的解决方案详解

    跨域问题本质是浏览器的一种保护机制,它的初衷是为了保证用户的安全,防止恶意网站窃取数据。那怎么解决这个问题呢?接下来我们一起来看

  9. Mybatis-Plus接口BaseMapper与Services使用详解

    这篇文章主要为大家介绍了Mybatis-Plus接口BaseMapper与Services使用详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪

  10. mybatis-plus雪花算法增强idworker的实现

    今天聊聊在mybatis-plus中引入分布式ID生成框架idworker,进一步增强实现生成分布式唯一ID,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

返回
顶部