14 ms·
Ruby `reject!`
- drodgers 10y agoI love this blog, but I'm not sure that I agree with this: > 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.
- erikpukinskis 10y agoEdit: I know this sounds like I am trying to dismiss the problem. That's not my point. I'm trying to say the problem is compounded by the choice to bundle the solutions to several different problems. If people have criticisms I would love to read a reply. </Edit> > 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.
- pcwalton 10y ago> 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. 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.
- STRML 10y agoIn this case, perhaps mutability is the real problem. Array#filter is quite fast in JS and never mutates the array.
- rickycook 10y agoit might be quite fast, but it's never going to be as fast as a mutable version of the same thing. there are plenty of cases where you have many (millions?) of elements and want to remove only a few. in that case, copying an array of many elements for the sake of immutability is quite wasteful *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
- elmigranto 10y agoNo one does immutability with copying, that would be a joke. There is also nothing tricky about not copying full lists on append at userland lib, just more advanced data structures. 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".
- leereeves 10y agoRather than an edge case, I'd call this a case of trying to satisfy two incompatible goals: fast and internally consistent after each deletion. Either implementation will be a poor choice for some use cases (hence the bug reports about both).
- xg15 10y agoCouldn't you easily satisfy both goals by moving the "copy all elements not marked for deletion into a new array" code into a "finally" clause? 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.
- phamilton 10y ago`..into a new array` is precisely what `reject` does. We're talking about `reject!` which modifies the existing array.
- brandonbloom 10y agoxg15's comment still makes sense if you replace "copy all ..." with "slide the remaining elements down by the number of removed elements" to match the mutative behavior. 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.
- leereeves 10y agoThat would still require O(n) space (to store the list of elements to keep or remove) so why not simply use the regular `reject` ?
- brandonbloom 10y agoBecause you're saving the O(N) time copy... 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.
- catnaroek 10y agoThe problem with `reject!` is that it's too ad-hoc: the more fundamental operation is to filter the elements of a stream. The input stream could be generated from any data structure (not necessarily an array), and the output stream could similarly be redirected into any data structure (not necessarily an array, let alone physically the same array).
- marvy 10y agoNot clear what you're suggesting here. Can you implement reject! using your propose more general interface? If so, how? Is it more efficient than just creating a copy and then overwriting the original, like this? ary = ary.reject {|x| x > 2} If there's a language agnostic insight to be had here, I'd love to see it. Actually, even if it's language dependent, I'd like to see it.
- catnaroek 10y agoHave something akin to C++'s `std::copy_if`. 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); (Ironically, in C++ this doesn't always work, because not all types are copyable or movable. But Ruby has no such problems.)
- marvy 10y agoOkay, but with copy_if, you need an extra resize step at the end, which is annoying in C++ and that Ruby users currently have the luxury of avoiding. And this seems fundamental. The reason that copy_if can't call resize for you is that it assumes nothing about the underlying container; indeed there may not even be one. You say this is a good thing, and there are certainly advantages, but it doesn't seem to solve this problem, unless I'm missing something. Or maybe you're saying that the need to call resize is worth it, since you get a more general interface for the price?
- catnaroek 10y ago
- tomphoolery 10y agoI think the argument here is to embrace the immutability of arrays in Ruby. The reason why this is called `reject!` rather than `reject` is because the designers of Ruby wanted you to favor returning new objects rather than mutating objects in place. Sure, you might need to do it from time-to-time and I'm really happy we have methods that enable such behavior, but this brings to mind the old adage "just because you can, doesn't mean you should". The author might have been trying to say in that quote that app developers should find other ways of solving whatever problem they have without resorting to mutating objects in place. I don't think we should go as far as to not include such methods in Ruby if everyone finds them useful from time-to-time, but I also think we should be staying away from mutating objects in place, rather than returning new versions of said objects and using that.
- rickycook 10y agoi wouldn't have said that the ! is there because the designers want you to favour immutable rather than mutable operations. it's there for the same reason confirmations are there for deleting files; they want to you be sure you know what you're doing, because the immutable operation is always safe while the mutable operation is sometimes unsafe. 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.
- steveklabnik 10y agoSmall Ruby conventions note: ! means "dangerous", not "mutable." Yeah, sometimes the kind of danger you're looking at is mutability, but it's a bit broader than that.
- tamal 10y agoTo expand, ! means it's a more dangerous version of the method without the ![0]. A method could be dangerous, but not have a safer counterpart, and thus be named without a !. [0] https://www.ruby-forum.com/topic/176830#773946 https://www.ruby-forum.com/topic/176830#773946
- seanp2k2 10y agoYeah, I like ruby (and especially rails) because it has stuff like this. I also like that most languages have sort() as part of the stdlib. If you need something specific, sometimes they come with more than one sort, or it would be easy enough to write yourself, but I appreciate and expect a high-level language to include the basics so I don't need to keep data structures and algorithms books within reach. Rails, especially rails 5 with API-only mode is particularly great as well.
- gkya 10y agoI find it weird that the case is called a "bug" multiple times. Sure, if its o(n^2), that's a problem, but if the code works correctly at the end, it's not a bug.
- ouid 10y agoYes it is? Asymptotic complexity is a well defined property of an algorithm. It is an output, and it doesn't match the expected output.
- jeffdavis 10y ago"reject!" is not an algorithm. It is a semantic element of the ruby language, which is implemented using an algorithm. That algorithm, in this case, is a quadratic one.
- ouid 10y agoNo, because a linear implementation of bsearch is clearly a bug.
- TheDong 10y agoIt's ruby, so the expected complexity of any line of code is "it might complete sometime in my lifetime". 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.
- aetherson 10y agoWell, probably the reason it lasted for about 4 years with no one caring is because .reject! is a fairly rarely used function.
- flukus 10y agoCan you point out where in the function definition this was defined?
- ouid 10y agoI think that perhaps the most interesting part of this article is that it comes from a blog called 'accidentallyquadratic' with more than one entry.
- thunderbong 10y agoYes! And posts dealing with quadratic behavior in languages!
- jameshart 10y agoI remember coming across it before when the left-pad incident happened, and marvelling at the fact there were already many entries there then. The problem is now, whenever a new entry on this blog gets linked, I find myself compelled to go back and read all the entries in it again. I can't help thinking that over time, that process is going to become prohibitively slow.
- emfree 10y agoOne of the older posts eloquently discusses why "accidentally quadratic" behavior is both so recurring and so insidious: http://accidentallyquadratic.tumblr.com/post/113840433022/why-accidentally-quadratic http://accidentallyquadratic.tumblr.com/post/113840433022/wh...
- skywhopper 10y agoI can't agree with the conclusion. Sure complexity is complex, but the solution here would seem to be better performance analysis of the standard library rather than blindly avoiding risk. How do you know where to stop? All built in block-accepting methods for enumerator types would seem to be equally risky in this analysis.
- rocqua 10y agoWithout much knowledge at all, I'd agree with the conclusion that "block-accepting methods for enumerator types would seem to be equally risky". It sounds to me like having non-pure functions that can terminate at any point. And that sounds like asking for trouble in your code. I like my safeties in languages though.
- tzwm 10y agoSo what is the right way to do the same thing? Use `select` and get new array included elements we want to keep instead of using `reject!`?
- pmontra 10y agoThat's what languages with immutable data structures do. Internally they implement simple data structures (lists, arrays) with more complex ones not to get a performance hit. For example, they don't want to copy every byte every time they add or remove from a list. In ascending order of complexity http://theerlangelist.blogspot.com/2013/05/working-with-immutable-data.html http://theerlangelist.blogspot.com/2013/05/working-with-immu... http://concurrencyfreaks.blogspot.com/2013/10/immutable-data-structures-are-not-as.html http://concurrencyfreaks.blogspot.com/2013/10/immutable-data... http://debasishg.blogspot.com/2010/05/grokking-functional-data-structures.html 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.
- danaliv 10y agoThere's a non-mutating version of `reject!` called `reject`. (Likewise there's a mutating version of `select` called `select!`.)
- deleted 10y ago[deleted]
- Dirlewanger 10y agoAvoiding this should be as simple as using the inverse, `select!`, and then flipping whatever the check is in the block, right?
- deleted 10y ago[deleted]
- yebyen 10y agoI think that only half avoids it, or shifts the wrong side of the big O to opposite of wherever it is now. select! also mutates in place. 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-21 https://ruby-doc.org/core-2.2.0/Array.html#method-i-reject-2...
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- eco 10y agoOne of the more confusing parts of the C++ standard library algorithms is remove/remove_if. A new user would think calling remove(v.begin(), v.end(), value_to_remove) would result in the value being removed from the container[1]. Instead, they'll find that all it did was shift around the ordering of the vector and leave the elements you wanted removed in place at the end (if you read the linked article you can already see where this is going) which is a very unintuitive result. They might look up the function signature and notice it returns an iterator which is also surprising. 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 https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom 3. http://dlang.org/phobos/std_algorithm_mutation.html#.remove http://dlang.org/phobos/std_algorithm_mutation.html#.remove
- wuch 10y agoThis is one of those things that makes perfect sense after you actually tried to implement it, but not necessarily beforehand. I think this happens a lot with C++ that design decision are quite well though through, but it is hard to appreciate this without taking time to understand the rationale.
- 10y ago
- throwaway1579 10y agoCan't wait for the entry on quicksort.
- pmarreck 10y agoShameless plug: 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_all_the_things.rb 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.
- steveklabnik 10y ago> I felt that "bang" methods should only be used for methods which mutate the receiver. I mentioned this upthread too, but it's a bit broader than that. Consider http://api.rubyonrails.org/classes/ActiveRecord/FinderMethods.html#method-i-first http://api.rubyonrails.org/classes/ActiveRecord/FinderMethod... vs http://api.rubyonrails.org/classes/ActiveRecord/FinderMethods.html#method-i-first-21 http://api.rubyonrails.org/classes/ActiveRecord/FinderMethod... for example. The ! version raises an exception rather than return nil.
- hawkice 10y agoI actually like the ActiveRecord convention more than destructive-to-receiver -- it was even adopted by the elixir community (which makes even more sense than ruby, as there really aren't destructive updates in elixir).
- pmarreck 10y agoGood points. It would be great if there were two separately available suffixes, one to signify receiver mutation and one to signify raising vs nil. I certainly think Elixir went the right way here on the latter front (as it doesn't have to worry about receiver mutation).
- vinhboy 10y agoAgreed. For whatever reason, my mind really gravitate towards the idea of bang being a mutator. That should have been a standard. `delete` always gets me.
- sriharis 10y agoWhy is `reject!` even a separate, and different implementation than `select!`? Perf reasons? Haskell's Data.List doesn't seem to even have a remove/reject. Clojure's remove is simply a complement of filter.
- yebyen 10y agoSame reason ruby has both "if" and "Unless", or capybara has .to_not as well as .not_to... there are times when the inverse expression is just more natural and less confusing. 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
- dopamean 10y agoI don't think the commenter is asking why the method exists. But more why is it that the bug exists with reject! and not select!. Why the underlying implementations of those two very similar methods different?
- CGamesPlay 10y agoThey are identical (inverted) implementations as of ruby 2.3, so I think it was just an oversight.
- LyndsySimon 10y ago
- jerianasmith 10y agoQuite a comprehensive Post ! What makes Ruby block an essential feature of language is it's power and elegance.
- pjfitzgibbons 10y agoI think worth clarifying, the fix on svn r49255 is in git tag v2_3_1, so if you're on ~2.3.1 Then you're back to linear #reject.