|
|
Which of these data structures is the fastest:
1) Binary Tree.
2) Stack.
3) Hash Table.
---
![Beer | [beer]](https://www.codeproject.com/script/Forums/Images/beer.gif) Hakuna-Matada
It means no worries for the rest of your days...
It's our problem free, Philosophy
<marquee behavior="alternate" scrollamount="5" scrolldelay="50"> ![Jig | [Dance]](https://www.codeproject.com/script/Forums/Images/jig.gif)
|
|
|
|
|
Depends on the implementation, and what do you like to do with it.
Inserting: Stack O(1), BinTree O(log n)
Deleting: Stack O(1), BinTree O(log n)
Searching: Stack O(n), BinTree O(log n)
Sorting: Stack O(n²), BinTree O(n log n)
Hash Table should be nearly the same to Binary Tree (I not quiet sure. It's monday morning, and I'm still almost asleep).
Regards,
Ingo
------------------------------
PROST Roleplaying Game
War doesn't determine who's right. War determines who's left.
"Would you like us to drop a bomb on you too? We have 10,000 of them!"
- espeir
"Perhaps we should lend them a nuke or two."
- espeir
|
|
|
|
|
Every data structure has a specific use.
lists are designed for inset-in-the middle scenerios, just as stacks are designed for Last-In-First-Out scenerios. A stack really can't be compared to the other two because usage is completely different.
A binary tree is not a replacement for a list, per se. Though it does handle add-anywhere scenerios, as does a Hash table. A binary tree is much superior to a list for searching, and even over a hash-table for some-search operations. A hash table is a one to one relationship with a key, and requires pre-allocated space. That makes its memory overhead a constant, its access time for any "one" item a constant. But if you want to output in sorted format, a hash is lousy, and a tree is still great.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
For search: Hashtable
BT is O(log n)
Stack is O(n)
HT is O(1)
|
|
|
|
|
Hashtable is the fastest for finding an exact value.
Binary tree is best if you need to do searches like "get the smallest value that is greater (or equal) some value".
You don't search in a stack, it always returns the element on top.
|
|
|
|
|
Hi.
It also depends on where/how the dats is stored. If it resides on disk rather than loaded into memory (due to a large dataset) then the access method will make a diffrence. A hash table might make no sense if the data cannot be contained completely within 'main' memory. It really depends on a number of factors and in the real world data cannot always be loaded as a whole. IBM developed the VSAM architecture which deals with this very issue, it is a b-tree that allows very fast access to a dataset of indeterminate size.
|
|
|
|
|
James Laing wrote: A hash table might make no sense if the data cannot be contained completely within 'main' memory.
A hash table does not have anything to do with memory, it is simply a method of associating a fixed size group of objects with a key. You can setup a large file with file pointer associated with the hash key. You can even use a double hash to associate multiple files and file pointers within with a key, or a split hash for the same. The problem with a hash table is it always represents access to a fixed size object (or group of objects), once the size and method is fixed it can be hashed. Access method is really irrelevant and simply up to the programmer. When you max out the hash table you have to completely rebuild it, that is when a hash table is a really, really innefficent.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
You can use hash tables on disk. If the hash table is not filled too much, you need only one seek operation (except for the few collisions where you might need two) to find a value, which is faster than any tree.
And if you're reading from disk, the "seek" is going to be the slow part.
|
|
|
|
|
Does any one has the idea of the exact calculation for superscript and subscript style of font. I mean the font is shrinked in MSWord. What calculation is used ? and also the baseline are moved as well. What are the standard calculations behind it ?
"C makes it easy to shoot yourself in the foot. C++ makes it
harder, but when you do, it blows away your whole leg."
- Bjarne Stroustrup
|
|
|
|
|
Font Creator web site [^] may provide you with the information you require. Also read some of these tutorials via Adobe [^]
modified 1-Aug-19 21:02pm.
|
|
|
|
|
if i have a text file, and this file contains sentences as lines.
each line my be english or other unicode language, and sometimes both.
now, i want to detect the lines that include english (A-z) and remove it.
Is there any way to detect that there is (A-z) character like calculate the summation of sentence charaters.
considering that i've converted the file encoding to something like UTF-8 or ISO-8859-15...etc
and is a deference of the size of the charater when converting from one encoding to another?
Faris Madi
Nothing Comes Easy (N.C.E.)
|
|
|
|
|
militiaware wrote: Is there any way to detect that there is (A-z) character like calculate the summation of sentence charaters.
Just load in the data from the file and march through it looking for the characters in that range.
militiaware wrote: and is a deference of the size of the charater when converting from one encoding to another?
UTF-8 is an 8-bit encoding. That means that each character is stored in 8-bits. This doesn't allow for many characters and the standard pretty much just has English characters in that set. UTF-16 is a 16-bit encoding which can hold character sets from many different languages. The size of each character in UTF-16 is exactly twice the size of a UTF-8 character.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: UTF-8 is an 8-bit encoding.
Its not. UTF-8 is a variable-length encoding, using one to four bytes per character.
Cheers,
Sebastian
--
Contra vim mortem non est medicamen in hortem.
|
|
|
|
|
Sebastian Schneider wrote: Its not. UTF-8 is a variable-length encoding, using one to four bytes per character.
It is an 8-bit encoding, though I probably could have been more specific by saying that it uses a maximum of 8-bits.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
To my knowledge, UTF-8 is a variable length encoding. You are right in one aspect: As long as you only use the first 127 UC characters, every character will be stored in 8 bits. As soon as you choose any other unicode character, that character will use up to four byte (32 bits).
UTF-8 is NOT a "8-bit encoding able to represent a subset of unicode characters", but a "Unicode encoding designed to be able to represent the most commonly used unicode character with as few bytes as possible".
Cheers,
Sebastian
--
Contra vim mortem non est medicamen in hortem.
|
|
|
|
|
http://www.utf-8.com/
You can find the RFC for it there as well. UTF-8 only holds the lower subset of the UNICODE standard. UTF-16 holds the whole thing.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: http://www.utf-8.com/
You can find the RFC for it there as well. UTF-8 only holds the lower subset of the UNICODE standard. UTF-16 holds the whole thing.
No it does not, as you'd know if you actually read the first few lines of your link.
www.utf-8.com wrote:
What is UTF-8?
UTF-8 stands for Unicode Transformation Format-8. It is an octet (8-bit) lossless encoding of Unicode characters.
UTF-8 encodes each Unicode character as a variable number of 1 to 4 octets, where the number of octets depends on the integer value assigned to the Unicode character. It is an efficient encoding of Unicode documents that use mostly US-ASCII characters because it represents each character in the range U+0000 through U+007F as a single octet. UTF-8 is the default encoding for XML.
Which is what Sebastian said. It's 8bits for us ascii, and expands to upto 32 for the remainder of unicode.
|
|
|
|
|
dan neely wrote: Which is what Sebastian said. It's 8bits for us ascii, and expands to upto 32 for the remainder of unicode.
I stand corrected. Sorry, I misread what it was saying the first time around.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Happens. I misread stuff all the time. My girlfriend, for example. She writes me a note "I love you. Clean the bathroom, if you find time." and I take it to mean what it says: if I find time, I'll clean the bathroom. Unfortunately, my chainsaw breaks and I have to mend it because I need it the next day... and then I spend the night on the couch 
Cheers,
Sebastian
--
Contra vim mortem non est medicamen in hortem.
|
|
|
|
|
|
Bassam Abdul-Baki wrote: Only 474 pages.
I've seen worse.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Yeah, me too. But still, I downloaded it and can't print it. So I have to wait for my SONY reader to come in.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
Bassam Abdul-Baki wrote:
Only 474 pages.
No wonder the explanation in the topology book on my shelf was a hard read; it was less than 10% that size thus must have left out important details 
|
|
|
|
|
Hi,
Do you know any open-source/free implementation/library for circular layout algortihm similar to
this?
Any ideas/links to any information on the topic would be usefull.
Thanks.
Vitaliy Tsvayer
Tikle
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
