• Post Reply Bookmark Topic Watch Topic
  • New Topic

Is there a data structure that has O(1) search complexity and maintains order?  RSS feed

 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can i ask another question in this post? If so:
Is there a data structure that has O(1) search complexity, or at least not O(n), and maintains the order? I think of SparseArray and using a key as a index.
 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is this Android rather than ordinary Java®?
 
Jeanne Boyarsky
author & internet detective
Sheriff
Posts: 37395
531
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does it have to be one data structure? You could have an ArrayList to preserve the order. And then a HashMap to map the hash to ArrayList index.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
SparseArray was added by Android. I think there is no equivalent in ordinary Java. I want one data structure. Items in the list are updated frequently and user can sort them by options like, price, rating, etc.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeanne Boyarsky wrote:Does it have to be one data structure? You could have an ArrayList to preserve the order. And then a HashMap to map the hash to ArrayList index.

How can i do that without duplicating data.(If there is no one data structure)
 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why are you worried about duplicating data? Isn't it better to have versions sorted by price than to sort repeatedly? How much memory will you use for a List containing 1000000 hotels? Isn't this something a database would do better?
You can get a Comparator out of the Comparator interface with its comparing() method (Java8+), which takes a Function object as its parameter. You can easily create a Function<Accommodation, BigDecimal> with a method reference Accommodation::getPrice. It is easy enough to create a sortedList:-Don't know why, but the Function link doesn't seem to work properly. Sorry. I can't open Function from the API homepage either.
 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The only data structures with constant search complexity are hash tables; you would want to use a hash map or hash set. I presume you are familiar with how you find pairs in a hash map. Their “linked” versions also preserve insertion order. Mutable reference types are not suitable for elements in a set nor as keys in a map.
[edit]An array list allows random access but only if you already know the index.
That sparse array data structure appears to be a way to reduce memory consumption of an array and does not appear to allow fast searching of its elements. If you want logarithmic search complexity, you will need to sort your collection before searching and that runs in at least nlogn complexity.

Databases do that sort of thing very quickly.
 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No. If you want O(1) lookups, you need a hash table variant. If you want to maintain custom ordering, you need a list variant. If you want both, you need both a hash table and a list. Note that the only thing being duplicated are references to your objects. In an earlier post you said you have around 1000 hotels. On an x64 system, that's 8kb. Is that something you need to be worried about?
 
Giovanni Montano
Ranch Hand
Posts: 426
7
Android Open BSD Slackware
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:SparseArray was added by Android. I think there is no equivalent in ordinary Java. I want one data structure. Items in the list are updated frequently and user can sort them by options like, price, rating, etc.

beautiful post


just to bring some contribution, here some concept I found on the internet
Although SparseArray is created with Android, the concept of sparse in data structures is not


here there is a nice cheatsheet specialized in Big-O with data structures

 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:...Their “linked” versions also preserve insertion order...

I'll create database for the app. I didn't know about stream(), Thank you. It's very useful method. But i don't know, Android supports Java8. Does LinkedHashMap, guarantees the order like ArrayList?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:... Is that something you need to be worried about?

Doesn't duplicate data violence integrity and makes changing, storing data difficult?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:...Note that the only thing being duplicated are references to your objects...

You mean Rvalues are equal and Lvalues are different? When for example:

 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:. . . Does LinkedHashMap, guarantees the order like ArrayList?
Have you read its documentation?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know how to delete a post. Ignore the last post.
If i sort The list, fields content that reference by indexes will change and The map no longer valid unless i correct it again.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Arash Babak wrote:. . . Does LinkedHashMap, guarantees the order like ArrayList?
Have you read its documentation?

Nope. I will. I thought it would be quicker if you answer and then read the documentation. But your right i should read it first.
 
Liutauras Vilda
Marshal
Posts: 4820
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Isn't really clear what is your goal, but what the guys suggesting seems to me is:
So you sort the list how you want, and always accessing through the same key.

Which Map's implementation to use, you choose based on your requirements. HashMap doesn't guarantee order, LinkedHashMap does.
 
Liutauras Vilda
Marshal
Posts: 4820
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:I thought it would be quicker if you answer

That's quicker for you, but not for the person who's helping you. In short, you need that stuff, not whoever helps you, so you really need to research yourself first, and then use somebody else's knowledge if you are stuck.
 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:Doesn't duplicate data violence integrity and makes changing, storing data difficult?

It makes changing the data more difficult, because you have to change it in one that more area. That's why you should encapsulate the two data structures into one class that manages both. It does not violate integrity if the class that encapsulates the data is properly written and tested.

Liutauras Vilda wrote:Isn't really clear what is your goal, but what the guys suggesting seems to me is:
So you sort the list how you want, and always accessing through the same key.

No, that is not the same. That creates a partial ordering. OP requires a total ordering over all objects.
 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:. . . you really need to research yourself first, and then use somebody else's knowledge if you are stuck.
. . . and you will remember whatever you search for much better than if I simply tell you.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:Isn't really clear what is your goal, but what the guys suggesting seems to me is...


I don't think you followed my posts. This not the key i mentioned. The key is a item's id in a list and Map<String, List<String>> doesn't even close to the data structure that i want. I think, Jeanne means: Map<"Item's id", "2"> that means, The item is in field number 2.
 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Giovanni Montano wrote:. . . here there is a nice cheatsheet specialized in Big-O with data structures
It is nice, isn't it. You do need to know your complexity theory before using that cheat sheet however.
 
Liutauras Vilda
Marshal
Posts: 4820
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:I don't think you followed my posts. This not the key i mentioned.

You are right.

Maybe you could give an example with 3 - 4 components showing of what exactly you need?
 
Campbell Ritchie
Marshal
Posts: 56223
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:. . . Doesn't duplicate data violence integrity and makes changing, storing data difficult?
Two options then:
  • 1: Keep one copy of the List and do the sorting with a Stream every time something changes.
  • 2: Use a database. Remember you can use transactions and serialisability of the data to ensure that no reads and updates interfere with each other.
  • 3: There is bound to be something I haven't thought of.
  • I have just tried sorting a “random” IntStream containing 10⁷ elements and it took about 1.3″, so you may find repeated sorting acceptable.
     
    Arash Babak
    Ranch Hand
    Posts: 41
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:
    Liutauras Vilda wrote:. . . you really need to research yourself first, and then use somebody else's knowledge if you are stuck.
    . . . and you will remember whatever you search for much better than if I simply tell you.

    Yes your right and thank you for your answers. But i think you didn't pay attention to the last part of my answer: "But your right i should read it first." well, i think there is no need to say it. And i don't go straight for coding after you helped me. I definitely research according to your guides. I learned Android by myself, by researching. Researching is what i learned in the university. But sometimes i have no time and sorry about that. Again thank you for your patience.
     
    Campbell Ritchie
    Marshal
    Posts: 56223
    171
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Arash Babak wrote:. . . Again thank you . . . .
    That's a pleasure.
     
    Giovanni Montano
    Ranch Hand
    Posts: 426
    7
    Android Open BSD Slackware
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:
    Liutauras Vilda wrote:. . . you really need to research yourself first, and then use somebody else's knowledge if you are stuck.
    . . . and you will remember whatever you search for much better than if I simply tell you.

    plus you will become a better problem solver, is your bread and butter reading the documentation. Is like you want to do the football player without a ball
     
    Don't get me started about those stupid light bulbs.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!