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

Groups > comp.lang.c > #150118

Re: Reinventing the wheel.

Show all headers | View raw

On 2/20/20 4:55 PM, already5chosen@yahoo.com wrote:
> On Thursday, February 20, 2020 at 10:46:12 PM UTC+2, James Kuyper wrote:
...
>> the same problem that I'm asking about. The existing C++ code for
>> dealing with this
>> problem is functionally equivalent to the following simplified version:
>>
>> std::vector<Value> storage;
>> std::map<std::pair<Key, Index> > newMap;
>>
>> // Inside the processing loop:
>> auto it = newMap.find(key);
>> if(it != newMap.end()) {
>> value = storage[it->second];
>> newMap.erase(it);
>> } else {
>> index = storage.size();
>> value = calculate_value(key);
>> storage.push_back(value);
>> newMap.push_back(std::make_pair(key, index));
>> }
>>
>> Later on, the values stored in storage get written to a file, along with
>> various other data
>> that includes indices referring to elements of that array.
> 
> For a C++ prototype, did you compare std::map (i.e. balanced binary tree) vs std::unordered_map (i.e. hash table)?
> 
> If the later is faster in prototype than probably it would be faster in C as well. That is, assuming that prototype runs on the HW at least remotely similar to the target's.

Interesting idea - and I was going to look into it. However, for reasons
that should become clear later, I'm not going to be bothering now.

> Above you said something very interesting: "list should never need to
> store more than about 2^9 key-location pairs".
> How do you know it? Do values of keys have some special property that guarantees that?

2^9 was an upper limit that I estimated. It's not so much a special
property of the values, as it is of the algorithm. There's a
two-dimensional grid that includes these points. Call the axes of that
grid x and y. The data that must be processed is circumscribed by a
rectangle in those coordinates, and covers about 2/3 of the area of that
rectangle. The points that need to be kept track of are points which
have already been processed, that are adjacent to points that haven't
been processed yet. Note: not all such points need to be kept track of,
a fact which will become very important near the bottom of this message.

The algorithm I'm developing processes the points in a complicated order
which is difficult to describe, will be proprietary, and cannot be
explained without delving into details I shouldn't be discussing
publicly. However, that algorithm has a property that makes it feasible
to calculate an upper limit on the number of such points, and I can
describe that property.

For any point {x0, y0} that has been processed, every point {x, y} such
that x <= x0 && y <= y0 will have already been processed. Similarly for
any point {x1, y1] that hasn't been processed yet, any point {x, y} such
that x1 <= x && y1 <= y will also not have been processed yet. Because
of those facts, you can determine that the length of the boundary
between the two regions cannot be longer than the length of the
rectangle plus it's height. Divide that sum by the spacing of the grid,
and that's an upper limit on the number of points that need to be kept
track of.

> If such property exists it most likely can be exploited for generation of "perfect hash" i.e. hash that is guaranteed to never collide. If it is indeed possible the rest would be trivial.

I'd like to thank you for making me think about this point. Thinking
about the form of the boundary between those two regions made me realize
that x-y is a perfect hash for this list. No two points on the list will
ever have the same value for x-y. The maximum possible range of values
for x-y, divided by the grid spacing, gives a number of buckets that's
relatively small, yet adequate to the task, making a hash table very
simple to implement.

However, I have even more to thank you for. The existing code that has
similar functionality to mine, handles the problem in a rather
disorganized fashion, and probably needs to keep a rather large number
of points in it's std::map<>. I was fooled by that fact into thinking
that the same would be true of my replacement algorithm.

However, your question made me think more carefully about that issue. My
algorithm is more systematic than the existing one, and because of it's
hierarchical approach using recursion, the maximum number of points it
needs to keep track of is approximately the log, base 2, of the upper
limit I described above. In other words, I don't need to store about 2^9
points. I only need to store a maximum of about 9 of them at any given
time. A simple linear search should be sufficient. I designed the
algorithm with other goals in mind. This benefit was a natural
consequence of meeting those other goals, but I hadn't noticed it before.

> Another important question for choosing the best index structure is probability of finding the key in the map.
> Low? High? In the middle (i.e. something like 0.2 to 0.8)?

It's exactly 0.5. Every key will be searched for exactly twice - the
first time will fail, resulting in an entry being added to the list. The
second time will succeed, resulting in the entry being removed from the
list.

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

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