Discussions

Performance and scalability: Binary Search Implementation

  1. Binary Search Implementation (3 messages)

    I am looking for a Open Source Java API that

    - Has a Binary Search implementation that can be used in our custom applications for faster search through a pool of in-memory objects.(Anywhere between 1,000 to 50,000 objects)

    - Does not store the objects physically into a database, everything is in-memory. (Found some implementation doing so, but they do not fit in the requirement. However, an API that can be configured to keep the objects in memory OR as a database will also do.)

    Cheers,


    Nitin

    Threaded Messages (3)

  2. Binary Search Implementation[ Go to top ]

    Just use Arrays.binarySearch - in the base java runtime.

    thanks - dave
  3. Thanks[ Go to top ]

    Thanks Dave M working on it.

    Regards,

    Nitin
  4. You could try...[ Go to top ]

    JoSQL (http://josql.sourceforge.net), but it doesn't use binary searching... I tried using binary searching via Lists but it starts to slow everything down when you insert a new record into the index... i.e. resorting 50K records just grinds everything to a halt... JoSQL is useful in that it allows SQL statements to be applied to Lists of Java objects... I may implement indexes in JoSQL eventually... JoSQL is pretty quick though... It depends upon what your desired response time is...

    For example on the following query:

    SELECT *
    FROM FileWrapper
    WHERE name LIKE '%.html'
    ORDER BY name

    on 108K "FileWrapper" objects, the WHERE clause took:

    ~0.1s to execute

    The ORDER BY part took:

    ~0.3s to execute for about 26K objects matched from the WHERE clause.

    I executed the above query on my home machine running Liunx, 512MB ram, 2.4GHz processor...

    You may be best off with a TreeMap... better insert performance, though can be slightly slower on searching...

    G.