我正在尝试从大小为 7,140,000 的 ArrayList 中删除 140,000 个对象。我预计这会花费几秒钟(如果那样的话)，但 Java 每千个对象花费几秒钟。这是我的代码:
for (int i = list.size(); i > P; i--)
{
int size = list.size();
int index = (int) (Math.random() * size);
list.remove(index);
}
注意:P 是我之前设置为 7,000,000 的常数。
循环的目标是从列表中随机删除对象，直到其大小为 7,000,000。
Java 需要这么长时间是因为我从超过 700 万个对象开始吗？过去我从来没有注意到从 ArrayLists 中删除的效率问题。如果有帮助，我会使用 DrJava Beta IDE。
最佳答案
每次从 ArrayList 中删除一个元素时，它都必须将所有具有更大索引的元素向下打乱一个位置。假设您删除了 7M 元素列表的第一个元素 - 然后您还必须移动 6,999,999 个元素。
如果您在循环中执行此操作，则需要 O(n^2)时间，在哪里n是列表的大小。对于 700 万个元素的列表，这会非常慢。
相反，如果您事先知道要删除哪些元素，则可以一次将所有元素向下移动:
int dst = 0;
for (int src = 0; src < list.size(); ++src) {
if (!toRemove(src)) {
list.set(dst++, list.get(src));
}
}
list.subList(dst, list.size()).clear();
哪里toRemove(src)是一些函数，它表示您是否要删除 src -th 元素。
例如，您可以构造一个 BitSet除了P元素集:
BitSet toRemove = new BitSet(list.size());
for (int i = list.size(); i > P; i--) {
int rand;
do {
rand = Math.random() * list.size();
} while (toRemove.get(rand));
toRemove.set(rand, true);
}
如果您只是从 7M 元素列表中删除零元素，您仍然需要将所有 6,999,999 个元素向右移动；但任何其他删除都不需要在顶部进行任何更多的转换。这个算法是O(n) ，其中 n 是列表的大小。
编辑:您可以选择 P列表中的元素(其中 P <= list.size() )如下所示:
int dst = 0;
Random rand = new Random();
for (int src = 0; dst < P; ++src) {
if (rand.nextInt(list.size() - src) < (P-dst)) {
list.set(dst++, list.get(src));
}
}
list.subList(dst, list.size()).clear();
此策略将以相等的概率 (*) 从列表中选择元素，并且适用于 P 的任何值。 ;它还保留了原始顺序。
如果要 sample K带有 N 的列表中的项目没有两次绘制相同元素的项目，有choose(N, K) = N! / (K! * (N-K)!)方法来做到这一点。如果你想以相同的概率从列表中选择所有元素，那么你应该选择这些 c(n,k) 中的任何一个。不同的配置。
当有 k待挑选的元素 n项，您将:
k-1剩余的元素 n-1项目;或k剩余的元素 n-1项目。为了保证等概率的挑到K元素整体，需要根据组合的个数在两个选项中选择一个从n-1中挑选元素:
#(combinations after taking first item)
P(take first item) = ------------------------------------------------------------------
#(combinations after taking) + #(combinations after not taking)
= C(n-1,k-1) / (C(n-1, k-1) + C(n-1, k))
= ... working omitted ...
= k / n
所以，当你有 k需要从 n 拿走的元素, 你应该拿第一项 k/n的时间。
需要指出的两个有趣案例是:
k == n , k/n = 1 ，所以你总是取元素。直觉上，如果你必须选择 n n 中的项目，你必须把它们全部拿走。k == 0 , k/n = 0 ，所以你永远取元素。直觉上，如果您已经选择了所有 K您的元素，您不需要再拿走。要实现这一点，您可以简单地生成一个均匀分布的随机数 r在 [0..n) 范围内, 如果 r < k 则从列表中“取出”元素.
就上述实现而言，k = P - dst , 和 n = list.size() - src .
关于java - 在 Java ArrayList 中删除对象 - 耗时，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46419578/
总的来说，我对ruby还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用
在控制台中反复尝试之后，我想到了这种方法，可以按发生日期对类似activerecord的(Mongoid)对象进行分组。我不确定这是完成此任务的最佳方法，但它确实有效。有没有人有更好的建议，或者这是一个很好的方法？#eventsisanarrayofactiverecord-likeobjectsthatincludeatimeattributeevents.map{|event|#converteventsarrayintoanarrayofhasheswiththedayofthemonthandtheevent{:number=>event.time.day,:event=>ev
我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为
查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html
我有一个表单，其中有很多字段取自数组(而不是模型或对象)。我如何验证这些字段的存在？solve_problem_pathdo|f|%>... 最佳答案 创建一个简单的类来包装请求参数并使用ActiveModel::Validations。#definedsomewhere,atthesimplest:require'ostruct'classSolvetrue#youcouldevencheckthesolutionwithavalidatorvalidatedoerrors.add(:base,"WRONG!!!")unlesss
好的，所以我的目标是轻松地将一些数据保存到磁盘以备后用。您如何简单地写入然后读取一个对象？所以如果我有一个简单的类classCattr_accessor:a,:bdefinitialize(a,b)@a,@b=a,bendend所以如果我从中非常快地制作一个objobj=C.new("foo","bar")#justgaveitsomerandomvalues然后我可以把它变成一个kindaidstring=obj.to_s#whichreturns""我终于可以将此字符串打印到文件或其他内容中。我的问题是，我该如何再次将这个id变回一个对象？我知道我可以自己挑选信息并制作一个接受该信
我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的
如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象
我在Rails工作并有以下类(class):classPlayer当我运行时bundleexecrailsconsole然后尝试:a=Player.new("me",5.0,"UCLA")我回来了:=>#我不知道为什么Player对象不会在这里初始化。关于可能导致此问题的操作/解释的任何建议？谢谢，马里奥格 最佳答案 havenoideawhythePlayerobjectwouldn'tbeinitializedhere它没有初始化很简单，因为你还没有初始化它!您已经覆盖了ActiveRecord::Base初始化方法，但您没有调
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/