 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] nawaz org<<<<<<
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
|
|
| |
| |
|
|
|
|
| |
|
|
