Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: how to do write this method with more efficiency ?

  1. #1
    Junior Member
    Join Date
    Sep 2012
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default how to do write this method with more efficiency ?

    The program below accept two array with hole pozitive nums, with same size N, and fill empty array "c" with nums of "a" that do not exist in "b" and return the biggest num of "a" that do not exist in "b".
    qustion: how to do write this method with more efficiency ?

     
    public int f(int[]a, int[]b, int[] c)
    	{
    		int N = a.length;
    		int j, max = 0, g = 0, t = 0;
     
    		for(int i=0; i < N; i++)
    		{
    			for(j=0; j<N; j++)
    				if(b[j] == a[i]) // if find the num in "b" go to the next num in "a"
    				   break;  
     
    			if(j == N)
    			{
    				c[t] =a[i]   // fill empty array "c" with nums of "a" that do not exist in "b"  
     
                                                            if(g ==0 || c[t] > max)
    				{
    					max = c[t]; // remmber the max num in "max"
    					g = 1; 
     
    				}
    				t++;
     
    			}	
     
     
    		}
    		return max; // max of "a" that you do not have in "b"


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,620
    Thanks
    50
    Thanked 2,235 Times in 2,207 Posts

    Default Re: how to do write this method with more efficiency ?

    Can you post a description in pseudo code of the logic of the posted code?

    Also posted at http://www.java-forums.org/advanced-...fficiency.html
    Last edited by Norm; October 1st, 2012 at 09:38 AM.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: how to do write this method with more efficiency ?

    Quote Originally Posted by romavolman View Post
    ...more efficiency ?
    Question:
    What is the time complexity of the code that you posted?

    I won't keep everyone in suspense; I'll give the answer in terms of a commonly used metric. Reference: Big O Notation - wikipedia

    It is O(N squared).

    Summary: The outer loop goes through all of the N elements of a. So the complexity contributed by the outer loop O(N).
    For each element in a, the inner loop goes through the N elements of b unless and until a matching value is found in b. Assuming that the elements of b are "randomly" ordered, the average number of times through the second loop is N/2. (So the complexity contributed by the inner loop is also O(N).

    Conclusion, as N gets larger, the total number of comparisons gets larger at a rate proportional to N squared. (Multiplicative constants like 1/2 are commonly omitted in Big-O expressions.)

    If we assume that the most time is consumed by the decision-making comparison and the resulting conditional branch that determines whether to put the element into array c, the time of the entire process will be primarily affected the total number of comparisons, which is equal to the product of number of times through the outer loop and the number of times through the inner loop.

    Therefore, the time complexity is O(N) times O(N), which, according to Big-O analysis described in the above reference, is equal to O(N squared).
    QED

    Next question: Can this be improved?

    Well...

    Here's a thought that came to me as a result of remembering a scene from an old Sherlock Holmes movie many years ago (Basil Rathbone, Nigel Bruce). Sherlock had two sets of papers. Each piece of paper had a number written on it (taxi registration numbers collected by several of his Baker Street Irregulars at two different locations or some such thing).

    He needed to make a list that consisted of numbers there were common to both sets. (This is slightly different from your problem where you need to find numbers that are in one array and not in the other, but the procedure can be the same and the time complexity will be the same.)

    I seem to remember that he didn't know whether or not any of the numbers in the first set were duplicates, and he wanted a list of all numbers that were common to the two sets.

    Anyhow...

    Time was of the essence, and he figured out that taking one number at a time from the first set and riffling through the second set for each one, starting with the paper on top and looking at papers of the second set one at a time, continuing unless and until he found a match, would take too long (the bomb was ticking).


    So Sherlock had a Better Idea: What if the papers in the second set were sorted according to the values of the numbers? (A little overhead here, performed only once: Sort the second set.)

    Then...

    It would be much quicker to see whether a given number from the first set is also in the second set, by the following procedure:

    For each number from the first set, you would start at the top of the second set, and you might get lucky. The number might match. If it did, then you are through with this search, so you do whatever you do in case of a match and go on to the next number in the first set.

    But if it didn't match, then you would "cut the deck" (the second set) in half and see if the number on top of the second half was less than, equal to, or greater than the number you were looking for. Maybe it would match, and you are through for this search. Put the second set back together again (still sorted), and go on to the next number in the first set.

    If it was not equal, then, since the second set is sorted, you could use the value of the number on the top sheet of the second half of the second set to decide whether the number you are looking for can be in the first half or the second half of the "cut" deck.

    Then...

    Take the selected half and "cut the deck" in half again. Repeat the inspection/selection process until either

    1. You have found what you were looking for.

    or

    2. You have cut the deck in half so many times that you have run out of things to cut. (Meaning that you have eliminated the possibility of finding it.)

    This procedure is known as a binary search algorithm, and its complexity is O(log(N)). Reference: Binary Search Algorithm - wikipedia

    So...

    Time complexity of the inspection process is O(N) (from the outer loop) times O(log(N)) (from the binary search), which is equal to O(N log(N)). Reference: Big O Notation - wikipedia (again)

    Now if you select a sort algorithm that is O(N log(N)) (remember, you only do this once), the total complexity is O(N log(N)), which, generally speaking, will be less than O(N squared).


    So, here's a plan: Sort array b. For each element in the array a, do a binary search of the sorted array b looking for that number. Act accordingly, and continue until you have run through all of the elements of a.

    Now, it just happens that...

    The java.util.Arrays class has convenient overloaded methods for sorting and performing binary searches that work great (and painlessly for the programmer) with arrays of ints.

    Note that, because of other things that go on in programs (time taken for things other than comparisons), the advantages might not be startlingly better for small arrays. In fact if you benchmark it for small arrays, the run times might even be longer for the "optimized" algorithm, but for larger arrays, we can expect improvement in average execution times.

    That's what the Big-O stuff (as well as other kinds of statistical analysis) is all about: Expectations, not guarantees.

    Final note: There may be additional optimization possibilities, but maybe this can be at least a start for further investigation. Once you break out of the "naive" mindset of nested loops going through the two sets, other things might occur. Let the creative juices flow...


    Cheers!

    Z
    Last edited by Zaphod_b; October 2nd, 2012 at 10:49 PM.

Similar Threads

  1. Need to write a public instance method for a simple dice program
    By akira25 in forum Object Oriented Programming
    Replies: 3
    Last Post: April 9th, 2012, 04:46 AM
  2. Write a method that searches the BST for a given input
    By Jurgen in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 6th, 2012, 10:46 AM
  3. Efficiency problem
    By mccolem in forum What's Wrong With My Code?
    Replies: 6
    Last Post: November 4th, 2011, 03:44 PM
  4. [SOLVED] Why can't I write to file inside a doGet() method?
    By FailMouse in forum Java Servlet
    Replies: 1
    Last Post: July 7th, 2010, 01:15 AM
  5. variables and efficiency
    By catkinq in forum Java Theory & Questions
    Replies: 3
    Last Post: February 7th, 2010, 05:09 AM