This week's book giveaway is in the Kotlin forum.
We're giving away four copies of Kotlin in Action and have Dmitry Jemerov & Svetlana Isakova on-line!
See this thread for details.
Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorted Arrays vs Unsorted Arrays  RSS feed

 
Joseph Williamson
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • 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?
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16026
87
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • 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.
 
ludoviko azuaje
Ranch Hand
Posts: 85
  • Mark post as helpful
  • send pies
  • 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.
 
Liutauras Vilda
Marshal
Posts: 4624
316
BSD
  • Mark post as helpful
  • send pies
  • 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
  • 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?
 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • 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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!