|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X.
If I am not mistaken you search the smallest count n for which the following statement is true:
n < 2*(count*cost) * ((count+1)/2)
depending on the language you use just use a solver for that and you don't need any loops.
if the count is small it won't make any differences (solver might be even slower), but no need to go through 10000 of loops if you can just solve it properly.
|
On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X.
If I interpret this right, you're looking for the largest c that solves the following formula:
![[image loading]](http://i.imgur.com/bFEFCU8.gif)
Pull the 5 out of the sum, apply this and, assuming that I didn't make a mistake somewhere, you should get:
![[image loading]](http://i.imgur.com/FbuwD1o.gif)
Can you go on from there?
|
On October 01 2016 21:07 Manit0u wrote:Show nested quote +On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X. You can use recursion.
int f(int x, int cost, int count) {
if (x < cost) {
return count;
}
return f(x - cost, cost + 5, count + 1);
}
I could use recursion, but that wouldnt make it any better. In fact, it would probably make it worse.
On October 01 2016 21:45 spinesheath wrote:Show nested quote +On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X. If I interpret this right, you're looking for the largest c that solves the following formula: Pull the 5 out of the sum, apply this and, assuming that I didn't make a mistake somewhere, you should get: Can you go on from there?
Your formula looks correct. But how can I solve this inequality by c in a more efficient manner than what I already had with my while-loop?
|
On October 02 2016 09:15 RoomOfMush wrote:Show nested quote +On October 01 2016 21:07 Manit0u wrote:On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X. You can use recursion.
int f(int x, int cost, int count) {
if (x < cost) {
return count;
}
return f(x - cost, cost + 5, count + 1);
}
I could use recursion, but that wouldnt make it any better. In fact, it would probably make it worse. Show nested quote +On October 01 2016 21:45 spinesheath wrote:On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X. If I interpret this right, you're looking for the largest c that solves the following formula: Pull the 5 out of the sum, apply this and, assuming that I didn't make a mistake somewhere, you should get: Can you go on from there? Your formula looks correct. But how can I solve this inequality by c in a more efficient manner than what I already had with my while-loop?
Your problem looked interesting so I tried it. Here is my analysis:
defining the initial state of the function as iteration 0,
this holds after the n'th iteration:
x[n] = x[n-1] - cost[n-1] (eq0)
cost[n] = 5 + 5n (eq1)
we will find n (finish the loop) precisely when:
x[n] < cost[n] (eq 2)
note that: by substituting eq1 into eq0
x[n] = x[n-1] - 5 - 5n + 5
=> x[n] = x[n-1] - 5n
Solving this last recurrence we obtain: (wolfram)
x[n] = c1 - (5/2)n(n + 1) (eq 3)
Note that by substituting 0 for n we get:
x[0] = c1
Now we have the following equation: (substituting eq1 and eq3 into eq2)
x[0] - (5/2)n(n+1) < 5 + 5n
2x[0] - 5n^2 - 5n < 10 + 10n
2x[0] - 10 - 5n^2 - 15n < 0
0 < 5n^2 + 15n + 10 - 2x[0]
now we can solve for n (using, for example the quadratic formula)
I made a short C program to show that it works:
#include <math.h>
#include <stdio.h>
int f1(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}
float f2(int x)
{
float a = 5;
float b = 15;
float c = 10 - 2*x;
float d = b*b - 4*a*c;
float n = (-b + sqrt(d)) / (2.0f*a);
// note that I had to add 1 here to make it 'match up'
return n + 1.0f;
}
int main(int argc, char **argv)
{
for (int i = 5; i < 125; i++)
{
int a = f1(i);
float b = f2(i);
printf("%d %f\n", a, b);
}
return 0;
}
Note that by re-ordering the calculations in f2, taking advantage of perfect squares and integer arithmetic and such, you can improve the code. This can be a nice exercise for you!
|
On October 02 2016 09:15 RoomOfMush wrote:Show nested quote +On October 01 2016 21:07 Manit0u wrote:On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X. You can use recursion.
int f(int x, int cost, int count) {
if (x < cost) {
return count;
}
return f(x - cost, cost + 5, count + 1);
}
I could use recursion, but that wouldnt make it any better. In fact, it would probably make it worse. Show nested quote +On October 01 2016 21:45 spinesheath wrote:On October 01 2016 20:31 RoomOfMush wrote:I have a major brainfart at the moment and can not think about this issue for the life of me: Is there any way I can implement this function without a loop? public int f(int x) {
int cost = 5;
int count = 0;
while (x >= cost) {
x -= cost;
cost += 5;
count++;
}
return count;
}It gives diminishing returns for growing X. If I interpret this right, you're looking for the largest c that solves the following formula: Pull the 5 out of the sum, apply this and, assuming that I didn't make a mistake somewhere, you should get: Can you go on from there? Your formula looks correct. But how can I solve this inequality by c in a more efficient manner than what I already had with my while-loop?
By doing what fmod does (although I'm missing the part where he rounds the result to an integer at the end?).
My last formula is a simple quadratic equation 1*x^2 + 1*x + k = 0 which has exactly 2 solutions. We only care for the larger of the 2 solutions, so calculate that and round it down.
|
On October 01 2016 16:45 Neshapotamus wrote:+ Show Spoiler +On October 01 2016 07:23 maybenexttime wrote:Show nested quote +On October 01 2016 01:44 supereddie wrote:Well, the biggest issue is the number of times the line is hit. Any way to reduce it? Unroll the loops? Maybe store the needed info in a better structure to later calculate points? Make more functions (and name them aptly) to improve readability.
Next, and I don't know if it helps, but you can use more local variables in the observe_points function.
I think you can optimize the calculation in observe_points? Perhaps something like
I'm not familiar with mathlab at all though... That's the essence of my question: how to vectorize (and thus remove the loop altogether) the following line in order to reduce the number of times it is called 180 times. points_observed = observe_points(data, p, transect_width(k)); I tried your suggestion about optimizing calculations in observe_points, but it made no difference. As for making more functions, I might do it in the final version of the code. Vectorization might require some major overhauls, so more functions would make implementing changes harder. Show nested quote +On October 01 2016 02:56 Neshapotamus wrote:Do you know linear algebra? Looking at your implementation, it seems that you are doing everything using loops instead of vectorized forms. Vectorized forms in matlab are far more efficient than using loops. I saw a comment that said "vectorized", but I am not sure you know what this means.
Writing some test code to help you understand the difference:
If you start making optimizations like this in your programs, your program to should start running a lot faster.
Vecotorized versions: (ex)
A = ones(5,5)
B = eye(1,5)
C = A + B
Loop version: (ex)
A = ones(5,5)
B = eye(1,5)
for r = 1 : 5
for c = 1 : 5
if (r == c) c(a,b) = a(r,c) + b(r,c)
Additionally, use markers to pinpoint the code that is taking the longest to run. A measure of the count of a function call alone is not a good indicator of bad performance. Try to figure out using print statements. Log the time taken in your program at each step and keep breaking it down and figuring how what is really taking time.
I know what vectorization means. I didn't when I first started working on this code (although I used it unknowingly a couple of times), since I only had one semester of MATLAB fundamentals and we mostly relied on loops. In the course of working on this problem, I learned what vectorization is and implemented it wherever I could. The problem is that it's rather trivial when you're dealing with one loop, but it gets very tricky when you're dealing with multiple loops and have to aggregate data and call different functions at various stages. Then you're dealing with multidimensional matrices and have to make sure you meet various criteria MATLAB functions have, such as matching matrix dimensions and so on. E.g. here's an example of how I tried to vectorize the p forloop: + Show Spoiler + % Selection of angular position:
p = 1:1:180;
% Transect angle:
transect_angle = p - 1;
% Finding the points inside the specified transect:
[angles_observed, radii_observed] = observe_points(angle, radius, p, transect_width(k));
for p = 1:180
% Calculation of the transect area:
transect_area = zeros(1, 180);
transect_area(p) = calculate_transect_area(x_min_local, ...
x_max_local, y_min_local, y_max_local, transect_angle(p));
% Preallocation of memory:
scaled_wavelet = zeros(1, n);
t = zeros(p, n);
% Calculation of scaled wavelets for each point within the transect /vectorized:
o = 1:1:n;
t = (angles_observed(p, o) - transect_angle(p))./scale(k);
scaled_wavelet = radii_observed(p, .*wavelet_function(t);
wavelet_transform(p) = sum(scaled_wavelet)/scale(k); % No density measure.
variance_normalized(p) = wavelet_transform(p)^2/transect_area(p);
end
variance_scale(k, = variance_normalized;
(...)
function [angles_observed, radii_observed] = observe_points(angle, radius, p, transect_width)
% Finding the points inside the specified transect:
i = 1:1:180;
step_size = 1;
angle_array = repmat((angle(1,), length(p), 1);
radius_array = repmat((radius(1,), length(p), 1);
p = transpose(p);
transect_lim_min = repmat(((p(i,1) - 1 - (transect_width/2)).*step_size),1,length(angle));
transect_lim_max = repmat(((p(i,1) - 1 + (transect_width/2)).*step_size),1,length(angle));
log_ind = ( transect_lim_min <= angle_array & ...
angle_array <= transect_lim_max ) | ...
( (transect_lim_min + 180) <= angle_array & ...
angle_array <= (transect_lim_max + 180) );
angles_observed = angle_array.*log_ind;
radii_observed = radius_array.*log_ind;
end While the loop was successfully vectorized to a large extent, the calculation time of observe_points increased by an order of magnitude because of those extra lines that were required to format the data. Perhaps my method of vectorization is not optimal, but I couldn't find a way to use logical indexing for multidimensional data without resorting to comparing corresponding elements of the matrices. That is why I asked for help. I did not vectorize transect_area because I did not know how to properly vectorize all the if conditions in calculate_transect_area. I did not vectorize "scaled_wavelet = radius_observed.*wavelet_function(t);" because I have absolutely no idea how to apply a custom function like wavelet_function to all non-zero elements in a radius_observed vector/matrix. Is there any algorithm/guide to loop flattening/vectorization? There isn't any guide that I have seen. Just to give you some insight into the matrix multiplication algorithm. A naive implementation would be something like this: int i_init =2 int j_init =5 int k_init = 10 A = rand(i_init,k_init) B = rand(k_init,j_init) C = zero(k_init,k_init) for i = 1 : i_init for j = 1 : j_init sum = 0 for k = 1 to k_init sum = sum + A(i,k) * B(k,j) C(i,j) = sum If we were to ask the running time of this algorithm, it would be i * j * k We can see that this is cubic in nature if we set i=j=k. so n^3 Now, there exists a much faster implementation called Strassen_algorithm: https://en.wikipedia.org/wiki/Strassen_algorithmThis runs in N^2.8074 The reason why I am telling you this is because matlab does these optimizations for you when you use the multiplication operator (*) Also to add, there are other algorithms to determine if you have a sparse matrix( meaning, lots of zeros) to speed up your algorithms as well. All this is taken care for you if you can use matrix multiplication. ex: Section 3.5 (sparse vectors) (http://www.cs.princeton.edu/courses/archive/fall16/cos226/lectures/34HashTables+35SearchingApplications.pdf) As for a guide to reducing loops, here is some advice. (It seems like you are doing it already in some sense) 1. Match the matrix dimensions. Use the matrix multiplication. This is just linear algebra. 2. Use the transpose operator(') to get the right dimensions 3. Use zero, ones, diag, and identity matrix for augmenting your data. 4. Matrix with multiple dim A * Matrix with multiple B. You have to iterate and do it at a vector level. ex  psudeo code) foreach v: Vector in A:Matrix { v * B } You can do the following, send me a private chat and we can discuss more in detail about what you are doing. Check in your code to github, so I can see your current implementation.
Thanks. I will figure out how GitHub works, and I'll PM you then.
Like you said, I am more or less doing what you described, but the problem is that in the process I am using many new tools for the first time. And if my optimization happens to be suboptimal (as with the vectorization of the p forloop), the calculation time increases so much that it gets prohibitive and prevents me from testing slightly different variants.
By the way, I figured out how to vectorize logical indexing without resorting to repmat, but it made little difference:
+ Show Spoiler [before] +function [angles_observed, radii_observed] = observe_points(angle, radius, p, transect_width)
% Finding the points inside the specified transect:
i = 1:1:180;
step_size = 1;
angle_array = repmat((angle(1,:)), length(p), 1);
radius_array = repmat((radius(1,:)), length(p), 1);
p = transpose(p);
transect_lim_min = repmat(((p(i,1) - 1 - (transect_width/2)).*step_size),1,length(angle));
transect_lim_max = repmat(((p(i,1) - 1 + (transect_width/2)).*step_size),1,length(angle));
log_ind = ( transect_lim_min <= angle_array & ...
angle_array <= transect_lim_max ) | ...
( (transect_lim_min + 180) <= angle_array & ...
angle_array <= (transect_lim_max + 180) );
angles_observed = angle_array.*log_ind;
radii_observed = radius_array.*log_ind;
end
+ Show Spoiler [now] +function [angles_observed, radii_observed] = observe_points(angle, radius, p, transect_width)
% Finding the points inside the specified transect:
i = 1:1:180;
step_size = 1;
p = transpose(p);
transect_lim_min = p - 1 - ((transect_width/2).*step_size);
transect_lim_max = p - 1 + ((transect_width/2).*step_size);
log_ind = ( bsxfun(@ge, angle, transect_lim_min) & ...
bsxfun(@le, angle, transect_lim_max) ) | ...
( bsxfun(@ge, angle, (transect_lim_min + 180)) & ...
bsxfun(@le, angle, (transect_lim_max + 180)) );
angles_observed = bsxfun(@times, angle, log_ind);
radii_observed = bsxfun(@times, radius, log_ind);
end
It turns out that <= and such can only compare the corresponding elements of the matrices, whereas @ge and so on in bsxfun do not have such restrictions. It seems that bsxfun includes implicit expansion of the output matrix.
|
@fmod, spinesheath, TBO:
Thanks guys, the formula checks out and seems to perform pretty well for large X.
|
On October 04 2016 01:14 RoomOfMush wrote:
@fmod, spinesheath, TBO:
Thanks guys, the formula checks out and seems to perform pretty well for large X.
If you implemented it correctly, it runs in O(1) time, so it should run in the same amount of time as for small X.
|
On October 04 2016 01:25 Acrofales wrote:Show nested quote +On October 04 2016 01:14 RoomOfMush wrote:
@fmod, spinesheath, TBO:
Thanks guys, the formula checks out and seems to perform pretty well for large X. If you implemented it correctly, it runs in O(1) time, so it should run in the same amount of time as for small X.
But the loop doesnt. The loop version is quite fast for small X. It only uses simple addition/subtraction. The version of fmod uses multiplications, divisions and the calculation of a square root. It may be O(1) but that is quite useless in real life. O(1) does not tell you anything about the static cost.
|
On October 04 2016 02:55 RoomOfMush wrote:Show nested quote +On October 04 2016 01:25 Acrofales wrote:On October 04 2016 01:14 RoomOfMush wrote:
@fmod, spinesheath, TBO:
Thanks guys, the formula checks out and seems to perform pretty well for large X. If you implemented it correctly, it runs in O(1) time, so it should run in the same amount of time as for small X. But the loop doesnt. The loop version is quite fast for small X. It only uses simple addition/subtraction. The version of fmod uses multiplications, divisions and the calculation of a square root. It may be O(1) but that is quite useless in real life. O(1) does not tell you anything about the static cost.
Sure. But the same still applies: if it's O(1) and slow, it is slow for all X, both large and small.
And let's face it: if finding the 0-points of a parabola takes a long time, you have implemented it atrociously.
|
Pretty bummed about my first midterm. I left thinking that I did pretty decently, but I did not. Average was 72, I scored 59. About 40% of it was knowledge type questions, which I did very well on. The other 60% was coding (hand written). It was graded much more harshly than I expected it would be and I did very bad. Even though I had a good general idea what was wanted, and how the classes and methods worked, my implementations were a little off or missing something each time and the graders just stacked minus points all over the place. On one of the questions I scored a 1 out of 15 despite showing that I clearly had a good general idea of what was going on.
So yeah, I am a bit sad about that. Mostly because I actually do spend quite a bit of time doing school work and this is the first time I've actually put decent effort into something and not been remotely successful.
|
Hyrule18904 Posts
On October 04 2016 05:37 travis wrote:
The other 60% was coding (hand written)
that's the thing I hated most on my tests :|
so dumb
|
On October 04 2016 05:37 travis wrote:
Pretty bummed about my first midterm. I left thinking that I did pretty decently, but I did not. Average was 72, I scored 59. About 40% of it was knowledge type questions, which I did very well on. The other 60% was coding (hand written). It was graded much more harshly than I expected it would be and I did very bad. Even though I had a good general idea what was wanted, and how the classes and methods worked, my implementations were a little off or missing something each time and the graders just stacked minus points all over the place. On one of the questions I scored a 1 out of 15 despite showing that I clearly had a good general idea of what was going on.
So yeah, I am a bit sad about that. Mostly because I actually do spend quite a bit of time doing school work and this is the first time I've actually put decent effort into something and not been remotely successful.
Coding on paper (as in actual code indead of just pseudocode) has precisely 0% real life relevance. You don't have to feel bad about that. In a real world environment you will always set up some sort of feedback loop - typically the IDE, compiler and ideally a test suite - so that you can check if your code does what it is supposed to do quickly and frequently. Not getting any immediate feedback is very unprofessional.
I get that this doesn't help you now and you never want to have to explain that your grades are bad because your tests were legitimately stupid. I hated university because of stuff like that. But since things probably aren't gonna change for the better anytime soon, I guess you should specifically practice writing code on paper and then check it afterwards in the IDE.
In any case, don't feel bad about that. Just work on not having it happen again.
|
On October 04 2016 05:37 travis wrote:
Pretty bummed about my first midterm. I left thinking that I did pretty decently, but I did not. Average was 72, I scored 59. About 40% of it was knowledge type questions, which I did very well on. The other 60% was coding (hand written). It was graded much more harshly than I expected it would be and I did very bad. Even though I had a good general idea what was wanted, and how the classes and methods worked, my implementations were a little off or missing something each time and the graders just stacked minus points all over the place. On one of the questions I scored a 1 out of 15 despite showing that I clearly had a good general idea of what was going on.
So yeah, I am a bit sad about that. Mostly because I actually do spend quite a bit of time doing school work and this is the first time I've actually put decent effort into something and not been remotely successful.
Don't worry, coding is one of these things where time and practice make you exponentially better. If you stick at it you will eventually rock it.
|
Yeah. Grading hand written code is pretty tough. But having students write their tests on computers doesnt make things much easier.
|
On October 04 2016 07:24 RoomOfMush wrote:
Yeah. Grading hand written code is pretty tough. But having students write their tests on computers doesnt make things much easier.
The real tests would not be making students write their own code but instead giving them the buggy code and the test being debugging it.
If you're good at debugging, you'll be good at coding. If you suck at debugging, you need to learn debugging.
|
Yeah, don't give up! One of my biggest regrets is early just getting too discouraged and getting trapped in this cycle of "well all that effort was pointless, I just suck at this". I ended up more or less ok (though I'm still a pretty terrible developer and/or programmer), but missed out on a ton more knowledge and skill-honing had I just stuck with it and trusted the process.
|
Russian Federation4235 Posts
Even though "whiteboard coding" is not a very useful production skill, it's almost an essential skill in passing the interviews when applying for a job. So getting good at it is pretty useful after all. Besides, it does change the way you reason about your code in a certain way. I recently applied for a new job and I had to get some training in coding on paper after failing an interview. At first I was enraged at why would someone ask for something that stupid but then I kinda accepted the fact and started training. What I discovered that I had a coding habit I didn't know of: I didn't think out corner cases (for example, having one less or one more increment than needed etc) and just ran the code to see if it was correct and then applied some changes if it wasn't. Doesn't work on paper, you have to slog through those "hard to reason, easy to check" moments. It is somewhat helpful to your general coding skills to learn to do that.
|
On October 04 2016 09:02 Manit0u wrote:Show nested quote +On October 04 2016 07:24 RoomOfMush wrote:
Yeah. Grading hand written code is pretty tough. But having students write their tests on computers doesnt make things much easier. The real tests would not be making students write their own code but instead giving them the buggy code and the test being debugging it. If you're good at debugging, you'll be good at coding. If you suck at debugging, you need to learn debugging.
It's intrinsically hard to come up with ever changing interesting debugging cases, because those are precisely not intentional.
|
On October 04 2016 17:42 ZenithM wrote:Show nested quote +On October 04 2016 09:02 Manit0u wrote:On October 04 2016 07:24 RoomOfMush wrote:
Yeah. Grading hand written code is pretty tough. But having students write their tests on computers doesnt make things much easier. The real tests would not be making students write their own code but instead giving them the buggy code and the test being debugging it. If you're good at debugging, you'll be good at coding. If you suck at debugging, you need to learn debugging. It's intrinsically hard to come up with ever changing interesting debugging cases, because those are precisely not intentional.
Well, you could base most of the tests off of ruby koans (which I still believe is the single best introduction to programming ever conceived).
Let me also share something that really cracked me up:
https://hackernoon.com/how-it-feels-to-learn-javascript-in-2016-d3a717dd577f
I'm so glad I've decided not to dive into JS some time ago and I sticked with this decision 
I've learned this one JS framework some time ago and it's been completely sufficient for my needs ever since.
Edit:
Also interesting if you're a web dev (from the back-end perspective): https://circleci.com/blog/its-the-future/
|
|
|
|
|
|
EPT
