Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #150232
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Reinventing the wheel. |
| Date | 2020-02-25 13:42 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <r334nc$rh7$1@dont-email.me> (permalink) |
| References | (1 earlier) <28c6d89d-1439-477a-ba1a-6d694deec7a1@googlegroups.com> <4451a8f8-84ea-4411-a4c8-f255ebad3ee3@googlegroups.com> <aa860413-7a4e-4a7e-8ca0-e2b756a673b0@googlegroups.com> <87y2ss3ptr.fsf@bsb.me.uk> <5e12ccc9-1c6d-473c-8eb8-56312ad9b1a1@googlegroups.com> |
On 25/02/2020 13:08, Malcolm McLean wrote: > On Monday, 24 February 2020 16:36:24 UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >>> On Saturday, 22 February 2020 18:38:59 UTC, already...@yahoo.com wrote: >>>> On Saturday, February 22, 2020 at 1:15:28 PM UTC+2, Malcolm McLean wrote: >> <cut> >>>>> Dust off your copy of Basic Algorithms and take the red black tree. >>>>> (The code used to be online but the provider has now gone defunct). >>>> >>>> Everything I read so far suggests (for me) that the optimal solution >>>> to James's task is some form of hash table rather than a tree. And >>>> if somehow I am wrong about it and the optimal solution is indeed a >>>> tree, it's a fat tree rather than a binary tree. >>>> >>> std::map is usually implemented as a red-black tree, and he specifically >>> mentioned that as acceptable. >> >> James did not say that implementing std::map is acceptable, only using >> it. The optimal solution takes into account the amount of work required >> to write the code, and a simple hash table seems to be way better than a >> red-black tree. >> >> You come over as simply pushing your self-published book. Why buy a >> book to implement red-black trees? >> > A red black tree is too complicated to derive yourself from first principles. > So if you don't understand how to implement one, you can either copy > code you don't understand, or you can obtain an explantion, maybe with > a usable implementation attached. It's convenient to have that explanation > in a book rather than on a website, because, if some time later you need to > revise the code, you're more likely to remember where to obtain the book than > you are likely to be able to navigate back to a website. > Red-black trees are not that hard to implement - it all depends on how familiar the programmer is with algorithm design of that type. (Inventing such data structures in the first place is hard, of course.) Websites are a far better medium for this sort of thing than a book. You can quickly find dozens of explanations, and pick one that matches your tastes (lots of pretty pictures and animations, deep mathematical analysis of behaviour, or whatever suits). Implementations and samples are a few clicks away, in any language you'd like. I know I have a discussion on red-black trees in a book on algorithm design I have from my university days - and I have no idea where the book is. I know it will be discussed in Knuth, which sit on my bookshelf waiting for the day I suffer from chronic insomnia. Finding the Wikipedia article on red-black trees, however, is done in perhaps ten seconds. I am a great fan of books, and like dead-tree format, but it's been a couple of decades since physical books made much sense in the software world.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 10:33 -0800
Re: Reinventing the wheel. Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-20 20:04 +0100
Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-20 19:11 +0000
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-20 21:50 +0100
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 21:01 +0000
Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-20 21:34 +0000
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 22:56 +0000
Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-21 00:34 +0000
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-21 09:40 +0100
Re: Reinventing the wheel. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-22 14:06 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-20 20:06 +0100
Re: Reinventing the wheel. Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-20 20:08 +0100
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 12:46 -0800
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-20 13:55 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:12 -0500
Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-21 16:16 +0000
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 09:20 -0800
Re: Reinventing the wheel. jadill33@gmail.com - 2020-02-21 10:07 -0800
Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-21 23:23 +0000
Re: Reinventing the wheel. Richard Damon <Richard@Damon-Family.org> - 2020-02-21 18:41 -0500
Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-22 16:20 +0000
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-22 10:33 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-22 15:00 -0500
Re: Reinventing the wheel. Richard Damon <Richard@Damon-Family.org> - 2020-02-22 15:16 -0500
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 08:42 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-21 18:23 +0100
Re: Reinventing the wheel. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-22 17:06 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-23 06:18 -0800
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 21:14 +0000
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:24 -0500
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 13:15 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 13:44 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 14:21 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 14:22 -0800
Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-20 15:19 -0600
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:28 -0500
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 23:27 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 23:52 -0800
Re: Reinventing the wheel. jadill33@gmail.com - 2020-02-21 08:20 -0800
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-22 03:15 -0800
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-22 10:38 -0800
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-24 02:50 -0800
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-24 16:36 +0000
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-25 04:08 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-25 13:42 +0100
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 05:00 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-26 10:53 +0100
Re: Reinventing the wheel. chad <cdalten@gmail.com> - 2020-02-26 06:51 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@gmail.com> - 2020-02-24 22:40 +0300
Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-24 16:37 -0600
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-25 01:37 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-25 13:07 +0300
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 04:50 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-25 19:30 +0300
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 08:43 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@gmail.com> - 2020-02-29 01:25 +0300
Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-25 15:40 -0600
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 13:40 +0300
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-25 11:29 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 13:47 +0300
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-26 09:32 -0500
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 21:26 +0300
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-22 23:32 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-03-07 22:22 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-03-07 22:38 -0800
csiph-web