 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Btw, a balanced binary search tree has all those properties and then
> some.
Random musing:
BST (binary search tree) sounds confusingly similar to BSP (binary space
partitioning).
If you think about it, a BST is kind of vaguely like 1D BSP.
I wonder if any BST self-balancing algorithms are applicable to BSP?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] san rrcom> wrote:
> 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?
If you are allowed to post-process, a PR-quadtree can be used to find
points closest to another point quite fast (faster than O(n), iirc).
If you are not allowed to post-process, then I can't think of anything
else than using http://en.wikipedia.org/wiki/Selection_algorithm and then
searching for all points smaller than the found one, which would be linear
complexity in average.
(That page, in fact, describes finding the n smallest elements, and
comments: "The resulting algorithm requires an expected time of only O(n),
which is just about the best any algorithm can hope for.")
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> I wonder if any BST self-balancing algorithms are applicable to BSP?
AFAIK, no.
A Kd-tree is basically a binary search tree for dimensions higher than 1.
It's a binary tree, and at each node in the tree you go to the left or the
right subtree depending on which side of the axis (or axial plane in 3
dimensions) the searched point is in relation to the current node. (The axis
or axial plane changes at each level in the tree.)
Adding a node to a balanced Kd-tree is a difficult operation and, AFAIK,
cannot be optimized in the same way as regular BSTs can. Wikipedia seems
to confirm that: http://en.wikipedia.org/wiki/Kd-tree
"Balancing a kd-tree requires care. Because kd-trees are sorted in
multiple dimensions, the tree rotation technique cannot be used to
balance them - this may break the invariant."
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I wonder if any BST self-balancing algorithms are applicable to BSP?
>
> AFAIK, no.
>
> "Balancing a kd-tree requires care. Because kd-trees are sorted in
> multiple dimensions, the tree rotation technique cannot be used to
> balance them - this may break the invariant."
Hmm. Yes, I can see how that would be a problem. Pity...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> 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...
Yeah, Haskell is pretty cool that way.
> Yeah, typically in Haskell you'd either do something like takeWhile to
> grab just the data you want, or write a custom loop yourself.
But by writing the loop yourself, you've separated the logic of the loop
from the logic the loop loops over. I.e., your control isn't anywhere
near (textually) your actions.
> Wanna pass more information around? Change the state data structure.
So you have it all wrapped up in some other data structure, and you're
adding to that. You still have to track down places you created it, and
add the additional information.
I.e., since looping requires recursion, every time you change what data
persists between iterations, you have to change all the recursive calls.
Maybe the state monad helps, and you could probably do the same thing by
wrapping your stuff in a record in Erlang, but that's just really
covering up the problem, in some ways.
> 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.)
Oh, Erlang has that sort of stuff. I guess I could write a turn-based
video game as a finite state machine. That still doesn't clarify how the
control flow flows. I.e., you can't just read off the steps for
performing a turn. Stuff like
Ask for a word
While the word is not valid
explain why, ask again
Ask for a number
while the number is invalid,
explain why, ask again
That winds up being like ten separate functions in Erlang,
once you deal with stuff like "the thing the user typed isn't
a number" and so on. It becomes really unobvious to me reading
the code just what the control flow is.
I'll check out the Parser thing and see what it suggests.
>> 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.
Yeah, even more obscure, unfortunately. :-) Now you not only have
hard-to-follow control flows, but you wind up passing a large record
full of stuff to a function that really only needs one or two fields, or
you wind up extracting just those couple of fields for that call at
which point you're back to the same problem again.
--
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:
> Darren New <dne### [at] sanrrcom> wrote:
>> 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?
>
> If you are allowed to post-process, a PR-quadtree can be used to find
> points closest to another point quite fast (faster than O(n), iirc).
I don't think you could start with an unsorted flat array and get better
than O(n) time. It would have to take that long to build the
PR-quadtree. But yah, if you know you're going to need this...
> If you are not allowed to post-process, then I can't think of anything
> else than using http://en.wikipedia.org/wiki/Selection_algorithm and then
> searching for all points smaller than the found one, which would be linear
> complexity in average.
Yep. That's what I came up with.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Gail Shaw wrote:
> 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.
Well, not necessarily.
Some people will be on a course because they employer sent them there,
but they themselves don't think they need it and it's a waste of their time.
But yes, *more* of them will want to be there.
BTW, I've only been on a course paid for by my employer once. It was a
course on Windows 2000. The guy leading it did spent a brief period
going over TCP/IP, and the subject of class-A/class-B/class-C networks
came up. Would you believe that *I* was the only person in the room who
knew that 2^24 is exactly 16,777,216?
Actually, the look the course leader and the other attendees gave me
was... not welcoming. The course leader later claimed that in the 15
years he's been doing this job, I'm the first person to know the exact
answer; most people just know it's "approximately 17 million"...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Yeah, typically in Haskell you'd either do something like takeWhile to
>> grab just the data you want, or write a custom loop yourself.
>
> But by writing the loop yourself, you've separated the logic of the loop
> from the logic the loop loops over. I.e., your control isn't anywhere
> near (textually) your actions.
I meant that you could write the loop and the processing logic as a
single function, if you really wanted to. (I tend to do this if the flow
control is complex enough that no standard combinator is likely to
implement it easily.)
>> Wanna pass more information around? Change the state data structure.
>
> So you have it all wrapped up in some other data structure, and you're
> adding to that. You still have to track down places you created it, and
> add the additional information.
True, but there shouldn't be very many of those.
> I.e., since looping requires recursion, every time you change what data
> persists between iterations, you have to change all the recursive calls.
> Maybe the state monad helps, and you could probably do the same thing by
> wrapping your stuff in a record in Erlang, but that's just really
> covering up the problem, in some ways.
Not sure what gave you that idea... Add a field to the data structure,
and only the places that use that new field have to care about it. It's
a lot less work than passing lots of parameters individually.
>> 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.)
>
> Oh, Erlang has that sort of stuff. I guess I could write a turn-based
> video game as a finite state machine.
Parsec allows you to write parsers without needing to explicitly build
state machines. Stuff like
integer = do
ds <- many1 digit
return (read ds)
decimal = do
ds1 <- many1 digit
char '.'
ds2 <- many1 digit
return (read $ ds1 ++ "." ++ ds2)
number = do
try decimal <|> integer
Now you can parse any valid number, without having to worry about the
actual state machine transitions needed to do that.
> That still doesn't clarify how the
> control flow flows. I.e., you can't just read off the steps for
> performing a turn. Stuff like
> Ask for a word
> While the word is not valid
> explain why, ask again
> Ask for a number
> while the number is invalid,
> explain why, ask again
>
> That winds up being like ten separate functions in Erlang,
> once you deal with stuff like "the thing the user typed isn't
> a number" and so on. It becomes really unobvious to me reading
> the code just what the control flow is.
Hmm, let's see:
word <- untilM valid_word ask_for_word
numb <- untilM valid_numb ask_for_numb
(Haskell has a function called "until", but there is no untilM function
for some reason. However, it is not hard to implement.)
Depending on how complex the validity and requesting code is, you can
write it inline or as a seperate function. Note that the validity check
code is still within the IO monad, so it can output an explanation of
why the answer isn't valid if needed.
>> 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.
>
> Yeah, even more obscure, unfortunately. :-) Now you not only have
> hard-to-follow control flows, but you wind up passing a large record
> full of stuff to a function that really only needs one or two fields, or
> you wind up extracting just those couple of fields for that call at
> which point you're back to the same problem again.
Well... I guess it depends on just how complex your flow control is.
Like I said, the key is finding the best way to structure your program -
and that means seperating out all the parts that don't really influence
each other, and finding a way of grouping things so you can get a nice
flow of code. This is easier said than done...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Orchid XP v8" <voi### [at] devnull> wrote in message
news:485be54d$1@news.povray.org...
>
> Some people will be on a course because they employer sent them there,
> but they themselves don't think they need it and it's a waste of their
time.
Even then, you don't get the same behavioural problems as with children. I
know a couple of people who do that kind of training. Serious behavoral
issues are rare.
Ok, there's sometimes a know-it-all who's out to prove he knows more than
the instructor or a person that doesn't care in the slightest. The 1st isn't
hard to manage, the second can be ignored.
Or so I'm told.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> going over TCP/IP, and the subject of class-A/class-B/class-C networks
> came up.
Did anyone point out that nobody uses class-A, class-B, or class-C
routing any more? :-)
--
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
|
|
| |
| |
|
|
|
|
| |
|
|
