草庐IT

java - 在一个范围内随机选择 k 个不同的数字

coder 2024-03-18 原文

我需要选择 k 0 to n-1 范围内的随机元素. n可以达到 10^9。和 k范围可以从 1 to n-1 .我只需将包含值 0 to n-1 的数组改组即可在 O(n) 时间内完成此操作然后先选择k它的元素。但是当k很小，这种方法的时间和内存效率都很低。这个问题有O(k)的解决方案吗？

注:已选k数字必须不同。

我正在考虑解决方案。我可以想到两种方法。让R是要返回的集合。

  1. 在范围内选择一个随机值并将其添加到R .继续这样做直到 |R| = k .此过程需要 sum(n/i) for n+1-k <= i <= n时间和 O(k) 空间。
  2. 在数组中插入0到n-1，打乱顺序，先取k它的元素。这个过程需要O(n+k)的时间和空间。

所以对于给定的 k我可以在 O(k) 时间内选择更可取的方法。

最佳答案

改进的 Fisher-Yates 算法

可以改进混洗解决方案，因为您只需混洗数组的前 k 个元素。但这仍然是 O(n)，因为简单的随机播放实现需要一个大小为 n 的数组，需要将其初始化为 n 值0 到 n-1。

Initialize value[n] to {0..n-1}
For i from 0 to k-1:
  swap(value[i], value[random_in_range(i, n)])
Result is value[0..k-1]

为了改进这一点，我们可以使用一种虚拟数组，由两部分组成:

  1. value:前 k 个元素的数组，这将是结果选择。这被初始化为 {0..k-1}

  2. rest:容量为 k 个条目的稀疏数据结构(例如哈希表)，包含数组的所有剩余条目，这些条目不是简单的自己的指数。最初是空的。

现在我们可以定义从值数组中交换元素i和j的函数(注意:ik，由上述算法保证):

# To swap elements i and j
If j < k:
  # Both elements to be swapped are in the selection
  tmp = value[i]; value[i] = value[j]; value[j] = tmp
Else If j in rest:
  # Element j has been swapped before
  tmp = value[i]; value[i] = rest[j]; rest[j] = tmp
Else:
  # The value at j is still j, we now add it to the virtual array
  rest[j] = value[i]; value[i] = j

对于 k≤n 的任意值，使用 O(k) 空间和时间。

三种算法攻略

一个使用 O(k) 内存的更简单的解决方案是只保留所有选定值的哈希表，并生成值直到哈希表包含 k 个值，拒绝重复.

对于较小的 k，随机选择的元素重复的概率微不足道，朴素哈希表无疑是最简单的解决方案。另一方面，如果 k 是 n 的重要部分，哈希表主要是浪费空间，因为大小为 n 足以记录已看到哪些值。对于非常大的 k，随着样本填满，拒绝算法将花费太多时间，并且洗牌所需的完整 vector 不会比用于保存样本的 vector 多多少空间样本。

因此，实用的解决方案可能是使用三个解决方案中占用较少空间和时间的任何一个:对于足够大的 k 值，n 位bitvector 小于具有 k 个条目的哈希表，但不会大到拒绝概率显着(例如，n/64≤k ≤n/4)，使用位 vector 。对于较小的 k 值，使用简单的哈希表算法，对于接近 n 的 k 值，在完整的 n 元素 vector (但限于 k 步)。

因为我们只在 k>cn 的情况下才选择 O(n) 策略常数 c，复合算法仍然是 O(k) 时间和空间，因为在该约束下，n 在 O(k )。

关于java - 在一个范围内随机选择 k 个不同的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30558866/

java在一个emcodevaluealgorithmsortingrandom

有关java - 在一个范围内随机选择 k 个不同的数字的更多相关文章

  1. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  2. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

    我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何

  3. ruby-on-rails - 渲染另一个 Controller 的 View - 2

    我想要做的是有2个不同的Controller，client和test_client。客户端Controller已经构建，我想创建一个test_clientController，我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集，然后呈现客户端Controller的索引View，以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>

  4. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  5. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  6. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  7. ruby - 触发器 ruby​​ 中 3 点范围运算符和 2 点范围运算符的区别 - 2

    请帮助我理解范围运算符...和..之间的区别，作为Ruby中使用的“触发器”。这是PragmaticProgrammersguidetoRuby中的一个示例:a=(11..20).collect{|i|(i%4==0)..(i%3==0)?i:nil}返回:[nil,12,nil,nil,nil,16,17,18,nil,20]还有:a=(11..20).collect{|i|(i%4==0)...(i%3==0)?i:nil}返回:[nil,12,13,14,15,16,17,18,nil,20] 最佳答案 触发器(又名f/f)是

  8. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  9. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  10. ruby-on-rails - Rails - 从另一个模型中创建一个模型的实例 - 2

    我有一个正在构建的应用程序，我需要一个模型来创建另一个模型的实例。我希望每辆车都有4个轮胎。汽车模型classCar轮胎模型classTire但是，在make_tires内部有一个错误，如果我为Tire尝试它，则没有用于创建或新建的activerecord方法。当我检查轮胎时，它没有这些方法。我该如何补救？错误是这样的:未定义的方法'create'forActiveRecord::AttributeMethods::Serialization::Tire::Module我测试了两个环境:测试和开发，它们都因相同的错误而失败。 最佳答案

随机推荐