ShoGun
asked on
AVL Data structure?
hello,
we using java but it's data structures hashtabel & vector(a growable array) are clumsy and memory hog after just 2000 insertions ,i said of using AVL trees for really fast searches to team,can we implemnt as replacement for vector? requirement of storing upot 500,000 recrods smoothly and only 1 tiem inserts mostly searches always as we think of storing values in it.
excellemt site for AVL
http://www.enteract.com/~bradapp/ftp/src/libs/C++/AvlTrees.html
we later remove recrusion as slows down,
and also what is a good replacement for hashtable ? itis useful for storing name-value pairs,so what good replacement for it?
please advice ,many people give many points.
Thanks you
ShoGun
we using java but it's data structures hashtabel & vector(a growable array) are clumsy and memory hog after just 2000 insertions ,i said of using AVL trees for really fast searches to team,can we implemnt as replacement for vector? requirement of storing upot 500,000 recrods smoothly and only 1 tiem inserts mostly searches always as we think of storing values in it.
excellemt site for AVL
http://www.enteract.com/~bradapp/ftp/src/libs/C++/AvlTrees.html
we later remove recrusion as slows down,
and also what is a good replacement for hashtable ? itis useful for storing name-value pairs,so what good replacement for it?
please advice ,many people give many points.
Thanks you
ShoGun
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Forgot, ternary serach trees can be used very well for pattern matching and 'near neigboor' searches.
ASKER
sorry but i try to read and cant understand that much how to convert them to Java? I dont think that anybody can help me but will have to ask some colleagues for heping me out.
can you tell me ?
Thanks you
can you tell me ?
Thanks you
ASKER
If u can help me please tell.
With the skiplist you mean?
ASKER
Yes the statement
>>>>>>>implement a dictionary using
skip lists
is what interestd me ,dictionary is superclass of hashtable in java.
I am right now doing taht ,will post some code sometime this week.
basically i am modifying code
>>>>>>>implement a dictionary using
skip lists
is what interestd me ,dictionary is superclass of hashtable in java.
I am right now doing taht ,will post some code sometime this week.
basically i am modifying code
I could help you with the skiplist algorithms as such, but I'm not a Java programmer.
Anything concrete you are stuck with
Is in Java a Dictionary a Super class of Hashtable? That is very odd design. I suppose you could implement a concrete dictionary by using a hashtable, but that doesn't make a hashtable a dictionary?
Anything concrete you are stuck with
Is in Java a Dictionary a Super class of Hashtable? That is very odd design. I suppose you could implement a concrete dictionary by using a hashtable, but that doesn't make a hashtable a dictionary?
ASKER
I dont know why its odd but hashtable is concrete implementation of Dictionary which is abstract.
data structures in Java are lot difficult than C/C++
data structures in Java are lot difficult than C/C++
Mh, well, guess I should not pass judgement too lightly here.
You ask for help but it is not clear to me on what, the skiplist, its implementattion? the ternary search tree (hash table replacement). Do you need help in understanding how they work or in the implementation?
You ask for help but it is not clear to me on what, the skiplist, its implementattion? the ternary search tree (hash table replacement). Do you need help in understanding how they work or in the implementation?
ASKER
http://www.csihq.com/CSI/pubs/skiplist.html
The page cannot be found ?
but i got this
http://www.ddj.com/articles/1998/9804/9804a/9804a.htm
Ok I want your help on a fast Data Structure for name-value pairs whaterevr that maybe.
Thanks you
The page cannot be found ?
but i got this
http://www.ddj.com/articles/1998/9804/9804a/9804a.htm
Ok I want your help on a fast Data Structure for name-value pairs whaterevr that maybe.
Thanks you
Indeed, it is off line. I'm sure I've tried it just before posting though!
It has been moved:
http://www.csihq.com/CSI/pub_Skip.html
Did you get access to the ftp link?
>> http://www.ddj.com/articles/1998/9804/9804a/9804a.htm
Yes those are the ternary serach trees.
AFAIK, name-value pair search structures are dictionaries ;)
Any way, you said you were using hashtables but you found they used to much memory. Ternary search trees are a possible replacement, were it not that they use even more memory.
I mentioned SkipLists becaue they use far less memory (1~2 links per node) then AVL binary trees (2 links + info per node). They are slightly less efficient then balanced (AVL) binary trees.
If you got to the ftp link working you should really take a look at the articles. If you have any questions, or can't find the articles let me know (I'll have to refresh my memory though)
It has been moved:
http://www.csihq.com/CSI/pub_Skip.html
Did you get access to the ftp link?
>> http://www.ddj.com/articles/1998/9804/9804a/9804a.htm
Yes those are the ternary serach trees.
AFAIK, name-value pair search structures are dictionaries ;)
Any way, you said you were using hashtables but you found they used to much memory. Ternary search trees are a possible replacement, were it not that they use even more memory.
I mentioned SkipLists becaue they use far less memory (1~2 links per node) then AVL binary trees (2 links + info per node). They are slightly less efficient then balanced (AVL) binary trees.
If you got to the ftp link working you should really take a look at the articles. If you have any questions, or can't find the articles let me know (I'll have to refresh my memory though)
ASKER
Yes i got access to ftp link,Ok can i transform Skiplists as a hashtable whcih is a name value pairs struture?
can yu transform it to C++ as then I can ask one of my friedns to help me out then.
I have 170 points now,cod eis 200 lines. pplease tell yes/no
Thanks you
can yu transform it to C++ as then I can ask one of my friedns to help me out then.
I have 170 points now,cod eis 200 lines. pplease tell yes/no
Thanks you
>> code is 200 lines
You already have code.
Well, i'm not so sure it is done in 200 lines, at least not how I would implement it: STL compatible.
A full implemetation would take a considerable amount of time, not before the weekend.
I suppose I could translate the basic algortihms in a few hours, so I'll look at it tonight, ok?
You already have code.
Well, i'm not so sure it is done in 200 lines, at least not how I would implement it: STL compatible.
A full implemetation would take a considerable amount of time, not before the weekend.
I suppose I could translate the basic algortihms in a few hours, so I'll look at it tonight, ok?
ASKER
thanks my friend,
my friend will then do the STL convesion to java as it is good and then i understand.
but the key and value is int in code?? We should Object in java or any other object,what use if not Object? I tink some expert like you can only implent it,we wnat any object mostly String to store as key and vector/hastable/ANY object as value.
Thanks you,I wait and i then mail you ,my 2 friedns will discuss me and we give u java code too.
friend,why dont you learn java its the future ,going to overtake c++ ,much as i dont like.
my friend will then do the STL convesion to java as it is good and then i understand.
but the key and value is int in code?? We should Object in java or any other object,what use if not Object? I tink some expert like you can only implent it,we wnat any object mostly String to store as key and vector/hastable/ANY object as value.
Thanks you,I wait and i then mail you ,my 2 friedns will discuss me and we give u java code too.
friend,why dont you learn java its the future ,going to overtake c++ ,much as i dont like.
I think it is just common practice in literature to use integers as key. In practice one can use any type whose objects can be 'ordered' in some way. A C++ implementation would typically be as a template. I suppose in Java all objects are from classes ultimately derived from Object? Then the skiplist would store Object's.
>> friend,why dont you learn java its the future ,going to
>> overtake c++ ,much as i dont like.
I doubt Java will overtake C++. It is a great language for Web applications, but has some disadvantages.
But whatever the future brings, Java seems so close to C++ in syntax and concepts that I am confident I can learn it without to much difficulty.
>> friend,why dont you learn java its the future ,going to
>> overtake c++ ,much as i dont like.
I doubt Java will overtake C++. It is a great language for Web applications, but has some disadvantages.
But whatever the future brings, Java seems so close to C++ in syntax and concepts that I am confident I can learn it without to much difficulty.
ASKER
>>>>>>>>I suppose in Java all objects are from classes ultimately derived from Object?
yes object is parent of all object in java.
>>>>>>>>I doubt Java will overtake C++. It is a great language for Web applications, but has some disadvantages.
My friedns all leaving c++ and trying jump java,i started learning now but they tell taht javas progress much fast than c++ in last 4 year,i tink release in 1996 ? how time till advanced featuires come in c++ ?much time ,yes but java slow for real time ,but they come with real time java specificasion,search for ti ,sun going everywhere.
now get back to work ,sorry but i also dont like what is happend ,if you do STL ,can template be easiyl converted to java?If not pls can you do normal? BUt yes if exception presenr very good as java is good in exceptin.
Thanks you
yes object is parent of all object in java.
>>>>>>>>I doubt Java will overtake C++. It is a great language for Web applications, but has some disadvantages.
My friedns all leaving c++ and trying jump java,i started learning now but they tell taht javas progress much fast than c++ in last 4 year,i tink release in 1996 ? how time till advanced featuires come in c++ ?much time ,yes but java slow for real time ,but they come with real time java specificasion,search for ti ,sun going everywhere.
now get back to work ,sorry but i also dont like what is happend ,if you do STL ,can template be easiyl converted to java?If not pls can you do normal? BUt yes if exception presenr very good as java is good in exceptin.
Thanks you
ASKER
>>>>>>>>now get back to work ,sorry but i also dont like what is happend ,
sorry I mean to said that what happen is bad ,2 frineds are fired from job,very bad change this.
sorry I mean to said that what happen is bad ,2 frineds are fired from job,very bad change this.
Sorry about that. I think the people who run the show often seem to follow every trend or hype in IT, without knowing anything at all.
I'll just write the algo's for search, insert and delete.
How does Java manage with 'pointers' and 'arrays'?
I'll just write the algo's for search, insert and delete.
How does Java manage with 'pointers' and 'arrays'?
ASKER
java has reference and arrays,
since no pinter i saw all source code,hashtable and vector have array implement.They resize array when grow occurs.where you working and how many years?what dis people tihink of not bother about experinced people?i fear that this come to me,sometime in past as my dad also fire two years ,no job stable in this and next come genratois.my friends they think of going US and earn money fast as can ,me too ,have got little knowledge but am a student,who will employ me ,none?i browse sometime ,now from part time work,so sorry for cry.i staring design pattern and EJb ,corba ,rmi ,learn what is happen in world,then when i pass out after 3 ,half years,do MS ? yes my english bad will imprpve fast ,but seen my source code?i think it's good ,my brother he login here at EE,he also knwos you ,he talked with and u helped himout too.he told me all people kind to beginner as all through stage once ,I even help my borther ,but what to do he got lead of 5 years over me.I take english lesson,but speech still hesitat ,u can send me mail at shogun@techie.com, i wish to remain anonmous and i liked book ShoGun by james clavell,yoshi toranaga is his name.
Yes you ask me anyhitng and i tell you what i know,dont hesitate.pastre text.
It's not how good you are
It's how bad you want it.
i want it bad.
Thanks you
since no pinter i saw all source code,hashtable and vector have array implement.They resize array when grow occurs.where you working and how many years?what dis people tihink of not bother about experinced people?i fear that this come to me,sometime in past as my dad also fire two years ,no job stable in this and next come genratois.my friends they think of going US and earn money fast as can ,me too ,have got little knowledge but am a student,who will employ me ,none?i browse sometime ,now from part time work,so sorry for cry.i staring design pattern and EJb ,corba ,rmi ,learn what is happen in world,then when i pass out after 3 ,half years,do MS ? yes my english bad will imprpve fast ,but seen my source code?i think it's good ,my brother he login here at EE,he also knwos you ,he talked with and u helped himout too.he told me all people kind to beginner as all through stage once ,I even help my borther ,but what to do he got lead of 5 years over me.I take english lesson,but speech still hesitat ,u can send me mail at shogun@techie.com, i wish to remain anonmous and i liked book ShoGun by james clavell,yoshi toranaga is his name.
Yes you ask me anyhitng and i tell you what i know,dont hesitate.pastre text.
It's not how good you are
It's how bad you want it.
i want it bad.
Thanks you