Win a copy of TensorFlow 2.0 in Action this week in the Artificial Intelligence and Machine Learning forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Checking Runtimes of Algorithms

 
Greenhorn
Posts: 6
C++ Java
  • Mark post as helpful
  • send pies
  • 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: 7395
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • 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: 7395
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • 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
  • 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: 3927
36
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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: 70714
288
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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.
     
    What are your superhero powers? Go ahead and try them on this tiny ad:
    the value of filler advertising in 2020
    https://coderanch.com/t/730886/filler-advertising
    reply
      Bookmark Topic Watch Topic
    • New Topic