| |
| |
| |
|
Page: 1 2 3 4 5 6 7 8
Comments:
<0> Mathematica default log base is e. C language ("math.h") log function gives natural logarithm (base e). Calc log gives log_10, ln gives log_e.
<1> Mole2 : if nothing is given log is usually base e
<2> Yep, that is what my calculator does.
<1> lg or lg_10 is base 10, log_2 is base 2, log or ln is base e
<2> As I thought, mathemathicians think log() means e as base, and programmers think it means 2 as base...
<3> lg is usually base 2
<1> dysprosia : no 10
<3> not from what i've seen
<4> 'lg' is usually the base--two logarithm.
<4> s/--/-/p
<3> log is usually base e or 10, ln is usually base e
<1> well the problem is none of these convention is generally accepted aside from ln
<4> (by analogy, i once saw someone write the base-twn logarithm as 'loooooooog'.)
<3> right
<2> In computer science there is an old myth that lookup in databases/tables etc can not be done faster than in O(log2(N)) time.
<1> so in doubt you need to check your text book or figure it from the textbook
<4> Mole2: "myth"? you need to specify a model of computation.
<2> When in fact many databases do lookups in O(log500(N)) steps. :))
<4> Mole2: you know that the base-two and the base-500 logarithms differ by only a constant factor, right?
<4> Mole2: and you also know that "O" is totally not what you mean, right?
<2> evilgeek: Yep.
<1> looks cs uses lg for base 2 : http://en.wikipedia.org/wiki/Binary_logarithm
<4> then why in god's name did you say that?
<1> however math books and calculators often use lg for base 10
<2> evilgeek: Problem is that most programmers thing that "rule" means there is no lookup faster then binary search. Which is log2().
<4> i've never seen a calculator use anything other than 'log' for the base-ten logarithm and 'ln' for the base-e logarithm.
<2> When there is methods that can tamper with that factor and make it say log500() instead which is way faster. :)
<4> Mole2: binary search is optimal.
<4> Mole2: well, on any sane model of computation.
<2> evilgeek: Well, anyway, I will use log10() and log2() in my documents to always be very clear.
<2> evilgeek: Nope, binary search is NOT optimal. We have way faster ones than binary now.
<1> evilgeek : good for you
<2> evilgeek: So you are stuck in the myth too? :))
<4> no, dude, we don't. it is very trivial to prove a lower bound on searching in an ordered list.
<2> Well, hash tables does lookup in close to O(1) time. :))
<3> yeah but what cost is insertion?
<2> About the same, about O(1) time. :)
<4> Mole2: hash tables ***ume that your data is hashable and that you have an incredible amount of space. in reality, randomly accessing this incredible amount of space tends to be of order Theta(log(amount of space)).
<2> As long as you use a sparsely populated hash table.
<3> mole: i don't think you're right
<4> IIRC, for such a hash table to be sufficiently sparse for your claim to hold, it has to use superlinear space.
<2> Haha, funny to see you guys jump to and think lookups has to be log2(). :))
<4> Mole2: it *does*.
<1> here's a source for lg for base 10 : http://de.wikipedia.org/wiki/Logarithmus
<4> Mole2: in any sane model of computation, it does.
<3> kmh: maybe in germany
<1> dysprosia : yes
<2> evilgeek: Nope, sparsely populated hash tables doesn't take up much more space than a simple list.
<3> that doesn't mean it's a global convention
<1> dysprosia : as i said there's no real standard aside from ln
<3> yes
<2> Since if you store objects of some reasonable size you allocate each of those objects once and then just insert indexes to them in the hash table.
<3> you will need to reheap at some time or other
<4> Mole2: you're ***uming that the objects have unreasonable size.
<1> dysprosia : i didn't say it is global convention, i said there's no global convention aside from ln
<3> or am i confusing this with something
<4> dysprosia: you're confusing Mole2 with someone who understands order notation.
<3> evil: heh
<2> Anyway, it is clear I should be very clear in my documents and use log2() and log10() etc to avoid missunderstandings.
<1> hehe
<5> @quote dysprosia
<6> scurvy dogs
<3> hehe
<2> And thanks to you guys I now know the correct notation to write those logs. So thanks.
<3> hello catfive
<4> ther eis no 'correct' notation, no.
<2> I admit I am not good at any kind of notation. :(
<4> anyway, if you want a reference that proves that a hash table with expected constant lookup and insert and friends will take superlinear space, see Motwani and Raghavan, Randomised Algorithms.
<1> dysprosia : which country are you from ?
<2> evilgeek: Now, are you pulling my leg or something since you mention "Randomised algorithms" ?
<7> It's a time-space tradeoff.
<3> australia
<1> ic
<4> Mole2: no.
<3> wait, we're talking abotu hash tables
<2> dysprosia: Yes, some of us were talking about hash tables.
<3> mole2: what search algorithm are you claiming is better than binary search?
<2> Well, not really "search" but "lookup" but usually is about the same thing.
<2> And forinstance hash tables are faster than binary search.
<3> you may have hash collisions
<2> Right, but if you have enough free space in your hash table such collisions mostly will just cost 1 or 2 operations extra.
<3> yeah, but you need that "free space"
<2> So on average you get below 2 operations to get the item you want.
<1> always depends on the context :)
<2> But that free space is just needed for the index, not for the full objects.
<3> you still need that free space as well
<2> The index can be just a list of pointers to the actual data objects you are looking for.
<3> so? same for an array
<2> And you only need say twice the index space as the number of indexed items or so for a hash table to behave very well.
<8> how long time will it take to apply the hash function on the n elements to be inserted? O(n)? ...
<3> if you're searching amongst K elements, your index array needs only K elements
<4> hash tables are not "faster" than binary search. in order to achieve constant expected worst-case lookup time, you need superlinear space.
<2> What I mean that having such an index is cheap in memory cost. Since it is just the index of pointers which does not take up much space.
<3> not so for hash tables
<4> regardless, hash tables do not work for data that cannot be hashed, but only compared against one another.
<2> evilgeek: Well, we usually consider the average speed etc. And yes, in the worst case a hashtable takes N operations to find the item. :((
<3> and what evilgeek said
<4> Mole2: no, you consider the worst-case speed, because you're doing computer science. and no, you don't need n operations in the worst case.
<2> Yeah, that might be true. Only I have a hard time coming up with an example of data that can be sorted but numbered. (And if it can be numbered it can be hashed.)
<2> *but not numbered.
<4> rooted trees?
<4> (yes, they can be hashed. no, it's not easy to prove that the hashing works.)
<1> geek is evil ...
<2> Ah well, anyway, I got what I need for today.
<4> (sorting is easy, however; store the subtrees in sorted order, and do a lexicographical comparison. a tree that has more vertices than another tree is considered to be larger.)
<2> Well, a good example is a tree where each node has say 4 children instead of 2 children. Then search can be done in log4 instead of in log2 time. Right?
<4> (the only useful hashing scheme of which i'm aware involves polynomials in n variables, where n is the depth of the tree, and you apply the schwarz-zippel theorem to prove that it works.)
<4> one will note that log_4 and log_2 differ by a constant factor.
<4> and, further, no.
<2> If the cost in the system is to reach each node (such as loading it from disk or connecting over the internet) and comparing the children in a node is cheap.
<2> Yes, they differ by a constant factor. But that makes a huge difference in number of jumps over the graph. Think forinstance of internet routing and similar "lookups".
<4> it makes a constant factor difference, huge or not.
<2> I know SGL databases often has say 100 children under each node and when you load a "node" it means loading a full block of data from disk that contains 100 pointers to children.
<2> There the cost is to load a block from disk, then you can just as well fill that block with children, see?
<2> *SQL databases
<4> i hate to break it to you, but comparing **** also costs.
<2> Ah well, I guess you are a mathematician and theoretician and not an engineer, right? So you don't bother about real world performance, right?
<4> suppose we have a sorted array of length n, and we want to see whether it contains a key k. how do you propose we determine whether k lies in this sorted array without expending at least log_2(n) - 1 comparisons in the worst case?
<4> no, i'm not an engineer. your claims have nothing to do with engineering.
<2> Well, for many systems it is not the number of comparisons that costs, but the loading/contacting of a node in the tree.
<4> i believe i am a fairly competent computer programmer, though.
<2> So then making each node have more children means faster.
<4> Mole2: yes, but you still need to do log_2(n) - 1 comparisons.
<4> yes, but it doesn't mean that you can beat the lower bound.
<2> Perhaps in the worst case yes.
<4> okay, you still need to do log_2(n) - 3 - 1/2^n comparisons in the average case. happy?
<4> scratch the -1/2^n term.
<2> As I see it a hash table doesn't need anything near log2(n) comparisons in most cases.
<4> it needs to be able to hash things.
<2> Well, computer data usually is very hashable. :)
<4> quickly, come up with an algorithm for hashing rooted trees.
<2> Well, you are talking about a special case. Most tables with data in computers do have hasheable items.
<2> And I actually think you can hash a rooted tree. :)
<4> you can. it's just way harder than doing things properly.
<2> Say it is a binary tree, then each leaf node actually has an address that can be written as 0's and 1's.
<4> it's not a binary tree.
<2> Well, whatever kind of tree it is you can translate the path down to one node to numbers.
<2> Anyway, you are just playing devils advocate and looking for exceptions.
<4> um, no.
<4> i'm pointing out that what you say is fundamentally bull****.
<2> What I said was that for many cases in computer systems the actual time to do something can be close to O(1) if you have a hashtable.
<4> what do you mean by "close to O(1)"?
<2> And if it involves contacting nodes ove the internet (costly) but the internal comparison of the say 100 children in the node is much cheaper then the contacting of the node then the bigger part of the cost is log100(n), which is really nice.
<4> part of the cost is log_100(n), but what you don't understand is that there is a huge constant factor in front of this and the other part of the cost is at least log_2(n) - 1.
<2> evilgeek: For me "O(1)" means that the work the lookup can be done in one operation.
<4> that's not what "O(1)" means, though.
<9> can anyone explain to me the kneeding process in new kind of science and how it is meant to work as a fractional part extractor?
<4> Mole2: i have no idea why you would begin a sentence with "For me, ___ means..." when you're asked to define something.
Return to
#math
or
Go to some related
logs:
Beetel PPP connection
yaboot%screen%resolution
mplayer xcompmrg
kstartconfig
#php
dns-lookup iptables 53
gaim disable popup
#centos
#ubuntu
mod_mysql_vhost ubuntu
|
|