Stan Austin

tasked to find the (K) largests numbers in an array of 50 million integers, the number range from 1-10 digits in length (0- 9,999,999,999)
there is a constraint to not use more than 500 Kilobytes of memory and identify the top 5000 numbers in under 1.75 seconds.
looking at performance programming i found that the best approach is to convert the array into a maxheap size (K) and as it is filled with ever larger number the smaller ones pop themselves out.
I got the max heap working so when I store the whole array in the heap i can find the top K numbers.

here is what I have so far;
public class TestClass { public int size; public int [] mH; public int position; public TestClass(int size){ this.size=size; mH = new int [size+1]; position = 0; } public void createHeap(int [] myArray, int K){ if(K>0){ for(int i=0 ;i<K;i++){ System.out.println("creating heap" + myArray[i]); insert(myArray[i]); } } } public void display(){ for(int i=0;i<mH.length;i++){ System.out.print(" " + mH[i]); } System.out.println(""); } public void insert(int x){ mH[position++]=x; bubbleUp(); System.out.println("inserting: " + x + "@position:" + position); } public void bubbleUp(){ int pos = position-1; while(pos>0 && mH[pos/2]<mH[pos]){ int y = mH[pos]; mH[pos]= mH[pos/2]; mH[pos/2] = y; pos = pos/2; } } public int extractMin(){ int min = mH[0]; mH[0]=mH[position-1]; position--; heapifyDown(0); return min; } public void heapifyDown(int Z){ int largest = Z; if( 2*Z+1 < position && mH[Z] > mH[2*Z+1]){ largest = 2*Z+1; } if(2*Z+2 < position && mH[largest] > mH[2*Z+2]){ largest = 2*Z+2; } if(largest!=Z){ swap(Z,largest); heapifyDown(largest);} } public void swap(int a, int b){ System.out.println("swapping" + mH[a] + " and " + mH[b]); int temp = mH[a]; mH[a] = mH[b]; mH[b] = temp; }    public static void main(String args[] ) throws Exception {        int K = Integer.parseInt(args[0]); int myArray[] = FastRead.FastReadArray(args[1]); int N = myArray.length; int i = 0;                        TestClass m = new TestClass(K+1); m.createHeap(myArray, K); m.display();                                for(i=0;i<myArray.length;i++){ System.out.println(m.extractMin()); }                 Stopwatch st = new Stopwatch(); double time = st.elapsedTime(); System.err.println("Elapsed Time: "+time+" s"); } }
Error message from cmd line:
D:\Users\Stefan\Documents\uni projects and assignments\computer science\CSCM12 Computer Efficiencies\CW2>java TestClass 2 input\Input3.bin creating heap34686901 inserting: 34686901@position:1 creating heap6193869 inserting: 6193869@position:2 34686901 6193869 0 0 34686901 6193869 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1        at TestClass.extractMin(TestClass.java:41)        at TestClass.main(TestClass.java:82)
Any help greatly appreciated. Thanks

Liutauras Vilda wrote:1. Another observation. If from the command line arguments you get an array of names, you don't actually need the loop to put everything to 'person' array.
You can simply do: String[] person = args; In fact, you don't even need that, you can pass just 'args' to your method.

I did originally do this but i had lots "more" errors occur so thought since they are there then i will just call them.

Liutauras Vilda wrote:2. Going further. You don't need to pass argslength as an argument and have it as a paremeter in longest_name() method, as you can identify that from the already passed array. Less arguments - better.

is this person[].size?

Liutauras Vilda wrote:3. Method name longest_name isn't conventional, it supposed to sound 'longestName'.

explicit instruction from tutor

Liutauras Vilda wrote:Q: What are you trying to achieve with this line of code?
if (argslength % 2 == 0)I understand what this line technically does, but what are you trying to achieve with this in general?
As well as you have such line:
for (int i = 0; i < argslength; i = i + 2)This is something uncommon, verify you understood correctly given requirements.

so I'm going to split this section of main into 2, if there are even args, read as described in code... however if there is an odd number of args then i will have one remaining... this i will treat as an outlier and print using the toString method in Employee, on its own... it's not elegant but it should be effective (and probably an extra 25 lines of code than needed :'D)

so the array should be for example  {bob, 123, john, 1234, steve, 12345, mike, 4}
so the next step is a function that add all the odd array inputs

Liutauras Vilda wrote:I think lines of your posted code are not in synch with what you have in your Netbeans, presumably because you have posted just a snippet of code. In different words, error occurs at line 24 as compiler says, but we don't see here that line 24.

yes sorry i missed the top lines package and public class to save space... (as such it moved everything up 4 lines)

Liutauras Vilda wrote:Line 20 in the posted code contains compiler error too, you can't pass 'person[]' like that. That shouldn't have '[]'.

So simple but effective, thank you i will note this down!

Liutauras Vilda wrote:And yes, indentation a bit better, not ideal yet, but better

Thank you i will work on this once my schedule clears up abit

Liutauras Vilda wrote:Somehow I feel you need organize yourself a bit more. Problem is in my opinion, that you solving this exercise in a trial and error way. Randomly trying things and expecting to see if it works - that is usually not a good way, at least not so efficient, so you shouldn't expect quick results.

haha in all honesty I have been so crazy busy at work, coding has just been forgotten about for the last 3 weeks, (and I only started 7 ago :/ not a good start really) yet I am meaning to keep up, so this is a slap-dash attempt to put the program together by any means...
as i have fallen behind, it could be lack of organisation, but essentially i have bitten off more than i can chew, also programming isnt as easy as i thought it would be

Liutauras Vilda wrote:Try to read some literature on relevant topics, so you'd feel a bit more confident. There are Oracle tutorials (google for it), could learn a lot from there.

I will get onto this I'm confident i will have more time after xmas, so that is the plan.
But thank you for pointing out my error, hopefully I will get it finished in time to actually sleep before work :'D (thanks again)

New code; still not compiling, the Error is on line 24 erroneous tree type: <any>
Also says cannot find class, person (still line 24) and "value" required "class" found.
I have tried re-writing it in several ways but it then just doesn't call the method, is my method signature wrong too?
(reason the longest name is i+2 is because every other argument will be an string and others an int that is allowed right?)

Hopefully this is much better formatting. i am using netbeans Formatting here and have created it as it's own little program not an excerpt of the bigger thing, so hopefully that helps.
Any pointers on this?

   public static String longest_name(String[] person, int argslength) {        int maxLength = 0;        String longestName = null;        for (int i = 0; i < argslength; i = i + 2) {            if (person[i].length() > maxLength) {                maxLength = person[i].length();                longestName = person[i];            }        }        return longestName;    } public static void main(String[] args){ int argslength = args.length;    if (argslength >= 4) {        if (argslength % 2 == 0) {            String[] person = new String[argslength];            for (int i = 0; i < argslength; i++) {                person[i] = args[i];            }            String longestName = longest_name(person[], argslength);            System.out.println(longestName);        }    } }

Carey Brown wrote:This is your culprit
i = i++

ahh now im getting errors .... and lots of them :'(
Thanks though at least I know where to start picking from (Y)

Liutauras Vilda wrote:Your code indentation is terrible. And you should have spent 2 minutes on fixing that before you post. No excuse, at all  

okay i will work on it, however i did spend about 5 mins adding indentation just for you, after your responce earlier in the topic, i had actually noted it and attempted to ensure it was better this time.
however i wonder if you know how to help me or just point out my short comings as a newbie

Haha, im not sure what assert even does, but they are there. and i've just ignored them.
My course is sponsored by my employer, i would have to fail then have to pay my employer, then try to get money back after the fact... im going to stick with passing in the first instance lol.
and yes i was trying to get find int overflow, and no that code didnt work... it does now you will be pleased to hear.
I am not stuck further on in the assignment that is due in under 12 hours :'(

this code just runs on no compiler errors, no prints just a complete blank until its manually stopped... any idea why?

 public static String longest_name(String[] person, int argslength) {      int maxLength = 0;      String longest_name = null;            for (int i=0; i < argslength; i=i+2) {          if (person[i].length() > maxLength) {              maxLength = person[i].length();              longest_name = person[i];          }      }      return longest_name;  } public static void main(String[] args){   int argslength = args.length;            String[] person = new String[argslength];            for (int i = 0; i < argslength; i = i++) {                person[i] = args[i];            }            String LongName = longest_name(person[i], argslength);            System.out.println(LongName); } String LongName = longest_name(person[i], argslength); System.out.println(LongName); }
Thanks

so I'm not sure if we are now moving on as the original question has been solved, if so i will raise a new question but since there is substantial background here i thought this would be easier...

so you guys are propably going to laugh as i think i have made a real dogs dinner of it... I'm Pretty tired (and a little stressed) now after being at it for hours tonight, Issue is I'm on a very tight dead line
but my code for changing the salary (in the main)

if (argslength == 3){ int salary= Integer.parseInt(args[1]); int modify = Integer.parseInt(args[2]); if (change_income == true){ int ModifiedSalary;     if (modify >= 0) ModifiedSalary = e1.bonus(modify); if (modify < 0) ModifiedSalary = e1.penalty(modify); Person e1 = new Person(args[0], ModifiedSalary); System.out.println(p1); } if (change_income == false) System.out.println("Failure."); }

and my code for the function.
   public static boolean change_salary(String[] args,int ModifiedSalary){    int modify = Integer.parseInt(args[2]);    if (modify >= 0) ModifiedSalary = p1.increase(modify);    if (modify < 0) ModifiedSalary = p1.decrease(modify);                if (ModifiedSalary < Integer.MAX_VALUE) return false;        if (ModifiedSalary > Integer.MIN_VALUE) return false;    return true ;        }
should be able to see what i am trying to do
but the issue i am having is that it is trying to Find my method, change_salary as a variable, when i want it to be a method being called, am i being really daft here? (dont answer that lol)
Thanks in advance

Campbell Ritchie wrote: I think that suggestion will do what is required of you. Why not post the code as it really shou‍ld be, rather than messing up the method names?

because I'm certain my lecturer does google searches of his own assignment to find plagerism, and so i dont risk getting accused if someone posts a very specific answer here that i think is the only way to code the solution this will help.

Campbell Ritchie wrote:What is wrong with line 33? It looks all right to me. I suggest you go through the documentation for (System.out).println() and keep following the links untill you find what method is called in the argument object.

nothing the line 33 is how i want my print formatted, i now have this working as for what method is being called, that has been confusing me but i think it is the Employee method of the Employee class, isnt it?

Campbell Ritchie wrote:
Did you only have an equals method? In that case it has been overridden incorrectly; if you look here, you will find out that you must override hashCode() too.

what now? the equals method, it compares two name to find out if they are the same right? some how we need to use that method, provided in the Employee class in the function we write. or that is how i have interpreted it, I have only just got to the first function now...
change the employees income by applying a bonus or penalty. (this is to be taken from the 3rd argument entered in the command line) our function should call the bonus and penalty methods, and it should return false if there is overflow or underflow of int.
currently working on this... using Pauls Previous comment as a bit of a guide line

Paul, good news i have got one stage further.
I am now getting the name and it is even printing as it should

if (argslength == 1){ Employee e1 = new Employee(args[0]); System.out.println(e1); }

printing e1 and e1.salary cant be done in the same println statement or it falls over seemingly, so that has cured that issue, also the increase decrease, do work.
not that i can get it to do it via the function but im one step closer thank you!!

Paul Clements wrote:
Do you understand this code and output?

yes, simple. lol
but that doesn't do what i require...
getting to increase and decrease salary seems like 20 steps away.
first i just need it to print as specified in Employee on line 33. surely?
at the moment i cant get the default salary to print yet alone manipulate it...
also i need to enter the name using the command line and for
Employee e1 = new Employee(args[0]);
the input isnt working :/

the error i get is:
non-static method salary() cannot be referenced from a static context

Paul Clements wrote:

Stan Austin wrote:however if i try to print "Employee.salary" it tells me salary is private!

Yes. That's called "encapsulation". It means keeping instance variable private and only allowing manipulation though the classes own methods i.e. what are commonly known as setters and getters. The getter on 'Salary' is salary(). Therefore if from within manage. java you create an Employee instance called e1 then e1.salary() should return what's held in 'Salary'.

Sorry im not sure i get this, been toying with it for the last 10 mins and I'm getting nothing
Is how i have defined an Employee an Employee instance as per your definition, or do i need a different way of creating an instance of employee too?

Paul Clements wrote:Stan, keep it simple. One step at a time i.e.
...
Build slowly on something which works. Don't get lost thinking too far ahead.

so i have Manage.Java
and i can hard code

if (argslength == 1){ String Employee = args[0]; System.out.println("Employee" + ": " + "0" ); }

Thus entering the default salary, by hand but im certain this isnt what is being asked for, however if i try to print "Employee.salary" it tells me salary is private!
same if i tried to add or subtract from it
this also happened if i attempted to add a name... hence my confusion why has this program been given to us if its not useable... or what am I doing wrong...
Thanks

so would the employee instances be held in my own program? and not need to call the Employee program/File?
i ask because the print should be formatted as it is on line 33.
when this program is run it works, new employee, "mike" is then printed as Mike: 0
also what is this assert that is in each function, I haven't seen that before.