A little more light-hearted but the same style to learn Ruby with Entirely Too Many Fizz Buzzes. See https://yukimotopress.github.io/fizzbuzz
Learn Rust with entirely too many linked lists (2019)
81–90 of 179 posts
Re: Learn Rust with entirely too many linked lists (2019)
#82I went through this a few years ago for fun. It's a great guided tour of the compiler errors when working with complex memory safety needs. The most important thing to know about these is that you would almost certainly never do these in a real project: lists are in `std` but even then the vast majority of cases should use `Vec`.
I am learning Rust due to it's memory safety features and comments like this rub me the wrong way for some reason -- they give me an uneasy feeling that I will run into unexpected limitations in the language because these corners are not exercised enough. Because people who know the language are saying that the kind of data-structures that I deal with day in and out in my day-to-day work are not the "preferred" thing…
Don't worry. The language has lots of support for the style you wish to work in.
As for the specific data structures, I recommend setting aside your knowledge of their utility and consider carefully why they are being criticized. Then run some experiments to convince yourself of what is true. If you come to the conclusion that the criticisms make sense, then you can proceed with the knowledge that the people in question have thought about the issue and came to good decisions. This should inspire hope that they have thought about other issues as well and may have valuable insights.
For the record, I concluded many years ago that some variant on arrays/vectors/whatever outperforms linked lists in most situations by a lot. (There are times when arrays/vectors/whatever can't work. But they are less common than most imagine.) And changes in hardware have made that more true over time. Trees, on the other hand, have a flexibility that lends itself to many problems that it is hard to find other structures for many use cases. But even so if performance is critical, it is worth jumping through a lot of hoops to make sure that all of the pointers that make up a tree are physically close together in memory to improve the efficiency of your caches.
Re: Learn Rust with entirely too many linked lists (2019)
#83Earlier quoted context omitted.
Sure, but algorithms that explicitly need a linked structure for performance are very few compared to algorithms that have the same or better asymptotic with a hash and a vector or for which the input sizes are such that the large constants pointer chasing causes don't make up for worse asymptotics.
If the algorithm calls for a balancing tree, you'd end up re-implementing it across of bunch of (linked) hash tables or over an array treated like a heap. Explicitly, or if one does not know what they are doing, implicitly. In either case you would have no performance advantage.
If you know what you are doing, you may well realize a performance advantage.
For example LevelDB (which is conceptually based on Google BigTable's design) looks a lot like a balancing tree in its access patterns, but is a lot faster than a variety of alternatives. And it is faster in part because sequential data is stored sequentially in order instead of using a data structure that results in random access patterns.
And no. It doesn't use linked lists.
Re: Learn Rust with entirely too many linked lists (2019)
#84>You're doing some awesome lock-free concurrent thing. I can confirm lists are pretty rarely used. The four times I've used a linked list in 10 years of professional programming were: -quick&dirty hashmap in C -threadsafe queue -keeping track of a set of objects that can't be copied ( threads) -LRU cache In C++ at least, the nice thing about a list is you can push/pop in the front/back without a reallocattion or inva…
Linked lists are used a lot in game programming where the worst-case behaviour of std::vector and similar structures is undesirable. Linked lists may be slow for a variety of reasons but they're simple and predictable which is very nice when you're trying not to miss the 16.67ms per-frame window.
Re: Learn Rust with entirely too many linked lists (2019)
#85>You're doing some awesome lock-free concurrent thing. I can confirm lists are pretty rarely used. The four times I've used a linked list in 10 years of professional programming were: -quick&dirty hashmap in C -threadsafe queue -keeping track of a set of objects that can't be copied ( threads) -LRU cache In C++ at least, the nice thing about a list is you can push/pop in the front/back without a reallocattion or inva…
I've used linked lists a little more because I mostly do C rather than C++. Sometimes I end up using it as a quick-and-dirty vector when I don't want to bother writing something or using a library, though I typically use some kind of block/arena allocator vs. just malloc.
Re: Learn Rust with entirely too many linked lists (2019)
#86Earlier quoted context omitted.
I am learning Rust due to it's memory safety features and comments like this rub me the wrong way for some reason -- they give me an uneasy feeling that I will run into unexpected limitations in the language because these corners are not exercised enough. Because people who know the language are saying that the kind of data-structures that I deal with day in and out in my day-to-day work are not the "preferred" thing…
Do you currently use C? C++ perhaps? I mean basically no other language that currently comes to mind fiddles so much with the basics. In Rust, just as in Java, people write highly optimized safe and fast data structures and others build upon that. In C/C++ it seems every project reinvents the wheel to a large degree. Or am I mistaken?
>In Rust, just as in Java, people write highly optimized safe and fast data structures and others build upon that.
I'm currently taking a class on API design with Josh Bloch (Java Collections, Effective Java, etc.), who pointed out that this wasn't the case until the late 90s or so - he pulled out an example of a KWIC system [1] described in a paper [2] from 1971:
Parnas 1971: This is a small system [that] could be produced by a good programmer within a week or two.
And then Josh proceeded to show his implementation of the same system, which he had written in It's really cool that these standard data structure implementations exist and are so accessible, making people orders of magnitude faster than before.
[1] https://en.wikipedia.org/wiki/Key_Word_in_Context [2] https://prl.ccs.neu.edu/img/p-tr-1971.pdf
Re: Learn Rust with entirely too many linked lists (2019)
#87I'll try this at some point. My first couple forays into Rust made me miss Java and C.
Re: Learn Rust with entirely too many linked lists (2019)
#88Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that.
If you have safe backpointers, most tree-type data structures with backpointers can be constructed. A nice feature to have.
Re: Learn Rust with entirely too many linked lists (2019)
#89Re: Learn Rust with entirely too many linked lists (2019)
#90Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that. If you have safe b…
As a non-Ruster, any particular reason they didn't include this? A lot of the code I've done over the years involve graphs, which have a lot of circular pointer and/or backpointers. I find it kinda weird they'd make such a common thing a PITA in a new language.