Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / New
Stats: 3,177,328 members, 7,900,799 topics. Date: Thursday, 25 July 2024 at 05:06 PM

Improve The Speed Of This Java Code. - Programming - Nairaland

Nairaland Forum / Science/Technology / Programming / Improve The Speed Of This Java Code. (3278 Views)

Help Me Solve This Java / Help Debug This Java Code / Better Way Of Writing This Java Code (2) (3) (4)

(1) (Reply) (Go Down)

Improve The Speed Of This Java Code. by logic101: 11:10pm On Oct 18, 2011
Aim .the aim of this code is to print out all 9 digits numbers that have perfect squares .
all 9-digit perfect squares, if any, that uses all the digits 1 to 9 exactly once.
For example, 139,854,276 is a solution as 11,8262 = 139,854,276.

this is my own code but my run time is slow,


public class NineDigitPerfectSquare {
         private final static int BEGINNING=10000000;
         private final static int END=999999999;

public static void main(String[] args) {
//System.out.println(isPerfect(65));

String s= printPerfectNumbers();

for(int i=0;i<s.length();i++){
System.out.println(s.charAt(i));

}


}

public static boolean isOrdered(int []numbers){
// int value=1;
 

for(int i=0,value=1;i<numbers.length;i++,value++){
if(numbers[i]!=value)
return false;
}
return true;

}


public static void bubblesort(int[]numbers){
int temp=0;
for(int i=numbers.length-1; i>1;i--){
for(int j=0;j<i;j++){
if(numbers[j] > numbers[j+1]){
temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;

}
}
}
}


public static int[] convertStringToIntArray(String s){
int permutation[]=new int[s.length()];
for(int i=0;i<permutation.length;i++)
permutation[i]= Character.digit(s.charAt(i),10);

return permutation;

}

public static boolean isPerfect(int n){


int x=1;
int sum=1;

while(sum<n){
x=x+2;
sum=sum+x;

}
return (sum==n);
   
}

public static boolean isPerfectSquare(int n){
return (Math.sqrt(n)==Math.floor(Math.sqrt(n)));
}



public static String printPerfectNumbers(){
int [] number1=new int[9];
String s=" "; String p="";
for(int i=BEGINNING ; i<=END ; i++){
if(isPerfectSquare(i) )
{
p=""+i;
// p.trim();
number1=convertStringToIntArray(p);
bubblesort(number1);
if(isOrdered(number1))
{
s=  s +  "  ,  " + i;
}

}
}
return s;
}
}
Re: Improve The Speed Of This Java Code. by Nobody: 6:16am On Oct 19, 2011
Re: Improve The Speed Of This Java Code. by Nobody: 6:58am On Oct 19, 2011
Re: Improve The Speed Of This Java Code. by logic101: 7:37am On Oct 19, 2011
omotodun i would luv to be your programming  son lol,
please do you mind explaining this bit of your code

public static boolean isSet(String squared) {
      int[] tens_digit = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
      char c;

      for(int i = 0; i < 9; ++i)
         if((c = squared.charAt(i)) == '0' || ++tens_digit[c - 48] > 1)
            return false;

      return true;
   }
Re: Improve The Speed Of This Java Code. by logic101: 7:38am On Oct 19, 2011
and also can you tell me if you know why my output was missing some results
Re: Improve The Speed Of This Java Code. by Nobody: 8:52am On Oct 19, 2011
Re: Improve The Speed Of This Java Code. by ektbear: 7:54pm On Oct 19, 2011
That is pretty nifty, @omo_to_dun.

Very much correct that you can search over square roots rather than squares. And your hashing-like approach to testing that each number is contained in the set {0,, 9} is much cheaper than sorting.

So quite a bit faster than the original.

(Side comment: Isn't bubblesort really, really bad? Even if you want to use a slow N^2 sort, I thought you were supposed to use insertion sort, since it has better behavior [both better theoretical constants and better performance in the real world.] Also, does anyone know if bubblesort or insertion sort is actually faster in practice for a list of size 10? What do the Java libraries use on small lists?)
Re: Improve The Speed Of This Java Code. by naijaswag1: 10:22pm On Oct 19, 2011
@ekt_bear

quicksort

I actually copied what i will paste here from the java 6 documentations of Arrays class,this is part of the description of all the overloaded sort methods


The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
Re: Improve The Speed Of This Java Code. by ektbear: 10:32pm On Oct 19, 2011
I thought that insertion sort ends up being faster on small lists? Like here where the list of size 10, I'm wondering if it won't be slightly faster in practice, despite being N^2 to Qsort's NlogN.

(For example if insertion sort is say  N^2 and Qsort is 10NlogN, then you go with insertion sort for small lists on a list of size 20, since 20^2=400 is smaller than 10*20*log2(20) ~ 864.)

Hrm, here is what Wikipedia has to say:

Optimizations
Two other important optimizations, also suggested by R. Sedgewick, as commonly acknowledged, and widely used in practice are:[6][7][8]

- To make sure at most O(log N) space is used, recurse first into the smaller half of the array, and use a tail call to recurse into the other.
- Use insertion sort, which has a smaller constant factor and is thus faster on small arrays, for invocations on such small arrays (i.e. where the length is less than a threshold t determined experimentally). This can be implemented by leaving such arrays unsorted and running a single insertion sort pass at the end, because insertion sort handles nearly sorted arrays efficiently. A separate insertion sort of each small segment as they are identified adds the overhead of starting and stopping many small sorts, but avoids wasting effort comparing keys across the many segment boundaries, which keys will be in order due to the workings of the quicksort process. It also improves the cache use.
http://en.wikipedia.org/wiki/Quicksort

I suspect that this Quicksort implementation used in Java detects small lists and just runs insertion sort on them. Would have to read this paper you mentioned to be sure, though.
Re: Improve The Speed Of This Java Code. by logic101: 12:34am On Oct 20, 2011
Thank you omotodun, Your a good teacher.I am still litttle bit confused on your algorithm but i would figure it tonight lol,
Re: Improve The Speed Of This Java Code. by Nobody: 9:48am On Oct 20, 2011
omo to dun, i like your reasoning
Re: Improve The Speed Of This Java Code. by Beaf: 10:04am On Oct 20, 2011
@omo to dun
Your sites registration doesn't work 100%, I received no email.
Re: Improve The Speed Of This Java Code. by Nobody: 10:53am On Oct 20, 2011
me need help with dis 1

$query = "SELECT b.*, u.nick, u.country, u.rate_sum FROM " . $DBPrefix . "bids b
LEFT JOIN " . $DBPrefix . "users u ON (u.id = b.bidder)


i wanna add another table called buyers with the same column WITH users
Re: Improve The Speed Of This Java Code. by Nobody: 10:57am On Oct 20, 2011
I'm learning.
Re: Improve The Speed Of This Java Code. by SayoMarvel(m): 11:53am On Oct 20, 2011
@omo_to_dun
good job!
Re: Improve The Speed Of This Java Code. by gymer(m): 1:43pm On Oct 20, 2011
You will not see the likes of Blacksta, Gbawe, Eko-Ile, Dayokanu, etc contributing in knowledgeable task like this. There own expertise is calling people names. Beaf I know has done something like this before and I was so impressed. Omo_to_dun also receive my resppect. Keep it up. It shows that NL is not only for names calling and insulting our leaders.
Re: Improve The Speed Of This Java Code. by Nobody: 4:26pm On Oct 20, 2011
Re: Improve The Speed Of This Java Code. by dammytosh: 4:54pm On Oct 20, 2011
@Omo_to_dun,

Thanks for your time. I really appreciated the fact that u ran the code the user posted and even spotted the errors.
Re: Improve The Speed Of This Java Code. by logic101: 10:48pm On Oct 22, 2011
@ omo t0 dun happy weekend bros, just a small question
i am a little bit confused  with this part.i understand the [c-48] part but i cant see any character being passed into the c.
the only time a character is passed into the c is c = squared.charAt(i).i also dont understand how your increasing the frequency.

++tens_digit[c - 48] > 1
Re: Improve The Speed Of This Java Code. by ektbear: 10:53pm On Oct 22, 2011
He assigns a value to c earlier in the line.

"++x" immediately increments the variable x.

If he instead did:


tens_digit[c - 48]++ > 1


Then you'd be checking the old value of tens_digit, not the incremented value.
Re: Improve The Speed Of This Java Code. by logic101: 11:04pm On Oct 22, 2011
thanks ekt

(1) (Reply)

Who Attended The Hack Lagos Traffic Big Data Materclass Powered By Andela? / Why You Should Probably Drop Out Of A Nigerian Uni And Learn To Code. / Asp.net, Vb.net, C# Help Needed

(Go Up)

Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health
religion celebs tv-movies music-radio literature webmasters programming techmarket

Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 29
Disclaimer: Every Nairaland member is solely responsible for anything that he/she posts or uploads on Nairaland.