5 ms·
> Going by their first example, the fact that I couldn't write list.delete(value) without realizing it involves a linear search is considered one of the benefit
by arp242 6y ago
> Going by their first example, the fact that I couldn't write list.delete(value) without realizing it involves a linear search is considered one of the benefits of Go.
I think this is mostly okay. Most experienced programmers will realize this is a linear search and that it may be slow on large arrays. And turns out that in the overwhelming majority of the cases that's just fine!
For other cases it's not-so-fine, but the mere presence of "list.delete" doesn't really stand in the way of implementing another, more efficient, solution.
Overall, I certainly think it's better than implementing the same linear searches all the time yourself!
- deleted 6y ago[deleted]
- kaba0 6y agoI’m sorry for the “gatekeeping”, but do you really want to work together with someone that doesn’t know the language’s standard library or won’t even look at the documentation? And instead it would be positive that he/she writes the very implementation of something?
- jholloway7 6y agoThis problem transcends documentation of any given language's standard library. list.delete(value) in any programming language is a degenerate without an ordering or hash built-in to the underlying data structure. If you ever need to delete based on value, it's a smell that a list is the wrong data structure. I'm sure there are cases in constrained environments where a linear search is heuristically okay, but generally in application development list.delete(value) is a hint that you're using the wrong data structure.
- mhaymo 6y agoGood point. I guess the reason the author finds removing from lists to be relevant is because there is no Set structure in the Go standard library. They should use a `map[t]bool`, but that is non-obvious to many programmers.
- dullcrisp 6y agoMy Google search suggests that maps in Go aren’t ordered. If so this doesn’t work in place of an array.
- vlowther 6y ago`map[t]struct{}` saves you a few bytes per entry. Just use the `_,found := foo[key]` form of lookup
- nitrix 6y agomap[t]struct{} so that the values don't require any space.
- simiones 6y agoUnfortunately, map[t]bool (or map[t]struct{}) only works for special structs that happen to have equality defined for them. It's not a general purpose solution, it's just a hack.
- citrin_ru 6y ago> Most experienced programmers will realize this is a linear search and that it may be slow on large arrays. Experienced programmer can think that values in a list with such operation are indexed by a hash and delete by value is O(1) unless there is a big warning in documentation. Novice programmer probably haven’t seen such combination of an array and a hash table and will assume O(N) as taught in a college.
- wizzwizz4 6y agoExperienced programmers will know that such a thing is possible, but I've never seen any (non-JavaScript, non-PHP) language where primitive arrays involve a hash table.
- Gaelan 6y agoAnd even in JS and PHP (and Lua) where arrays and hash tables are technically the same data structure, a hash table used as an array isn't actually indexed on elements, just numbers, so you don't get O(1) search.
- thezilch 6y agoExperienced programmers, if perf matters to their project, should think about their data structures, memory size, and access patterns. It's not clear why an experienced programmer would think an array defaults to wasting memory on a hash table. Why use an array, if they need lots of values and to delete them at random?
- shakow 6y agoExperienced programmer will know whether the vanilla array of the language they use feature this kind of convoluted data structure. Which, for virtually all languages, is “obviously not”.
- alkonaut 6y agoAnd it's not exactly gatekeeping to think that anyone who uses a method on any data structure on their platform should know the (rough) complexity of it (At least in the family constant, linear, or better/worse than linear). Removing a value from an array-backed list that isn't at the end is usually not a good idea. My main problem with having "remove items by value" in standard library apis is that it assumes a notion of value equality. Having that notion inserted at the very "bottom" (Like Equals/GetHashCode in .NET for example) is a mistake that has caused an infinite amount of tears. I much prefer this situation where the user must provide his own implementation and think about equality. It's boilerplate, but the boilerplate is useful here.
- lstamour 6y ago> I much prefer this situation where the user must provide his own implementation and think about equality. But that doesn’t scale beyond the first user. Every subsequent developer now needs to read implementations to understand what the code does thanks to a lack of standardization for these functions. Consider if there was a smaller standard library with fewer interfaces and conventions, it would become a lot harder to understand a number of concepts in Go, by design. That’s fine, but conventions are what made Ruby on Rails projects so successful that they scaled up to being the monolith monstrosities most of us with startup experience ended up knowing them to be. Note that I’m suggesting something akin to C++’s standard library where algorithms are already written for you to use and compose with. Yes, the drawbacks are a slower compile time, and some conventions like constexpr can really complicate things, but… I can’t say that a larger standard library or a larger set of conventions would make Go harder to use assuming the implementations hide a sufficient amount of complexity to outweigh the overhead of learning of them in the first place. What functions provide more value than the overhead required to learn them? Delete is one such function, mutable immutable data structures generally are likely another. Yes, the documentation needs to specify big O complexity, but it can still be easy to read. For example: https://immutable-js.github.io/immutable-js/docs/#/List https://immutable-js.github.io/immutable-js/docs/#/List The only way to get easier than that would be to use the same syntax for immutable operations as mutable ones: https://immerjs.github.io/immer/docs/introduction https://immerjs.github.io/immer/docs/introduction I recognize that the Go community finds the built-in standard library restrictive now, but that’s no reason not to support a versioned standard library that ships separately but contains common functionality. I can only point to TypeScript for how such a system might work, given the large community project that exists to provide and publish types for that language, without actually publishing them with the language or compiler itself, excluding browser dom etc.