MarkingKey

Niko Schwarz niko.schwarz at gmx.net
Wed Jun 12 15:54:33 UTC 2002


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am Mittwoch, 12. Juni 2002 04:24 schrieb Richard A. O'Keefe:

> Precisely.  The point is, most of the time a sentinel is useful,
> your "marking key" is not. [because marking keys work just one side]

well, i had no problem to use my markingkey to implement a heap. the 
theoretical problem that a < b XOR a >= b must be true, is easily avoidable 
by making sure that the "sentinel" is on the right side of the comparison.
im not experiencing any trouble.

> 	They're quite useful, each one, like an element
> 	z in a linked list.
>
> Well, no, an element z in a linked list is NOT particularly useful,
> and if any books are candidates for burning, books that make simple
> linked lists look difficult are on the top of that pile.

The very same sedgewick algorithms book is such one, and it simply makes 
sense. this book is the classical book for that matter, no doubt about that. 
and i gladly see how simple the z element makes linked lists. if you disagree 
with the classical book, then youll have a hard time to win the reputation 
you need to seriously fight it. most of all since its really obvious: such 
elements make implementations easier, faster and plainly: more fun.

> As I have demonstrated, your "marking key" didn't work with numbers,
> and while that could be fixed, it still didn't work with Strings,

it _did_ work. your problem is entirely theoretical: ive got _no_ problem to 
use it.

> One day it dawned on me that I COULDN'T use the sentinel technique in
> Pascal, because if I had to sort an entire array, there just wasn't
> any place to PUT the sentinel. 

well, specially with ocs, there usually is space. and you neednt use it all 
the time, when theres no space, you can simply search for one from inside the 
array: i dont see a problem.

> 	How "seldom appropriate"?
>
> I mean that if you use maxInt as a sentinel in an array,
> you are setting yourself up for disaster.

didnt notice that..

> One day someone will innocently include maxInt as a value in the array,
> and your algorithm will stop working.

well, i cant recall any situation ive come to see where maxInt was an 
unavoidable legitimate value, but if there ever might be one, the cool thing 
bout squeak is that you can easily fix the situation.
but again: if your calculations go any near maxInt, and you do not switch to 
longs, then its really your fault...

> Basically, in most languages, any time you have a predicate less(x,y),
> ANY of the values that less(,) accepts as an argument COULD be legitimate
> data in some container.  If you "steal" one of those values to use as a
> sentinel, then one day you will have to pay for your crime, because one
> day that value will appear as data that you have to handle as normal data.

ill call you when it comes, ok?

> 	I need a value that is below or above anything else,
> 	that's all.
>
> No, you don't need it.  You just think you do.  Your problem is not
> "find a magic value", it's "sort fast".

No, nono. I have two problems: 
a) experiment with all that's fun, cos for the next months ill have plenty of 
time (go to the army) and
b) make fast basic data structures.

while for b) we can argue what is useful or not, the need isnt big to fight so 
hard there... soon as i have a benchmark for my heap, ill compare it to the 
one shipped with squeak, and then the discussion will be odd, right?
(hay... *dreamingBoutFindingMyCodeInSqueak....*)

and for a) I have a copy of that algorithms book, and i want to practice with 
it. simply widen my horizens bout new techniques. and if a sentinel is part 
of that, then i need one. but as it looks to me, squeak should have one, too. 
but: since implementing it is trivial, and you really seem to feel offended 
by the idea, i promise i wont push the of including that class, for you. 

> 	And when numbers are keys (very common) than the biggest or
> 	smallest number is the solution.
>
> Not as common as you might think.  Dates, Times, and/or Timestamps, yes.

stockings, sales, numbers, priorities.... sorting by numbers is extremely 
common.

> You can only use your MarkingKey class when you KNOW you are sorting
> numbers.

nonsense..

> And if you know you are sorting numbers, you should use a radix
> sort or a bucket sort, not insertion sort.

radix sort and straight radix sort both speed up when you mix them with 
insertion sort, for random distributions.

regards,

nick

- -- 
Let He who taketh the Plunge Remember to return it by Tuesday.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9B268c9uyCiO8RNQRAi12AJ9BFZl55xdx7yFM/y1VS2eLM42khQCeMADn
Zve/a6YMoyrpJEZI/Ko3k+0=
=qpzv
-----END PGP SIGNATURE-----




More information about the Squeak-dev mailing list