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 1 of 4  [1] 2 3 4  Next page →

#150093 — Reinventing the wheel.

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?

[toc] | [next] | [standalone]

#150095

> 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

Sure you need a map and not a unordered map, i.e. a hashtable.
A hashtable should be quite easy to implement.
And why aren't external libs not allowed if you get their sources?

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

#150098

On 20/02/2020 19:04, Bonita Montero wrote:
>> 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
> 
> Sure you need a map and not a unordered map, i.e. a hashtable.
> A hashtable should be quite easy to implement.
> And why aren't external libs not allowed if you get their sources?


A hashtable was my first thought. However, items need to removed when 
they are looked up. This would be problematic in the kind of hashtable I 
normally use.

(One workaround is to leave the item in place, but mark it as not in 
use, and not available to use; but that could mean the size growing 
bigger than would be acceptable, even if the memory used for allocation 
was recovered. And slow down lookups.)

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

#150100

On 20/02/2020 20:11, Bart wrote:
> On 20/02/2020 19:04, Bonita Montero wrote:
>>> 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
>>
>> Sure you need a map and not a unordered map, i.e. a hashtable.
>> A hashtable should be quite easy to implement.
>> And why aren't external libs not allowed if you get their sources?
> 
> 
> A hashtable was my first thought. However, items need to removed when 
> they are looked up. This would be problematic in the kind of hashtable I 
> normally use.
> 
> (One workaround is to leave the item in place, but mark it as not in 
> use, and not available to use; but that could mean the size growing 
> bigger than would be acceptable, even if the memory used for allocation 
> was recovered. And slow down lookups.)

That was my thought.  The numbers shown so far are not that big - 
leaving the old data in place might be fine.

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

#150101

Bart <bc@freeuk.com> writes:

> On 20/02/2020 19:04, Bonita Montero wrote:
>>> 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
>>
>> Sure you need a map and not a unordered map, i.e. a hashtable.
>> A hashtable should be quite easy to implement.
>> And why aren't external libs not allowed if you get their sources?
>
>
> A hashtable was my first thought. However, items need to removed when
> they are looked up. This would be problematic in the kind of hashtable
> I normally use.

That's curious.  What do you usually use that makes removal problematic?

-- 
Ben.

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

#150106

On 20/02/2020 21:01, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:

>> A hashtable was my first thought. However, items need to removed when
>> they are looked up. This would be problematic in the kind of hashtable
>> I normally use.
> 
> That's curious.  What do you usually use that makes removal problematic?
> 


Suppose a fragment of the hashtable already looks like this (index and 
value):

   ....
   100 ABC
   101 DEF
   102 --- (free)
   ....

Say that ABC and DEF both have the same hash value of 100 (modulo table 
size). Then in looking up DEF, 100 doesn't match, but 101 does - fine.

But suppose that before looking up DEF, a successful lookup for ABC is 
done, which is then removed to result in:

   ....
   100 --- (free)
   101 DEF
   102 --- (free)

Now, you look up DEF, but location 100 is empty, a sign usually that 
what you're looking for doesn't exist. Lookup fails.

Maybe your hash algorithm is different, but with mine:

* Starting at the first hash index: you compare successive entries until 
either a match or an empty slot is found (wrapping as needed). Empty 
means not found.

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

#150116

Bart <bc@freeuk.com> writes:

> On 20/02/2020 21:01, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>
>>> A hashtable was my first thought. However, items need to removed when
>>> they are looked up. This would be problematic in the kind of hashtable
>>> I normally use.
>>
>> That's curious.  What do you usually use that makes removal problematic?
>
> Suppose a fragment of the hashtable already looks like this (index and value):
>
>   ....
>   100 ABC
>   101 DEF
>   102 --- (free)
>   ....
>
> Say that ABC and DEF both have the same hash value of 100 (modulo
> table size). Then in looking up DEF, 100 doesn't match, but 101 does -
> fine.
>
> But suppose that before looking up DEF, a successful lookup for ABC is
> done, which is then removed to result in:
>
>   ....
>   100 --- (free)
>   101 DEF
>   102 --- (free)
>
> Now, you look up DEF, but location 100 is empty, a sign usually that
> what you're looking for doesn't exist. Lookup fails.

Removal from a hash table using open addressing is a well-known
algorithm (actually there are two) so I probably would not call
implementing it "problematic", but it is certainly the most fiddly part.
I was imagining some design that made it well-neigh impossible.

> Maybe your hash algorithm is different, but with mine:
>
> * Starting at the first hash index: you compare successive entries
> until either a match or an empty slot is found (wrapping as
> needed). Empty means not found.

If you do what's called lazy deletion (I did not know it had a name
until just now!) you delete by invalidating the entry while keeping the
entry marked as occupied.  The search operation works exactly as above
(the invalidated entries won't match any valid key), but you make a note
of the first invalid-but-occupied slot you see on the way.  If the key
is found, and there was an invalid-but-occupied slot on the way, you
move the entry to that slot just before the return.

The other way is the more obvious one of shuffling entries with the
same hash value down when you delete.

-- 
Ben.

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

#150117

On 20/02/2020 22:56, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:

> If you do what's called lazy deletion (I did not know it had a name
> until just now!) you delete by invalidating the entry while keeping the
> entry marked as occupied.  The search operation works exactly as above
> (the invalidated entries won't match any valid key), but you make a note
> of the first invalid-but-occupied slot you see on the way.  If the key
> is found, and there was an invalid-but-occupied slot on the way, you
> move the entry to that slot just before the return.

The first part of that sounds like my workaround, where deleted entries 
are marked as not valid, but also not free to use.

I can't quite see yet how the moving will work (what goes in place of an 
entry after it's moved?), but it might also be tricky because stored 
entries won't normally retain their original hash values. I'd have to 
look at it some more.

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

#150123

On 20/02/2020 23:56, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
> 
>> On 20/02/2020 21:01, Ben Bacarisse wrote:
>>> Bart <bc@freeuk.com> writes:
>>
>>>> A hashtable was my first thought. However, items need to removed when
>>>> they are looked up. This would be problematic in the kind of hashtable
>>>> I normally use.
>>>
>>> That's curious.  What do you usually use that makes removal problematic?
>>
>> Suppose a fragment of the hashtable already looks like this (index and value):
>>
>>   ....
>>   100 ABC
>>   101 DEF
>>   102 --- (free)
>>   ....
>>
>> Say that ABC and DEF both have the same hash value of 100 (modulo
>> table size). Then in looking up DEF, 100 doesn't match, but 101 does -
>> fine.
>>
>> But suppose that before looking up DEF, a successful lookup for ABC is
>> done, which is then removed to result in:
>>
>>   ....
>>   100 --- (free)
>>   101 DEF
>>   102 --- (free)
>>
>> Now, you look up DEF, but location 100 is empty, a sign usually that
>> what you're looking for doesn't exist. Lookup fails.
> 
> Removal from a hash table using open addressing is a well-known
> algorithm (actually there are two) so I probably would not call
> implementing it "problematic", but it is certainly the most fiddly part.
> I was imagining some design that made it well-neigh impossible.
> 
>> Maybe your hash algorithm is different, but with mine:
>>
>> * Starting at the first hash index: you compare successive entries
>> until either a match or an empty slot is found (wrapping as
>> needed). Empty means not found.
> 
> If you do what's called lazy deletion (I did not know it had a name
> until just now!) you delete by invalidating the entry while keeping the
> entry marked as occupied.  The search operation works exactly as above
> (the invalidated entries won't match any valid key), but you make a note
> of the first invalid-but-occupied slot you see on the way.  If the key
> is found, and there was an invalid-but-occupied slot on the way, you
> move the entry to that slot just before the return.
> 
> The other way is the more obvious one of shuffling entries with the
> same hash value down when you delete.
> 

As usual with these things, there are many ways to handle them - with
many different balances in the efficiency.  Bart's method makes searches
and insertions efficient if the table stays sparse, and avoids needing
to store extra data of the true hash value.  (If you want to be able to
delete ABC here, you need to know if DEF is in the correct spot of 101
or if it should be moved up to 100.)  If deletions are rare in the
particular usage of the hash map (say, a global symbol directory), then
it's great.  If deletions are common, it's a pain.

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

#150165

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Bart <bc@freeuk.com> writes:
>
>> On 20/02/2020 21:01, Ben Bacarisse wrote:
>>
>>> Bart <bc@freeuk.com> writes:
>>>
>>>> A hashtable was my first thought.  However, items need to removed
>>>> when they are looked up.  This would be problematic in the kind
>>>> of hashtable I normally use.
>>>
>>> That's curious.  What do you usually use that makes removal
>>> problematic?
>>
>> Suppose a fragment of the hashtable already looks like this (index
>> and value):
>>
>>   ....
>>   100 ABC
>>   101 DEF
>>   102 --- (free)
>>   ....
>>
>> Say that ABC and DEF both have the same hash value of 100 (modulo
>> table size).  Then in looking up DEF, 100 doesn't match, but 101
>> does - fine.
>>
>> But suppose that before looking up DEF, a successful lookup for ABC
>> is done, which is then removed to result in:
>>
>>   ....
>>   100 --- (free)
>>   101 DEF
>>   102 --- (free)
>>
>> Now, you look up DEF, but location 100 is empty, a sign usually
>> that what you're looking for doesn't exist.  Lookup fails.
>
> Removal from a hash table using open addressing is a well-known
> algorithm (actually there are two) so I probably would not call
> implementing it "problematic", but it is certainly the most fiddly
> part.  I was imagining some design that made it well-neigh
> impossible.
>
>> Maybe your hash algorithm is different, but with mine:
>>
>> * Starting at the first hash index:  you compare successive entries
>> until either a match or an empty slot is found (wrapping as
>> needed).  Empty means not found.
>
> If you do what's called lazy deletion (I did not know it had a name
> until just now!) you delete by invalidating the entry while keeping
> the entry marked as occupied.  The search operation works exactly as
> above (the invalidated entries won't match any valid key), but you
> make a note of the first invalid-but-occupied slot you see on the
> way.  If the key is found, and there was an invalid-but-occupied
> slot on the way, you move the entry to that slot just before the
> return.

That helps with lookup times, but it doesn't help with occupancy
rate.  If the hash table is never cleaned up, a long term steady
state of adding and removing will eventually fill up the hash
table with "occupied but invalid" tombstones (ie, besides the
actual still-live entries).  So there needs to be more than just
marking a removed table entry with a tombstone (as I am used to
calling them).

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

#150096

On 20/02/2020 19:33, 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.
> 
> 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?
> 

How big are your keys and values?

Since you suggest it would be straightforward with std::map<> and C++, 
can you give the code in that language so that it's clear exactly what 
you are wanting?  (Obviously the calculation stuff can be skipped or 
simplified.)

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

#150097

> Since you suggest it would be straightforward with std::map<> and C++, 
> can you give the code in that language so that it's clear exactly what 
> you are wanting?  (Obviously the calculation stuff can be skipped or 
> simplified.)

I think the code he needs would be something having the same type
of genericity like sort(), i.e. the code f.e. would have callbacks
to generate the hash-value and to compare the keys of the nodes.

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

#150099

The key is a 32-bit integer, the value is 3 64-bit doubles, and the
location is represented
by a 32-bit unsigned integer.

There's existing C++ code that does something similar to what my C code
needs to do,
though by a different algorithm. Both algorithms need to deal with
different versions of
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.

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

#150110

On Thursday, February 20, 2020 at 10:46:12 PM UTC+2, James Kuyper wrote:
> The key is a 32-bit integer, the value is 3 64-bit doubles, and the
> location is represented
> by a 32-bit unsigned integer.
> 
> There's existing C++ code that does something similar to what my C code
> needs to do,
> though by a different algorithm. Both algorithms need to deal with
> different versions of
> 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.

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


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

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

#150118

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.

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

#150124

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>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.

In the several days this discussion has been in process, you could have
implemented a dozen different algorithms for comparision....

Is it truely performance sensitive?

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

#150127

Scott Lurndal wrote:
> In the several days this discussion has been in process,

I posted the first message on this thread slightly over 23 hours ago.

> you could have
> implemented a dozen different algorithms for comparision....

No, I could not. I cannot write working correct code anywhere
near that fast, and it always amazes me when someone else
says something that implies that it is normal to write it
that fast. I occassionally wonder what it is that you people
do differently from me that allows you to be that productive.
I'd be lucky to complete a correct complete implementation
of a binary tree in less than several hours.

> Is it truely performance sensitive?

Not particularly. So long as it's not significantly slower
than the algorithm it will be replacing (which uses C++ and
std::map<>), I should be fine - I just want to be sure that
it will be no slower. I'm primarily interested in ease of
implementation. The Subject of this thread was chosen to
express my annoyance at having to reimplement something
that has been implemented and thoroughly tested many times
by many other people. 

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

#150129

On Friday, February 21, 2020 at 12:20:57 PM UTC-5, James Kuyper wrote:
> Scott Lurndal wrote:
> > In the several days this discussion has been in process,
> 
> I posted the first message on this thread slightly over 23 hours ago.
> 
> > you could have
> > implemented a dozen different algorithms for comparision....
> 
> No, I could not. I cannot write working correct code anywhere
> near that fast, and it always amazes me when someone else
> says something that implies that it is normal to write it
> that fast. I occassionally wonder what it is that you people
> do differently from me that allows you to be that productive.
> I'd be lucky to complete a correct complete implementation
> of a binary tree in less than several hours.
> 
> > Is it truely performance sensitive?
> 
> Not particularly. So long as it's not significantly slower
> than the algorithm it will be replacing (which uses C++ and
> std::map<>), I should be fine - I just want to be sure that
> it will be no slower. I'm primarily interested in ease of
> implementation. The Subject of this thread was chosen to
> express my annoyance at having to reimplement something
> that has been implemented and thoroughly tested many times
> by many other people.

You can try starting with a glib implementation.  It implements some of
the data structures out of the box, and is pretty mature.  It's got hash
tables and memory slices.  Once you have a conceptual version that works,
then you can work out the requirement for it to be standalone, and have
a metric for speed and correctness.

Search for GLib Reference Manual.  I'd start there.

Best regards,
John D.

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

#150131

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>Scott Lurndal wrote:
>> In the several days this discussion has been in process,

>
>Not particularly. So long as it's not significantly slower
>than the algorithm it will be replacing (which uses C++ and
>std::map<>), I should be fine - I just want to be sure that
>it will be no slower. I'm primarily interested in ease of
>implementation. The Subject of this thread was chosen to
>express my annoyance at having to reimplement something
>that has been implemented and thoroughly tested many times
>by many other people. 

To that end, if you're able to use a gnu C library (glibc),
there's tree, hash and binary search capabilities available
using 'tsearch et. alia', 'bsearch et. alia' and 'hsearch et alia'.

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

#150133

On 2/21/20 6:23 PM, Scott Lurndal wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>> Scott Lurndal wrote:
>>> In the several days this discussion has been in process,
> 
>>
>> Not particularly. So long as it's not significantly slower
>> than the algorithm it will be replacing (which uses C++ and
>> std::map<>), I should be fine - I just want to be sure that
>> it will be no slower. I'm primarily interested in ease of
>> implementation. The Subject of this thread was chosen to
>> express my annoyance at having to reimplement something
>> that has been implemented and thoroughly tested many times
>> by many other people.
> 
> To that end, if you're able to use a gnu C library (glibc),
> there's tree, hash and binary search capabilities available
> using 'tsearch et. alia', 'bsearch et. alia' and 'hsearch et alia'.
> 

And to meet the 'self contained' requirement, you just need to add the 
library source code to your project (and follow the licensing restrictions)

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

Page 1 of 4  [1] 2 3 4  Next page →

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

csiph-web