There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
There are three kinds of actuaries: those who can count, and those who can't.
Being Java programmer.
Campbell Ritchie wrote:Are you supposed to produce lots of different ways to remove duplicates, or find the most elegant way.
In this case, I think Campbell Ritchie gave you a good solution.Skott Elliott wrote:now I'm tasked with getting the most effective/efficient way of doing this in an ArrayList;
Being Java programmer.
It isn't a black hole at all, but an opportunity to rise to the challenge. You must acknowledge all suggestions given here. How you do that depends on how formal they want you to be about the problem. You can now create yourself a List with millions of words in. Download a text‑only version of the Bible, War and Peace, Complete Works of Shakespeare or similar from Project Gutenberg and read every word into your List. Go through all the algorithms and work out which run in linear time, which quadratic and which nlogn complexity. Write down your reasoning for all those. Find out how to time the execution of your algorithms, and also how to trick the JIT compiler into getting to full speed before you start your timings. Find out how many of those techniques can be parallelised to take advantage of multi‑core processors. Find out whether the fastest technique is different for a 1000000‑word collection and a 20‑word collection.Skott Elliott wrote:. . . a never ending black hole. . . . I'm not sure if this is a clue of things to experiment with, or if it's how I should track which is most efficient.
You will need more than tea and water. . . litre of water and cup of tea and have a think.
That's a pleasureThanks for all the help and replies . . .
Campbell Ritchie wrote:
It isn't a black hole at all, but an opportunity to rise to the challenge. You must acknowledge all suggestions given here. How you do that depends on how formal they want you to be about the problem. You can now create yourself a List with millions of words in. Download a text‑only version of the Bible, War and Peace, Complete Works of Shakespeare or similar from Project Gutenberg and read every word into your List. Go through all the algorithms and work out which run in linear time, which quadratic and which nlogn complexity. Write down your reasoning for all those. Find out how to time the execution of your algorithms, and also how to trick the JIT compiler into getting to full speed before you start your timings. Find out how many of those techniques can be parallelised to take advantage of multi‑core processors. Find out whether the fastest technique is different for a 1000000‑word collection and a 20‑word collection.Skott Elliott wrote:. . . a never ending black hole. . . . I'm not sure if this is a clue of things to experiment with, or if it's how I should track which is most efficient.
Now you will be busy for the next four hours doing all that and writing it down. If what you write is any good, post it here for us to admire.You will need more than tea and water. . . litre of water and cup of tea and have a think.
That's a pleasureThanks for all the help and replies . . .
Learning the language is easy, but programming is renowned for being a difficult activity.
All things are lawful, but not all things are profitable.
Knute Snortum wrote:Big Hint: what happens if the key value is already present?
All things are lawful, but not all things are profitable.
Campbell Ritchie wrote:Why do you need the remove method?
What you can do is put all the elements of your List as Keys into the Map, and use a dummy object as a Value. You can actually use the same instance for the Value for every pair. If you go through the code for HashSet, you will find that is how it is implemented. Then you can iterate the Key set in the Map and put everything into another List. If you use a LinkedHashMap rather than an ordinary HashMap, you should get the order of insertion maintained in your new List. You may need some condition like:-
if (!myMap.containsKey(myList.get(123))) ...
Don't copy and paste that code.
Go through the documentation for those different kinds of Map and see what it says, and the Java™ Tutorials.
There is nothing inane about your post; I was considering reporting it to the other mods as an interesting thread. What appears to have happened is that you have been given a rather awkward additional requirement, to remove elements from the current List without creating a new List. That is probably done to make the task more challenging and see how you handle it. They are probably only being awkward like that so as to see how good you areSkott Elliott wrote:. . . I see you get a lot of inane posts like this from others. . . .
Campbell Ritchie wrote:
There is nothing inane about your post; I was considering reporting it to the other mods as an interesting thread. What appears to have happened is that you have been given a rather awkward additional requirement, to remove elements from the current List without creating a new List. That is probably done to make the task more challenging and see how you handle it. They are probably only being awkward like that so as to see how good you areSkott Elliott wrote:. . . I see you get a lot of inane posts like this from others. . . .
What is Timer? Is it an app to time your execution time? If so, why do those methods appear to be static?
You appear to have used caps lock in line 1
Why have you changed from Strings to Integers?
How are you populating your List? That would be interesting to see. I have my own ideas about how to populate a List<Integer>.
What do you know about for and while loops for Lists? What do you know about their performance? There are all sorts of interesting things you can find out there, and you can do that all in about 20 minutes of you look in the right place.
Why are you iterating your loop backwards? Why have you written > 1 in the loop? Why are you catching the out of bounds Exception? Do you know how to write a for loop so you can never get an out of bounds Exception?
did this give correct output? I don't think so.Skott Elliott wrote:
Then just decrement i by 1 i.e. i--; when condition returns true.We are going to carry on to the original end of the ArrayList, which is impossible since elements are being removed, so the list is getting shorter. Hence IndexOutOfBounds Exception. But by doing:
Being Java programmer.
Avoid Date like the plague. Look in the Java™ Tutorials for what to use instead. For timing execution times you are probably better off with System.nanoTime(). Search my posts for nanoTime and you can probably find examples of it in use.Skott Elliott wrote:. . . Timer, this is just new Date() . . .
Integers are easier to get out of a Random object, but I would use a Stream to create the random List. Again, search my posts and you should find an example within the last six months. Don't use 1E5 which is not an int but a double. Don't use doubles with < in loops or if statements.I changed to Integers for no real reason. The truth is that I forgot that I was working with Strings, had accidental made an iteration with Integer, so I ran with it.
If you write a for loop correctly you will never suffer an out of bounds exception. Use myList.size() not a constant, otherwise the size and that constant might be different. . . Iterating the loop backwards so that there is always an index and won't . . . . i > 1... you got me. Probably should have wrote that as i >= 0.
I didn't find it in the Java™ Tutorials, but I would expect to find it in any decent book.For the last question, I don't know how to do that. I'd be all ears. Could I find that specific information in the Oracle docs?
Skott Elliott wrote: Consequently, the LinkedHashSet is the slowest, with the nested loop method being the fastest. I'm going to implement the huge text file and run these tests again.
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |