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 11 of 11

Thread: FASTEST List

  1. #1
    Member
    Join Date
    Feb 2013
    Posts
    78
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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...


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,372
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default 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?

  3. #3
    Member
    Join Date
    Feb 2013
    Posts
    78
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.

  4. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,372
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default Re: FASTEST List

    I'm not really noticing issues (yet)
    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 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.
    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 implementation

  5. #5
    Member
    Join Date
    Feb 2013
    Posts
    78
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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...

  6. #6
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,372
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default 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.

  7. #7
    Member
    Join Date
    Feb 2013
    Posts
    78
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.

  8. #8
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    897
    Thanks
    0
    Thanked 166 Times in 148 Posts

    Default 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.

  9. #9
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,372
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default 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.

  10. #10
    Member
    Join Date
    Feb 2013
    Posts
    78
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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...

  11. #11
    Junior Member
    Join Date
    Apr 2014
    Posts
    3
    My Mood
    Cool
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: FASTEST List

    nice question

Similar Threads

  1. Replies: 3
    Last Post: October 5th, 2013, 10:14 AM
  2. Fastest way to read and search a string in a large file using core java
    By patilsn_jay in forum File I/O & Other I/O Streams
    Replies: 3
    Last Post: November 26th, 2012, 04:35 AM
  3. Fastest way to read and search a string in a large file using java
    By patilsn_jay in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 24th, 2012, 09:29 AM
  4. What is the fastest and most memory-efficient data structure?
    By aussiemcgr in forum Collections and Generics
    Replies: 5
    Last Post: October 11th, 2012, 04:48 PM
  5. What is the fastest and most efficient for 3 dimensional structures?
    By aussiemcgr in forum Collections and Generics
    Replies: 10
    Last Post: December 11th, 2010, 07:50 PM