Custom Data Structure vs. Primitive Array objects

Discussion in 'Java' started by sangwoo.im@gmail.com, Jan 21, 2007.

  1. Guest

    Hi,
    In last semester, I wrote a program for algorithm analysis class. It
    was critical to make the program to run as fast as possible. My first
    approach was making custom classes that can represent the required data
    model for the given problem. But, the program ran extremely slow with
    a large data set. I suffered from that performance problem and I
    decided to rewrite the program with only primitive data classes that
    provided in Java for default. obviously, there was no change in
    programming logics or algorithms. It began to ran comparatively faster
    than before. (It was amazingly reduced the running time.) This was a
    weird observation for me because the custom data structure (class) that
    I wrote before was just a data container with few methods for data
    field accessors (getters/setters); there was no intensive computation
    in the class. I'm just reasoning the observation by a guess. "Java
    might handling custom objects slow due to the garbage collector
    mechanism and maintaining the objects (retain counter, etc)." But, this
    is just a guess. I have no clear reason to explain what I observed.
    Would this happen in other programming language/environment, too?

    Thanks for any comments

    Sangwoo
     
    , Jan 21, 2007
    #1
    1. Advertising

  2. wrote:
    > Hi,
    > In last semester, I wrote a program for algorithm analysis class. It
    > was critical to make the program to run as fast as possible. My first
    > approach was making custom classes that can represent the required data
    > model for the given problem. But, the program ran extremely slow with
    > a large data set. I suffered from that performance problem and I
    > decided to rewrite the program with only primitive data classes that
    > provided in Java for default. obviously, there was no change in
    > programming logics or algorithms. It began to ran comparatively faster
    > than before. (It was amazingly reduced the running time.) This was a
    > weird observation for me because the custom data structure (class) that
    > I wrote before was just a data container with few methods for data
    > field accessors (getters/setters); there was no intensive computation
    > in the class. I'm just reasoning the observation by a guess. "Java
    > might handling custom objects slow due to the garbage collector
    > mechanism and maintaining the objects (retain counter, etc)." But, this
    > is just a guess. I have no clear reason to explain what I observed.
    > Would this happen in other programming language/environment, too?
    >
    > Thanks for any comments
    >
    > Sangwoo
    >


    In general, data organization can be key to practical algorithm
    performance. At a minimum, it can affect the constant multiplier. In
    some cases, it can even change the time or space complexity. For
    example, in Java indexed access to element n of an N element list is
    O(1) if it is an array or ArrayList, but O(N) for a LinkedList.

    Changes in data organization can have dramatic effects on cache hit
    rates. Most algorithms will not achieve acceptable speed if more than a
    small fraction of loads and stores go to memory.

    Theoretical algorithm analysis usually starts by ignoring cache issues,
    because there is a finite upper bound on the ratio between performance
    with and without caching. Cache hit/miss cannot affect the computational
    complexity.

    Your array and primitive version may have grouped together in memory the
    data needed in the inner loops of the algorithm, in the order in which
    it was needed.

    Patricia
     
    Patricia Shanahan, Jan 21, 2007
    #2
    1. Advertising

  3. wrote:
    > In last semester, I wrote a program for algorithm analysis class. It
    > was critical to make the program to run as fast as possible. My first
    > approach was making custom classes that can represent the required data
    > model for the given problem. But, the program ran extremely slow with
    > a large data set. I suffered from that performance problem and I
    > decided to rewrite the program with only primitive data classes that
    > provided in Java for default. obviously, there was no change in
    > programming logics or algorithms. It began to ran comparatively faster
    > than before. (It was amazingly reduced the running time.) This was a
    > weird observation for me because the custom data structure (class) that
    > I wrote before was just a data container with few methods for data
    > field accessors (getters/setters); there was no intensive computation
    > in the class. I'm just reasoning the observation by a guess. "Java
    > might handling custom objects slow due to the garbage collector
    > mechanism and maintaining the objects (retain counter, etc)." But, this
    > is just a guess. I have no clear reason to explain what I observed.
    > Would this happen in other programming language/environment, too?


    Without more details we can really not say much.

    Arne
     
    =?ISO-8859-1?Q?Arne_Vajh=F8j?=, Jan 21, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Henri
    Replies:
    0
    Views:
    416
    Henri
    May 17, 2004
  2. Replies:
    3
    Views:
    14,820
  3. Replies:
    7
    Views:
    606
    Victor Bazarov
    May 9, 2005
  4. bernd
    Replies:
    1
    Views:
    791
    bernd
    Jun 13, 2008
  5. Daniel Pitts
    Replies:
    7
    Views:
    483
Loading...

Share This Page