Suppose you have a large ASCII text file, with a random non-negative integer on each line, each in the range from 0 to 1,000,000,000. There are 100,000,000 lines in the file. What's the fastest way to read through the file and calculate the sum of all the integers?
Constraint: we've got 10MB of RAM to work with. The file is 1GB in size, so we don't want to read the whole thing in and then process it.
Here are …
TL; DR版本,对于那些不想要背景的人,是以下具体问题:
为什么Java没有真正的多维数组的实现？有坚实的技术原因吗？我在这里错过了什么？
Java在语法级别具有多维数组,可以声明
int[][] arr = new int[10][10];
但似乎这真的不是人们所期望的.它不是让JVM分配足够大的连续RAM块来存储100 int秒,而是作为ints 的数组阵列出现:所以每个层都是一个连续的RAM块,但整体而言并非如此.arr[i][j]因此访问速度相当慢:JVM必须这样做
int[]存储的arr[i];int存储的arr[i][j].这涉及查询对象从一层到另一层,这是相当昂贵的.
在一个层面上,不难看出为什么这不能被优化为简单的扩展和添加查找,即使它们都被分配在一个固定块中.问题是arr[3]它本身就是一个引用,它可以被改变.因此,尽管数组具有固定大小,但我们可以轻松编写
arr[3] = new int[11];
现在,由于这一层已经成长,因此缩放和加载是固定的.您需要在运行时知道是否所有内容仍然与以前相同.此外,当然,这将被分配到RAM中的其他地方(它必须是,因为它比它更换的更大),所以它甚至不适合扩展和添加.
在我看来,这并不理想,这有两个原因.
首先,它很慢.我使用这些方法运行的测试用于求和单维或多维数组的内容,对于多维情况(a 和a 分别填充随机值,运行1000000次,温度)几乎是两倍长(714秒对371秒)高速缓存).int[1000000]int[100][100][100]int
public static long sumSingle(int[] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
total+=arr[i];
return total;
}
public static long sumMulti(int[][][] arr) {
long total = 0; …我决定尝试一些实验,看看我能发现堆栈帧的大小,以及当前执行代码在堆栈中的距离.我们可能会在这里调查两个有趣的问题:
StackOverflowError？这是我能想到的最好的:
public static int levelsDeep() {
try {
throw new SomeKindOfException();
} catch (SomeKindOfException e) {
return e.getStackTrace().length;
}
}
这看起来有点黑客.它生成并捕获异常,然后查看堆栈跟踪的长度.
不幸的是,它似乎也有一个致命的限制,即返回的堆栈跟踪的最大长度为1024.除此之外的任何内容都被削减,因此此方法可以返回的最大值为1024.
题:
有没有更好的方法做到这一点,不是那么hacky并没有这个限制？
对于它的价值,我的猜测是没有:Throwable.getStackTraceDepth()是本机调用,它暗示(但不能证明)它不能用纯Java完成.
我们可以达到的等级数量将由(a)堆栈帧的大小和(b)剩余堆栈量确定.让我们不要担心堆栈框架的大小,只需看看我们达到之前可以达到多少级别StackOverflowError.
这是我执行此操作的代码:
public static int stackLeft() {
try {
return 1+stackLeft();
} catch (StackOverflowError e) {
return 0;
}
}
它的工作令人钦佩,即使它在堆栈剩余量方面是线性的.但这是非常非常奇怪的部分.在64位Java 7(OpenJDK 1.7.0_65)上,结果完全一致:9,923,在我的机器上(Ubuntu 14.04 64位).但Oracle的Java 8(1.8.0_25)给出了非确定性结果:我的记录深度在18,500到20,700之间.
现在为什么它是非确定性的呢？应该有一个固定的堆栈大小,不是吗？并且所有代码对我来说都是确定性的.
我想知道错误捕获是否奇怪,所以我尝试了这个:
public static long badSum(int n) {
if (n==0)
return 0;
else
return 1+badSum(n-1);
} …这似乎可以使用Java 7和任何版本的Scala库进行编译:
public static void main(String[] args) {
scala.collection.immutable.Set<String> set = new scala.collection.immutable.HashSet<String>();
Iterator<String> iterator = set.iterator();
}
它还可以编译Java 8和Scala 2.11.5+.但是使用Java 8和Scala 2.11.4,Eclipse抱怨:
The method iterator() is ambiguous for the type Set<String>
我不明白这一点.您可能会对在某些上下文中选择哪个重载方法感到不明确,但如果您没有传递任何参数,肯定不会？
真奇怪的是,如果我像这样重铸:
public static void main(String[] args) {
Iterator<String> iterator = new scala.collection.immutable.HashSet<String>().iterator();
}
投诉消失了.在我看来,这与上面的版本完全相同.那为什么它现在编译好了？
在下面的类中,由于调用模糊,我得到了Java 8的编译错误this().但是,使用Java 6,这个类编译得很好.我知道我可以使用工厂方法重构这个但是对于发生问题的实际类,我强烈希望现在维护当前的API.
任何人都可以想到一种方法来解决歧义而不改变外部API？
public class Vararg8 {
public Vararg8(final Object... os) {}
public Vararg8(final boolean b,
final String s,
final int... is) {}
public Vararg8() {
this(true, "test", 4, 5, 6);
}
}
今天（请不要杀死我）我使用了一个<blink>标签。
这只是一个测试：我需要一些文本放入一些代码中，以检查它是否正确地提供了HTML，因此我将其Hello world!包装在一个<blink>标签中。
我知道我做错了，我保证不会再做。
但是，我很惊讶地发现Firefox 34并没有使文本闪烁！这是可以预期的吗？Chrome和IE也会拒绝这样做吗？从技术上讲，这是实现HTML规范的失败吗？
显然，我永远不会<blink>在真实代码中使用标签。但是我确实记得，他们在1990年代首次出现时就让我震惊，我觉得我已经失去了一部分青春期，即使您知道那已经是青春期的绝妙部分了，这还是有些痛苦的。
我知道这Thread.stop()是被弃用的,并且有充分的理由:它通常不安全.但这并不意味着它永远不会安全......据我所知,它在我想要使用它的环境中是安全的; 而且,据我所见,我别无选择.
上下文是双人战略游戏的第三方插件:国际象棋将作为工作示例.第三方代码需要被赋予当前的董事会状态,并且(比方说)10秒来决定其移动.它可以返回其移动并在允许的时间内终止,或者它可以在任何时候发出信号,指示其当前的首选移动; 如果时间限制到期,则应该在其轨道上停止,并且应该播放其最近的首选移动.
编写插件以便在请求时正常停止不是一个选项:我需要能够采取任意不受信任的第三方插件.所以我必须有一些强行终止它的方法.
这是我正在做的锁定它:
SecurityManager:所有类都可以进行数字运算.Thread.join()任何未创建的线程.因此,似乎插件不能将任何东西保持在不一致的状态(除了它可能创建的任何对象,然后将被丢弃); 并且它不会影响任何其他线程(除了它产生的任何线程,它们将是相同的ThreadGroup,因此也将被杀掉).
它看起来好像Thread.stop()不赞成的原因在这里不适用(按设计).我错过了什么吗？这里还有危险吗？或者我是否仔细隔离了事情,以至于不存在问题？
还有更好的方法吗？我认为唯一的替代方案是启动一个全新的JVM来运行不受信任的代码,并在不再需要时强制终止该进程,但这还有其他一千个问题(昂贵,脆弱,依赖于操作系统).
请注意:我对答案不感兴趣,因为"噢,因为某种原因而被弃用,你想观看它,交配." 我知道它被弃用是有原因的,我完全理解为什么一般来说放弃笼子是不安全的.我要问的是,在这种情况下是否有一个特定的理由认为它是不安全的.
对于它的价值,这里是代码的(删节)相关位:
public void playMoveInternal(GameState game) throws IllegalMoveException,
InstantiationException, IllegalAccessException,
IllegalMoveSpecificationException {
ThreadGroup group = new ThreadGroup("playthread group");
Thread playthread = null;
group.setMaxPriority(Thread.MIN_PRIORITY);
GameMetaData meta = null;
StrategyGamePlayer player = null;
try {
GameState newgame = (GameState) …我正在阅读Robert Sedgwick关于算法的讲座视频,他解释说随机改组确保我们不会遇到快速排序中最坏情况的二次时间场景.但我无法理解如何.
信中的权利要求为二进制堆Wikipedia页面是插入是O(登录Ñ)在最坏的情况下,但O(1)平均:
所需的操作数量仅取决于新元素必须上升以满足堆属性的级别数,因此插入操作的最坏情况时间复杂度为O(log n),但平均情况复杂度为O(1 ).
该链接页面试图证明这个如下:
但是,平均而言,新插入的元素不会在树上移动很远.特别是,假设密钥的均匀分布,它有一半的机会大于其父级; 鉴于它比其父母更大,它有一半的机会比祖父母更大; 因为它比它的父母大,所以它有一半的机会大于它的曾祖父母,等等[...]所以在平均情况下插入需要恒定的时间
但这肯定是胡说八道？在我看来,如果树是随机排序的,那么新元素比其父元素大50/50的可能性; 但是,从大致来说,大型元素沉到底部,随着堆的增长,机会远小于50/50.
是对的吗？
几个月来维基百科就像这样......