• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Sorted Arrays vs Unsorted Arrays

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have been reading about arrays and I have discovered that sorted arrays seem to be faster in Java. Why is that? Does it have to do anything with the compiler or is it an efficiency of the language? Is there a circumstance when this would not be the case in Java or any other language for that matter?
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There has to be some context to the statement "sorted arrays are faster in Java" that you left out.

Arrays are arrays. An array itself doesn't care in what order its elements are. Some methods, such as Arrays.binarySearch(...) require that the elements of the array are sorted, otherwise the method doesn't work correctly. But it is not the case that in general, sorted arrays are somehow always faster.
 
Ranch Hand
Posts: 146
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Dear Sir,

For an array the access time is constant because the access is done by an index, no matter how large is the array.

In context, when searching for an element within an array then the array must be sorted to take advantage of binary search methods.
 
Sheriff
Posts: 8064
569
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

ludoviko azuaje wrote:In context, when searching for an element within an array then the array must be sorted to take advantage of binary search methods.

That is correct. But what Jesper mentioned, there is nothing special about the sorted or unsorted arrays as about the data structure as such. It is about the way you search data within an array. In your mentioned case it is binary search, which algorithm defines what kind of prerequisites needs to be satisfied in order for binary search algorithm work correctly. Read about the binary search algorithm. You'll find some useful information there.
 
Joseph Williamson
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What about branch prediction? I know that the processor will have an impact on it but can't Java the code itself help mitigate some of that time when using a sorted array?
 
author
Posts: 23907
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Joseph Williamson wrote:What about branch prediction? I know that the processor will have an impact on it but can't Java the code itself help mitigate some of that time when using a sorted array?



A few responses. First, I highly doubt that a very low level pipeline optimization can have noticeable affect based on the high level organization of the data. Second, even if there is an affect, I highly doubt that the cause and effect can be conclusively established... which bring us to third, as in most cases, if you believe that there is an useful optimization, you should confirm it. Write a test program and confirm the impact. Otherwise, you are just adding complexity to your code, for something that may help, may hurt, or may have no noticeable effect on performance.

Henry
 
Run away! Run away! Here, take this tiny ad with you:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic