|
Re^6: [OT:] Is this Curriculum right?
by Marshall (Canon) on Nov 26, 2021 at 23:37 UTC
|
I guess that I don't really understand what is meant by a C++ vector. A Perl hash table calculates a "vector" to a short linked list. Perl has an algorithm such that, in general, when these "short linked lists" become too long, Perl doubles the hash size and creates more "vectors". The lists associated with one vector, will become distributed amongst other vectors as more vectors become available. As long as each "vector" just points to a short linked list, this is just fine. You don't need one to one vector to object. You need vector to a few objects.
BTW, if you are writing in Perl, just use the Perl array and use splice to insert or delete if you need to. I personally cannot remember writing Perl code that does that explicitly does that in the past decade. Mileage varies. There is no need for a specific linked list implementation in Perl. | [reply] |
|
|
... just use the Perl array and use splice to insert or delete if you need to ...
there is no need for a specific linked list implementation in Perl
Agreed. I too find Perl's arrays a delight to use. :)
I guess that I don't really understand what is meant by a C++ vector
A C++ vector is similar to a Perl array.
Like C arrays, C++ vectors use contiguous storage locations for their elements (great for CPU cache performance),
while their size can change dynamically, with storage handled automatically by the container
(great for protection from dreaded C memory faults).
A Perl hash table calculates a "vector" to a short linked list.
Perl has an algorithm such that, in general, when these "short linked lists" become too long, Perl doubles the hash size and creates more "vectors".
I have not studied how Perl implements its hash tables;
I hope to find more time to study them in the future.
The standard C++ library equivalent of a Perl hash are the
UnorderedAssociativeContainers,
especially std::map
and std::unordered_map.
Though the C++ standard library is an interface and does not specify implementation
(thus allowing library implementations to adapt to new hardware in the future),
I believe that
std::map is usually implemented using red-black trees,
while std::unordered_map (closest to Perl's hashes)
is usually implemented, apparently due to
a small "oversight" in the specification,
by "storing a linked list to external nodes in the array of buckets".
There are a wide variety of associative containers in the C++ standard library, all sharing
a similar interface. For example, in High Performance Game of Life:
- I ended up using std::unordered_set with a customized hasher for cell_lookup_type ... after benchmarking different containers (which was very easy due to their consistent interface).
- For cell_list_type, I used std::vector<Cell>.
| [reply]
[d/l]
[select] |
|
|
| [reply] |
|
|
> I have not studied how Perl implements its hash tables; I hope to find more time to study them in the future.
see https://st.aticpan.org/source/RURBAN/illguts-0.49/index.html#hv
the collisions for a bucket are stored in a linked list.
> Agreed. I too find Perl's arrays a delight to use. :)
Perl arrays use a doubling trick to ensure that push and unshift are near O(1) like with linked lists.
They allocate more memory than needed, and start and end are given by pointers° inside that area. In the rare cases it's exhausted, twice as much memory is dynamically allocated and the data transferred.
So its space for time and the cost for re-allocation is reduced to a constant on average.
And splice'ing should still be far more expensive than with linked lists.
°) kind of a sliding window
| [reply] |
|
|
|
|
|
Re^6: [OT:] Is this Curriculum right?
by karlgoethebier (Abbot) on Nov 26, 2021 at 20:25 UTC
|
«…never felt the urge to write my own linked list class…»
I talked about this issue with the boy’s teacher and it was like talking to a horse as we say in German. Best regards, Karl
«The Crux of the Biscuit is the Apostrophe»
| [reply] |
|
|
> it was like talking to a horse as we say in German
Thanks for the lesson in German idioms!
What I love about Perl monks is you can't predict what new things you'll learn each time you log in. :)
I think I agree with your sentiment ... unless I've totally misunderstood due to my lack of fluency in German :).
Sadly, I can't think of a single thing I learnt at Melbourne University that was of
pratical use in the workplace, it was all way too theoretical ...
while a lot of the stuff I learnt at good old
RMIT night school was of immediate practical use on the job next morning ...
though I see working class RMIT has now become a "University". Oh well. :)
For every one Alexander Stepanov, writing complex and powerful low level libraries,
or Larry Wall, designing post-modern programming languages,
there are thousands of journeyman programmers being paid to get their job done
by using these languages, libraries and frameworks.
And, frankly, you wouldn't want to let most of them near such intricate code.
Though I'd love to have a well paid job designing languages or low level libraries,
there aren't many positions available.
Though a brief lesson on data structure concepts (arrays/vectors, strings, maps, hashes, trees, and yes, linked lists) is basic and essential,
a more practical education would spend more time on using them, rather than implementing them.
Please let me know if I've misunderstood the point you were trying to make.
| [reply] |
|
|
Let's see what happens with the code that I sent you.
BTW, here in the US we had a talking horse on a popular TV show called, "Mr. Ed" and he was a pretty smart horse.
If your boy's instructor cannot understand my code, then as you perhaps would say, "I see black", Ich sehe schwarz.
| [reply] |
|
|
| [reply]
[d/l] |
|
|
|
|
|
|
|
| [reply] |