• Post Reply Bookmark Topic Watch Topic
  • New Topic

Which data structure?  RSS feed

 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I have for example, 200 objects with a key for each as a member variable. There are main data which means i want sort them search in them update them and etc. Which data structure is more efficient or has less time complexity and space complexity : Arraylist of objects or Hashmap of objects with object's key as Hashmap key?
 
Stephan van Hulst
Saloon Keeper
Posts: 7927
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When you have to perform lookups, you should pretty much always go for a Map. If you need to perform a lot of searches, use a TreeMap, otherwise use a (Linked)HashMap.
 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you always using the key to search? The fastest way to find something from a key is to use a hash map. Unfortunately the Java™ Tutorials don't say much about the performance of Maps, only that HashMap is the fastest, but the API documentation for the three implementations Stephan named is a bit more informative. Linked hash map and hash map: constant time for put and get: tree map: logarithmic time for put and get. Since an array list (linear time for a search) and the two hash collections have backing arrays, their space requirements will be similar. A tree which has no empty nodes might use slightly less space, but memory is cheap, so forget about space problems.
I think you won't notice any performance problems for 200 objects, a small collection. If you are searching on anything other than a plain simple key in a map and you have many more records than you have at present, then you will probably be better off with a database.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry for less information. i couldn't edit my question.
I'm using JAVA for android programming and thus memory is important. and data are hotels information and can be more than 1000. And sorting is important. I mean if a user sorts hotels by for example, stars, should be remain sorted till she/he changes them again(i mean remain sorted in memory). And position of an item in the collection, somehow is important. For example, a user selects some hotels as favorites; position of these items in the list, must be remembered.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And i use the key and the type for searching. (the type is type of accommodation and is an integer an is a member variable)
 
Stephan van Hulst
Saloon Keeper
Posts: 7927
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thousand objects is not a lot. You probably won't really notice any real performance difference between the various data structures.

Why would you use type as the key? I imagine multiple hotels can have the same type. It appears you just want to sort a list of hotels according to some criteria, and you don't want to perform any lookups. In that case, ArrayList is the structure you need.
 
Junilu Lacar
Sheriff
Posts: 11428
173
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For Android apps, I imagine you'd want to limit the amount of data you're keeping in memory. Think of what would happen if mapping apps like Waze and Google maps were to download the results of a search all at once. The results would not be good. When memory is at a premium, you usually have to resort to paging or incrementally downloading the results into a limited-sized buffer. If the user wants to view more data that hasn't been downloaded yet, you page some of the buffered data out and more new data in. There will always be a trade-off between speed and resource/memory usage. The faster you want the user experience to appear, the more memory your app is going to have to use, and vice versa. You have to figure out where the acceptable balance point is.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12558
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another point...The common wisdom is to determine the requirements FIRST, and THEN write the code.  In other words, decide your app. should only use X MB of memory, and respond within Y seconds.  That way, you know when you've achieved your goals. 

If you don't define the targets first, you're always chasing after something without knowing when you get there...

If you meet all the goals easily, then consider revising one or two, and see if you can meet that without breaking the others.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you, Stephan. And you're right. The key is the hotel id and the type is a kind of category(hotel, suite, villa, ...). I'll use ArrayList for these data volume. And thank you Campbell for your good information.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes that's right Junilu. But for now that the data is just one city hotels, i think i can keep them in memory. Searching, sorting and etc would be faster. But in the future for more cities i definitely go for paginate.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for your advice, fred.
 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You may want a Map<Type, List<Hotel>> or similar. But your requirements really are beginning to look like something for a databse.
 
Junilu Lacar
Sheriff
Posts: 11428
173
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:But in the future for more cities i definitely go for paginate.

Just to be clear, there's a difference between paginating display results and paging or segmentation as a memory management strategy. I was talking about the latter. With regard to incrementally downloading data, I was referring to first downloading summary information and show that to the user. From there, the user can drill down into a specific item to see more detailed information. Only then do you download the detailed information for that particular item. This can be done in several increments with each increment going into more details but only for the item that was chosen at the previous level. The tradeoff in this approach is that the user will have to do more to get to the information they want.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Junilu. I didn't read your quote correctly. Yes, this is a correct way to implement apps with large data like KAYAK or booking.com.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:You may want a Map<Type, List<Hotel>> or similar. But your requirements really are beginning to look like something for a databse.


For first release because it's just for one city, I use ArrayList<AGoodPlace> structure and SharedPreferences for storing and retrieving data. SharedPreferences are sets of key/values that stored persistently like database.
 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:. . . because it's just for one city . . .
And when you add another city, you will have no end of work upgrading the system to accommodate it. Why not make the system expandable, particularly if that simply entails good design?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Arash Babak wrote:. . . because it's just for one city . . .
And when you add another city, you will have no end of work upgrading the system to accommodate it. Why not make the system expandable, particularly if that simply entails good design?

I agree with you. But consider this:

1. User can see only accommodations of one city at a time.
2. A city has at most 300 hotels, plus another accommodations, can be around 1000.(In my country of course)
3. I don't need to search for specific accommodation because searching is done by the server.
4. Lookups for me, can be done by position of an item in the list. If user selects a accommodation as a favorite, then i save the position because an item's position in a ArrayList is guaranteed. If user clicks on a accommodation then i use it's position to display the details.
5. Information of a accommodation is changed at most two times in a month.(is not frequent)
6. The accommodation class member variables:



Photos fields are just URLs. I request them from server when user wants to see them.

According to these facts, i use ArrayList and SharedPreferences and get them all at first and keep them in memory. (I think SharedPreferences is faster than database. Opening and closing of database are expensive and time consuming. I know they are different but in this situation i don't think i need a database)

If i'm wrong, please correct me.
 
Stephan van Hulst
Saloon Keeper
Posts: 7927
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why is your class so weakly typed? What are the stars and off, distances and virtualTour fields for? From what to what do the mapAddress, rooms, phones and userReview fields map? Why are they inside lists?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Why is your class so weakly typed? What are the stars and off, distances and virtualTour fields for? From what to what do the mapAddress, rooms, phones and userReview fields map? Why are they inside lists?


Thank you for your attention.

1. stars               : are stars font icons.
2. off                  : is discount.
3. distances        : is a web url (it's loaded in WebView)
4. virtualTour      : is a web url.
5. mapAddress    : is {latitude:"theLatitude", longitude:"theLongitude"} (it can be ArrayList)
6. rooms             : is hotel's rooms info in the form of {"type":"theType", "bedType":"theType"", guests":"theNumber", "extraGuests":"theNumber" "services":"theServices", "agencyPrice":"thePrice", "userPrice":"thePrice", "photos" : "url"}
7. phones            : is {"phone"  : ["manager : 33333333", ...], "mobile" : ["manager : 0915333333", ...]}
8. userReview      : is {"date":"theDate", "name":"theName", "tripType":"theTripType", "description":"theDescription", "userRank":"theRank"}
 
Dave Tolls
Ranch Foreman
Posts: 2996
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can see a number of things there that ought to be classes in their own right.
Like the MapAddress (surely coordinates?), or Room, or UserReview...

That's what Stephan is talking about when he says the class looks weakly typed.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dave Tolls wrote:I can see a number of things there that ought to be classes in their own right.


Yes. But more instantiating doesn't take more space (and time)?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And about "MapAddress", yes,  it should be "coordinates".
 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:
1. stars               : are stars font icons.
I assume that stars is a hotel rating. If that is the case, then it makes sense to make it an Integer since it only (typically) has values 1,2,3,4,5.
Whether you want to render e.g. "oneStar.jpeg" or "threeStar.jpeg" should be a UI decision.
Keeping it in this way allows the database to treat it as data and not just strings and you can do cool stuff such as sorting ascending descending according to stars. You can also have a filter search where a user wants to see hotels having a minimum 3 stars, etc...

 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For 1,000? Space is cheap. Very cheap. And instantiation doesn't take a long time. You will only have problems about space when you have multiple millions of objects “live” simultaneously.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
salvin francis wrote:
Arash Babak wrote:
I assume that stars is a hotel rating. If that is the case, then it makes sense to make it an Integer since it only (typically) has values 1,2,3,4,5.


The starsNum variable is a hotel rating. And the stars variable contains "star Icon Font"s .(i use  Icon Font instead of an image). Instead of using switch/case to set the TextView:

Just write one line of code:

I initial the variable:

 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well I still don't agree using String where a number should reside. Like I explained, you want to treat it as a number since you will want to sort, limit it at some point of time. Besides, it's a number, it is "rendered" as a star.

Here's my solution: Create a custom widget:

In the future, you can change it to a label or even an image, it stays as a number in the data layer.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
salvin francis wrote:Well I still don't agree using String where a number should reside...

Thank you Salvin, for your solution. But there is a problem here:

Assumed that we have 200 items in a list. Well it means 600 method calling and at most 1000 comparison. And you know the cost of method calling.(Runtime stack, evaluating and pushing parameters, etc). But this not the main problem. The main problem is every time that user scrolling down and up the list, some items come to screen and RecyclerView Adapter  that responsive for creating item views of the list, has to call methods and does comparison to set TextViews. But if i store star characters in a variable and write this:

The The Adapter calls 400 methods without comparison .

I have two variables for hotel rating. One for calculations(private int starsNum;), another for filling the TextView(private String stars;). This is my sorting:

 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't like that code at all. There is something wrong with an array of ints representing options. Not at all an object oriented solution.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Don't like that code at all. There is something wrong with an array of ints representing options. Not at all an object oriented solution.


"ascendingOrder" doesn't represent options. This is for Asc/Des ordering. I have five tabs and one sorting options window. Every tab has one RecyclerView(a list). "ascendingOrder" array is for keeping sort order of five lists(there is one button for ascending and descending order). "1" means ascending and "0" means descending.
 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arash Babak wrote:. . . . "1" means ascending and "0" means descending.
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Arash Babak wrote:. . . . "1" means ascending and "0" means descending.

Sorry for my bad explanation.



When a list get ordered, for example, in ascending order, corresponding position of the list in "ascendingOrder" array, is set to "1". Thus next time when the button is clicked, i will know the previous order.
 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I still think that isn't good design. There is nothing to explain that 1 means ascending and 0 means descending, nor is there anything to stop you entering 2.
Why would you want to retain records of how a List is sorted? Why would you want to sort the same List twice? You can simply reverse a list already sorted.
Why not have an enumerated type recording sorting orders?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Why would you want to retain records of how a List is sorted? Why would you want to sort the same List twice? You can simply reverse a list already sorted.
Why not have an enumerated type recording sorting orders?

I didn't know about "reverse ". Thank you for that. And about ints array, yes your right; enumerated type is better. But with reverse method of ArrayList (that i didn't know; believe me.), no need for that. Thank you for your patience.
Another question is, i need a data structure that can access an item in O(1), at least not O(n), and maintains the order. I think of SparseArray and using a key as a index.
 
Campbell Ritchie
Marshal
Posts: 56197
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is there a reverse method? This is as near as I could find, but that shou‍ld reverse your List.
 
Stephan van Hulst
Saloon Keeper
Posts: 7927
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm actually not quite sure why you're doing this sorting stuff manually. Can't you just let table views sort on a column in Android?
 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I'm actually not quite sure why you're doing this sorting stuff manually. Can't you just let table views sort on a column in Android?

I don't use a TableLayout because i use a RecyclerView. For sorting a RecyclerView you have to sort The list that the RecyclerView shows on screen and then call "notifyDataSetChanged". Usually items like Hotels are shown with CardView and list of CardViews are shown with ListView or RecyclerView(new version of ListView). RecyclerView is more flexible and efficient than ListView. It recycles views and has more built-in animations.
 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I do have a feeling there could be a simpler way. I am not so well-versed with android, I have just worked on a few personal projects that were entirely graphically based without using the standard UI components.
As per my design, setStarRating is a delegation method for setText. I was going to suggest using a simple Map instead of a switch case but it looks like you would rather maintain two different copies of the same data (one as Number and other as String) in the same model than to maintain one version and let UI handle it. As per my experience, such kind of designs lead to hard to track bugs in the future. Since this is a directly user-facing data, you need to ensure that there is synchronization between them.
e.g If someone modifies your code and does a setStarsNum() without calling setStars() and all hell breaks loose. An item representing 5 stars can potentially render as 1 star in the UI


 
Arash Babak
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
salvin francis wrote:... If someone modifies your code and does a setStarsNum() without calling setStars() and all hell breaks loose. An item representing 5 stars can potentially render as 1 star in the UI

Yes, i agree with you. I'm not comfortable with that myself. I'm running out of time in this project. I couldn't think more about it. I think "Map" idea is better than two variables with one meaning. Thank you.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!