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

Groups > comp.lang.c > #150093 > unrolled thread

Reinventing the wheel.

Back to article view | Back to comp.lang.c

Contents

  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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#150158

On Saturday, February 22, 2020 at 1:15:28 PM UTC+2, Malcolm McLean wrote:
> On Thursday, 20 February 2020 18:33:10 UTC, James Kuyper  wrote:
> > It's reinventing the wheel time, again.
> > 
> > I have some code I need to write, with the externally imposed
> > requirement that it be written in C and be self-contained. That is, it
> > must not reference any external libraries other than the C standard
> > library. If I could use C++, I'd use std::map<> to solve the problem
> > described below, and even in C there's many widely available third-party
> > libraries I could use to similar effect. Because those alternatives are
> > normally available, the last time I had to implement any such algorithm
> > was about 30 years ago. My BS was in Physics, not CS, so I never did a
> > formal study of such algorithms. Therefore, I'm looking for advice as to
> > the best algorithm to use, and ideally public-domain source code I could
> > copy and modify as needed. Efficiency is the key thing I'm looking for,
> > but keep in mind that std::map<> would have been acceptably efficient,
> > if I could have used it. Since I'm going to have to write, understand,
> > and test the code, simplicity of implementation is also important.
> > 
> > What kind of data structure would you recommend for storing that list of
> > key-location pairs?
> 
> 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.

[toc] | [prev] | [next] | [standalone]

#150196

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:
> > On Thursday, 20 February 2020 18:33:10 UTC, James Kuyper  wrote:
> > > It's reinventing the wheel time, again.
> > > 
> > > I have some code I need to write, with the externally imposed
> > > requirement that it be written in C and be self-contained. That is, it
> > > must not reference any external libraries other than the C standard
> > > library. If I could use C++, I'd use std::map<> to solve the problem
> > > described below, and even in C there's many widely available third-party
> > > libraries I could use to similar effect. Because those alternatives are
> > > normally available, the last time I had to implement any such algorithm
> > > was about 30 years ago. My BS was in Physics, not CS, so I never did a
> > > formal study of such algorithms. Therefore, I'm looking for advice as to
> > > the best algorithm to use, and ideally public-domain source code I could
> > > copy and modify as needed. Efficiency is the key thing I'm looking for,
> > > but keep in mind that std::map<> would have been acceptably efficient,
> > > if I could have used it. Since I'm going to have to write, understand,
> > > and test the code, simplicity of implementation is also important.
> > > 
> > > What kind of data structure would you recommend for storing that list of
> > > key-location pairs?
> > 
> > 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. 

[toc] | [prev] | [next] | [standalone]

#150197

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?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#150230

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.

 

[toc] | [prev] | [next] | [standalone]

#150232

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.

[toc] | [prev] | [next] | [standalone]

#150235

On Tuesday, February 25, 2020 at 2:42:29 PM UTC+2, David Brown wrote:
> 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,

Not sure about it. 
Red-black trees were not invented yet back when the 3rd volume was originally written. They are similar in principle (automatic balancing) to Adelson-Velsky and Landis (AVL) trees that are discussed there in depth, but they are not identical.

> 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.

[toc] | [prev] | [next] | [standalone]

#150261

On 25/02/2020 14:00, already5chosen@yahoo.com wrote:
> On Tuesday, February 25, 2020 at 2:42:29 PM UTC+2, David Brown

>> 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,
> 
> Not sure about it. Red-black trees were not invented yet back when
> the 3rd volume was originally written. They are similar in principle
> (automatic balancing) to Adelson-Velsky and Landis (AVL) trees that
> are discussed there in depth, but they are not identical.
> 

You are right - I forget how old TAOCP really is.  Precursors to
red-black trees (various B-trees) are in volume 3, but the defining
paper on red-black tress came after it was published.  (This time I
checked physically, rather than guessing!)

[toc] | [prev] | [next] | [standalone]

#150269

On Monday, February 24, 2020 at 8:36:24 AM UTC-8, 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?
> 

I haven't read his book, but a lot of the books on this subject, well, are dismal. They seem to fall into two distinct categories.

1)Pseudo code with a very terse, but correct explanation. This includes a some university level books.

2)Poor, buggy, and complete implementation, but with really poor and misleading explanation. This includes sites like geeksforgeeks, or a blog by a self professed computer geek that speaks broken English.

[toc] | [prev] | [next] | [standalone]

#150200

Malcolm McLean:

> 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).

Why do you propose a red-black tree with O(log N) performace
instead of a straight hash table with O(1) performance?

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150209

On Mon, 24 Feb 2020 22:40:00 +0300, Anton Shepelev
<anton.txt@gmail.com> wrote:

>Malcolm McLean:
>
>> 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).
>
>Why do you propose a red-black tree with O(log N) performace
>instead of a straight hash table with O(1) performance?


One advantage is that a red-black tree also has O(log n) worst case
performance.  It also gracefully expands, unlike a hash as the table
fills (or for separate chaining, as the number of data items starts
significantly exceeding the table size).

[toc] | [prev] | [next] | [standalone]

#150221

On Monday, 24 February 2020 22:37:13 UTC, robert...@yahoo.com  wrote:
> On Mon, 24 Feb 2020 22:40:00 +0300, Anton Shepelev
> <anton.txt@gmail.com> wrote:
> 
> >Malcolm McLean:
> >
> >> 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).
> >
> >Why do you propose a red-black tree with O(log N) performace
> >instead of a straight hash table with O(1) performance?
> 
> 
> One advantage is that a red-black tree also has O(log n) worst case
> performance.  It also gracefully expands, unlike a hash as the table
> fills (or for separate chaining, as the number of data items starts
> significantly exceeding the table size).
>
Another advantage is that you don't need a "hash function" to create
an essentially random integer from the key. You just need a 
comparison function, which is more intuitive.

The other advantage is that the code is there. It is actually online

https://github.com/MalcolmMcLean/babyxrc

Take the file "rbtree.c" from the repository.

[toc] | [prev] | [next] | [standalone]

#150225

Malcolm McLean to Robert Wessel:

> > Anton Shepelev:
> >
> > > Why do you propose a red-black tree with O(log N)
> > > performace instead of a straight hash table with O(1)
> > > performance?
> >
> > One advantage is that a red-black tree also has O(log n)
> > worst case performance.  It also gracefully expands,
> > unlike a hash as the table fills (or for separate
> > chaining, as the number of data items starts
> > significantly exceeding the table size).
>
> Another advantage is that you don't need a "hash function"
> to create an essentially random integer from the key. You
> just need a comparison function, which is more intuitive.

All true, but James said there is an exact limit on the
number of entries (so that resizing is not required) and
that speed is his primary concern (so that O(1) is better
than O(log N)).

> The other advantage is that the code is there. It is
> actually online
> https://github.com/MalcolmMcLean/babyxrc
> Take the file "rbtree.c" from the repository.

Thanks.  Again, if speed and ease of use are important, I
propose to change the void* data and key pointers to the
actual data types that James needs, losing generality.

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150233

On Tuesday, February 25, 2020 at 12:07:25 PM UTC+2, Anton Shepelev wrote:
> Malcolm McLean to Robert Wessel:
> 
> > > Anton Shepelev:
> > >
> > > > Why do you propose a red-black tree with O(log N)
> > > > performace instead of a straight hash table with O(1)
> > > > performance?
> > >
> > > One advantage is that a red-black tree also has O(log n)
> > > worst case performance.  It also gracefully expands,
> > > unlike a hash as the table fills (or for separate
> > > chaining, as the number of data items starts
> > > significantly exceeding the table size).
> >
> > Another advantage is that you don't need a "hash function"
> > to create an essentially random integer from the key. You
> > just need a comparison function, which is more intuitive.
> 
> All true, but James said there is an exact limit on the
> number of entries (so that resizing is not required) and
> that speed is his primary concern (so that O(1) is better
> than O(log N)).
> 

According to my understanding, an exact limit is known, but sizing [a primary] hash table according to this limit would be badly sub-optimal in the most common case, because it will cause a lot of unnecessary data cache misses.
On modern hardware a compactness of the data layout is often more important for speed than few extra arithmetic operations or even than few extra look-ups, as long as the later fit in cache.

On the other hand with red-black tree you only pay for what you use, i.e. in common case it will be compact and in rare worst case it would be big.

However,  for other reason, I wouldn't recommend red-black tree for James's task. The reason is browsing of such tree contains plenty of virtually unpredictable branches.

Yet another reason is a ratio of read-only lookups vs addition/deletion.
In James's case  this ratio is very low, actually zero.
For such case  red-black tree is better than classic AVL tree, but not much better. If one goes down self-balanced tree road, it makes sense to use tree that is balancing itself even less pro-actively than red-black.

> > The other advantage is that the code is there. It is
> > actually online
> > https://github.com/MalcolmMcLean/babyxrc
> > Take the file "rbtree.c" from the repository.
> 
> Thanks.  Again, if speed and ease of use are important, I
> propose to change the void* data and key pointers to the
> actual data types that James needs, losing generality.

Ignoring what I said above about general sub-optimality of red-black trees for the task, if one is going to use them nevertheless, than I would think that pointer to payload stored at the node is a way to go.
The tree has to be as compact as possible, because it is accessed O(log(N)) times per iteration. The payload, on the other hand, is accessed only once per iteration, so its compactness is less important.


> 
> -- 
> ()  ascii ribbon campaign - against html e-mail
> /\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150240

already5chosen to Anton Shepelev:

> According to my understanding, an exact limit is known,
> but sizing [a primary] hash table according to this limit
> would be badly sub-optimal in the most common case,
> because it will cause a lot of unnecessary data cache
> misses.  On modern hardware a compactness of the data
> layout is often more important for speed than few extra
> arithmetic operations or even than few extra look-ups, as
> long as the later fit in cache.

I don't know how data cache works.  If you are interested,
let us compare the performance of Malcolm's red-black trees
with my implementation of a hash table for James's problem.

> > Again, if speed and ease of use are important, I propose
> > to change the void* data and key pointers to the actual
> > data types that James needs, losing generality.
>
> Ignoring what I said above about general sub-optimality of
> red-black trees for the task, if one is going to use them
> nevertheless, than I would think that pointer to payload
> stored at the node is a way to go.  The tree has to be as
> compact as possible, because it is accessed O(log(N))
> times per iteration. The payload, on the other hand, is
> accessed only once per iteration, so its compactness is
> less important.

But those accesses will be through pointers anyway, so stack
throughput should be roughly the same.  But we can save on
pointer dereferencing.

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150241

On Tuesday, February 25, 2020 at 6:30:43 PM UTC+2, Anton Shepelev wrote:
> already5chosen to Anton Shepelev:
> 
> > According to my understanding, an exact limit is known,
> > but sizing [a primary] hash table according to this limit
> > would be badly sub-optimal in the most common case,
> > because it will cause a lot of unnecessary data cache
> > misses.  On modern hardware a compactness of the data
> > layout is often more important for speed than few extra
> > arithmetic operations or even than few extra look-ups, as
> > long as the later fit in cache.
> 
> I don't know how data cache works. 

That is VERY bad for programmer that is even minimally interstead in speed of the programs he or others develop.
You have to educate yourself.

> If you are interested,
> let us compare the performance of Malcolm's red-black trees
> with my implementation of a hash table for James's problem.
> 
> > > Again, if speed and ease of use are important, I propose
> > > to change the void* data and key pointers to the actual
> > > data types that James needs, losing generality.
> >
> > Ignoring what I said above about general sub-optimality of
> > red-black trees for the task, if one is going to use them
> > nevertheless, than I would think that pointer to payload
> > stored at the node is a way to go.  The tree has to be as
> > compact as possible, because it is accessed O(log(N))
> > times per iteration. The payload, on the other hand, is
> > accessed only once per iteration, so its compactness is
> > less important.
> 
> But those accesses will be through pointers anyway, so stack
> throughput should be roughly the same.  But we can save on
> pointer dereferencing.
> 
> -- 
> ()  ascii ribbon campaign - against html e-mail
> /\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150343

already5chosen to Anton Shepelev:

> > I don't know how data cache works.
>
> That is VERY bad for programmer that is even minimally
> interstead in speed of the programs he or others develop.
> You have to educate yourself.

I will.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150253

On Tue, 25 Feb 2020 04:50:46 -0800 (PST), already5chosen@yahoo.com
wrote:

>On Tuesday, February 25, 2020 at 12:07:25 PM UTC+2, Anton Shepelev wrote:
>> Malcolm McLean to Robert Wessel:
>> 
>> > > Anton Shepelev:
>> > >
>> > > > Why do you propose a red-black tree with O(log N)
>> > > > performace instead of a straight hash table with O(1)
>> > > > performance?
>> > >
>> > > One advantage is that a red-black tree also has O(log n)
>> > > worst case performance.  It also gracefully expands,
>> > > unlike a hash as the table fills (or for separate
>> > > chaining, as the number of data items starts
>> > > significantly exceeding the table size).
>> >
>> > Another advantage is that you don't need a "hash function"
>> > to create an essentially random integer from the key. You
>> > just need a comparison function, which is more intuitive.
>> 
>> All true, but James said there is an exact limit on the
>> number of entries (so that resizing is not required) and
>> that speed is his primary concern (so that O(1) is better
>> than O(log N)).
>> 
>
>According to my understanding, an exact limit is known, but sizing [a primary] hash table according to this limit would be badly sub-optimal in the most common case, because it will cause a lot of unnecessary data cache misses.
>On modern hardware a compactness of the data layout is often more important for speed than few extra arithmetic operations or even than few extra look-ups, as long as the later fit in cache.


If you know the size of the data, and the hash table is allocated
accordingly, you're not really going to be having many extra cache
hits.  If you use separate chaining, the root table entries (just a
pointer) will be much smaller than the data items, so even
under-populating the table to a fair degree will not leave you worse
off.

[toc] | [prev] | [next] | [standalone]

#150263

Robert Wessel:

> If you know the size of the data, and the hash table is
> allocated accordingly, you're not really going to be
> having many extra cache hits.  If you use separate
> chaining, the root table entries (just a pointer) will be
> much smaller than the data items, so even under-populating
> the table to a fair degree will not leave you worse off.

I was thinking not of separate chaining but of allocating a
bit more to keep a useful fill-factor.  My idea would be to
use quadratic probing with triangular numbers in an array of
size 2^n:  https://en.wikipedia.org/wiki/Quadratic_probing .

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

#150246

Anton Shepelev wrote
> All true, but James said there is an exact limit on the
> number of entries (so that resizing is not required) and
> that speed is his primary concern (so that O(1) is better
> than O(log N)).

Your impression that I have a fixed upper limit is probably due to
confusion I caused by my incomplete explanations. Here's a more complete
one.

I was asked to add a feature to some existing code. My implementation of
that feature requires a reorganization of the way that the code does
its work, and in particular, some functionality currently implemented in
C++ will have to be replaced by similar functionality that will have to
reside in a location where we're required by our clients to use C. As a
result of a career that started when memory was a lot more expensive
than it is now, my reorganization drastically reduces the memory
required, but I think it will also save time by avoiding unnecessary
copies and re-calculations - but none of those advantages are the reason
for this code change.

The work to be done involves two phases that are relevant to my
question, both optional. I got so wrapped up in thinking about the
easier first phase, that my initial discussions on this thread ignored
the needs of the second phase.

When I was assigned this feature, I came up with an implementation that
met the specified requirements using a 20-bit key. The owner of my
company looked at what I'd come up with, and said "That key will have to
be stored in a 32-bit integer anyway - let's expand the key to 32-bits,
just in case we might need it some day". The expansion didn't make my
code any slower or more complicated, so I had no problem with that. In
the following discussion, I'll mention various numbers. Next to some of
the numbers, I'll put a second value in parentheses. That number refers
to the possible future case where someone makes full use of the 32-bit
capacity of the key.

The work done during the first phase has a simple regular pattern, that
will require a maximum of anywhere from 8 to 4096 (32768) points to be
saved, depending upon a choice made by the calling routine. The choice
that would require 4096 points is pretty common. The work done during
the second phase does not have any simple pattern, and can require a
maximum of anywhere from 3 to 7,864,320‬ (251,658,240‬) points to be
saved, depending upon choices made by the calling routine. Choices that
would lead to anything even approaching either the lower or upper
limits are extremely unlikely, but my code should be able to handle
those unlikely possibilities, should they come up. The geometric mean of
those numbers is 4587, and would probably be more typical of realistic
situations. Because of the better organized approach used by my new
code, most of those numbers should be smaller than they would be for the
current code. One test I performed showed the current code keeping
track of 6069 points when my algorithm would only have required 1024.
However, the two biggest numbers I mentioned above are the same for
both versions.

I don't want to waste any time unnecessarily, but my main concern about
the performance is that my new algorithm not be any slower than the
current one, which uses std::map<> to keep track of the points. Ease of
implementation is my main concern. The two phases could use different
approaches to handling this problem, but there would have to be a good
justification for doing so. The wide range in the number of points that
might need to be stored might favor a more complicated approach using a
resizable hash table.

> ... Again, if speed and ease of use are important, I
> propose to change the void* data and key pointers to the
> actual data types that James needs, losing generality

You're right - this is not intended to be a general purpose package - if
I end up needing such a thing, I'll argue more strongly for using an
existing 3rd-party solution. As long as I have to customize it, I'm
going to make it more type-safe by using T* rather than void*, more
efficient by not using callbacks, and more special purpose by having
the find() function automatically (lazily?) delete any matching record
that it finds, which is not at all what a general purpose package should
do.

[toc] | [prev] | [next] | [standalone]

#150264

James Kuyper to Anton Shepelev:

> > All true, but James said there is an exact limit on the
> > number of entries (so that resizing is not required) and
> > that speed is his primary concern (so that O(1) is
> > better than O(log N)).
>
> Your impression that I have a fixed upper limit is
> probably due to confusion I caused by my incomplete
> explanations. Here's a more complete one.

OK, thanks for the explanation.

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web