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.
LinkBack URL
About LinkBacks
FASTEST List
I need a collection that I can add/remove to. Order doesnt matter at all. The only thing that matters is SPEED. Honestly, push/pop or even add/pop.. doesnt matter. Just different names for the "same" thing (as far as how I will use it). I am told that a Stack is slow? IDK. Either way, need the fastest possible list type collection. I would be fine with writing my own as well but I doubt I could do better than the JDK...
Related threads:
Re: FASTEST List
Fast is completely relative to what you are doing. Some implementations of a List will be 'faster' relative to others in different ways they are used. Are you noticing performance issues? Will you be adding/removing a lot of items at the front of the List? Do you need to continually access the items in the List by their index?
Re: FASTEST List
I'm not really noticing issues (yet). I will be adding/removing a LOT. I don't care about indexes or ordering.
I wrote an implementation of exactly what I need which, with a bit of testing, seems to be faster than the Java collections... its not a "complete" collection.. but it has what I need.
Re: FASTEST List
Than why worry about it? Let your algorithm/data crunching/whatever rely on the List interface (in other words, program to the interface and not the implementation). If you run into efficiency problems, then you can try different implementations of the List (or write your own) to see if one performs better.I'm not really noticing issues (yet)
Again, 'fast' is relative. A LinkedList will outperform an ArrayList when it comes to inserting at the beginning of the List, and an ArrayList will outperform a LinkedList when it comes to looking up values at a particular index (especially near the end of the List). Think about how the implementations work, read the API's, and you will be much better suited at choosing the appropriate implementationI wrote an implementation of exactly what I need which, with a bit of testing, seems to be faster than the Java collections... its not a "complete" collection.. but it has what I need.
Re: FASTEST List
Why worry about it.. well.. as much as I want to argue a point, I know that I cannot.
Okay, when I say fast.. I dont care about indexes or where elements go... it doesn't matter whatsoever to me. I just need to add/remove things to it... just need to store things in it. For all I care, I could remove a random index and it would work fine. Same for adding. As far using the List interface.. yeah you're right. I should program to the interface... I still think my implementation is best for me.. to be specific, my implementation is a LIFO... and to test it, I simply got an average time of adding/removing from my implementation compared to some other ones (ArrayList, LinkedList, Stack). Mine simply had the lowest average times...
Re: FASTEST List
Perhaps more progress could be made with some code. If you're willing, post the class you made, and post the code you used to profile - preferably using methods your project will rely on most, and preferably as an SSCCE.
Re: FASTEST List
Ah bloody hell, I have to stop deleting things. (oh yeah its on git.. oh well) Deleted the profiling code. Lets start from a different spot.
First of all, my requirements:
A collection that will store a bunch of objects. Order is not important. I need to push/pop (or add/remove(0)/remove(size-1)) to/from it. The reason I say 0 or size-1 is because it really doesn't matter. I just have to get an object from it and put an object into it. It doesn't matter WHICH object it is or WHERE it is.. I just have to get ANY one of the objects and add objects to it. These two operations have to be as fast as possible.
The implementation that I wrote is here: https://github.com/sci4me/SciEngine/...util/LIFO.java
It is not a proper collection really... doesn't implement anything.
I was just trying to see if I could write something faster than the other ones..
What I used to test it: https://github.com/sci4me/SciEngine/...SpeedTest.java
I mean, it works fine... but it doesn't implement anything which is kind of .. not great..
So, first of all I should determine what interface I need... List? Like I said, remove(0) or remove(size-1) is fine.. could be remove(random(size)) but that may be a bit slower (based on the ArrayList implementation) since it would have to move elements and whatnot.
Re: FASTEST List
If order is not important to you then perhaps you do not need a list.
Maybe you want to use a different kind of collection. If you know that objects will never be added twice to the collection you might want to go with a HashSet which uses an objects hashCode to store it in a HashMap. This would give you ~O(1) for add / remove / contains and you could still iterate over all objects.
Re: FASTEST List
I'm not sure I understand your pop implementation
/** * Pops an object off of the {@link LIFO} * * @return */ public T pop() { if(this.size == 0) return null; @SuppressWarnings("unchecked") // safe because the only type that can be added to the array is T T t = (T) this.elements[0]; this.elements[this.size--] = null; return t; }
This does not remove and return the first value, it returns the first value and removes the last. Is this the behavior you wish? I understood it as you wanted to return and remove the first value, in which case - like an ArrayList - you will need to shift all the values down in the array.
Re: FASTEST List
Ok, I have since realized that the LIFO is broken. I do want it to return and remove like an ArrayList.
I forgot to mention, I do need duplicate entries...
Looking into it a tish more, it seems that the best option currently is ArrayList...
Re: FASTEST List
nice question
Reply With Quote