Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #150120
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Reinventing the wheel. |
| Date | 2020-02-21 00:28 -0500 |
| Organization | A noiseless patient Spider |
| Message-ID | <r2nppi$if9$1@dont-email.me> (permalink) |
| References | <7ca1c103-6910-48ad-8eee-b2f47e7b1db0@googlegroups.com> <0mtt4f11chm1b6uo1pdjdm4kc8vbop2ln7@4ax.com> |
On 2/20/20 4:19 PM, Robert Wessel wrote: > On Thu, 20 Feb 2020 10:33:01 -0800 (PST), James Kuyper > <jameskuyper@alumni.caltech.edu> 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. >> >> My code will be computing a large number of values, and will unavoidably >> have to deal with each value exactly twice. It would be nice to avoid >> calculating each value twice, but the computation time isn't large >> enough for that to be a significant issue. The main problem is that I >> need to store each value exactly once. >> >> There's a key that I can easily calculate that uniquely identifies each >> value, so one approach would be >> >> Compute key >> Search for key in a key-location list >> IF found THEN >> Retrieve previously calculated value from the corresponding location >> Remove key-location pair from list >> ELSE >> Calculate new value >> Allocate storage >> Store that value in that location. >> Add the key-location pair to the list >> ENDIF >> >> In the worst case, my code will be generating on the order of >> 2^18 different values, but that list should never need to >> store more than about 2^9 key-location pairs (possible future >> developments might increase those values to 2^31 and 2^16, >> respectively). >> >> What kind of data structure would you recommend for storing that list of >> key-location pairs? > > > A hash table with separate chaining is my first thought. Especially > if you can either estimate the number of items, or do the first pass > without needing lookups. > > You need the table of root pointers, and only link field in each item. > You size the root pointers based on the number of (linear) search > steps you want to do on average (if there a N items, and you want the > average chain to be about 4 items, N/4). If you can't produce an > estimate, you can just do the entire first pass, dumping all the items > into a linked list, and then allocate the root table and hash all the > entries after the pass. > Features of my algorithm that I didn't notice, and therefore didn't explain, turn out to make a hash table overkill for this problem. See my response to already5chosen for more details.
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