草庐IT

java - 有效地从列表中选择 N 个随机元素(无需 toArray 并更改列表)

coder 2024-03-05 原文

如标题所示，我想使用 Knuth-Fisher-Yates 洗牌算法从列表中选择 N 个随机元素，但不使用 List.toArray 并更改列表。这是我当前的代码:

public List<E> getNElements(List<E> list, Integer n) {
    List<E> rtn = null;

    if (list != null && n != null && n > 0) {
        int lSize = list.size();
        if (lSize > n) {
            rtn = new ArrayList<E>(n);
            E[] es = (E[]) list.toArray();
            //Knuth-Fisher-Yates shuffle algorithm 
            for (int i = es.length - 1; i > es.length - n - 1; i--) {
                int iRand = rand.nextInt(i + 1);
                E eRand = es[iRand];
                es[iRand] = es[i];
                //This is not necessary here as we do not really need the final shuffle result.
                //es[i] = eRand;
                rtn.add(eRand);
            }

        } else if (lSize == n) {
            rtn = new ArrayList<E>(n);
            rtn.addAll(list);
        } else {
            log("list.size < nSub! ", lSize, n);
        }
    }

    return rtn;
}

它使用 list.toArray() 来创建一个新数组以避免修改原始列表。但是，我现在的问题是我的列表可能非常大，可能有 100 万个元素。然后 list.toArray() 太慢了。我的 n 可以在 1 到 100 万之间。当 n 很小时(比如 2)，该函数效率非常低，因为它仍然需要对 100 万个元素的列表执行 list.toArray()。

有人可以帮助改进上面的代码，使其在处理大型列表时更有效率。谢谢。

这里我假设 Knuth-Fisher-Yates shuffle 是完成从列表中选择 n 个随机元素的最佳算法。我对吗？如果有比 Knuth-Fisher-Yates shuffle 更好的其他算法在速度和结果质量(保证真正的随机性)方面完成这项工作，我将非常高兴。

更新:

这是我的一些测试结果:

当从1000000个元素中选择n个时。

当 n<1000000 时，最快的方法是使用="" daniel="" lemire="" 的="" bitmap="" 函数先选择="" n="" 个随机="" id，然后获取具有这些="" id="">

public List<E> getNElementsBitSet(List<E> list, int n) {
        List<E> rtn = new ArrayList<E>(n);
        int[] ids = genNBitSet(n, 0, list.size());
        for (int i = 0; i < ids.length; i++) {
            rtn.add(list.get(ids[i]));
        }
        return rtn;
    }

genNBitSet 使用来自 https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java 的代码 generateUniformBitmap|

当 n>1000000/4 时，水库采样方法更快。

所以我构建了一个函数来结合这两种方法。

最佳答案

您可能正在寻找类似 Resorvoir Sampling 的内容.

从具有前 k 个元素的初始数组开始，然后用概率递减的新元素修改它:

类java伪代码:

E[] r = new E[k]; //not really, cannot create an array of generic type, but just pseudo code
int i = 0;
for (E e : list) {
   //assign first k elements:
   if (i < k) { r[i++] = e; continue; }
   //add current element with decreasing probability:
   j = random(i++) + 1; //a number from 1 to i inclusive
   if (j <= k) r[j] = e;
}
return r;

这需要对数据进行单次传递，每次迭代都使用非常便宜的操作，并且空间消耗与所需的输出大小成线性关系。

关于java - 有效地从列表中选择 N 个随机元素(无需 toArray 并更改列表)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23719990/

中选toArraylistsectioncodejavaalgorithmrandom

有关java - 有效地从列表中选择 N 个随机元素(无需 toArray 并更改列表)的更多相关文章

  1. ruby-on-rails - Ruby on Rails 迁移，将表更改为 MyISAM - 2

    如何正确创建Rails迁移，以便将表更改为MySQL中的MyISAM？目前是InnoDB。运行原始执行语句会更改表，但它不会更新db/schema.rb，因此当在测试环境中重新创建表时，它会返回到InnoDB并且我的全文搜索失败。我如何着手更改/添加迁移，以便将现有表修改为MyISAM并更新schema.rb，以便我的数据库和相应的测试数据库得到相应更新？ 最佳答案 我没有找到执行此操作的好方法。您可以像有人建议的那样更改您的schema.rb，然后运行:rakedb:schema:load，但是，这将覆盖您的数据。我的做法是(假设

  2. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  3. ruby-on-rails - 项目升级后 Pow 不会更改 ruby​​ 版本 - 2

    我在我的Rails项目中使用Pow和powifygem。现在我尝试升级我的ruby​​版本(从1.9.3到2.0.0，我使用RVM)当我切换ruby​​版本、安装所有gem依赖项时，我通过运行railss并访问localhost:3000确保该应用程序正常运行以前，我通过使用pow访问http://my_app.dev来浏览我的应用程序。升级后，由于错误Bundler::RubyVersionMismatch:YourRubyversionis1.9.3,butyourGemfilespecified2.0.0，此url不起作用我尝试过的:重新创建pow应用程序重启pow服务器更新战俘

  4. ruby - Capistrano 3 在任务中更改 ssh_options - 2

    我尝试使用不同的ssh_options在同一阶段运行capistranov.3任务。我的production.rb说:set:stage,:productionset:user,'deploy'set:ssh_options,{user:'deploy'}通过此配置，capistrano与用户deploy连接，这对于其余的任务是正确的。但是我需要将它连接到服务器中配置良好的an_other_user以完成一项特定任务。然后我的食谱说:...taskswithoriginaluser...task:my_task_with_an_other_userdoset:user,'an_othe

  5. 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/

  6. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  7. jquery - 我的 jquery AJAX POST 请求无需发送 Authenticity Token (Rails) - 2

    rails中是否有任何规定允许站点的所有AJAXPOST请求在没有authenticity_token的情况下通过？我有一个调用Controller方法的JqueryPOSTajax调用，但我没有在其中放置任何真实性代码，但调用成功。我的ApplicationController确实有'request_forgery_protection'并且我已经改变了config.action_controller.consider_all_requests_local在我的environments/development.rb中为false我还搜索了我的代码以确保我没有重载ajaxSend来发送

  8. ruby - 更改 ActiveRecord 中对象的类 - 2

    假设我有一个FireNinja我的数据库中的对象，使用单表继承存储。后来才知道他真的是WaterNinja.将他更改为不同的子类的最干净的方法是什么？更好的是，我很想创建一个新的WaterNinja对象并替换旧的FireNinja在数据库中，保留ID。编辑我知道如何创建新的WaterNinja来self现有FireNinja的对象，我也知道我可以删除旧的并保存新的。我想做的是改变现有项目的类别。我是通过创建一个新对象并执行一些ActiveRecord魔法来替换行，还是通过对对象本身做一些疯狂的事情，或者甚至通过删除它并使用相同的ID重新插入来做到这一点，这是问题的一部分。

  9. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  10. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

随机推荐