• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Checking Runtimes of Algorithms

 
Greenhorn
Posts: 6
C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

I'm currently doing a sorting project where we have to implement random arrays for 10, 100, 1000, 10000, and 100000 elements per sorting algorithm. I've created a method to generate the arrays and I've done some of the sorting methods in order to calculate clock times, array access times, and comparison times. I'm running into a problem with a few of my algorithms. For the one method algorithms like bubble sort and selection sort, I was fine. But when I got into merge sort and quick sort, I see some issues popping up. Can someone please take a look at what I've done wrong?

Generate array


Analysis


mergesort


quicksort with insertion sort


The issue popped up with QuickSort alone as well.
This is how I'm calling it in the main method


Thank you for your help!
 
Saloon Keeper
Posts: 10834
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You'll be wanting to do the start/end time gathering and analysis outside of any of your sort methods, i.e. in main().
 
Carey Brown
Saloon Keeper
Posts: 10834
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Your array access and comparison times are far below the granularity of milliseconds. I don't think you can capture this with nano seconds. In general, to measure the performance of something that something must be run many times and the overall difference in time calculated and divided by the number of times run. In your setup you can do this for any sort method but not the array times within the methods.
 
Max Brown
Greenhorn
Posts: 6
C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So I moved out the clock time calculation and analysis to the main method. So far, its been working for everything but when I bring up the 100000 element arrays, I get errors
Main Method


quicksort regular



partition


Error:


So where would I place the array access checks?
 
Rancher
Posts: 5008
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Exception in thread "main" java.lang.StackOverflowError
   at project1.Project1.quicksort(Project1.java:43)
   at project1.Project1.quicksort(Project1.java:47)


Looks like there is a recursive call at line 47.  Can you post the code that shows lines 43 and 47
 
Max Brown
Greenhorn
Posts: 6
C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is where the error is


it only shows up for 100000 elements. works otherwise
 
Ranch Hand
Posts: 574
VI Editor Chrome Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you really want to get tangled up in your underwear take a look at the Time Stamp Register.  It's a 64 bit register that counts clock ticks.  Back in the day it was a great way to get nanosecond resolution.  Then some perverted boffins invented stuff like multiple cores, threads, and CPUs that could adjust their clock frequency based on demand.  If you're clever you can work around these, I'm not that clever.

If you want I might still have some C++ code I wrote about 20 years ago that uses the register, I'd just have to dig around to find it.

Then again, I have no idea how you could read a hardware register in Java.

Caveat:  I haven't looked at this register in 20 years, I'm not even sure it still exists in modern CPUs.  It may also be Intel specific.

Edit:  Looky what I found.



 
Marshal
Posts: 79520
379
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can you actually reach that register from Java®?

I would suggest a few things for simple performance testing:-
  • 1: If you are doing anything beyond the most basic and simplest timings, get yourself a profiler program.
  • 2: You have an optimising compiler and runtime. Before you try any timings, be sure to run all the code you are going to test, so you get > 10,000 iterations. For example, sort a few 1,000,000 element arrays before you test anything. That will encourage the JVM to implement all the optimisations.
  • 3: Timings are not exact, and vary. I have found cses where alorithm A runs 10% faster than algorithm B 75% of the time, and the other 25% of the time alorithm B is 10% faster! Ignore any differences that small.
  • 4: Try the System#nanoTime() method for timings.
  • I am adding this disucssion to our preformance forum.
     
    reply
      Bookmark Topic Watch Topic
    • New Topic