🔒 Locked

binary tree or link list

Started by danchuee Apr 11, 2005 at 4:20 PM 5 replies 450+ views

Original Post

Apr 11, 2005 at 4:20 PM

I'm working on a chat system right now for a very simple online game. Say I have one State (or room) (name Ohio) and within that state are counties, say 2 of them ( name Orange, Apple) and within each county is a city (name A,B,C,D,E,F). Each person can be part of a group. Now because someone is part of a group doesn't mean that they are in the same county. Each person can only be in one state, county and city at a time. A person can be in county and not in a city. A person can't be county and in a city. I'm planning to handle 5-10 people at a time. (I would like to have something to handle more but it's not needed right now). I'm trying to find out which would be faster and more effecient and how to code it. I'm thinking a tree would be better suited to handle this because I wouldn't have to go thru each member if I know exactly which level of the tree I wanted to transmit too. (did I say that right). But then I run into the problem that 'Hey I want to tell my friend hi'. Well the program doesn't know where exactly that person is so it would have to go thru the whole tree to find that person. Then maybe a linklist would be better since I wouldn't have to create a tree and the code would be much smaller. Maybe I could use a database to store where people are? That way, I could find them pretty quickly? But then if people are telling people hi alot, then processing for the database would rise significantly. I haven't started with the actual code because I want to get some information and a better idea on what might be better. I hope this makes sense. =P

Fruny

Apr 11, 2005 at 4:33 PM

Do both. One "geographical" data structure, one alphabetical data structure.

If you're programming in C++, the alphabetical data structure can be a std::map

Drew_Benton

Apr 11, 2005 at 4:39 PM

Quote:
Maybe I could use a database to store where people are? That way, I could find them pretty quickly? But then if people are telling people hi alot, then processing for the database would rise significantly.

I'd suggest that, however, don't you think one lookup is a lot faster than renavigating all the nodes each time? Not only that, All you have to do is make a binary search as well as implement the binary insertion method to store all the users in. That way, you have something that is fast as well as efficient.

You could also use a 'cache' that remembers where the last person was, so you can check there first, then consult the database if needed. That or you can have an auto update cache that updates itself every 5 mins or so.

So for your plan, have your hierarchy of rooms, with each state being the root, then from there on, the county is a child, then the cities are the sub-childs. Each time a user changes rooms, you will update the data-base with the new location. When you want to message someone, the software simply looks it up with the database and viola. Just my opinion though [smile]

xor

Apr 11, 2005 at 4:51 PM

Quote:

Do both. One "geographical" data structure, one alphabetical data structure.

If you're programming in C++, the alphabetical data structure can be a std::map

I'de complement Fruny's post by adding an interconnection between the structures.

In the tree node of a given user, put a pointer to it's corresponding node in the alphabetical structure, and in the alphabetical structure of a given user, put a pointer to the corresponding tree node. Facilitates operations, user deletion for instance.

hplus0603

Apr 11, 2005 at 5:00 PM

It's just not going to matter for 10 users. Use whatever is easier to debug.

Also, both trees and linked lists are pretty heavy on the cache misses, so if low-level performance really matters, and the data set is small (10 items), then you probably want a vector<> rather than either a list or a map.

Zahlman

Apr 11, 2005 at 5:30 PM

To refine Fruny's and xor's ideas: store the "geographical information" and "name" , in whatever way, as members of the User struct. Make comparators for pairs of User*, which dereference and then either compare the name or the geographical information. Then, for each User object, store one pointer to it in a std::map, and another pointer to the same User in a std::map, where in each case the 'key' points to the appropriate data within the pointed-at User. You may want to make a member function for the User which will have it register itself in both (presumably global) maps, and two (presumably global) functions which will accept a key of either type, reference it (so that you don't have to pass a pointer yourself) and do lookup in the appropriate map.

Something like this (not tested at all):

template <typename T>struct DereferencingComparator {  bool operator< (T* lhs, T* rhs) {    return *lhs < *rhs;  }}std::map<Geography*, User*, DereferencingComparator<Geography> > byLocation;std::map<std::string*, User*, DereferencingComparator<std::string> > byName;void User::register() const {  byLocation[&myGeography] = this;  byName[&myName] = this;}User& getUserByLocation(const Geography& location) {  return *byLocation[&location];}User& getUserByName(const std::string& name) {  return *byName[&name];}

iMalc

Apr 12, 2005 at 3:41 AM

Quote:
Original post by hplus0603
It's just not going to matter for 10 users. Use whatever is easier to debug.

Also, both trees and linked lists are pretty heavy on the cache misses, so if low-level performance really matters, and the data set is small (10 items), then you probably want a vector<> rather than either a list or a map.

Yep, I second all of that.
Just make sure that you do a good job of asbtracting the "set" of users (for the lack of a better term) from the underlying algorithms that manipulate and access them. That way you can easily change the data structure later if your number of users increases.
STL does this for you, and would be the preferred solution.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.