Re^4: [OT:] Is this Curriculum right?
by LanX (Saint) on Nov 26, 2021 at 21:36 UTC
|
> Actually, linked lists have recently become completely unimportant!
For how long?
Things which were relevant in the 90s became unimportant because of hardware a dozen years later to reappear as relevant after the same time span again.
Example:
- Multiplication on the Motorola 68000 was so slow (~74 cycles IIRC) that Mandelbrot sets were best implemented by precalculating a big lookup table in RAM (~8 cycles)
- Later using lookup tables became obsolete by the speed difference between CPU calculations compared to RAM access.
- Later caches became so big that big tables could fit again easily
Lessons:
- Efficiency of algorithms are effected by hardware
- You can't always predict how hardware evolves.
All this doesn't justify not to study linked lists:
- they can be used in many contexts
- with many advantages
- are easily implemented (see LISP)
- and performance is not always an issue.
Now what exactly do you mean with a vector?
If you mean something with equidistant entries, how would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?
| [reply] [Watch: Dir/Any] |
|
Sorry LanX, I confess I was indulging in the traditional Aussie pastime of
stirring
when I claimed that linked lists have become completely unimportant. :)
You've made some excellent valid points in defence of linked lists.
To answer your last question more seriously:
How would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?
I'd try using the standard library:
std::vector<std::string>
... hoping/trusting/assuming that this common case has already been optimized ...
and googling indicates that most implementations of the C++ standard library do in fact use some form of
Short/Small String Optimization (SSO)
so that smallish strings are not stored on the heap, vastly improving locality of reference:
A std::string typically stores the string as a pointer to the free store ("the heap"),
which gives similar performance characteristics as if you were to call new char [size].
This prevents a stack overflow for very large strings, but it can be slower, especially with copy operations.
As an optimization, many implementations of std::string create a small automatic array, something like char [20].
If you have a string that is 20 characters or smaller (given this example, the actual size varies), it stores it directly in that array.
This avoids the need to call new at all, which speeds things up a bit...
If I get time later, I may try to do some sort of benchmark of your interesting use case in both Perl and C++.
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
v<-c(1:3)
typeof(v)
length(v)
min(v)
max(v)
median(v)
mean(v)
append(v, 4)
# shuffle(v)
# sort (v)
This yields in an interactive R session:
[1] "integer"
[1] 3
[1] 1
[1] 3
[1] 2
[1] 2
[1] 1 2 3 4
Now the kids are forced to write down such stuff in German Pseudocode - with Umlauts. As we are in Germany. No kidding. Plus some UML diagrams. Just to come back to the roots. Or the original question. Now you can guess the next step? Best regards, Karl.
Regards, Karl
«The Crux of the Biscuit is the Apostrophe»
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
| [reply] [Watch: Dir/Any] [d/l] |
|
> Now the kids are forced to write down such stuff in German Pseudocode - with Umlauts.
That's the classical way to check examinations and written homework, it's not practical to have a whole class sitting in front of hardware.
Pseudocode is good to demonstrate the algorithmic understanding while not worrying about syntax errors.
The other extreme is googled "homework" code.
This might be passing passing the syntax check and is somehow producing the required result because of a lot of try and error.
But will often not demonstrate any understanding.
| [reply] [Watch: Dir/Any] |
|
|
|
mische(victor)
sortiere(victor)
Now describe what a Übersetzer and a Bindelader is. In German as we are in Germany. You got one minute as we are in a hurry 🤪 Then write a class StandardChorobaBibliotkekDoppeltVerketteteListe. Don‘t google. Don’t read any man page. As real programmers never make it so. You got 5 minutes. Else you are durchgefallen.
«The Crux of the Biscuit is the Apostrophe»
| [reply] [Watch: Dir/Any] [d/l] [select] |
Re^4: [OT:] Is this Curriculum right?
by Marshall (Canon) on Nov 25, 2021 at 04:38 UTC
|
I think that Stroustrup's concept as referenced, is completely out of context. Searching a "short" array or traversing a "short" linked list sequentially will always be relevant! A vector to a short linked list (like a hash table) is very efficient.
| [reply] [Watch: Dir/Any] |
|
Sorry, I don't understand the point you are trying to make.
Are you suggesting that C++ vector is faster than linked list only for "small" containers?
Note that Stroustrup measured up to half a million nodes, as confirmed in
this talk by Herb Sutter (two years later).
Herb likewise exhorts C++ programmers to prefer vector to linked list.
Update: see also.
As a journeyman C++ programmer, I greatly admire both Bjarne Stroustrup and Herb Sutter
for their many contributions to C++ over so many years, especially their work on language standardisation.
When they both exhort you to use std::vector
(and std::map) as your default containers, I pay attention.
... which BTW has a nice synergy with Perl. At least, I've always enjoyed using Perl's
analogous default containers (built-in arrays and hashes) ...
and never felt the urge to write my own linked list class in Perl. :)
| [reply] [Watch: Dir/Any] |
|
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] [Watch: Dir/Any] |
|
|
|
|
|
| [reply] [Watch: Dir/Any] |
|
|
|
|
|