Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #34857

Re: Rosetta Code: Top rank per group

Show all headers | View raw

On Monday, December 8, 2014 9:08:43 PM UTC-7, Melzzzzz wrote:
> On Mon, 8 Dec 2014 16:43:22 -0800 (PST)
> hughaguilar96@gmail.com wrote:
> > A program like this is trivial using my ASSOCIATION.4TH in the novice
> > package: http://www.forth.org/novice.html
> > It uses an LLRB tree internally, and it allows associations (or
> > subsets of associations) to be traversed in order. I would just build
> > one association sorted by department, then for each department I
> > would build an association sorted by salary, then just dump out the
> > leftmost N nodes. For a real program that has a lot of data and has
> > to be robust, it would make more sense to build an association sorted
> > by name, and then build associations sorted by department, salary,
> > etc. in which the record is a pointer to a node in the main
> > association --- like a relational-database, this saves memory by not
> > replicating data.
> 
> Hm, sounds complicated. SQL/Database is best for such tasks...
> You just have to send SQL command and that's all. Not worth a fuss...

Using a database is going to be hugely slow --- I wouldn't do this unless there was so much data that it wouldn't fit in memory all at once.

If using SQL is allowed by Rosetta Stone however, then I suppose they will allow me to use my novice package. It is not clear to me what the purpose of Rosetta Stone is --- we are comparing languages' libraries?

> > I don't think Rosetta Stone allows the use of libraries however ---
> > so it favors languages such as Perl that have data-structures built
> > in --- if the programmer has to implement all of these
> > data-structures from scratch as Elizabeth Rather demands her cult
> > members to do, the program is going to be huge and complicated. It
> > will also likely use an inefficient data-structure such as a basic
> > binary-tree rather than an LLRB tree, because implementing an LLRB
> > tree for a single program is way too much work.
> 
> What's so good about LLRB tree? I think that classical RB tree
> performs better. Only advantage of LLRB is like AA tree ease
> of implementation, I guess...

Have you actually implemented an RB tree? This stuff is more complicated than you might suppose --- I would not use the term "ease of implementation" for LLRB trees.

> > Actually, implementing a basic binary tree with insert and delete is
> > a lot of work too,
> 
> Nope, not much of a code. It requires some thinking but nothing 
> one cannot finish in couple of days.

True, but the whole program should be completed in one or two hours.

>  if it has to be done from scratch for every
> > program.
> 
> One can write it once and use it in every other program.
> It is not necessary to write everytime one starts new
> program. Problem is that like C (which also doesn;t have
> standard container library) Forth is low level language
> and people can't agree on interface. 

The problem with C is not that people can't agree on the interface --- the problem is that its type system gets in the way of passing a pointer to a function as a parameter --- the whole point of the exercise is that you can have various functions each working with different data types, but if the data-type has to be declared in the declaration for the function, then that defeats your purpose! The type system can be defeated using VOID declarations, but the result is an incredibly ugly mess.

Forth doesn't have the problem of type declarations, so it much easier in Forth. The problem in Forth is just basic ignorance:

On Thursday, September 26, 2013 12:09:59 PM UTC-7, Elizabeth D. Rather wrote: 
> On 9/26/13 2:27 AM, Albert van der Horst wrote: 
> > In article <043a32ac-c009-4aff-beda-aa4041daadcb@googlegroups.com>, 
> >   <hughag...@yahoo.com> wrote: 
> >> On Wednesday, September 25, 2013 11:44:35 AM UTC-7, Elizabeth D. Rather wrote: 
> >>> But my point is that you can define data objects to behave *exactly* the 
> >>> way you want them to, to solve the problem at hand. 
> 
> >> I totally disagree with this. It is foolish to custom-implement basic 
> >> data structures such as arrays for every application. It is easy to 
> >> write a general-purpose array or linked-list or whatever, that works 
> >> exactly the way that you want it to for *every* application. 
  
> Does "*every* application" you write use exactly the same kind of data 
> arranged in the same way? If so, having written it once you can reuse it 
> often. If not, you either have to rearrange your data to make it work or 
> modify your "general-purpose" structure. 

ANS-Forth has become a cult of ignorance. Everybody who programs in ANS-Forth feels required to maintain a level of ignorance equal to Elizabeth Rather's so that she will allow them to be members of the cult. Because Elizabeth Rather doesn't understand the concept of general-purpose data-structures, all ANS-Forth programmers are required to also be ignorant of the subject --- write every program entirely from scratch as she requires --- this is why ANS-Forth will always be considered a toy language.

>  This is why ANS-Forth is never used in commercial
> > programming --- implementing everything from scratch is just too much
> > work --- the boss expects a trivial program like this to be done in
> > an hour or two, and he will fire a programmer who spends a week on it
> > and then says: "Well, um, I'm bogged down in figuring out how LLRB
> > trees work, as they are quite complicated!"
> 
> There is internet, but then again, there are programmers that make
> memory leaks in Java :p

My experience with implementing the LLRB tree, is that there is nothing directly useful on the internet. Robert Sedgewick invented the LLRB tree. When you read his PDFs however, they provide non-working Java code for the implementation. It is not possible to just port this code over to Forth or any other language; it doesn't even compile because it references functions that aren't provided --- it is Java-like pseudo-code at best. I think Sedgewick purposely crippled this code so that students wouldn't be able to use his code without understanding the algorithm --- prevent the script kiddies from getting an 'A'. I had to actually figure out the algorithm to implement it, which wasn't easy (for me; maybe easier for others).

There are implementations that actually work (more than one for CLOS), so if you assume that whoever wrote those knew what he was doing, then you can port those directly into Forth or whatever without understanding the algorithm. I didn't do this, because I don't have so much faith in other people's understanding of subjects that I don't understand --- so I did it the hard way, and figured out the algorithm (but now I've forgotten it!).

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-08 16:43 -0800
  Re: Rosetta Code: Top rank per group Melzzzzz <mel@zzzzz.com> - 2014-12-09 05:08 +0100
    Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-09 21:43 -0800
      Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-09 21:55 -0800
        Re: Rosetta Code: Top rank per group november.nihal@gmail.com - 2014-12-10 03:40 -0800
          Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-11 19:15 -0800
            Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-13 09:11 -0800
              Re: Rosetta Code: Top rank per group "WJ" <w_a_x_man@yahoo.com> - 2014-12-15 06:08 +0000
              Re: Rosetta Code: Top rank per group "WJ" <w_a_x_man@yahoo.com> - 2014-12-17 02:50 +0000
                Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-18 22:06 -0800
                Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-21 17:14 -0800
                Re: Rosetta Code: Top rank per group Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-12-22 10:27 +0000
                Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2014-12-22 22:03 -0800
                Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2015-01-08 17:17 -0800
                Re: Rosetta Code: Top rank per group Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-01-09 09:56 +0000
                Re: Rosetta Code: Top rank per group hughaguilar96@gmail.com - 2015-03-16 19:11 -0700
                Re: Rosetta Code: Top rank per group "WJ" <w_a_x_man@yahoo.com> - 2014-12-24 05:25 +0000
  Re: Rosetta Code: Top rank per group mix <mix@test.net> - 2014-12-14 11:55 +0000
    Re: Rosetta Code: Top rank per group empty-buffers <empty.buffersYOU-DONT-WANT-THIS@gmail.NEITHER-THIS.com> - 2014-12-14 13:52 +0000
  Re: Rosetta Code: Top rank per group mix <mix@test.net> - 2014-12-14 11:58 +0000

csiph-web