The 2nd Monitor - 2014-06-02 (page 2 of 3)

« first day (394 days earlier) ← previous day next day → last day (3614 days later) »

Simon André Forsberg

4:00 PM

What's that array you have there btw? [-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434] ??

Either way I bet that on most other occasions, @rolfl's code is drastically faster than mine. Especially when it comes to multi-threading.

0

A: Finding the sub-array with the maximum sum - my approach

Performance Benchmarks In the interest of performance benchmarking, I put three versions of the code through some benchmarks. The three version are: My answer to the original quesiton Simon's answer with the code in this question. My suggested changes to Simon's answer here. The results are ...

I gave it some bigger data to play with.

@rolfl The part of this I find the most interesting is that your code is actually faster when run cold than when run hot. That's pretty unusual...

The cold result is actually just the first run, not the average.....

I still don't buy that big of a difference :p

And, that is on a 'hot' system.... the results you see are from after the warm-up.

@skiwi Simon alluded to the scalability of the algorithm he chose.

His scales much better.

Simon André Forsberg

4:06 PM

@rolfl Could you also add a benchmark for the previous OP's original code?

Um .... no.

I could not figure out how to use it ... ;-)

3

If you can package it in a way that has a simple static-method API ... then.,... yes.

Simon André Forsberg

Hmmm, I'll try

@skiwi - BTW, I used your ProjectEuler framework for this.

Why did you stop working on those?

@rolfl I found them more focusing on math skills than programming skills at some point...

there's a difference?

4:09 PM

If you're not a performance guru, then yes ;-)

And busy with the TCG lately :)

I'm wanting to understand how to use JavaFX properly with FXML, but the tutorials won't let me

@rolfl If you have some request for a specific question, then just shout and I'll try to find time for it ;)

I think I understand JavaFX better now... It is not the goal to create reusable classes, it is the goal to create different "screens" for your application and reuse those.

Though if a certain screen is used a lot of times in variations then I believe it's still possible to create some sort of custom element for it

Simon André Forsberg

@rolfl zomis.net/code.txt (Don't wanted to use pastebin for that)

@SimonAndréForsberg I think with JavaFX I can potentially make a very nicely looking TCG if I get into it... With which GWT would have a harder time?

Simon André Forsberg

@skiwi I agree with you there. Which is why I like the Community Challenges of Code Review more than yet-another-interview-question

2

@skiwi In GWT it's all about HTML and CSS. And depending on your skill, there's a lot of things that can be done with HTML and CSS.

So I'm not sure what would be the easiest to use. I hope I'll see a nice JavaFX GUI coming from you later on.

@SimonAndréForsberg JavaFX is (in advanced form), FXML ('html'), CSS and Java

Simon André Forsberg

So I guess JavaFX can produce the same things as GWT then.

Unfortunately though, I stink at web design. But I think my Card games have a quite nice GUI (for being me, at least)

4:27 PM

@SimonAndréForsberg It is not finishing for me.

Simon André Forsberg

@rolfl What is not finishing? The page load? The current code with the file? The same code with some other input?

The OP's code on the test data

It is, I think, in an infinite loop.

I have the following results so far (which also indicate a bug)....

  P 8: [0, 1, 11, 9, 8, 0, 25, 28, 45769, 0, 0]

it completes the 1000 test case.....:

 [-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434]

What it should be ~~^^^~~

The 10,000 cases are still going.....

Note that, for yours and my code, I ran them 1000 times each in the warmup, and 1000 times again for the real run.

This is running the first time only, and still going.

Oh, there's one:

 OP 9: [0, 1, 11, 9, 8, 0, 25, 28, 45769, 447857, 0]

@skiwi Yup--Euler was a mathematician, not a programmer... :-)

@Jerry that makes me feel better :)

Hmmm ~~^^^~~

 OP 10: [0, 1, 11, 9, 8, 0, 25, 28, 45769, 447857, 50645434]

Simon André Forsberg

4:35 PM

Wow, it finally got results!

That must really be very slow code then

Yes, and, apart from some negative issues, it's right.

Simon André Forsberg

All because of one lousy variable: int sum=0;

And what does the speed say?

(Do I even want to know?)

Well, it has just finished the warm-up run..... (all of one run == warmup).

Now it is doing the 'real' run.

Simon André Forsberg

Oh dear.

I guess we're talking minutes then and not milliseconds...

The original question is on the hot list

I killed it...... then pulled the last two test data inputs.

Added in some smaller ones... and ran again.

Array Sum OP        => [0, 1, 11, 9, 8, 0, 25, 28, 4668, 45769] (hot 172.59619ms - cold 276.603ms (total 635.823ms))
Array Sum Rolfl     => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769] (hot 0.22864ms - cold 3.350ms (total 261.051ms))
Array Sum SAF       => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769] (hot 0.00438ms - cold 0.094ms (total 13.125ms))
Array Sum SAF Rolfl => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769] (hot 0.00328ms - cold 0.061ms (total 10.805ms))

4:42 PM

@SimonAndréForsberg At a quick guess (without looking at the code) it says: "O(N*N) algorithm".

Real run:

Array Sum OP        => [0, 1, 11, 9, 8, 0, 25, 28, 4668, 45769] (hot 166.70651ms - cold 187.864ms (total 522.231ms))
Array Sum Rolfl     => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769] (hot 0.26869ms - cold 0.253ms (total 295.948ms))
Array Sum SAF       => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769] (hot 0.00273ms - cold 0.008ms (total 10.047ms))
Array Sum SAF Rolfl => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769] (hot 0.00190ms - cold 0.007ms (total 22.806ms))

You can see the scalability differences here... in this case, your code is only 100X faster ;-)

Simon André Forsberg

@JerryCoffin Well, considering the size of N for the last two inputs, I guess that could be correct. Feels like N^3 or N^4 to me though.

"only"

What if you try the benchmarking on only somewhat smaller arrays, such as those with size <= 20 ?

The variance in measurement screws around with sjort things like that, but sure.

Simon André Forsberg

I'm expecting that the OP's original code will still be quite slower than ours though.

Array Sum OP        => [0, 1, 11, 9, 8, 0] (hot 0.04996ms - cold 0.042ms (total 5.193ms))
Array Sum Rolfl     => [-1, 1, 11, 9, 8, -1] (hot 0.00029ms - cold 0.011ms (total 3.907ms))
Array Sum SAF       => [-1, 1, 11, 9, 8, -1] (hot 0.00014ms - cold 0.011ms (total 3.708ms))
Array Sum SAF Rolfl => [-1, 1, 11, 9, 8, -1] (hot 0.00016ms - cold 0.008ms (total 3.604ms))

Simon André Forsberg

4:45 PM

As expected.

    public static final int[][] DATA = {
        {-1},
        {1},
        {-5, 1, -3, 7, -1, 2, 1, -4, 6},
        {-5, 1, -3, 7, -1, 2, 1, -6, 5},
        {-5, 6, -3, -2, 7, -5, 2, 1, -7, 6},
        {-5, -2, -1, -4, -7},
//        {4, 1, 1, 4, -4, 10, -4, 10, 3, -3, -9, -8, 2, -6, -6, -5, -1, -7, 7, 8},
//        {4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1 },
//        buildRandom(100, -10, 100),
//        buildRandom(1000, -10, 100),
//        buildRandom(10000, -10, 100),
//        buildRandom(10000, -1, 10000)

You want the full code?

@rolfl: Without bashing you but: What did you expect? Your algorithm is quadratic and @SimonAndréForsberg 's is to complex for my current state of mind to analyze (but I think it might be linear) so it should scale better and better (and the OP's algorithm is cubic)

@Nobody - My original assertion, based on the discussion I had with Simon, was that the overhead of managing memoization state in the algorithm was going to offset the performance gains from doing less work.

He put together an algorithm that does not need to have any memoization.

In the context of the original code, (which is the context this discussion happened in ), I am quite happy with all the results.

2

Simon André Forsberg

@rolfl So am I :)

But, I am especially happy to see a way of doing things I had not considered.

4:52 PM

I am not sure which kind of memoization you mean but IIRC the memoization solution I learned in CS was O(n*n)

Simon André Forsberg

@rolfl Just curious though, what kind of memoization was it that you were thinking of? How could this problem be solved in a memoized way?

That's the thing, I thouht you were going to have to keep a backtrack or some other state, but, I just had not thought through the problem enough.

You took the time to think it through, do the math, and you consequently have a good result.

Simon André Forsberg

Yeah. It did take a bit longer time than I expected at first to come up with the approach I ended up with. I guess that's what made it work so well in the end though.

And my question is almost "Nice question" already

@SimonAndréForsberg I'm sorry to ruin your dreams there :p But not that I could do any better (on the web for sure) either :(

It seems to be functional at least

@JerryCoffin No comment on that :P

@rolfl Yours looks fast now.

Also maybe he used an O(n^(n!)) algorithm if such exist.

It is not as bad as all that.

5:01 PM

Now I feel like writing code for it too... but gotta afk first

An n! algo would not have completed this year with more than 20 members... and his solved 10000.

3

Would you mind linking my framework (your edited version) to me?

Sure.

Captain Obvious

0

Q: Create a LINQ Killer Sudoku Cage Solver

When playing Killer Sudoku I find myself repeatedly writing stuff like this: 12/3 921 831 741 732 651 642 543 and then crossing out the combinations that include say 9, 7, and 6 IE I need a list of any 3 digits between 1 and 9 that add up to 12, excluding 9, 7, and 6 because they are alread...

@skiwi - you there?

Can I post it as a question ... ;-) ?

5:43 PM

@rolfl Now I am here

@skiwi ... Post the framework as a question?

@rolfl Sure, go ahead :)

Shadow Mode can now be used with desktop capture - Yay for NVidia Shadow Play

@rolfl No, but now that I've looked, it appears I was wrong -- yours and SAF's solutions were actually O(N*N) but as shown in the answer I just posted there's a fairly simple/well-known linear solution.

@JerryCoffin: Do you mind sharing the analysis of SAF's algorithm? I had a look at it and then gave up. The two loops make it look O(n*n) at first but the break and continue have driven me crazy and led me to believe that the resulting "looping" might be the same as in the linear solution that you posted

Simon André Forsberg

@JerryCoffin I don't think my solution is as O(n*n) as it appears to be

5:55 PM

I made a mistake googling what the GFY extension exactly is...

Do not just google GFY.

Monkening everybody ;)

@Nobody i didn't analyze his very carefully--maybe it really is linear (or something less than O(N*N) anyway).

@chillworld you still there?? thanks for the answer. Btw, what I meant by scoping was the @*Scoped annotation in the beans. But your scoping point is also valid

Monking @Vogel612

Monking @skiwi. I finally forked your project 2 days ago..

Simon André Forsberg

5:57 PM

@JerryCoffin My code is linear, except that some iterations is done twice. But never more than twice. So it's maximum O(2n). This is why I believe I can make some minor modifications to my code to make it only as one for-loop

then I pulled it to my machine and had to reinstall the whole Java env, when I found out you run on oracle-java8...

Simon André Forsberg

Monking @Vogel612 (When are you going to fork mine? :D)

@SimonAndréForsberg which of the many???

2

also I am definitely not gonna write your unit-tests too...

Simon André Forsberg

@Vogel612 Oh crap. OK, nevermind then.

@SimonAndréForsberg Sounds reasonable. I suspect when you're done you'll basically have re-invented Kadane's algorithm--but that can be an interesting/fun sort of exercise (and you never know--you might end up with something original that's better than previously-known algorithms).

Simon André Forsberg

6:00 PM

@JerryCoffin Should I call it Simon's algorithm or Code Review's algorithm? :)

@Vogel612 I saw it ;)

@SimonAndréForsberg First you need to see if the final version ends up any different from Kadane's algorithm... :-)

If it does, I think @rolfl deserves at least a little credit though...

Simon André Forsberg

@JerryCoffin It probably won't. Sure, I might be quite smart, but I don't think I'm that smart.

@skiwi well I didn't get to do much, though.. I had an extremely busy weekend..

also, why the heck does chat regularly disconnect??^^

@SimonAndréForsberg The other part is, I believe Kadane's is already about as good as theoretically possible. It basically only looks at each input once. Since I'm pretty sure the correct answer requires looking at all inputs, it's impossible to beat on a big-O basis, and probably very difficult to beat on constant factors either.

6:07 PM

@Vogel612 That might be an issue on your end unfortunately

@Vogel612 Be sure though to add a downstream of my own version though

Simon André Forsberg

@JerryCoffin I just wish your C++ code was Java, because I speak Java better than C++. I have however quite easily taken @rolfl's version of my algorithm and simplified it a little bit. I'll post an answer shortly.

@skiwi - codereview.stackexchange.com/questions/52289/…

@rolfl Cool ;)

@skiwi I'll try to keep it up to date ;)

You're probably still gonna be implementing features faster than I can write unit-tests...

@rolfl problems.stream().forEachOrdered(new ProblemConsumer()); should be ProblemConsumer::new? You are throwing away the problem in problems now anyhow

@Vogel612 Do you already know for what you want to write stuff? :p

6:13 PM

@skiwi not the slightest clue..

you can propose something...

afk for a bit. relaxing

Well, you can see the Hand cq HandEvent events there, I basically want those for every class

It are events that modify the structure in a structural way

Such a thing is needed for other classes as well, I could give the xxxEvent implementation myself quite quickly I suppose

Hi guys

Hi!

@skiwi - I see I put that code on the answer to that question of yours anyway (months ago).

Captain Obvious

3

Q: Micro-Benchmark framework

Performance benchmarking small functions in Java is notoriously difficult, and there are a number of tools out there to help (caliper, others). Those other tools require a fair amount of setup and installation to get them working. This code is adapted from a question @skiwi asked. He produced th...

java performance

Simon André Forsberg

0

A: Finding the sub-array with the maximum sum - my approach

Looking at my code again, and looking at @rolfl's version of my code, I found a way to remove the outer loop, ending up with what looks pretty much the same as Kadane's algorithm that @JerryCoffin wrote. Personally I think this one's better though as this doesn't allow empty sub-arrays :) And tha...

6:22 PM

@rolfl Heh, I also have that same thing in my old code

Simon André Forsberg

@JerryCoffin I ended up with Kadane's algorithm

Ah wait it does make perfect sense, it's just very weird.

Simon André Forsberg

@Phrancis Hey there. Learning any PHP yet?

Not so much, been trying to get SQL Server 2008 to work on my Windows XP (blech) partition so I can move away from MySQL

Been talking to local hiring managers and developers, apparently in Louisville KY area SQL Server is the most common and I'm looking to find new employment soon

Get away from help desk work hopefully

So what was the question we were trying to solve? Find the sub-array with maximum sum in an array, right?

Are there any restrictions to the question, or none at all?

6:26 PM

Again a phantom ping, is it possible that the same sound is used to notify about edits to an answer on an opened question page?

And I suppose sub-array is meant to be an array in one piece, and not disjoint elements?

@skiwi: If you could pick at will then you would just pick all positive numbers

Simon André Forsberg

@skiwi Yes, find a sub-array with maximum sum. And since we're talking about arrays and not sets, it has to be consecutive.

Thanks :)

@rolfl:

private static final int[] buildRandom(int size, int min, int max) {
    return new Random().ints(size, min, max).toArray();
}

Looks familiar?

@SimonAndréForsberg I see that (and just commented on it).

6:35 PM

I wonder why nobody has been programming concurrently there :o

As to being better because it doesn't allow empty sub-arrays: the problem was originally posed for something about maximum likelihood of one image being a sub-image of another image. At least in that context, what you want is an indication of the best match (i.e., the sum itself) not the sub-array that gives that sum, and you do want to allow empty sub-sequences (i.e., a probability less than 0 doesn't make any sense).

@skiwi Read through my answer, and a reason will become apparent: with almost any normal processor, you can expect a single thread to saturate bandwidth to main memory, so you have roughly zero chance of gaining anything from concurrent programming.

Simon André Forsberg

@JerryCoffin I was neither aware that the original problem was about images, nor was I aware that it was about probabilities

@JerryCoffin I'll do and remember... but I can't take an exhaustive look at the answers yet without cheating myself

So we get an int[] and only need to return its sum?

@SimonAndréForsberg Not surprising--it's an interesting enough problem in itself that it's frequently posed with no context (though, TBH I don't know of any other use for it that would benefit from returning the subset or requiring a non-empty subset either).

Solving this problem efficiently needs extra special music here.

6:41 PM

@skiwi That's how I did it. Simon returned the actual subset. There's not really a lot of difference between the two (the latter just requires keeping track of the starting/ending points instead of just the sum).

Ah true

Simon André Forsberg

@skiwi Given the array { 4, -1, -4, 4, -2, 3, -7, -1, 4 } you should return either the array { 4, -2, 3 } or the sum of that array: 5. Because that is the largest consecutive sum of the sub-arrays.

@skiwi Quite true--the immediately obvious solutions are mostly O(N*N) (or thereabouts).

btw, this problem is completely trivial if all numbers are positive... I already thought it was easy :P

Simon André Forsberg

@skiwi Feel free to add some complex numbers if you'd like, just to make things more.... complex.

6:43 PM

@skiwi Also trivial if all are negative.

Simon André Forsberg

Also trivial if all are zero.

3

If I can get this implemented I might have a nice solution ;)

Had a sudden brainsparkle.

btw. Shouldn't we return a long if the input is an int[]?

Captain Obvious

0

Q: Getting NullPointerException in my code.

I am solving this problem from Spoj. For that i need to implement a Dijkstra java code. But i am getting NullPointerException in there. here is my code (Please take a look at Dijkstra() function) - class Edge { public int v; public int w; public Edge(int v, int w) { this.v = v; this...

> i just want to be a programmer.

Is it normal to get kind of an headache when solving such things...? It is one of the reasons I quit Algorithms class.

@SimonAndréForsberg I did edit in my best guess at a translation to Java (though it's been quite a while since I wrote any Java, so I certainly can't guarantee that it's syntactically correct). A few bits I just CnP'd from your code though, so at least part of it shouldn't be terribly wrong...

Simon André Forsberg

6:50 PM

@skiwi Drink water. Plenty of water. Not cola.

@skiwi I think you're right there. Indeed it's better to calculate the sum by using a long.

Just trying to be representative? What were the warmup and realrun numbers used?

Is break label; equivalent in Java to what in C would be goto label;? Edit: yup. I should google things first...

@Simon / @Jerry

Array Sum SAF        => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 2.09168ms - cold 38.264ms (total 23081.425ms))
Array Sum SAF Rolfl  => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 1.81022ms - cold 6.304ms (total 19830.686ms))
Array Sum SAF Coffin => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 1.75809ms - cold 5.736ms (total 19366.451ms))

(Just obviously break would have more restrictions on where it's valid -- I just mean in the context of the answers to the question y'all are talking about)

That is with, warmup 1000, realrun 10,000

and the test data:

    public static final int[][] DATA = {
        {-1},
        {1},
        {-5, 1, -3, 7, -1, 2, 1, -4, 6},
        {-5, 1, -3, 7, -1, 2, 1, -6, 5},
        {-5, 6, -3, -2, 7, -5, 2, 1, -7, 6},
        {-5, -2, -1, -4, -7},
        {4, 1, 1, 4, -4, 10, -4, 10, 3, -3, -9, -8, 2, -6, -6, -5, -1, -7, 7, 8},
        {4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1 },
        buildRandom(100, -10, 100),
        buildRandom(1000, -10, 100),
        buildRandom(10000, -10, 100),
        buildRandom(10000, -1, 10000),

6:54 PM

@rolfl I may be stupid, but...

You may be.... ;-)

Nevermind... whoever made that sneaky implementation...

    public String getResult() {
        return String.valueOf(execute());
    }

The real run does not do the String.valueOf().

^^ okay

Hmm

Simon André Forsberg

@Corbin Not quite I think. In Java, you're breaking outside a specified loop. If you use two labels for two loops, outer: and inner: then break outer; will break both loops.

6:56 PM

Exception in thread "main" java.lang.IllegalStateException: Unexpected result [I@279f2327

How did I do this

Because I return different int arrays every time.. but it checks for equals

How did you not get that error then?

yes, because, in my code .... ;-)

@Override
public String getResult() {
    return Arrays.toString(execute());
}

Smart.

This is the test I just ran:

Why am I not that smart?

package euler.arraysum;

import java.util.Arrays;

import euler.Problem;

public class ArraySumSAFCoffin extends Problem<int[]> {

    public ArraySumSAFCoffin() {
        super("Array Sum SAF Coffin", 1000, 10000);
    }

    @Override
    public String getResult() {
        return Arrays.toString(execute());
    }


    @Override
    public int[] execute() {
        int[] res = new int[CoreData.DATA.length];
        for (int i = 0; i < CoreData.DATA.length; i++) {
            res[i] = scanArray(CoreData.DATA[i]);

Simon André Forsberg

6:57 PM

@skiwi assertArrayEquals in JUnit

I think my solution isn't really efficient yet ;)

I'm at the point where I would need a progress indicator.

Simon André Forsberg

@rolfl Did you also add a benchmark for my self-answer?

That is it ... ~~^^^~~

@SimonAndréForsberg I guess what I'm confused about is that it seems like the labeled break could simply be return max. In the break outer case, it seems that the loop condition will always be false, and thus the loop gets skipped over. What's the purpose of the labeled break then? Why not just return? I feel like there must be something I'm missing.

Captain Obvious

0

Q: Am I using the javascript "module pattern" correctly?

I am reading this article about how you can organize js code for large projects. I am attempting to write a simple events calendar as a way to play with some of these design patterns. Using the module pattern I started to create a calendar module, but I have some questions: var calendarModule ...

javascript design-patterns modules revealing-module-pattern

Simon André Forsberg

6:59 PM

@Corbin In this specific case, the labeled break could be just return, yes.

0

Q: Getting NullPointerException in my code

I am solving this problem from Spoj. For that i need to implement a Dijkstra java code. But i am getting NullPointerException in there. here is my code (Please take a look at Dijkstra() function) - class Edge { public int v; public int w; public Edge(int v, int w) { this.v = v; this...

java nullpointerexception

Simon André Forsberg

I chose to not do it that way because I figured that I could for once use a single return :)

@rolfl I do think I spotted a mistake now in your benchmarking

@SimonAndréForsberg ah. It just caught me off guard, and I wanted to make sure I wasn't missing anything. Never seen a labeled break in the wild before :).

Let's say you have 99 problems. Then you first warm up all 99, then at that point the first problems are already deoptimized by the JVM, and then you start executing all 99.

Simon André Forsberg

7:01 PM

@Mat'sMug It's nice to see that they're closing such questions as duplicates actually. ~~Some~~ A lot of "programmers" really need to learn how to read a stacktrace.

@skiwi Can code ever be deoptimized by the JVM?

@Corbin Watch this:

http://codereview.stackexchange.com
for (int i = 0; i < array.length; i++) {
    //stuff
}

@skiwi 99 problems on the wall, 99 little problems...

It's valid Java ^

@SimonAndréForsberg Yes.

Simon André Forsberg

@skiwi I believe it's valid C++ as well. Besides the array.length part

Find Maximum Sub-array Problem => [-1, 1, 11, 8, 6, -7, 15, 26, 43918, 443289, 50288224] (hot 27,72493ms - cold 33,653ms (total 305083,162ms))

Erm..

7:03 PM

@skiwi - I have yet to see deoptimization.

Simon André Forsberg

@skiwi When / How / Who / Why?

@SimonAndréForsberg ...which could be valid, if array were some type with a public data member named length.

Simon André Forsberg

@JerryCoffin If it was, then the name array wouldn't be valid for it :) (JK)

@skiwi Not happy with those results, are you?

@skiwi hah. Seen that trick in C before. http is just a label, and the rest is a comment. Certainly a bit of a brain freak the first time you see it :p

Unfortunately I can't answer about the JVM deoptimization. But the specification allows it.

7:05 PM

I actually didn't know until today that Java even has labels. They seem weirdly out of place in Java.

I think they're more of a convienience than a neccessity

@rolfl If I'm not mistaken, the JVM basically keeps a cache of compiled methods. Eventually, I suppose that would overflow and some would get thrown out, but assuming it's big enough to be useful for real applications, it would take a lot of trivial cases like these before the first was removed from the cache.

btw, for the interested ones, this was my slow code... basic

private int computeMaxSum(final int[] array) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
        int sum = 0;
        for (int j = i; j < array.length; j++) {
            sum += array[j];
        }
        if (sum > maxSum) {
            maxSum = sum;
        }
    }
    return maxSum;
}

Which is O(n * (n / 2)) I believe, worst case

Which is just O(n^2)

@skiwi Right.

Find Maximum Sub-array Problem => [-1, 1, 11, 8, 6, -7, 15, 26, 43918, 443289, 50288224] (hot 27,73866ms - cold 27,169ms (total 305116,165ms))

, results from real run.

Is it even correct?

7:08 PM

@JerryCoffin You are correct. What's more, is that it depends on the JVM policy whether it invalidates existing stuff, or just does not compile new stuff.

The code-cache size is also configurable.

Assignment for you guys: Spot the bug in the method I just posted there :P

@rolfl Ah, come to think of it, I'd read that but forgotten it. Sometimes wish my memory were even close to as dependable as my computer's. :-)

Simon André Forsberg

@skiwi [-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434] is correct. So you got some of them wrong.

@skiwi empty arrays return Integer.MIN_VALUE?

@rolfl, unfortunately I have spotted another error.

7:10 PM

One other twist, is that JVM's often compile code, then recompile it with more optimization, or base don more empirical data.

@Corbin Appereantly...

            final long start = System.nanoTime();
            for (int i = rreps; i > 0; i--) {
                problem.execute();
            }
            final long end = System.nanoTime();
            final long elapsed = end - start;

            String actual = problem.getResult();

Your whole real run loop can get optimized away.

user image

4

@BenVlodgi TS

@skiwi Hmmm....

Simon André Forsberg

@skiwi Does Java optimize away code like that, the way some C++ compilers apparently does?

7:11 PM

The thing is that the JIT/JVM is quite advanced... It might figure out that problem.execute() and problem.getResult() are strictly unrelated...

@SimonAndréForsberg It's worse. It happens at runtime.

Captain Obvious

0

Q: Dynamically assign values - python

looking to improve the efficiency of my code, as while my current method works, i feel it can be improved currently this is my code : if ouroraddrlen == (4,): ouropip = struct.unpack(">bbbb", payload[6:10]) # Need to change this to accept ipv6 as well print "Our I.P : ", ouropi...

@rolfl Orring the hashcodes will do I suppose

Simon André Forsberg

Oh, then it is a real problem indeed.

@SimonAndréForsberg Except, it has not, otherwise all tests would run in the same time.... right.?

Simon André Forsberg

@skiwi Thinking of writing an answer to monkey's question? (I plan on doing so myself actually)

7:13 PM

I actually wasn't... But I might ;)

Simon André Forsberg

@rolfl True. s/is/could be/

@skiwi Kinda feels like you've reviewed half of it already, so why not get some rep for it?

Btw, they aren't strictly unrelated

I first must come up with a faster implementation of mine...

The key point is though that you cannot just decide whether you add the next element or not... Because adding two elements might be better as not adding one.

Captain Obvious

0

Q: Most optimized way to get minimum strpos from multiple needles

function min_strpos_array($haystack, $needles) { $min = null; for ($i = 0; $i < count($needles); $i++) { $strpos = strpos($haystack, $needles[$i]); if ($strpos !== FALSE) { $min = $strpos; for ($i; $i < count($needles); $i++) { $strp...

Array Sum SAF        => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 2.12077ms - cold 2.201ms (total 23304.850ms) hash 549967581)
Array Sum SAF Rolfl  => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 1.73473ms - cold 1.778ms (total 19147.456ms) hash 92288569)
Array Sum SAF Coffin => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 1.74108ms - cold 1.865ms (total 19159.585ms) hash 892305010)

~~^^^~~ calculates and reports the hash of the values returned from execute.

Damnit, my PC crashed.

7:20 PM

25 mins ago, by rolfl

Array Sum SAF        => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 2.09168ms - cold 38.264ms (total 23081.425ms))
Array Sum SAF Rolfl  => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 1.81022ms - cold 6.304ms (total 19830.686ms))
Array Sum SAF Coffin => [-1, 1, 11, 9, 8, -1, 25, 28, 4668, 45769, 447857, 50645434, 44991590] (hot 1.75809ms - cold 5.736ms (total 19366.451ms))

Compare.

Does anyone understand this? My PC crashed booted at 21:18:29, max 1 min after the crash, and the crash report tells that the last crash of 20:54:22 was unexpected.

@rolfl Looks like we were lucky there.

Does anyone want to help me a bit? What is the next logical optimization after O(n^2) in the problem?

I think the step to O(n) may be too big

@skiwi - it's a math thing, not a programming thing.

But, according to someone .... math != programming

@skiwi: O(n log n)

I'm afraid this just goes beyond me at this point.

It is a divide and conquer solution

7:28 PM

Anyone seen syb0rg recently?

you split the array into two halves and find the maximum on each of the subarrays

then look if they actually join on the split and if so you have a bigger/better solution

if not, take the one of the two that is bigger

:)

0

Q: Tic Tac Toe (2 players)

So here we have a little game of Tic Tac Toe I've made. It runs well on TI-83/84 calculators and it doesn't seem to have any problems. However, I'd like to eliminate some of the code that seems bulky and repetitive as well as possibly add some checks so you can't overwrite a square that's already...

@Nobody I see, that could (does) work

Captain Obvious

2

Q: Tic Tac Toe (2 players)

So here we have a little game of Tic Tac Toe I've made. It runs well on TI-83/84 calculators and it doesn't seem to have any problems. However, I'd like to eliminate some of the code that seems bulky and repetitive as well as possibly add some checks so you can't overwrite a square that's already...

anyone has a clue why someone would base some logic on this?

select substring('NY',status/1024&1+1,1),status from master..sysdatabases where name=DB_NAME()

why would they do status/1024&1+1?

sql-server

@Timtech saw him this weekend, he's alive ;)

7:40 PM

private int computeMaxSum(final int[] array) {
    return internalComputeMaxSum(array, 0, array.length);
}

private int internalComputeMaxSum(final int[] array, int i, int j) {
    if (i + j <= 1) {
        return array[i];
    }
    int pivot = (i + j) / 2;
    int left = internalComputeMaxSum(array, i, pivot);
    int right = internalComputeMaxSum(array, pivot, j);
    return left + right;
}

Does this have a real StackOverFlowError, or is it because of heap space?

Okay... I see something

The results look somewhat correct.

But I never actually calculate the maximum

@SimonAndréForsberg - thought I was getting spammed, then I realized ... I was!!!

Find Maximum Sub-array Problem => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (hot 0,07607ms - cold 0,108ms (total 847,363ms))

user image

2

@skiwi That's a long time for a lot of nothing.

I'm so close to the solution, yet so far away.

Simon André Forsberg

@Mat'sMug Obfuscation is my only guess. Does a/b have precendence or 1024&1? (Considering what 1024&1 is, and that you don't get a DivisionByZero error, I guess I just answered my own question)

7:46 PM

It doesn't return anything negative and I can't see (yet) why.

Simon André Forsberg

@rolfl A review == Spam? :)

Looked like it ;-)

Why is sometimes the total result negative anyhow?

Don't you have to calculate the maximum subarray

And 0 > some negative?

Captain Obvious

0

Q: Pizza project code - looking for reviews

I've just recently started c# and I was wondering if there's anything I can improve on.. using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows....

@skiwi - what is the sum of an empty array.

7:47 PM

@rolfl 0

Simon André Forsberg

@skiwi Well, "calculating the maximum subarray" is what the entire problem is about...

Yet... the result of an 1-element-negative-array is negative?

@CaptainObvious Hey, look at that: a post from a new user that looks topical!

Pizza!!!!

Simon André Forsberg

@JerryCoffin Depending on what's on the pizza, it could even be tropical!

7:48 PM

@rolfl Exactly--Pizza is always topical!

Simon André Forsberg

@CaptainObvious I think I'll pass that one over to @Mat'sMug

And now I just realized that @Mat'sMug could be misread as @Math'sMug

@SimonAndréForsberg When I was in the Air Force, I had a room mate who always had Hawaiian pizza. I didn't like the pineapples on pizza that well though.

Simon André Forsberg

@JerryCoffin I also don't like pineapple ~~on pizza~~ anywhere

@SimonAndréForsberg ...and if he gets conceited about solving lots of problems on Project Euler, maybe even MathSmug!

@JerryCoffin Hawaï Pizza is the best!

7:52 PM

Project Euler meets Tolkein: MathSmaug.

3

Guys, I'm already out of stars...

Stop saying funny stuff.

Simon André Forsberg

@rolfl I'm sorry if the review sounded a bit harsh, I just don't see a reason why the ProjectEuler class shouldn't be more re-usable than it is.

bye all

@SimonAndréForsberg I would like to take credit for all the crap that is in that code.... but I can't.

@Nobody Later.

Simon André Forsberg

7:53 PM

@JerryCoffin You mean Project Euler meets Tolkien meets Code Review

Cheers Nobody

@SimonAndréForsberg Well yes--that was implicit.

Simon André Forsberg

@rolfl Are you saying that you're blaming @skiwi? You were the one who posted the question :)

@rolfl That's...

@SimonAndréForsberg Review of your comment: You have a comma-splice.

7:54 PM

@SimonAndréForsberg I never daid that!

Find Maximum Sub-array Problem => [-1, 1, 7, 7, 7, -1, 22, 22, 44354, 447330, 50036880]

What is going on/wrong?!

I did win the jackpot seemingly in my calculations.

@rolfl "daid"? Is that shorthand for "said or did"?

pick/choose ;-)

@rolfl Chat should support drop-down pick lists...

Simon André Forsberg

@JerryCoffin Comma-splice? Please, help me learn. What's the error / How to correct? Should the comma be a period instead?

7:56 PM

This is so frustrating...

@SimonAndréForsberg Yes--what's on each side of the comma is really a complete sentence. You could use a period or (if you want to indicate their being particularly closely related) a semicolon.

Simon André Forsberg

@skiwi It took me quite a while to come up with the solution I posted. No rush. Take your time. Analyze. Step through the code with a debugger.

@JerryCoffin Noted, thanks. (I just did it again, didn't I?)

Anyone know how/why this got reopened?

@SimonAndréForsberg Yes, pretty much.

I forgot it does 1000 runs :P

7:59 PM

Is that the single reopen vote we're seeing in action?

How about... 1 run for debugging

« first day (394 days earlier) ← previous day next day → last day (3614 days later) »

Transcript for

Jun '142

The 2nd Monitor

General discussion about codereview.stackexchange.com - Welcom...

addicted-to-cr here-be-pedants just-saying-hi monkey-business my-code-is-compiling nice-people-room

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile