Programming homework and newbie help thread - Page 75 - Computer Technical Help

I figured it out. Adding a built-in timer (which was very simple: System.currentTimeMillis() ) required me to use a while-loop in Version A that was previously unused for FRAC.length < 3 on my machine. This while-loop added about 8 or 9 seconds to the multi-threaded time.

Code:

while(true)
   if(pool.isTerminated())
      break;

Version B always uses that loop, which is why it's slower than A.

Just now i tested increasing the #trials to 10M with and without the loop. Now the loop takes 90 seconds which makes sense.

So when multi-threading, if I want a speed boost I either have avoid making the code do things after the threads, or I have to find a more efficient way to make it wait for them to terminate. There is probably a better way than checking pool.isTerminated() every nanosecond (or w/e) until the thread is done. This had crossed my mind when writing the while-loop, but then when comparing the versions it didn't occur to me that one of them wasn't using the loop as often.

Nice work! For your loop issue, it looks like this function might be good: ExecutorService.awaitTermination(). APIs like that will often have functions that let you wait for something to finish, but if they don't you can...
- add synchronization yourself (for example, lock the main thread and unlock it from worker threads as they complete, keep re-locking the main thread until some counter indicates that all workers are done)
- keep the loop you had but just add a sleep call for, say, 100ms between checks

Quote:

Originally Posted by heehaww

The results were so much different than I expected that the difference can't be chalked up to reaction time.

I believe you, it's more just a quality of life thing. Who wants to pull out a stopwatch when you can have your program do that for you with exceptional precision?

Quote:

Originally Posted by heehaww

I don't understand what you're proposing. What does the bolded mean?

Sorry, I was speaking more generally and not necessarily about your particular program. As an example, here's a C++ snippet for a simple algorithm that adds one to each number in an array:

Code:

// bad; inflexible, makes assumptions about data set
// being worked on

int* array;

int main(void) {
  array = new int[20];
  // ...pretend array is seeded with values...
  runAlgorithm();
}

void runAlgorithm() {
  for (int i = 0; i < 20; i++) {
    array[i]++;
  }
}


// good; flexible, works on the set given to it with no
// other assumptions, can be multithreaded by passing
// different parts of an array in parallel

void runAlgorithm(int* array, int begin, int end) {
  for (int i = begin; i < end; i++) {
    array[i]++;
  }
}

// usage examples
int main(void) {
  ...
  runAlgorithm(array, 0, 20);
  ...
  for (int i = 0; i < numThreads; i++) {
    // create thread working on individual chunk of array
    // (leaving out thread creation syntax because it will
    // look like greek to non-C++ people)
    int chunkStart = ...
    int chunkEnd = ...
    runAlgorithm(array, chunkStart, chunkEnd);
  }
}

Your code isn't doing the things in the "bad" section, but it's also not quite the "good" section because your algorithm code isn't isolated - it depends on being used a specific way, and version A of it isn't quite interchangeable with version B. Like, as someone reading this code, I'd like to see - "ok, I have this algorithm doing this work, but when I use it this one way it's fast and benefiting from multithreading, but when I use it this other way it's not" - that's a problem we can dive into. Because the algorithm itself is subtly working differently depending on which version we're looking at, though (even if it's just at a bookkeeping level since the meat of it is doing the same thing), it's hard to determine where the issue is without comprehending the behavior of the entire program. You're doing the right thing having the mindex/maxdex sort of thing in version B, but because you can't take that same code and plug it into version A, that makes it a variable - and the process of debugging is one of removing and isolating variables.

One other random thought - in compareMedian you have several member variables that are only used within the scope of one function - code is more readable if variables are declared at the most specific location where they're used. i.e.

Code:

// bad
  int i, j, k, l, m;
  for (i = 0; i < .....) {
    j = 1; // j is not used outside this for loop
    if (j + ... ...) {
      k = ... // k is not used outside this if statement
    }
  }

// good
  for (int i = 0; i < .....) {
    int j = 1;
    if (j + ... ...) {
      int k = ...
    }
  }

The first one is bad because it's impossible to tell without further inspection how widely used these variables are - they "pollute" the scope where they exist, so to speak. A more tightly scoped variable is easier to think about because you know the usage of the variable can't extend any wider than the scope where it's declared. In the case of compareMedian, the only variables that need to be class members (as opposed to being declared within the call() function) are the variables that are set by the constructor.

Quote

04-23-2018 , 09:26 PM

#1852

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Thanks goofy, super helpful

Quote:

Originally Posted by goofyballer

ExecutorService.awaitTermination()
- add synchronization yourself (for example, lock the main thread and unlock it from worker threads as they complete, keep re-locking the main thread until some counter indicates that all workers are done)
- keep the loop you had but just add a sleep call for, say, 100ms between checks

Cool I'll play around with those solutions to compare speeds. I'll look at the awaitTermination() code to see what it does. Kicking myself for not thinking of sleep.

Quote:

Your code isn't doing the things in the "bad" section, but it's also not quite the "good" section because your algorithm code isn't isolated - it depends on being used a specific way, and version A of it isn't quite interchangeable with version B.
...
it's hard to determine where the issue is without comprehending the behavior of the entire program.
...
the process of debugging is one of removing and isolating variables.

Got ya, good point.

Quote:

One other random thought - in compareMedian you have several member variables that are only used within the scope of one function - code is more readable if variables are declared at the most specific location where they're used.
...
In the case of compareMedian, the only variables that need to be class members (as opposed to being declared within the call() function) are the variables that are set by the constructor.

This makes sense and I'll adopt the habit. But out of curiosity, from an evil micro-optimization standpoint, is any performance sacrificed when initializing a variable compared to just setting its value? My guess would be "int k=5" is two steps whereas "k=5" is only one.

Quote

04-23-2018 , 10:30 PM

#1853

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Quote:

Originally Posted by heehaww

Whether it's "2 steps" or not, you have to do both steps.

Code:

int i=0;
for (i=0; i<10; i++) {}

has all the same steps as

Code:

for (int i=0; i<10; i++) {}

Anyway, I have a few comments on multi-threading. Approaching the problem is more of an art than a science.

As noted, don't do busy loops waiting for the threads to end, every language with threads has a wait() or a join() or something like that which will block until the threads finish. Barring that, yeah, put in delays checking for completion.

Your instinct is to make the same number of threads as processes and that may not be a bad idea, but splitting a job into 2 equal parts has a bad worst-case scenario, where one thread is done way before the other and sits there doing nothing while the other finishes. Unless you can be really sure that each thread will take the same amount of time (which you can't, more on that in a second), then you usually want to break it into more pieces than that.

There are a few approaches:
1. make N threads and split into K jobs where K >> N. "feed" jobs to the worker threads so that as soon as one finishes a parcel it takes up the next one. This way your worst cases added latency is the amount of time required to finish one parcel. Smaller parcels means less latency but more overhead managing the parcels.

2. Make N threads and N jobs, where N is more than the number of processors. This might seem counterintuitive but it's pretty common for a thread to have little delays where another thread can slip in and get some work done, for example IO, memory accesses, etc. If you think about it, threads are lighter weight than processes and your computer right now is probably running 50+ processes just fine.

There are probably more that I'm not thinking of right now.

Also, something to keep in mind is Amdahl's Law
https://en.wikipedia.org/wiki/Amdahl%27s_law
which describes the maximum performance boost you can get from threading.

The basic idea here is that you have some part of your program that can't be threaded or split - initialization or maybe post-analysis or something. Let's say that portion of your program is 1/3 of the total (single threaded) run time. If you somehow had infinite processors and your algorithm scaled perfectly, you could optimize 2/3 of your program into zero time, but that will leave the original 1/3. So the *maximum* theoretical speedup would be 3x.

It's a good thing to keep in mind because making a program multi-threaded might make it an order of magnitude more complicated, harder to read, understand, fix, find bugs in, etc. If it makes your program 10x faster, probably worth it. If it makes it 50% faster, probably not.

Quote

04-23-2018 , 11:20 PM

#1854

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

In src.zip I opened up ExecutorService.java and scrolled down to awaitTermination().

Code:

boolean awaitTermination(long timeout, TimeUnit unit)
        throws InterruptedException;

That's all. Wtf? Where's the code?

Quote:

Originally Posted by RustyBrooks

Whether it's "2 steps" or not, you have to do both steps.

Yeah but if it's 2 steps, putting "int k" inside the loop (per goofy's suggestion) means you have to perform those 2 steps on every iteration of the loop instead of just once before the loop.

Quote:

There are a few approaches:
1. make N threads and split into K jobs where K >> N.

2. Make N threads and N jobs, where N is more than the number of processors.

Quote:

Your instinct is to make the same number of threads as processes and that may not be a bad idea, but splitting a job into 2 equal parts has a bad worst-case scenario, where one thread is done way before the other and sits there doing nothing while the other finishes. Unless you can be really sure that each thread will take the same amount of time (which you can't, more on that in a second), then you usually want to break it into more pieces than that.

Interesting, the bolded is even true when the pieces are identical? Fwiw in Version A, the outputs for the 2 threads always occur at almost the same time (though the order of which finishes first is unpredictable). But going forward I'll definitely keep this in mind. I appreciate the wisdom being shared. Stuff like this is especially useful since it's not Java-specific.

Quote:

your computer right now is probably running 50+ processes

Self-fulfilling prophecy! I had 49 running, but opening Task Manager bumped it to 50.

Quote

04-24-2018 , 12:19 AM

#1855

goofyballer

Carpal \'Tunnel

Join Date: Jun 2005 Posts: 70,719

Quote:

Originally Posted by heehaww

But out of curiosity, from an evil micro-optimization standpoint, is any performance sacrificed when initializing a variable compared to just setting its value? My guess would be "int k=5" is two steps whereas "k=5" is only one.

Quote:

Originally Posted by heehaww

Yeah but if it's 2 steps, putting "int k" inside the loop (per goofy's suggestion) means you have to perform those 2 steps on every iteration of the loop instead of just once before the loop.

I'm not sure what the internals of Java are doing, but I can talk about C (Java's internals are probably similar tbh) - the declaration of a stack variable happens in stack memory. This is very fast and simple, because "memory allocation" in a stack basically just involves moving the stack pointer up 4 bytes. So, say you go into a new function, that function's memory space (which sits on top of the memory space of all the functions below it in the call stack) looks like this:

0 bytes <-- stack pointer here
1
2
3
4
5 ...

Now we hit a line, say, "int k = 1"

Stack now looks like this:

0 <-- used by k
1 <-- used by k
2 <-- used by k
3 <-- used by k
4 bytes <-- stack pointer is now here
5 ...

Stack operations are absurdly cheap compared to what most of the code you'll write is doing, especially in a language like Java. There are situations where what you wrote about might be a valid concern, but probably not until you're writing hyper-optimized C for embedded controllers or something.

And this does apply more to stack variables - if we were talking 'int* k = new int[20]' instead of 'int k = 2', then that does make a new heap allocation which is going to perform worse than a stack allocation.

Interestingly, in practice, stack memory doesn't really need to be "allocated". This is a cool website that can show you the CPU instructions generated by code: https://godbolt.org/

Try a super simple function, like:

Code:

void myFunc() {
    int k = 1;
}

The output is color coded to show you which assembly corresponds to which line of source, and the output is:

Code:

myFunc:
  push rbp
  mov rbp, rsp
  mov DWORD PTR [rbp-4], 1 //********
  nop
  pop rbp
  ret

The ****** line is the only one associated with "int k = 1" - the assignment is the only operation, there's no "allocation". Basically, because the memory at the top of the stack isn't being used by anything else, the program can just assign whatever to it, and since the compiler is really smart it knows that what you call "k" is really just "the first 4 bytes at the top of my stack". The only time the stack pointer actually needs to be advanced is when calling into another function, and at that point the compiler knows how much the stack pointer needs to be advanced because it knows how many variables you've put onto the stack. If you put 4 ints on the stack, the compiler can just advance the stack pointer by 16 bytes, and it can do this in one instruction rather than doing it once per every variable declared.

When you write code like "new suchandsuch", that comes from the heap, which is the global memory space available to all threads of your program. So, as written, those variables in compareMedian like 'bet', 'stack', and 'bankroll' are included in that heap allocation that reserves the space for a new compareMedian object. Which is fine, but for the other reasons I mentioned about readability, I think they'd be better as more tightly-scoped stack variables.

Quote:

Originally Posted by heehaww

Interesting, the bolded is even true when the pieces are identical?

Yes. In practice, when the pieces are identical and the cores are running the same code, they will probably finish at the same time. However, it's a bad idea to ever assume they will, because things can and will go wrong - for one example, your program is still at the mercy of your OS scheduler, which is also running other programs on the same cores your program is using, so your threads will get interrupted in a non-deterministic manner. It's better to prepare for the worst than assume the best.

Quote

04-24-2018 , 10:06 AM

#1856

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Quote:

Originally Posted by heehaww

Yeah but if it's 2 steps, putting "int k" inside the loop (per goofy's suggestion) means you have to perform those 2 steps on every iteration of the loop instead of just once before the loop.

No, it doesn't re-allocate it every time through the loop. Why would it do that?

Quote:

Interesting, the bolded is even true when the pieces are identical?

Right, because as mentioned, your computer is running dozens of other processes. Any of your threads could get interrupted and control could be transferred to some other process.

Quote

04-24-2018 , 01:22 PM

#1857

KatoKrazy

Pooh-Bah

Join Date: Jan 2009 Posts: 4,533

Quote:

Originally Posted by RustyBrooks

No, it doesn't re-allocate it every time through the loop. Why would it do that?

+1

This is why it's good to have an understanding of how things are working under the covers when you are writing code that needs to be performant.

I currently work on the performance team for an Enterprise SSD project, so I spend a lot of time thinking about things like this.

Quote

04-24-2018 , 02:42 PM

#1858

goofyballer

Carpal \'Tunnel

Join Date: Jun 2005 Posts: 70,719

Quote:

Originally Posted by RustyBrooks

No, it doesn't re-allocate it every time through the loop. Why would it do that?

To be fair, change the allocation from "int k = 1" to "Object whatever = new Object" and it would do that - the distinction requires knowing about the difference between the stack and the heap. (and even between languages - you can put objects on the stack in C/C++, but not Java*) (*and even that comes with a caveat, because although you can't assume it will, it appears the Java compiler will do introspection to determine when it can) (this stuff is complicated for new programmers!)

Quote

04-25-2018 , 12:13 AM

#1859

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Thanks guys!

I compared awaitTermination() vs a while-loop with varying amounts of sleep. As expected, awaitTermination() is the better choice. The sleep can be calibrated to match the performance of awaitTermination(), but not exceed, so there's no reason to go that route.

I redesigned the program per Rusty's suggestion and went with the "N threads for N jobs" approach. I made #threads a parameter. Previously I was using 2 threads for 2 humongous jobs. Slightly better performance is obtained with more threads, but the performance has a peak. With 1M trials my performance was best with something like 400-500 threads. Using 1k-2k threads resulted in basically the same performance, so all things being equal I'd pick the larger number for greater reliability. But after 2k it starts to dip, e.g. 10k threads takes 15sec to complete whereas 1k only takes 9sec.

I also noticed that threads cost RAM. Two threads used about 18 MB of RAM whereas 1000 threads used about 100 MB.

@Rusty, when you said to use more threads, was 1000 threads in the ballpark of what you meant for a program like this one (when simulating 1M series of 1k random events)?

Here's the latest version in case it matters:

Code:

import java.util.Random;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.Callable;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;

public class LoansomeKelly{
   static final int THREADS = 1000;
   static int SUBSAMPLE = (int)Math.round(1000000.0/THREADS);
   static final double[] FRAC = {.01};
   static final int ROUNDS = 1000;
   static final int INTEREST = 770;
   static final double MINBET = 1.0;
   static final int POSSIBILITIES = 100;
   static final int WIN_POSSIBILITIES = 51;
   static final int INSTALLMENT = 5000;
   static final int BUYINS = 4;
   static int SAMPLE = SUBSAMPLE*THREADS;
   static double INITBR = (double)BUYINS * INSTALLMENT;
   static short[][] br = new short[FRAC.length][SAMPLE];
   static int[][] subset_busts = new int[FRAC.length][THREADS];
   static int[][] subset_ruins = new int[FRAC.length][THREADS];

   public static void main(String[] args){
      final long BEGINTIME = System.currentTimeMillis();
      ExecutorService[] pool = new ExecutorService[FRAC.length];
      for(int p=0; p<pool.length; p++){
         double medianGrowth;
         int total_busts = 0;
         int total_ruins = 0;
         pool[p] = Executors.newFixedThreadPool(THREADS);
         for(int c=0; c<THREADS; c++) pool[p].submit(new compareMedian(p,c));
         pool[p].shutdown();
         try{pool[p].awaitTermination(1, TimeUnit.HOURS);}
         catch(InterruptedException ie){System.err.println("Oh no");}
         finally{
            if(pool[p].isTerminated()){
               for(int c=0; c<THREADS; c++){
                  total_busts += subset_busts[p][c];
                  total_ruins += subset_ruins[p][c];
               }Arrays.sort(br[p]);
               medianGrowth = (br[p][SAMPLE/2] + br[p][SAMPLE/2-1])*100.0/(2*INITBR);
               System.out.println("N="+SAMPLE+": After "+ROUNDS+" rounds of "+FRAC[p]+" ,");
               if(medianGrowth>0.0) System.out.println("Median growth per round = " + Math.pow(medianGrowth, 1.0/ROUNDS));
               else System.out.println("Median growth per round = 0");
               System.out.println((double)total_busts/SAMPLE+" busts on avg, with ruin occurring "+100.0*total_ruins/SAMPLE+" %");
               System.out.println();
            }else pool[p].shutdownNow();
         }
      }
      System.out.println("T = "+(double)(System.currentTimeMillis()-BEGINTIME)/1000);
   }
   private static class compareMedian implements Callable<Void> {
      private int mindex, maxdex, jobdex, fracdex;
      private double frac;
      Random rand = new Random();
      
      public compareMedian(int p, int c){
         fracdex = p;
         jobdex = c;
         frac = FRAC[p];
         mindex = c*SUBSAMPLE;
         maxdex = mindex+SUBSAMPLE;
         subset_busts[p][c] = 0;
         subset_ruins[p][c] = 0;
      }
      @Override
      public Void call() throws Exception{
         for(int e=mindex; e<maxdex; e++){
            int busts = 0;
            double stack = (double)INSTALLMENT;
            double bankroll = INITBR;
            
            for(int r=0; r<ROUNDS; r++){
               double bet = frac*bankroll;
               if(bet>stack) bet=stack;
               else if(bet<MINBET)
                  if(stack>=MINBET) bet=MINBET;
                  else bet=stack; //Allows one extra bet.
               int outcome = rand.nextInt(POSSIBILITIES);
               if(outcome < WIN_POSSIBILITIES){
                  bankroll += bet;
                  stack += bet;
               }else{
                  bankroll -= bet;
                  stack -= bet;
                  if(stack==0.0){
                     busts++;
                     if(bankroll>0.0) stack=(double)INSTALLMENT;
                     else break;
                  }
               }
            }if(busts>0){
               subset_busts[fracdex][jobdex] += busts;
               if(busts==BUYINS) busts--;
               bankroll -= (double)busts*INTEREST;
            }br[fracdex][e] = (short)Math.round(bankroll*.01);
            if(bankroll<=0.0) subset_ruins[fracdex][jobdex]++;
         }
         return null;
      }
   }
}

Quote

04-25-2018 , 10:20 AM

#1860

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

I wasn't necessarily thinking of 1000 threads but certainly I thought dozens to hundreds. The right number is very hard to predict and mostly comes down to trial and error. Like in your case you can usually find a range of acceptable performance that's pretty broad, select something in the middle and generally be OK.

Yeah, more threads = more memory but it's gotten a lot better over the years. On some platforms, a decade or more ago, threads used to be relatively expensive. You have sort of a best case example where you don't have to worry too much about concurrent access to resources. If you had to do a lot of locking, more threads would probably be a problem, because your threads would be waiting for locks to clear a lot. Generally you want to use locking only when you have to.

Quote

04-25-2018 , 11:40 AM

#1861

plexiq

veteran

Join Date: Apr 2007 Posts: 2,554

There's no point in running thousands of threads if your system can only physically run e.g. 16 at the same time, unless your tasks have to block for IO. If your tasks are just CPU work w/o IO then take the # of physically supported threads times 1.5-2x and you'll be fine.

Quote

04-25-2018 , 12:29 PM

#1862

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Quote:

Originally Posted by plexiq

If it runs faster with 100 than with 10, then run it with 100. If you really care to find out why it runs faster with more, you can probably get it down to a much lower number.

Quote

04-26-2018 , 02:15 AM

#1863

plexiq

veteran

Join Date: Apr 2007 Posts: 2,554

Well, the likely reason that 1000 threads are faster here is because he is allocating the work into fixed sets of tasks at the start, ie batches of 1000 simulations per thread.

The fixed allocation will lead to unnecessary idle time towards the end. Worst case, all but one batches are finished and the last remaining batch is just starting out, in that case you have 1000 tasks remaining and are utilizing only a single thread.

Using more threads will decrease the average idle time in the end, due to smaller batch size per thread. If you want to optimize this then the alternative would be to dynamically allocate the tasks, so you can keep all cores busy right until the end and still use a much smaller number of threads to reduce overhead.

e.g. something like this:

Code:

public class LoansomeKelly{
   static final int THREADS = 32;
   static final double[] FRAC = {.01};
   static final int ROUNDS = 1000;
   static final int INTEREST = 770;
   static final double MINBET = 1.0;
   static final int POSSIBILITIES = 100;
   static final int WIN_POSSIBILITIES = 51;
   static final int INSTALLMENT = 5000;
   static final int BUYINS = 4;
   static int SAMPLE = 1000000;
   static double INITBR = (double)BUYINS * INSTALLMENT;
   static short[][] br = new short[FRAC.length][SAMPLE];
   static int[][] subset_busts = new int[FRAC.length][THREADS];
   static int[][] subset_ruins = new int[FRAC.length][THREADS];

   public static void main(String[] args){
      final long BEGINTIME = System.currentTimeMillis();
      ExecutorService[] pool = new ExecutorService[FRAC.length];      
      for(int p=0; p<pool.length; p++){
    	 AtomicInteger tasks = new AtomicInteger(0);
         double medianGrowth;
         int total_busts = 0;
         int total_ruins = 0;
         pool[p] = Executors.newFixedThreadPool(THREADS);
         for(int c=0; c<THREADS; c++) pool[p].submit(new compareMedian(p,c,tasks));
         pool[p].shutdown();
         try{pool[p].awaitTermination(1, TimeUnit.HOURS);}
         catch(InterruptedException ie){System.err.println("Oh no");}
         finally{
            if(pool[p].isTerminated()){
               for(int c=0; c<THREADS; c++){
                  total_busts += subset_busts[p][c];
                  total_ruins += subset_ruins[p][c];
               }Arrays.sort(br[p]);
               medianGrowth = (br[p][SAMPLE/2] + br[p][SAMPLE/2-1])*100.0/(2*INITBR);
               System.out.println("N="+SAMPLE+": After "+ROUNDS+" rounds of "+FRAC[p]+" ,");
               if(medianGrowth>0.0) System.out.println("Median growth per round = " + Math.pow(medianGrowth, 1.0/ROUNDS));
               else System.out.println("Median growth per round = 0");
               System.out.println((double)total_busts/SAMPLE+" busts on avg, with ruin occurring "+100.0*total_ruins/SAMPLE+" %");
               System.out.println();
            }else pool[p].shutdownNow();
         }
      }
      System.out.println("T = "+(double)(System.currentTimeMillis()-BEGINTIME)/1000);
   }
   private static class compareMedian implements Callable<Void> {
      private int jobdex, fracdex;
      private double frac;
      Random rand = new Random();
      private AtomicInteger tasks;
      
      public compareMedian(int p, int c, AtomicInteger tasks){
         fracdex = p;
         jobdex = c;
         frac = FRAC[p];
         subset_busts[p][c] = 0;
         subset_ruins[p][c] = 0;
         this.tasks = tasks;
      }
      @Override
      public Void call() throws Exception{
    	 int e;
         while((e=tasks.getAndIncrement())<SAMPLE){
            int busts = 0;
            double stack = (double)INSTALLMENT;
            double bankroll = INITBR;
            
            for(int r=0; r<ROUNDS; r++){
               double bet = frac*bankroll;
               if(bet>stack) bet=stack;
               else if(bet<MINBET)
                  if(stack>=MINBET) bet=MINBET;
                  else bet=stack; //Allows one extra bet.
               int outcome = rand.nextInt(POSSIBILITIES);
               if(outcome < WIN_POSSIBILITIES){
                  bankroll += bet;
                  stack += bet;
               }else{
                  bankroll -= bet;
                  stack -= bet;
                  if(stack==0.0){
                     busts++;
                     if(bankroll>0.0) stack=(double)INSTALLMENT;
                     else break;
                  }
               }
            }if(busts>0){
               subset_busts[fracdex][jobdex] += busts;
               if(busts==BUYINS) busts--;
               bankroll -= (double)busts*INTEREST;
            }br[fracdex][e] = (short)Math.round(bankroll*.01);
            if(bankroll<=0.0) subset_ruins[fracdex][jobdex]++;
         }
         return null;
      }
   }

Last edited by plexiq; 04-26-2018 at 02:34 AM.

Quote

04-26-2018 , 11:12 AM

#1864

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

I don't have time to read over your changes but I think I agree. It was one of the methods I suggested, where you say make a bunch of packages of 1000 simulations each, make 10 or 20 threads, and "feed" the threads jobs.

This method has more overhead while running the parallel part, but less startup and probably less idle time if done right.

Quote

04-26-2018 , 11:44 AM

#1865

plexiq

veteran

Join Date: Apr 2007 Posts: 2,554

Yeah, I only noticed after posting that you actually suggested that approach earlier.

I'd argue it's more efficient even for the parallel part, because the atomic incrementAndGet calls are probably negligible compared to the additional context switches that occur when running 1000 threads. Idk for sure though.

Quote

05-04-2018 , 10:55 PM

#1866

jduyon

enthusiast

Join Date: Jun 2016 Posts: 58

Hey guys,

I need help on a word pair problem:

For a given list of words, find the word pair with the largest product of each word length, and no matching letters.

So like, the pair:

['foot','ball'] would have a score of 16: len(foot) * len(ball) = 4*4 = 16

A brute force approach is a simple nested loop that checks each word combination and keeps track of the largest pair seen.

That takes O(n^2) time.. Can we do better?

I've thought about reverse sorting the list (largest words first), and doing the same thing - but stopping once we find the first valid pair. This is fast, but there are weird edge cases where it's not the best answer. For instance, if you have a list like:

['aaaaabd','bbbbb','ccccd','fffff']

'aaaaabd', 'fffff' has the highest score of 35, yet bbbbb, ccccd would be chosen because it would be iterated first (and the algorithm would stop).

^ Is this the right approach, but I should just figure out those edge cases? Can I utilize the information I have about the lengths of words I've seen to make some better assumptions?

Quote

05-05-2018 , 01:14 AM

#1867

ChrisV

Carpal \'Tunnel

Join Date: Jul 2004 Posts: 40,336

This is off the top of my head, there might be better ways. Create a function that takes a reverse-sorted word list, starting position, and current best answer and does this:

- If the product of length of first two words in the list is less than or equal to best answer, return current best answer
- Take the first word in the list and iterate over the rest, checking for answers. If you find a new best answer, OR if you reach a point where the product of the lengths is less than or equal to current best answer, return your function invoked recursively on the list, using the subsequent starting position.

Here's a demo of how this would work on the list ['fails', 'foot', 'ball', 'cup', 'hi']:

Current Best	Comparing	Notes
0	fails, foot
0	fails, ball
0	fails, cup	Found new best, invoke recursively on ['foot', 'ball', 'cup', 'hi']
15	foot, ball	Found new best, invoke recursively on ['ball', 'cup', 'hi']
16	ball, cup	4 * 3 <= 16, terminate program returning { ['foot', 'ball'], 16 }

This is guaranteed to return the best answer and should be a lot better than O(n^2) in most cases.

When you reverse-sort the list, also put the words into a data structure that has the length and a bit map of what letters are in the word. Something like a uint32, with rightmost bit showing whether it has any As in it, next bit Bs, next Cs etc. Once you have that, to check whether two words have no letters in common you can just check that a bitwise AND comes out to zero. Also, since you're recursing, careful that you don't create whole new objects on each function call. Rather than just passing in a list, you should pass in a list and a start position, that way you can just operate on the same list object the whole time.

Edit: Having thought about it a bit more, there is no reason to recurse. Just do it all in the one function, changing the start position you're considering.

Last edited by ChrisV; 05-05-2018 at 01:33 AM.

Quote

05-07-2018 , 10:38 AM

#1868

jmakin

banned

Join Date: Jan 2008 Posts: 30,120

this is a really silly Q but I'm terrible at this stuff, I'm trying to HTTP request using a JS function and then print the result to the page from the php function.

here's my JS function:

Code:

<script>
function getData() {
  var xhr = new XMLHttpRequest()
  xhr.onreadystatechange = function() {
    if (xhr.readyState === 4 && xhr.status === 200) {
      console.log(xhr.responseText)
    }
  }

  xhr.open("GET", "/test.php", true)

  xhr.send()
}   
</script>

now, my php function is just a php file that echos "hello" and i want to print this to the web page but it's going straight to the console.

Last edited by _dave_; 05-07-2018 at 04:11 PM. Reason: indentation

Quote

05-07-2018 , 10:42 AM

#1869

jmakin

banned

Join Date: Jan 2008 Posts: 30,120

To clarify: I want to achieve this with an HTTP request. I don’t want to write PHP code inside of my HTML document

Quote

05-07-2018 , 11:09 AM

#1870

txpstwx

old hand

Join Date: Jun 2008 Posts: 1,239

Create an HTML element on the page with the id "result" and do this: document.getElementById("result").innerHTML = xhr.responseText; insead of "console.log(xhr.responseText);".

Quote

05-07-2018 , 11:11 AM

#1871

jmakin

banned

Join Date: Jan 2008 Posts: 30,120

thank you i just figured our i need to use xhr.responseText rather than the console log statement, i have no idea how any of this works and the lectures were super unhelpful.

thank you!

Quote

05-07-2018 , 11:18 AM

#1872

jmakin

banned

Join Date: Jan 2008 Posts: 30,120

i wish we were allowed to use JQuery for this project because every online solution to everything uses it, but I only can use vanilla JS.

I just need to get some data from a SQL database and output it to the page. Not super complicated but I am struggling for some reason.

Quote

05-07-2018 , 03:48 PM

#1873

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

vanilla JS includes the "fetch" library which is somewhat simpler.

console.log() is like... printf or system.out.println(), it's just a print statement.

Code:

fetch('http://example.com/movies.json')
  .then(function(response) {
    return response.json();
  })
  .then(function(myJson) {
    console.log(myJson);
  });

Note that you'll want to actually do something in the final anonymous function, wheras the example, like your example, just prints it.

Quote

05-07-2018 , 03:50 PM

#1874

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Also I'll be frank and say I don't know JS really, but I don't understand why this canonical example isn't just this:

Code:

fetch('http://example.com/movies.json')
  .then(function(response) {
    console.log(response.json());
  })

I suspect it's because response.json() returns a promise and not an actual value and that there's no magic to resolve that for you.

https://developer.mozilla.org/en-US/...PI/Using_Fetch

Quote

05-07-2018 , 04:15 PM

#1875

_dave_

_Pooh_Bah_

Join Date: Feb 2005 Posts: 13,146

Jmakin, I fixed your indentation (get vscode+prettier if you can!)

you need your function to add at the end:

Code:

return xhr.responseText

and then do something with it after you call the function, or within the function itself do something with the result to display it on the page.

txpstwx's response is vanilla JS, and a good suggestion.

You could probably just use a simple

Code:

document.write(xhr.responseText)

which is similar to console.log, except it outputs to the html page - but probably not something you'd use much in actual pages compared to setting the contents of a pre-positioned DIV.

Last edited by _dave_; 05-07-2018 at 04:21 PM.

Quote

Page 75 of 80

First

25 55 65 70 71 72 73 74 75 76 77 78 79 80

Last

Post Reply Subscribe

...

Page 75 of 80

First

25 55 65 70 71 72 73 74 75 76 77 78 79 80

Last