Ruby `reject!`
accidentallyquadratic.tumblr.com
accidentallyquadratic.tumblr.com
> In my mind, I’d just rather not have a reject! at all, and callers who need to mutate an array in-place can figure out how to do safely with respect to their own use cases.
We ought to have a standard version of the reject! code precisely because it's so difficult to get right. Saying application developers should solve the problem themselves just sounds like some sort of political move: 'sure they may get the edge cases wrong, but then it will be their fault not ours'.
One of the best things about Ruby is that having helper methods for every kind of possible operation frees application developers from re-solving these edge-case problems and allows them to just write their business logic.
> We ought to have a standard version of the reject! code precisely because it's so difficult to get right.
No, it's easy to get right in any specific case. It's iterating over a dang list, it's the first thing you learn how to do as a programmer. It's only hard to get right if you're trying to solve it for every use case with a single interface.
Essentially: you are taking two different algorithms and trying two switch between them behind a single interface. Meaty if-statements behind flags are an indication this is happening. It's cool of you want that but put it in a library and give it a GitHub per.
An example: I don't use a library to merge attributes on objects. I cut and paste one of a few snippets or write from scratch. Sometimes you want to mutate an object, sometimes you want a copy, sometimes you want to shallow copy or keep a reference to the parent. I could write a nasty complicated function that intelligently solved "the problem". But all that does is bundle together a bunch of different solutions to different problems and make it hard for me to understand which one it picked.
Edit 2: I could be persuaded that what I'm saying is just not Rubyish. I'm a JavaScript programmer (after many years of Ruby) so maybe there's some truth in that. I do think that distancing ourselves from the mechanics of list manipulation can be bad for our code quality.
Isn't any correct implementation of any function that retains any only the elements that pass some predicate going to have to do basically the same thing that reject! does, or else be slow (creating a new list instead of mutating in place)?
I guess there's a somewhat simpler implementation that would work for some use cases (those in which order is not important) that just swaps in the last element instead of removing. But if maintaining order is important the complexity is similar.
I think that what would happen if Ruby didn't include reject! is that most programmers would just needlessly create new arrays all the time, since that's easier to write.
*edit: i say never, but if you do cool stuff with referencing array ranges so that you don't copy, but reference the unchanged parts of the previous array then sure, but that's more of a low level feature of the language (eg erlang and clojure both do this i thiiiink?) than something you'd want to implement in a library because it can be suuuuper tricky to get right
Yes, it won't be as fast in modifying. But it will be a lot faster in other operations, so it's a trade off and you chose appropriately for your use case.
Plus, it's a lot easier to read and understand "immutable code".
A version which doesn't allocate a new chunk of memory will always be faster.
The rule of thumb I personally go by is that if you're working in e.g. Ruby or Python it's better to favor immutability over mutability because mem alloc will almost never be the problem.
I say this having worked on a Python (pypy) product where mem alloc WAS the bottleneck in a particular area. So I know it's not always true, but almost always. Probably preaching to the choir here :)
Well, possible things you might want that still fall under the banner of "in-place reject":
- single slice at the end, vs atomic iterations as the article stated
- traversing the list in different directions, or according to priority
- aborting part way through
- any of a million domain concerns
If you rolled your own iteration, you have a platform for handling any of these. If you used a library, even the standard library, you need to start over from scratch, and either build your own iteration anyway, or find another library.
The exception to this is something like Haskell where the abstractions of the abstractions are modelled in the type system, so you never have to start anything over you just bisect your types and reassign responsibilities around the wound.
I'd push-back in code-review anyone who tried to do something not in obvious, idiomatic (read: LINQ) C#.
Oof! reject! is not "iterating over a list," but compacting an array. It's a pretty simple operation that should be available in a standard library. There will be some hairy edge cases around nonlocal exits and accesses to the array itself within the reject block, but it's not too hard to create a standard implementation that properly handles most of the edge cases, and documents the ones that aren't handled.
Roughly, you move elements into place as you go, but don't shift all the higher-index elements down right away. Document that the block can only access elements with greater indices than the current element, and you're good to go.
Rubyish-ness aside, this just seems like a worse solution than a library.
1. You're cluttering your files with code that isn't essential to your business logic (and although you might be able to recognise a particular snippet as in-place-merge vs shallow-copy-merge, anyone new who's reading your code will need to read each snippet as they come across it to understand what high-level operation you're performing).
2. Especially in JS, more copied code equals more parse time (which can be a real killer as a project grows).
3. If your code does have a bug (like being accidentally quadratic), you now have a harder time finding and updating all of the places that use it.
4. You've spent your own time writing, customising, debugging and maintaining these snippets when you could have just written _.extend() and had short, clear, working code that most JS developers already understand the behaviour-of.
I'm not saying never write your own snippet — there will be plenty of times when you need some really specific behaviours or performance characteristics — but the default way to do common data-shuffling operations should be a clearly named function call to a shared library.
2. I don't know if I entirely buy the more code=more parse time being a real reason here if you're willing to pull in the entire underscore library just to get _.extend
3. See response to #1
4. I disagree with this, for the reasons you stated with #2 actually - I really can't stand bringing in one gigantic library for a single piece of functionality. It's the exact reason that jQuery lingers in so many projects when it's really just there to provide a coherent XHR request interface.
I think the general direction of smaller reusable modules that node pushed everyone towards is the best solution.
I think 4. it actually really important — regardless of whether you're using big or small libraries — it doesn't take long before the maintenance cost of any code you write starts to become a drag; any maintenance you can avoid by using open source libraries should be considered an investment in future productivity. Of course, that doesn't apply if the third party code is crap or not suited to your immediate use case.
That said, my experience is that in some cases you still end up with a bunch more code than expected because of internal dependencies, but perhaps that code would've been necessary anyways.
Another good reason is that the Ruby standard library implements many methods, such as `#reject!`, in C instead of pure Ruby, for vastly better performance. You can do that yourself of course, but that sort of defeats the purpose of using Ruby. Try implementing some `Array` iteration methods in pure Ruby with for loops, then benchmark them against the standard equivalent; they'll usually be dozens to hundreds of times slower.
Either implementation will be a poor choice for some use cases (hence the bug reports about both).
If I remember correctly, that should ensure the code is executed even if the block contains a break.
That said, I'd wager Ruby's strange way of handling breaks in blocks passed to functions is the real source of problems here.
However, a bigger problem is concurrent modification: What happens if your reject! predicate has a side effect which modifies the array? Ideally you'd receive a "ConcurrentModificationException" or the like.
iirc, Ruby's array doesn't expose the distinction between length and capacity, but internally it may decide to amortize the cost of such copies. For example, if reject only removes a small % of elements, it may choose not to shrink capacity.
(That's assuming you copy at all, instead of simply updating the reference.)
You have an "ensure" block (finally) protecting the code which handles the cases where dirty is true (moving all the remaining elements after the current max). Then you truncate the array.
It appears order is guaranteed to be maintained but it's not specified :)
Here's an example of how you'd manage the contention yourself:
my_array = [1, 2, 3]
my_array_lock = Mutex.new
Thread.new do
my_array_lock.synchronize do
my_array.reject! { |x| x % 2 == 0 }
end
end
Thread.new do
my_array_lock.synchronize do
my_array.push(4)
end
end
Thread.new do
my_array_lock.synchronize do
# Because we've serialised our operations on the array, there's no chance
# that we read the elements in an incorrect order
my_array.each do |x|
puts x
end
end
end ary = ary.reject {|x| x > 2}
auto first = vec.begin();
auto last = vec.end();
last = std::copy_if(first, last, first,
[](int x) { return x > 2; });
auto size = std::distance(first, last);
vec.resize(size);
(0) A collection of elements to be processed (given by an InputIterator range).
(1) A collection of already processed elements (given by an OutputIterator range).
When the algorithm starts running, (1) is empty. With each iteration of the algorithm's loop, (0) becomes smaller and (1) becomes larger [maybe]. When the algorithm halts, (0) is empty.
Notice that, while both collections share the same underlying buffer, each has its own size. So there is no need to perform a `resize()` step at the end.
const auto last{ std::copy_if(vec.cbegin(), vec.cend(), vec.begin(),
[](const auto x) { return x > 2; }) };
vec.resize(last - vec.cbegin());
const auto last{ std::remove_if(vec.cbegin(), vec.cend(), vec.begin(),
[](const auto x) { return x <= 2; }) };
vec.resize(last - vec.cbegin());In the unlikely event some future reader is copy-pasting these snippets, here's the corrected version:
const auto last{ std::remove_if(vec.begin(), vec.end(),
[](const auto x) { return x <= 2; }) };
vec.resize(last - vec.cbegin());if the ! for mutable operations weren't there, people would often be very surprised by the behaviour of reverse, sort, etc because in languages like ruby (python, etc too) they expect things to be fairly safe by default.
there are plenty of cases when mutating an object is far preferable to doing the same in an immutable way for both speed, and algorithmic complexity.
The standard library has lots of side-effecting methods which don't come with ! suffix. On the same Array type that has reject!, there's delete, pop, push, among others. Only some of them have pure equivalents - e.g. last for pop.
Push and pop don't have it because they mutate the array like they do in almost every non-hardcore-functional language, so that's the expected behavior.
Things like map! and reject! have them because there _is_ another version, and _this_ one might bite you. It has nothing to do with side-effects or immutability per se, that's just the most common case.
1) There's another, similar, method without the suffix.
2) The ! version has some side effect (usually mutating something or throwing an exception) that the non-! doesn't, which doesn't mean that the non-! has no side effects (`ApplicationRecord#save` and `#save!` both have side effects, but only `#save!` throws on failure).
—
Is there any idiomatic Ruby library where ! methods don't follow this convention?
Mutation per se isn't harmful — if our ape brains were better able to think like a digital computer, we'd never have created functional programming (or even procedural, but I digress). What's harmful is our ape-brain habit to use mutation incorrectly (i.e. a buggy implementation). So a very large part of the problem can be solved with a (standard) library that provides (in theory) correct, performant implementations of common mutation patterns (such as Ruby's `Array#reject!`).
(I realize you were taking the devil's advocate; I sort of am too, since I rarely use mutating methods when I write Ruby).
Rails, especially rails 5 with API-only mode is particularly great as well.
After years working with Ruby, I felt that "bang" methods should only be used for methods which mutate the receiver. Many methods which do do so do not have a "!" at the end.
To that end I created a little library called "Bang All The Things" :) https://github.com/pmarreck/ruby-snippets/blob/master/bang_a...
I'm convinced that this simplification helps prevent bugs, at the minor cost of changing some conventions possibly borrowed from other languages.
I have since (mostly) moved on to Elixir which does not have the "mutability problem" at all.
I mentioned this upthread too, but it's a bit broader than that. Consider http://api.rubyonrails.org/classes/ActiveRecord/FinderMethod... vs http://api.rubyonrails.org/classes/ActiveRecord/FinderMethod... for example. The ! version raises an exception rather than return nil.
`delete` always gets me.
raises hand
Imagine you have a React SPA where users can select a number of items for which they want more information (I can't give more details at this moment). Said information has to be fetched from the server upon selection.
I recently discovered that the website would fetch all selected items whenever a new item was selected, including previously selected items, regardless of whether it had already been fetched. So if I start with one selection and build up to n, that is 1 + 2 + .. + n-1 + n = (n²+n)/2[0]. Whoops.
To make it worse, I had also somehow had managed to set up my components in such a way that for each fetch being received, React would remount (that's right, re-mount) all of the selected items. Don't ask me how. I'll just say have only been doing web stuff since last year and leave it at that.
If we assume a user clicks fast enough to select every item before the fetches are received, that would be the previous equation multiplied by n selections, so.. (n³+n²)/2. Yikes!
So yeah... that was stupidly slow. Here's what I did to fix it; obvious but worth spelling out:
- only fetch what hasn't been/isn't being fetched
- only re-render the component that was updated
- don't immediately do the above when the user
selects an item; let them make a selection first,
then click a "show information" button, then
fetch all the needed information in a *single* fetch
and render it in a *single* update to the components.
Even after discovering they have to call the container's erase method using the result of remove and an iterator to the end of the container[2] they'd probably just decide that remove just has a terrible design. It takes experience and some data structures knowledge to realize why it is designed the way it is.
The design of remove means every element that remains are only be shifted (in the case of an array/vector), at most, one time. The naive approach results in the problem described in the article where you are constantly shifting the elements forward as you progress through the container.
The usability of remove is still a problem (the concept shouldn't need a wikipedia page explaining it) but the way it was done was done for good reasons (within the design decisions of STL at least). It's probably fixed in the C++ ranges proposal but I haven't looked.
D's standard algorithm library remove[3] (which is very much based on Stepanov's STL too) goes one performance step further and lets you specify the swap strategy so that if stability isn't a requirement the number of shifts required is the absolute minimum possible (essentially moving elements from the end of the range into spots freed up by the items being removed).
1. Slightly more experienced users would quickly notice that it can't remove the value, it has no reference to the container to change its length.
2. So common and unintuitive it gets its own wikipedia page: https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom
3. http://dlang.org/phobos/std_algorithm_mutation.html#.remove
Cool thing is that it is not C++, where remove is hardcore stl magic, and I can just iterate over elements' memory and remove them in sliding ranges, so multi-remove problem simply doesn't exist. Idk why c++ overengineers everything. We abstract a generic vector away from our convenience only to to store items in regular array, because it is the only fast solution for generic cases.
Haskell's Data.List doesn't seem to even have a remove/reject. Clojure's remove is simply a complement of filter.
Rubocop, on the other hand against what I've just said, will tell you in almost every case that you might use Unless, or in agreement with what I think it is that You are saying here, the preferred idiom is to not use the inverse, and you should only say "unless" when what you meant to say is unambiguously !if.
IOW sometimes you really mean reject
I've been using Ruby (in the context of Rails apps) for almost six months now, after a decade or so in mostly Python. Ruby is just "messy" in my opinion, and having the separate methods Array#select and Array#reject is just a single symptom of that.
Another example is that something in Rails adds Array#fourth. I can't imagine a circumstance where using my_array.fourth is clearer than my_array[3].
But I'm not totally sure about that, after reading the Rubydoc for Array[1], only reject! has the warning about mutating the array every time the block is called, select! does not have any such warning. You might be right.
[1]: https://ruby-doc.org/core-2.2.0/Array.html#method-i-reject-2...
I like my safeties in languages though.
In ascending order of complexity
http://theerlangelist.blogspot.com/2013/05/working-with-immu...
http://concurrencyfreaks.blogspot.com/2013/10/immutable-data...
http://debasishg.blogspot.com/2010/05/grokking-functional-da...
In the case of Ruby, it's a language build on mutability so let's use mutable data. There are already plenty of languages with immutable data to use if we want to.
No surprises for users here, which is why that bug lasted for about 4 years with noone caring.
If the documentation stated it was O(n), or benchmarks tested it was fast, then it being slow would become a bug.
As is, it's just what it is.
That algorithm, in this case, is a quadratic one.
Nitpick: not sure it's nonsensical. Plug g(x) = 0 into the usual definition, and you get |f(x)| ≤ k⋅0 for some k in R, which reduces to f(x) = 0. Which is not satisfiable by any nontrivial algorithm, so not very useful, but not nonsensical.
There are cases where accidental quadratic complexity would definitively be considered a bug. If a fleet of GitHub servers were burning cycles due to a quadratic reject!, I'm pretty sure the engineers would classify the misbehavior as such.
A peeve I have with Ruby is that methods in the standard library don't have defined big-O complexities. If they did, I don't think reject! would have been specified to be O(n²), and so it would be a bug.
Then in reviews its explicit when someone's doing something dumb (specifying high complexity for new algos) at compile time if a lower-complexity function calls a higher complexity one with the same sized input, or in CI when an algorithm isn't within the complexity it claims to be (experimentally)
You'd also likely want to somehow encode space complexity as well, otherwise silly things like "precompute every possible result and put it in a giant lookup table" will register as "O(1)".
Here the algorithm is quadratic but will, theoretically, always complete. Thus there is no bug, but a performance problem. I think that a bug is a mistake in a programme that causes erroneous behaviour.
Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed?
I'd rather call this a mistake as long as the output from the function is as expected. I'm not saying that it's a negligible mistake to use a quadratic algo where there is a linear one though. Just that I doubt it is fundamentally a bug.
This only makes sense if you completely ignore context, which doesn't make any sense at all. The point/"bug"/mistake here is using a quadratic algorithm when it isn't necessary, not just the fact that the algorithm is quadratic. If something can be solved in O(1) time, it's a mistake to use an O(n) algorithm, and similarly, if something can be solved in O(2^(n!)) time, it's a mistake to use a O(9999^(n!)) algorithm (assuming constant factors are of similar orders of magnitude etc, as they are in the OP).
Though, this behaviour was changed after all which leaves me wondering how much Ruby people care about backward compatibility.