 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
...OK, actually I can only think of 2 things to use a Min Heap for:
1. A heap sort.
2. Building Huffman trees.
Can anybody else think of a good use for a Min Heap? (Or even a Max Heap?)
I can think of plenty of algorithms that require some data in sorted
order, but any sorting algorithm will do for that. (And on current
hardware, in-place algorithms are usually faster than a heap sort.) Can
anybody think of an algorithm that benefits from an actual heap?
[For anybody not already familiar with such things...
A Min Heap is a kind of binary tree that stores data in such a way that
retrieving the "minimum" element is an O(1) operation. Insertion and
deletion are both O(log n), and I believe joining two heaps should be
O(log n) as well.
A "heap sort" involves turning something into a heap (with O(n log n)
complexity) and then repeatedly removing the minimum element (with O(n)
complexity) to yield a fully sorted list.
To build a "Huffman tree", you start with a set of trivial 1-node trees.
Each tree has a probability assigned to it. The algorithm is to simply
select the two lowest-probability tries, remove them from the set,
combine them into a larger tree (with a correspondingly higher
probability) and insert this back into the set. Eventually you will have
1 tree with Pr=1.
If this "set" is in fact a Min Heap sorted by tree porbability, then you
end up with a nice fast algorithm.
Here ends the lesson on algorithms and data structures.]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Dude, you so should be doing something else than fixing computers for a job.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> Dude, you so should be doing something else than fixing computers for a
> job.
No, really??
Heh. Now tell me something I don't already know. ;-) [Such as how to
*find* a better job... that'd be useful!]
While I'm not desputing the truth of your statement, I am curios to know
what lead you to this conclusion. The fact that I know what a min heap
is? [It's clearly described on Wikipedia. Doesn't take long to
comprehend.] That I know about Huffman trees? [Again, not hard to look
up.] What?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> No, really??
>
> Heh. Now tell me something I don't already know. ;-) [Such as how to
> *find* a better job... that'd be useful!]
Try hammering some random search terms into monster.co.uk, even "haskell"
brings up a couple of results! I can't believe there is no job on there for
you.
> While I'm not desputing the truth of your statement, I am curios to know
> what lead you to this conclusion. The fact that I know what a min heap is?
> [It's clearly described on Wikipedia. Doesn't take long to comprehend.]
> That I know about Huffman trees? [Again, not hard to look up.] What?
The fact that you always go on about quite complicated stuff that not many
other people would understand, and I mean not many within the IT industry,
not the entire population.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> No, really??
>>
>> Heh. Now tell me something I don't already know. ;-) [Such as how to
>> *find* a better job... that'd be useful!]
>
> Try hammering some random search terms into monster.co.uk, even
> "haskell" brings up a couple of results!
Yep. Already done that. And they have my CV, so every now and then they
email me a job advert or 12. [Usually in Canada... WTF??] I even went to
an interview a few weeks back...
They've sent me a couple of messages telling me I'm "ideal" to work for
HMGCC. ("HMG" as in "Her Majesty's Government". Scary shit, right there!)
> I can't believe there is no job on there for you.
I'm fairly confident somebody somewhere wants to employ somebody like
me. The part I'm worried about is *finding* this company...
>> While I'm not desputing the truth of your statement, I am curios to
>> know what lead you to this conclusion.
>
> The fact that you always go on about quite complicated stuff that not
> many other people would understand, and I mean not many within the IT
> industry, not the entire population.
Pfft. It's all stuff that's readily available on Wikipedia. And it's not
exactly "complicated".
Assuming you already comprehend what a binary tree data structure is, a
heap is just a special case: Every node holds data, and the data in each
node must be less than or equal to the data in both its child nodes.
[Notice there's no ordering constraint on siblings - so the tree need
not be fully ordered, only partially.]
Finding the minimum element is O(1) because, by definition, the minimum
element is always in the root node.
Inserting an element means comparing it to what's in the root node,
putting the smaller of the two back into the root, and propogating the
larger of the two down the tree recursively. [Notice I didn't say which
child node. There are actually several possible algorithms here, each
with different characteristics.]
Deleting an element likewise involves throwing away what's in the root
and moving the smaller of the two child elements up into the root. This
"moving" thereby deletes an element from one of the child nodes, so you
must recurse.
Personally I think Haskell source code says it better, but that's just me.
A Huffman code is a similarly straight-forward idea. When you save a
normal ASCII text file, each character is given an 8-bit code. [But if
you want to be technical, ASCII is a 7-bit code, so the extra bit is
always a 0.] The idea behind Huffman codes is that instead of every
character having an 8-bit code, different characters can have codes of
different lengths.
If you give the most common characters shorter codes [and therefore, by
necessity, give the rarer characters longer codes], then simply
re-encoding your text from ASCII to this new coding system will make
your file smaller! :-D
But how to construct this new coding scheme? And if codes can be
different lengths, how do you figure out where one code ends and the
next begins?
The answer to the second question is that the code must be a "prefix
code". That is, no full code can ever be the prefix of another full
code. (It may be a suffic, but never a prefix.) So if 011 is a valid
code, all on its own, then no other valid code can begin with 011
(although it can END with 011). This means that if the decoder sees 011,
it knows it just read a whole code, and the next bit is a seperate code.
An easy way to build a prefix code is to make each code be a set of
directions from the root of a tree to the leaves. Assuming each leaf
stores a character, each leaf's address will be a prefix code.
So, "all" we have to do is build a tree where the rare characters are
deep in the tree, and the common characters are shallow. We then read
off the tree address for each character and we will have our prefix code.
One obvious way is to take our set of characters and split it into two
halves such that the total probability for each half is roughly 50%.
Then all the characters in one set go on one side of our tree, and all
the characters in the other half go on the other side of our tree.
Recurse until you're done, and you have a nice tree.
This is called a Shannon tree, and it doesn't work very well. It's
actually fairly hard to split a set into two equal-probability sets. (I
have a vague recollection it might be NP-complete. Darren will know.)
The *other* thing you can do is work backwards. The rarest characters
should end up at the bottom of the tree, so let's put those into trees
*first*. And the common characters need to end up near the top, so let's
add those *last*. In other words, pick the two lowest-probability trees,
join them into a single tree, repeat until, like Hilander, there is Only
One.
*This* is called a Huffman tree. And it works much better. So, to summarise:
- Assign a "probability" to each character. [Guess them, estimate them,
count them up, whatever.]
- Build a set of trivial trees each consisting of a leaf containing a
character and its probability.
- Select the two lowest-probability trees, remove them from the set,
join them into a larger tree, insert this back into the set. Repeat
until only 1 tree remains.
- For each ASCII code in your input, replace it with the tree address of
that character in your tree.
- Assuming the probabilities you assigned were correct, the output file
is *guaranteed* to be smaller than or, in the worst case (every
character has equal probability), exactly the same size as the original.
(But note that you probably need to write down what the tree was so the
decoder can reconstruct it! This will make the file fractionally larger.)
Note that *any* prefix code will work. There's nothing "magical" about
Huffman codes. The Huffman algorithm is just an efficient way to build
such a code. If you know that, for example, low numbers are common in
your input and high numbers are rare, you can use a "Fibonacci code",
which is a prefix code with a predefined set of probability assumptions,
so it takes no effort to compute. [It's based on Fibonacci numbers,
hence the name.]
For something like a sound signal, where most samples are near to zero,
this could be a win. (Also, look at Predictive Coding, where you make a
"prediction" for each sample based on some property of the last few
samples, and record the "error" between the prediction and the actual
sample. Assuming your predictions are good, the errors will always be
"small" numbers.)
Huffman codes will work on anything, and they work quite well. There
*is*, however, a thing called "arithmetic coding", which does the same
thing but better. You see, it assigns a *fractional* number of bits to
each character.
That probably sounds completely incomprehensible. Put simply, the
compressed file contains an integral number of bits. (Duh!) But if you
encode 100 identical characters, the output bit length need not be
divisible by 100. You could say the number of bits gets rounded up to
the nearest whole number when you complete the file.
In practice, what this means is that the number of bits per character
can be closer to the binary logarithm of the probability for that
character - the "perfect" bit size. So you get a few percent more
compression this way. OTOH, the algorithm is harder. And patented, I
believe...?
Of course, comming up with better probability estimates will have a much
more dramatic effect on compression. Running a Huffman coder on a normal
text file gives typically 50% compression. But take into account letter
*combination* frequencies and you can go much higher than that.
Theoretically, PPM + arithmetic coding should give the best compression
that money can buy!
You know what? I think I might have just disproven the point I was
trying to make...? <:-,
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> They've sent me a couple of messages telling me I'm "ideal" to work for
> HMGCC. ("HMG" as in "Her Majesty's Government". Scary shit, right there!)
I would have thought so too, I had a couple of friends that seemed to posses
the same skills and interests that you do, and they got jobs there. The pay
isn't that great, but it would be good experience.
> Pfft. It's all stuff that's readily available on Wikipedia. And it's not
> exactly "complicated".
Not to you maybe, but it would be to lots of "IT" people I know. Just
believe me, it's not normal for someone working in IT (and I don't mean
software development) to know about half the stuff you post about (and seem
to understand).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> Heh. Now tell me something I don't already know. ;-) [Such as how to
> *find* a better job... that'd be useful!]
>
Actually, with respect to finding a better job, the problem has less to do with
*knowing* what to do (which isn't all that complicated) than with resolving to
actually do it. The work-a-day world can can easily leave one feeling drained
and thoroughly disinclined to take on as demanding a project as conducting a
proper job search. Job hunting not only uses up lots of time and effort in the
physical sense, it is also emotionally taxing in that it requires one to face
the likelihood of multiple rejections before achieving any success. It's
rather unlikely that the following list contains anything that you couldn't
have thought of yourself, but it might be useful to have these ideas in front
of you for consideration, so here goes:
1. Don't wait until you NEED a new job to look for a new job. That's how
people end up having to take yet another job that they don't get anything from
but a paycheck.
2. Make a short list NOW of places where you would like to be working in two
years and establish communications with both the human resources department AND
the department(s) that you would like to work for. Be very explicit that your
interest is specific, serious, focused and long-term and that you are NOT
merely inquiring in regard to current posted openings.
3. Create and *maintain* a library of job search support documents such as
resumes in various formats, references, recommendations. college transcripts
and examples of your work so that you can take advantage of any opportunity
INSTANTLY using top quality documents.
4. Always send important communications in BOTH electronic and paper format.
In any given company, it might be either one that will be retained and used to
contact you should an opportunity arise. Always send your resume and cover
letter UNFOLDED and in a presentation cover in a flat 9' x 12' envelope. Making
the effort to introduce yourself with professional looking documents really DOES
matter.
5. Keep records of whom you have contacted and when. Never allow more than
ninety days to go by without renewing a contact. Only make contact more
frequently than this after you have established a relationship with a specific
individual who has expressed a positive interest.
Again, none of this is any great revelation. The real question is whether or not
one is actually DOING it.
Best Regards and Good Hunting,
Mike C.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> They've sent me a couple of messages telling me I'm "ideal" to work
>> for HMGCC. ("HMG" as in "Her Majesty's Government". Scary shit, right
>> there!)
>
> I would have thought so too, I had a couple of friends that seemed to
> posses the same skills and interests that you do, and they got jobs
> there. The pay isn't that great, but it would be good experience.
Heh. When I went to that job interview a few weeks back, the guy said "I
don't think you belong in a commercial enterprise. I think you would be
better as a research associate at a university somewhere." Yeah, cos
research is what I do best...? Wait, WTF? o_O
I'm not too sure about HMGCC. The whole "you will be cleared to a high
level of security clearance" think kinda freaks me out in that whole Big
Brother type way. o_O
Plus, all their software development stuff clearly says all over it
"prior experience of developing large-scale applications is an absolute
requirement". So I guess I fail, right there.
>> Pfft. It's all stuff that's readily available on Wikipedia. And it's
>> not exactly "complicated".
>
> Not to you maybe, but it would be to lots of "IT" people I know. Just
> believe me, it's not normal for someone working in IT (and I don't mean
> software development) to know about half the stuff you post about (and
> seem to understand).
Hmm. Tell me something - all that stuff I just posted? Does it make any
semblance of comprehensible sense?
To *me* it makes sense, but then *I* wrote it. And I'm aware that often
an expert will try to explain something and completely forget some vital
item of information that the audience doesn't have but is so "obvious"
to the expert that they forget to mention it...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Actually, with respect to finding a better job, the problem has less to do
> with
> *knowing* what to do (which isn't all that complicated) than with
> resolving to
> actually do it. The work-a-day world can can easily leave one feeling
> drained
> and thoroughly disinclined to take on as demanding a project as conducting
> a
> proper job search.
"Take time to sharpen your saw"
I forgot who told me that, it was probably quoted from some management fluff
book, but it's true. It's better to take a break from your routine and try
to optimise it, it will be beneficial in the long run, even if it means you
don't get as much work done that day. And by optimise, it could just be
writing a program in Haskell to speed up some repetitive task, reorganising
your entire workload, or even looking for a new job.
I'm always quoting that to our Japanese colleagues because they seem to work
such long hours so inefficiently, and often give the "we don't have time"
excuse for not doing something.
> 2. Make a short list NOW of places where you would like to be working in
> two
> years and establish communications with both the human resources
> department AND
> the department(s) that you would like to work for.
This link may help, if you can't think of enough places:
http://www.timesonline.co.uk/tol/life_and_style/career_and_jobs/best_100_companies/best_100_tables/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Heh. Now tell me something I don't already know. ;-) [Such as how to
>> *find* a better job... that'd be useful!]
>
> Actually, with respect to finding a better job, the problem has less to do with
> *knowing* what to do (which isn't all that complicated) than with resolving to
> actually do it.
Probably not complicated if you know what you're doing. I haven't got a
clue. Sure, I've tried the obvious things, but those haven't worked. So
now I'm kinda not sure what's next.
> The work-a-day world can can easily leave one feeling drained
> and thoroughly disinclined to take on as demanding a project as conducting a
> proper job search.
Yeah, that's true enough. Sometimes I struggle to find the motivation to
do stuff I *like* doing, damnit! (It can be very hard to try to motivate
yourself to do stuff when you know nobody is actually going to care one
way or the other.)
Actually, I've been thinking about maybe taking a week off work so I can
spend some time doing this "for real". Unfortunately every place of
business shuts 20 minutes before I get home. [Quite maddening really!]
If I had a week, I'd be able to go places and speak to people and stuff...
> 1. Don't wait until you NEED a new job to look for a new job.
Heh. I'm tempted to leave this job right NOW, even though I have nowhere
else to go! But clueless as this company is, they've been around for 20
years, and I don't suppose they're going anywhere real soon. They'll
just continue to blunder on, making spectacular financial losses, as
they always have.
> 2. Make a short list NOW of places where you would like to be working in two
> years and establish communications with both the human resources department AND
> the department(s) that you would like to work for. Be very explicit that your
> interest is specific, serious, focused and long-term and that you are NOT
> merely inquiring in regard to current posted openings.
OK, I fail here. I cannot think of *any* company I'd actually want to
work for.
I mean, theoretically working for somebody like Yamaha or Korg or even
Nokia "sounds" realy neat. But actually? I have no clue who would really
be worth working with. My dad works in a laboratory, which "sounds"
really cool, but actually... isn't.
I did look into a list of big-name technology companies to see where
they have bases of employment. IIRC, Nokia, HP and Erricson have big UK
bases, but they're nowhere near where I live. Yamaha has a big place in
my city, but I think that's manufacturing not R&D. Korg has a base here
too, but I couldn't find any data without speaking to a human. That's
about as far as I got.
> 3. Create and *maintain* a library of job search support documents such as
> resumes in various formats, references, recommendations. college transcripts
> and examples of your work so that you can take advantage of any opportunity
> INSTANTLY using top quality documents.
I have an up-to-date CV. Spent lots of money on consultants to help me
sharpen it. It's currently available online at Monster.co.uk. Every now
and then some random agency contacts me, asks me a few questions, and
then is never heard from again.
It says on my CV "references available on request", but it strikes me
taht I don't actually *have* anybody I could point them to. Nobody knows
me! All the management in my current place of work recently changed, so
nobody in management here really knows anything about me. My university
shut down when I graduated. I don't have any "friends" or anything...
As for examples of my work... it strikes me that I've almost never
produced a "finished" program in my life. That's not a good thing. And
obviously, nobody is going to employ me to program in Haskell; they'll
want C, C++, Java or VB (or maybe some scripting language). I haven't
touched any of those in years now.
And then there's the minor detail that although I know a lot of stuff
about stuff... how many people actually need to know what a Huffman tree
is? None. Nobody needs to know this. It serves no useful purpose. And
Warp is probably right: I'm not a very good programmer.
> 4. Always send important communications in BOTH electronic and paper format.
You can't do that without a postal address. (And stamps. Do you have any
idea how hard it is to purchase stamps?!)
> 5. Keep records of whom you have contacted and when. Never allow more than
> ninety days to go by without renewing a contact. Only make contact more
> frequently than this after you have established a relationship with a specific
> individual who has expressed a positive interest.
Fair enuf...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Wed, 18 Jun 2008 14:44:15 +0100, Invisible <voi### [at] devnull> wrote:
>
>You can't do that without a postal address. (And stamps. Do you have any
>idea how hard it is to purchase stamps?!)
Petrol stations!
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> And then there's the minor detail that although I know a lot of stuff
> about stuff... how many people actually need to know what a Huffman tree
> is? None. Nobody needs to know this. It serves no useful purpose.
Of course it does, it is evidence that you are *willing* and *capable* of
learning such things. That is more important than what you actually know.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> And then there's the minor detail that although I know a lot of stuff
>> about stuff... how many people actually need to know what a Huffman
>> tree is? None. Nobody needs to know this. It serves no useful purpose.
>
> Of course it does, it is evidence that you are *willing* and *capable*
> of learning such things. That is more important than what you actually
> know.
Certainly a point worth making, and one I always try to emphasise. Heck,
that's how I got *this* job in the first place! ;-)
I think anybody who decides to "learn PostScript" in their lunchbreak
just out of boredom is a fairly unusual type of person.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> ...OK, actually I can only think of 2 things to use a Min Heap for:
>
> 1. A heap sort.
>
> 2. Building Huffman trees.
>
> Can anybody else think of a good use for a Min Heap? (Or even a Max Heap?)
Answer:
http://wordaligned.org/articles/top-ten-tags
--
Computer Lie #1: You'll never use all that disk space.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> ...OK, actually I can only think of 2 things to use a Min Heap for:
> 1. A heap sort.
> 2. Building Huffman trees.
Priority queue.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Priority queue.
See, I knew Warp would come up with a good answer...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> A Huffman code is a similarly straight-forward idea.
Tell that to Huffman. ;-)
Seriously, put together some essays and/or whitepapers about this stuff,
explaining it. You might be able to get a job teaching, or find a
publisher who will pay you to write a book. If you can write clearly
enough to teach complex stuff like this to youngsters, you can have a
pretty good career.
If nothing else, go to your local high-school and ask them if anyone
needs tutoring in computer programming.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Plus, all their software development stuff clearly says all over it
> "prior experience of developing large-scale applications is an absolute
> requirement". So I guess I fail, right there.
Yoda would think otherwise. You can only fail if you don't try.
Well, that's not quite true. But believe me, you won't get past the
phone interview if they're actually serious about that.
> Hmm. Tell me something - all that stuff I just posted? Does it make any
> semblance of comprehensible sense?
Quite! That's what people are trying to tell you. You explain things
very clearly.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> As for examples of my work... it strikes me that I've almost never
> produced a "finished" program in my life.
I don't know anyone who ever thought their program was finished. Even
games that go out the door aren't "finished" as far as the people
working on them are concerned.
> And then there's the minor detail that although I know a lot of stuff
> about stuff... how many people actually need to know what a Huffman tree
> is? None. Nobody needs to know this.
Actually, the cool places do. Read some of the google whitepapers and
actually look at the algorithms they use. It's the first place in 25
years I've seen using Bloom filters.
> You can't do that without a postal address. (And stamps. Do you have any
> idea how hard it is to purchase stamps?!)
Now you're just making up excuses. :-) I'll admit stamp purchasing is
unobvious in Europe to someone from America who would expect to be able
to buy stamps at, say, the post office, but it can't be *that* difficult.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Of course it does, it is evidence that you are *willing* and *capable* of
>> learning such things. That is more important than what you actually
>> know.
>
> Certainly a point worth making, and one I always try to emphasise. Heck,
> that's how I got *this* job in the first place! ;-)
Any decent company will have this mentality while interviewing too. Do you
pick the person who has spent 10 years learning the exact skills you need,
or the person who has spent 5 years learning a dozen different skills that
are all just as difficult as the one you need?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> As for examples of my work... it strikes me that I've almost never
>> produced a "finished" program in my life.
>
> I don't know anyone who ever thought their program was finished. Even
> games that go out the door aren't "finished" as far as the people
> working on them are concerned.
Well yeah, but you don't ship a game while it's still not playable
without a C compiler and some heavy-duty programming skills. :-P
>> And then there's the minor detail that although I know a lot of stuff
>> about stuff... how many people actually need to know what a Huffman
>> tree is? None. Nobody needs to know this.
>
> Actually, the cool places do. Read some of the google whitepapers and
> actually look at the algorithms they use. It's the first place in 25
> years I've seen using Bloom filters.
Yeah, but I won't be working for Google, will I? :-P
>> You can't do that without a postal address. (And stamps. Do you have
>> any idea how hard it is to purchase stamps?!)
>
> Now you're just making up excuses. :-) I'll admit stamp purchasing is
> unobvious in Europe to someone from America who would expect to be able
> to buy stamps at, say, the post office, but it can't be *that* difficult.
The Post Office?
Oh, you mean that place that shuts 20 minutes before I got home? :-P
[What annoys me is that there used to be a machine outside that
despenses stamps. But then they turned it off... It's still there, it
just won't give you any stamps!]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Plus, all their software development stuff clearly says all over it
>> "prior experience of developing large-scale applications is an
>> absolute requirement". So I guess I fail, right there.
>
> Yoda would think otherwise. You can only fail if you don't try.
>
> Well, that's not quite true. But believe me, you won't get past the
> phone interview if they're actually serious about that.
They're talking about people who have experience with Linux kernel
development and stuff - *I* can't even *read* C.
>> Hmm. Tell me something - all that stuff I just posted? Does it make
>> any semblance of comprehensible sense?
>
> Quite! That's what people are trying to tell you. You explain things
> very clearly.
Well, *I* like to think I explain things very clearly. But unless other
people actually agree with me, I have to wonder whether I'm just kidding
myself...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> The Post Office?
>
> Oh, you mean that place that shuts 20 minutes before I got home? :-P
>
> [What annoys me is that there used to be a machine outside that despenses
> stamps. But then they turned it off... It's still there, it just won't
> give you any stamps!]
Don't you have any supermarkets or newsagents nearby? They usually open
much later and have stamps.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> The Post Office?
>>
>> Oh, you mean that place that shuts 20 minutes before I got home? :-P
>>
>> [What annoys me is that there used to be a machine outside that
>> despenses stamps. But then they turned it off... It's still there, it
>> just won't give you any stamps!]
>
> Don't you have any supermarkets or newsagents nearby? They usually open
> much later and have stamps.
To be honest, I've never seen stamps on sale anywhere except at a post
office. Maybe they keep 'em hidden behind the counter or something, but
I've never seen them on sale...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> To be honest, I've never seen stamps on sale anywhere except at a post
> office. Maybe they keep 'em hidden behind the counter or something, but
> I've never seen them on sale...
http://www.royalmail.com/portal/rm/jump2?catId=400046&mediaId=26800663
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> To be honest, I've never seen stamps on sale anywhere except at a post
>> office. Maybe they keep 'em hidden behind the counter or something,
>> but I've never seen them on sale...
>
> http://www.royalmail.com/portal/rm/jump2?catId=400046&mediaId=26800663
Heh. Yeah. I ended up having to use this once...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> A Huffman code is a similarly straight-forward idea.
>
> Tell that to Huffman. ;-)
Huffman coding is one of those algorithms that seems delightfully
"obvious" after you've been told the algorithm. No doubt it seemed
highly non-obvious before anybody thought of it. ;-)
> Seriously, put together some essays and/or whitepapers about this stuff,
> explaining it. You might be able to get a job teaching, or find a
> publisher who will pay you to write a book. If you can write clearly
> enough to teach complex stuff like this to youngsters, you can have a
> pretty good career.
>
> If nothing else, go to your local high-school and ask them if anyone
> needs tutoring in computer programming.
Nah. Teaching requires social skills, not to mention a truly heroic
level of self-confidence. I possess neither.
I do enjoy writing about such things... but it never seems to generate
much of a reaction. I guess I'm the only person who cares. :-(
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> [For anybody not already familiar with such things...
>
> A Min Heap is a kind of binary tree that stores data in such a way that
> retrieving the "minimum" element is an O(1) operation. Insertion and
> deletion are both O(log n), and I believe joining two heaps should be
> O(log n) as well.
data MinHeap x = Node x (MinHeap x) (MinHeap x) | Null
is_empty Null = True
is_empty _ = False
top (Null) = error "empty heap"
top (Node x _ _) = x
insert nx (Null) = Node x Null Null
insert nx (Node x h0 h1) = Node (min x nx) (insert (max x nx) h1) h0
delete (Null) = error "empty heap"
delete (Node _ h0 Null) = h0
delete (Node _ Null h1) = h1
delete (Node _ h0 h1) =
let x0 = top h0; x1 = top h1
in if x0 < x1
then Node x0 (delete h0) h1
else Node x1 (delete h1) h0
> A "heap sort" involves turning something into a heap (with O(n log n)
> complexity) and then repeatedly removing the minimum element (with O(n)
> complexity) to yield a fully sorted list.
list_to_heap = foldl' insert Null
heap_to_list = unfoldr (\h -> if is_empty h then Nothing else (top h,
delete h))
heap_sort = heap_to_list . list_to_heap
> To build a "Huffman tree", you start with a set of trivial 1-node trees.
> Each tree has a probability assigned to it. The algorithm is to simply
> select the two lowest-probability tries, remove them from the set,
> combine them into a larger tree (with a correspondingly higher
> probability) and insert this back into the set. Eventually you will have
> 1 tree with Pr=1.
data Tree x =
Leaf {prob :: Double, symbol :: x} |
Branch {prob :: Double, branch0, branch1 :: Tree x}
instance Eq (Tree x) where
x == y = prob x == prob y
instance Ord (Tree x) where
compare x y = compare (prob x) (prob y)
huffman :: (Ord x) => [(x,Double)] -> Tree x
huffman = top . build . setup
where
setup :: (Ord x) => [(x,Double)] -> MinHeap (Tree x)
setup = list_to_heap . map (\(x,pr) -> Leaf {prob = pr, symbol = x})
build :: (Ord x) => MinHeap (Tree x) -> Tree x
build (Node t Null Null) = t
build h =
let
(t0,h0) = (top h, delete h)
(t1,h1) = (top h0, delete h0)
in insert (make_branch t0 t1) h1
make_branch t0 t1 =
Branch {prob = prob t0 + prob t1, branch0 = t0, branch1 = t1}
> Here ends the lesson on algorithms and data structures.]
[You knew it had to be done...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 19 Jun 2008 09:25:41 +0100, Invisible <voi### [at] devnull> wrote:
>
>To be honest, I've never seen stamps on sale anywhere except at a post
>office. Maybe they keep 'em hidden behind the counter or something, but
>I've never seen them on sale...
Most newsagents keep them behind the counter and sell as many as you
want, from 1 upwards.
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Most newsagents keep them behind the counter and sell as many as you
> want, from 1 upwards.
Also if you go to the cigarette/lotto counter at the front of most large
supermarkets, they have stamps.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 19 Jun 2008 12:37:36 +0200, "scott" <sco### [at] scottcom> wrote:
>> Most newsagents keep them behind the counter and sell as many as you
>> want, from 1 upwards.
>
>Also if you go to the cigarette/lotto counter at the front of most large
>supermarkets, they have stamps.
>
But do they sell self confidence?
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> A Min Heap is a kind of binary tree that stores data in such a way that
> retrieving the "minimum" element is an O(1) operation. Insertion and
> deletion are both O(log n), and I believe joining two heaps should be
> O(log n) as well.
> A "heap sort" involves turning something into a heap (with O(n log n)
> complexity) and then repeatedly removing the minimum element (with O(n)
> complexity) to yield a fully sorted list.
Btw, a balanced binary search tree has all those properties and then
some. Insertion and deletion are O(log n) operations, and you can not
only get the minimum but *also* the maximum element in O(1) time. Such
a tree can be used to sort a list of elements in O(n log n) time.
Moreover, the tree preserves full ordering: If so needed, you can traverse
the entire tree in O(n) steps and get all the elements in increasing order
(something you can't do with a heap). And even moreover, *searching* for
an element is an O(log n) operation (again something which cannot be done
so fast with a heap).
So the question arises: Given that a balanced binary search tree has all
the same properties as a heap, and even more, why are heaps considered
useful at all?
The answer is: Heaps don't require any ancillary data whatsoever (while
balanced binary search trees require three pointers and a flag for each
element). Moreover, the entire heap can be stored in a contiguous array
(which, as said, doesn't require *any* additional data).
This is what makes heaps more efficient than binary search trees in
many cases. For example using a binary tree for sorting an array of
elements requires O(n) amount of additional RAM, while using heap sort
requires O(1) additional memory. Same applies, for example, for a priority
queue.
Note that a heap requires random access (at least if it's used without
any ancillary data), while a binary tree doesn't. For this reason a heap
can only be used efficiently with arrays.
So this raises another question: If you are going to use a heap with
something else than an array (for example a tree structure), what are
the advantages of the heap over a regular balanced binary search tree?
The advantages of the binary tree over the heap are plenty. By constructing
a heap tree you are throwing away the one property heaps have: Space
efficiency.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> A Min Heap is a kind of binary tree that stores data in such a way that
>> retrieving the "minimum" element is an O(1) operation. Insertion and
>> deletion are both O(log n), and I believe joining two heaps should be
>> O(log n) as well.
>
> Btw, a balanced binary search tree has all those properties and then
> some. Insertion and deletion are O(log n) operations, and you can not
> only get the minimum but *also* the maximum element in O(1) time. Such
> a tree can be used to sort a list of elements in O(n log n) time.
> Moreover, the tree preserves full ordering: If so needed, you can traverse
> the entire tree in O(n) steps and get all the elements in increasing order
> (something you can't do with a heap). And even moreover, *searching* for
> an element is an O(log n) operation (again something which cannot be done
> so fast with a heap).
>
> So the question arises: Given that a balanced binary search tree has all
> the same properties as a heap, and even more, why are heaps considered
> useful at all?
I was under the impression that any kind of balanced tree tends to be
faster to access [because it's balanced, so you avoid the O(n)
worst-case behaviour], but slower to update [because you have to keep
re-balancing it]. A heap is much simpler to keep balanced because you
have far more freedom about where to put things. (On the other hand, an
in-order traversal is much slower.)
So it appears to me that the two simply have "different" properties.
Some things are more efficient with a heap, some with a balanced search
tree.
Unless you know something I don't...
> The answer is: Heaps don't require any ancillary data whatsoever (while
> balanced binary search trees require three pointers and a flag for each
> element). Moreover, the entire heap can be stored in a contiguous array
> (which, as said, doesn't require *any* additional data).
>
> So this raises another question: If you are going to use a heap with
> something else than an array (for example a tree structure), what are
> the advantages of the heap over a regular balanced binary search tree?
> The advantages of the binary tree over the heap are plenty. By constructing
> a heap tree you are throwing away the one property heaps have: Space
> efficiency.
Hmm, interesting...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> They're talking about people who have experience with Linux kernel
> development and stuff - *I* can't even *read* C.
Well, yes, OK. That's not what you said first, but OK. So find someplace
that's doing new things. Or apply anyway, and figure out how to do
interviews.
>> Quite! That's what people are trying to tell you. You explain things
>> very clearly.
>
> Well, *I* like to think I explain things very clearly. But unless other
> people actually agree with me, I have to wonder whether I'm just kidding
> myself...
Well, you're getting a lot of agreement here. What's that tell you? :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Huffman coding is one of those algorithms that seems delightfully
> "obvious" after you've been told the algorithm. No doubt it seemed
> highly non-obvious before anybody thought of it. ;-)
That's kind of what I was saying.
> Nah. Teaching requires social skills, not to mention a truly heroic
> level of self-confidence. I possess neither.
Note that "teaching" and "tutoring" are two separate things. To tutor,
you don't really need to be organized or deal with behavior problems in
the students or anything. You're doing pure teaching stuff, helping kids
learn what other teachers have already decided they should learn.
> I do enjoy writing about such things... but it never seems to generate
> much of a reaction. I guess I'm the only person who cares. :-(
Count the responses to your post.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Yeah, but I won't be working for Google, will I? :-P
Not if you don't apply!
> Oh, you mean that place that shuts 20 minutes before I got home? :-P
If you can't take off long enough to buy stamps, and you can't talk Gina
into getting some for you, you definitely need to switch jobs. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> To be honest, I've never seen stamps on sale anywhere except at a post
> office.
Every european country I've been to, the "tobacconists" seem to deal
with all the government collect-small-sums kinds of things, like
lotteries and stamps. Maybe a tobacco shop would have them?
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> data MinHeap x = Node x (MinHeap x) (MinHeap x) | Null
This is much cleaner than anything you'd see in Erlang, fwiw. Lots of
Erlang syntax for passing around functions (or lambdas) is so
heavy-weight that making (say) a list of lambdas as a bound variable in
another lambda you pass somewhere winds you up with so much nesting and
syntax cruft you're almost required to split it into a different function.
I've found there's a couple of annoyances with functional programming
(at least in Erlang):
1) Every control-structure is out of line. You can't really do a while
loop without having the body show up somewhere else, and almost always
needing a name. (I suspect Haskell's lazy evaluation makes this much
less of a problem, since you can just use something like fold over a
multi-gigabyte file and not worry about bombing out.)
2) There's no simple way to pass private information around. If I'm
doing some process that is (say) reading thru a big file, processing
hundreds of lines a second but still taking dozens of minutes to run, if
I want to put in a counter to print how far along it has gotten every
1000 lines (so I know it's working), it's a major pain to pass and
update that everywhere, interfering with all kinds of things (including
the caller of the function needing to pass the initial counter).
3) If you have a functionality that has a complex control flow, you
basically wind up writing it as a bunch of separate functions with tail
calls routing things around, like a state machine. Every time one you
change one of those to track something new, you have to track down every
call and pass the new thing. (For example, you have a turn-based game
that has a dozen paths thru it that all lead back to the next turn. You
decide you want to keep track of each move in the game. You can't just
add a static variable and append each move to it - you have to modify a
dozen places where the function is called to pass the partial list.)
I will admit, pretty much everything worked right pretty easily once I
got it to run at all, so it isn't that difficult, but it does seem like
a maintenance problem in a big program with lots of functionality.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> only get the minimum but *also* the maximum element in O(1) time.
This needs a pointer from the root directly to the smallest leaf and
largest leaf, doesn't it? Not to dispute; I'm just trying to understand
how it's a constant-time operation. O(lg N) is easy to understand.
And by "three pointers" you're including a pointer to the parent, yes?
What's the flag? the red/black flag?
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > only get the minimum but *also* the maximum element in O(1) time.
> This needs a pointer from the root directly to the smallest leaf and
> largest leaf, doesn't it? Not to dispute; I'm just trying to understand
> how it's a constant-time operation. O(lg N) is easy to understand.
Yes, you obviously require a pointer to the first and last nodes, but
these pointers can be kept updated at no extra cost (in other words,
keeping these pointers doesn't change the computational complexity of
any of the operations, and are very lightweight to keep updated).
Even without the pointers getting the min and max values is O(log n).
With a heap getting the max value is an O(n) operation.
> And by "three pointers" you're including a pointer to the parent, yes?
Right. (AFAIK self-balancing binary trees require the parent pointer
at each node, and they also make things like traversing the tree using
iterators much easier.)
> What's the flag? the red/black flag?
Yes. Keeping the tree balanced requires some ancillary data besides
the pointers.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Yes, you obviously require a pointer to the first and last nodes,
Cool. It was obvious to me, but I thought maybe smarter folks had come
up with something less obvious. ;-)
I had an interesting question today:
Given a large number N of points (say, millions) in a 2D cartesian
space, how do you find the K points closest to the origin most
efficiently? E.g., you have a million (X,Y) pairs in an unsorted array;
how do you find the five thousand pairs with the smallest (X*X+Y*Y) values?
You can actually do it with better time than "sort the whole list and
pick the five thousand first elements". Not, AFAIK, better in the O()
sense, but you can cut out a lot of unnecessary computation.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Yeah, but I won't be working for Google, will I? :-P
>
> Not if you don't apply!
Er... last time I checked, Google doesn't even *employ* people in the
UK! :-P
>> Oh, you mean that place that shuts 20 minutes before I got home? :-P
>
> If you can't take off long enough to buy stamps, and you can't talk Gina
> into getting some for you, you definitely need to switch jobs. :-)
That I definitely need to switch jobs isn't really in question here, is
it? ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>>> Yeah, but I won't be working for Google, will I? :-P
>>
>> Not if you don't apply!
>
> Er... last time I checked, Google doesn't even *employ* people in the
> UK! :-P
http://www.google.co.uk/intl/en/jobs/index.html
--
recursion, n.: see recursion.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Darren New" <dne### [at] sanrrcom> wrote in message
news:485ac0f5@news.povray.org...
>
> Note that "teaching" and "tutoring" are two separate things. To tutor,
> you don't really need to be organized or deal with behavior problems in
> the students or anything. You're doing pure teaching stuff, helping kids
> learn what other teachers have already decided they should learn.
Other thing that comes to mind is adult education. There's worlds of
differences between that and normal schools,
With the schools, most of the children don't want to be there. The're going
to misbehave, ignore homework, etc, etc.
With adult training (and I'm talking about the IT training complanies that
do the vender-related courses), the people in the course want to be there
and have often paid for it. Makes things a lot easier.
Worth considering.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Quite! That's what people are trying to tell you. You explain things
>>> very clearly.
>>
>> Well, *I* like to think I explain things very clearly. But unless
>> other people actually agree with me, I have to wonder whether I'm just
>> kidding myself...
>
> Well, you're getting a lot of agreement here. What's that tell you? :-)
Yay! Something I don't suck at! :-D
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Er... last time I checked, Google doesn't even *employ* people in the
>> UK! :-P
>
> http://www.google.co.uk/intl/en/jobs/index.html
Damnit, I'm *sure* I looked into th- oh, wait. London.
I wouldn't work in London if you *paid* me for it! :-P
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> And by "three pointers" you're including a pointer to the parent, yes?
>
> Right. (AFAIK self-balancing binary trees require the parent pointer
> at each node, and they also make things like traversing the tree using
> iterators much easier.)
>
>> What's the flag? the red/black flag?
>
> Yes. Keeping the tree balanced requires some ancillary data besides
> the pointers.
Well now, there's red-black trees, AVL trees, the BWS algorithm,
B-trees... exactly *which* self-balancing tree algorithm are we talking
about here?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> data MinHeap x = Node x (MinHeap x) (MinHeap x) | Null
>
> This is much cleaner than anything you'd see in Erlang, fwiw. Lots of
> Erlang syntax for passing around functions (or lambdas) is so
> heavy-weight that making (say) a list of lambdas as a bound variable in
> another lambda you pass somewhere winds you up with so much nesting and
> syntax cruft you're almost required to split it into a different function.
I've seen a lot of programming languages described as "functional".
(Lisp, Erlang, Clean, etc.) But I have yet to see any language that
works the way Haskell does. Lots of languages that allow you to program
in a functional way (hack, assembly language can do that!), but none
that really facilitate this very strongly.
Haskell is a "pure" functional language, in the same way that Eiffel is
a "pure" OO language. It seems that most "functional" languages aren't
very pure. Conclude what you want about that...
> I've found there's a couple of annoyances with functional programming
> (at least in Erlang):
>
> 1) Every control-structure is out of line. You can't really do a while
> loop without having the body show up somewhere else, and almost always
> needing a name. (I suspect Haskell's lazy evaluation makes this much
> less of a problem, since you can just use something like fold over a
> multi-gigabyte file and not worry about bombing out.)
Yeah, typically in Haskell you'd either do something like takeWhile to
grab just the data you want, or write a custom loop yourself.
> 2) There's no simple way to pass private information around. If I'm
> doing some process that is (say) reading thru a big file, processing
> hundreds of lines a second but still taking dozens of minutes to run, if
> I want to put in a counter to print how far along it has gotten every
> 1000 lines (so I know it's working), it's a major pain to pass and
> update that everywhere, interfering with all kinds of things (including
> the caller of the function needing to pass the initial counter).
State monad.
Wanna pass more information around? Change the state data structure.
> 3) If you have a functionality that has a complex control flow, you
> basically wind up writing it as a bunch of separate functions with tail
> calls routing things around, like a state machine.
Take a look at Parsec.
It's a parser library, and the usual way to implement a parser is with
some kind of state machine. However, Parsec uses a parser monad to
implement complex flow control (choice, iteration, back-tracking, error
handling, etc.)
For many kinds of complex flow control, you can structure the algorithm
either as a monad or maybe an arrow. (Every monad is an arrow. Some
arrows are monads.)
The really killer decision is finding exactly the right way to abstract
the task you're trying to perform. This is critical in any language, but
can be particularly non-obvious in Haskell. And usually, once somebody
shows you a better solution, you wonder why you didn't think of it
yourself... ;-)
> Every time one you
> change one of those to track something new, you have to track down every
> call and pass the new thing.
In that case, it's probably best to define the information you're trying
to keep track of as a data type and just add/remove fields as required
when the design changes. That way you only pass around a single parameter.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> Well now, there's red-black trees, AVL trees, the BWS algorithm,
> B-trees... exactly *which* self-balancing tree algorithm are we talking
> about here?
Does it matter?
Btw, fun fact about balanced binary search trees: When traversing the
tree from the smallest element to the largest, the computational
complexity of one step (ie. moving from one element to the next larger
element) is O(log n). Oviously since you are traversing all the elements
in the tree, you are doing n such steps. Intuition would tell that the
computational complexity of the whole traversal would, thus, be O(n*log n).
However, it's only O(n).
Proving this sounds difficult, but it's surprisingly simple.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Well now, there's red-black trees, AVL trees, the BWS algorithm,
>> B-trees... exactly *which* self-balancing tree algorithm are we talking
>> about here?
>
> Does it matter?
Well, some operations are in different complexity classes depending on
which one you pick - not unlike BST vs heap. ;-)
> Btw, fun fact about balanced binary search trees: When traversing the
> tree from the smallest element to the largest, the computational
> complexity of one step (ie. moving from one element to the next larger
> element) is O(log n). Oviously since you are traversing all the elements
> in the tree, you are doing n such steps. Intuition would tell that the
> computational complexity of the whole traversal would, thus, be O(n*log n).
> However, it's only O(n).
>
> Proving this sounds difficult, but it's surprisingly simple.
I couldn't prove my way out of a paper bag. :-(
Where most normal people figure out that (a+b)^3 = a^3 + 3 a^2 b + 3 a
b^2 + a^3 my shifting algebra, I was too stupid for that. I worked it
out by drawing a set of 8 3D cubes and attempting to figure out the
volume of each one. :-S
[Ever tried drawing a complex 3-dimenional figure by hand and annotating
it with measurements? It's not actually very easy - especially if you
can't draw...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
