Replace std:find_if in 80% of the cases
sandordargo.com
sandordargo.com
> This means that the Pareto principle applies here too. In 80% of the cases, std::find_if should not have been used.
I don't think this is the pareto principle. Its a rule of probabilities, i.e 1-X.
When the percentage sign's
89 minus nine
That's ParetoBut if having linear complexity is fine, std::find_if/any_of/none_of/all_of/etc. are of course fine and you should prefer the version that's most expressive.
The whole point of this is to find every element in the list which matches the lambda. Which is why it returns an iterator: you're supposed to use that value, increment it, then call std::find_if again with it as the first parameter.
Granted, the documentation is failing here, since it doesn't provide an example of this use case.
for(auto i = begin(v), e = end(v); find_if(i, e, lambda_func) != e; ++i) {
cout << "Found a match: " << i
}
If the STL contained something whose "whole point" was "to find every element in the list" which fulfilled the predicate, it would be an iterator adaptor, like Python 2's `itertools.ifilter`, Python 3's `filter`, Boost's `filter_adaptor`, or C++20's `std::ranges::filter_view`.
The closest thing in the STL is `copy_if`, which is happy to take an output iterator for its destination parameter, for example a `back_insert_iterator`.
return numbers.end()
!= std::find_if(numbers.begin(), numbers.end(),
[](int number) { return number % 2 == 1; });
return any(number % 2 == 1 for number in numbers)
Sandor's suggested replacement solves the first problem of clearly saying what is desired:
return std::any_of(numbers.begin(), numbers.end(),
[](int number) { return number % 2 == 1; });
Because of Python's better orthogonality, you can factor out the lazy boolean sequence generator into a function of its own if that's a useful thing to do:
def oddnesses(numbers):
return (number % 2 == 1 for number in numbers)
return any(oddnesses(numbers))
all(oddnesses(numbers)) # addressed by all_of in OP
zip(numbers, oddnesses(numbers))
sum(oddnesses(numbers)) # punning booleans as ints
sum(map(operator.mul, numbers, oddnesses(numbers)))
But we could wish for a language with the efficiency and in-the-large maintainability of C++ and the clarity and generality of Python.
std::ranges::any_of(numbers, [](auto i){ return i % 2 == 0; }))
v | std::views::reverse | std::views::drop(2);
// assuming `numbers` is an iterator
numbers.any(|i| i % 2 == 1)
Ruby's Enumerable is a concrete class; Rust's std::iter::Iterator is a trait, which has some aspects in common with Ruby classes and other aspects in common with Python protocols such as the Python iterator protocol. std::iter::Iterator is (primarily, though not in this case) an external iterator like Python iterators, STL iterators, and ranges in C++20 or D, not an internal iterator like (the original version of) Ruby Enumerable. Rust's type-checking strategy is more like ML than like Ruby, Python, C++, or D, while its compilation strategy is more like C++'s or D's compilation strategy than those of Ruby, Python, or ML.
> Ruby: closure syntax
warning: called `is_some()` after searching an `Iterator` with `find`
--> src/lib.rs:2:9
|
2 | numbers.find(|i| i % 2 == 1).is_some()
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: use `any()` instead: `any(|i| i % 2 == 1)`
|I think I'm going to have to get serious about Rust. I had a dismaying epiphany writing https://news.ycombinator.com/item?id=28660097 the other day: like Perl, Python just isn't saving me very much effort except for quick hacks, maybe a factor of 2–4 over C (if we discount CVEs, heh). It's not the order-of-magnitude development speed improvement I was hoping for, and now that I've been using it for 20 years I know it never will be. Python starts to buckle under the strain of large projects, they totally fucked up Unicode handling to an epic degree never seen in any other programming language, and it typically costs you orders of magnitude in performance.
And—this is the worst of all—at best a library written in Python is only usable from Python and maaybe the JVM languages, and you can probably call it from a shell script. (I don't know, maybe the CIL languages too.) By contrast, if I write a library in Rust or C or C++ or D I can use it in Rust, C, C++, D, Python, Perl, Ruby, LuaJIT, Julia, PHP, node.js, Scheme, Common Lisp, OCaml, Golang, the JVM languages, the CIL, and maybe even Arduino. So the effort is greater (though, as you point out in this case, not necessarily much greater, though you didn't mention compile time, which sucks pretty bad for both Rust and C++) but the benefit is much greater.
(Also, the Python 2→3 gap was pretty badly flubbed, especially at the social level; no other language community tries to shame people out of maintaining backward compatibility that I know of.)
So I think from now on I'll try to start writing prototypes in Python or OCaml but, if the prototype seems worthwhile, writing the Real Thing in Rust. Which is gonna be pretty rough since I don't know Rust. :)
numbers.iter().any(|i| i % 2 == 1)
for (int i: numbers)
if (i % 2 == 1)
return true;
return false;
numbers.some(number => (number % 2) === 1)
What about Haskell? Maintainability yes; efficiency mostly. It has a GC that can be a pain for high-memory scenarios if you don't spend a lot of effort optimising, but on the whole Haskell is surprisingly fast for its expressivity.
Any odd? `any odd numbers`. Or equivalently, `or (map odd numbers)`, which is compositional in that `map odd numbers` is just a list again -- no distinction between lazy and strict lists in Haskell. Your other four examples are `and (map odd numbers)`, `zip numbers (map odd numbers)`, `sum (map (fromEnum . odd) numbers)`, `sum (zipWith (*) numbers (map (fromEnum . odd) numbers))`. Note I used `map odd` instead of defining `oddnesses = map odd` and using `oddnesses`, because the definition is shorter than the name. :)
This changes somewhat when you use arrays instead of lists: Haskell's lists are in terms of behaviour mostly "generators that are implicitly stored as a lazy linked list if necessary". So if you want to store stuff more compactly, or you want to index into the list (as opposed to looping over it), you need arrays. But even for arrays the story doesn't change much! Using the 'vector' library, actually all of the above examples work just fine, with no unnecessary intermediate vectors because of some intelligent fusion rules, if you put `V.` before the list-related function names.
I think there's an underlying tension between generality and clarity. Clarity is when the code can't do things that aren't immediately obvious upon reading it. Generality is when it can. (There's a bit of squirrely equivocation here about what kinds of "thing" is being done, and what sense of "can" is meant, which is why they're just in tension and not really opposite, but I think there's some truth too.)
Right, that's a downside. I believe there is a way in which you can call Haskell code from C, but I've never seen anyone use it myself.
> I think there's an underlying tension between generality and clarity.
You're on to something here. C++ has the same problem, where the syntax itself is context dependent: `a * b;` could be a multiplication if `a` is a variable, or a variable definition if `a` is a type. Also template meta-programming, and overloading and {con,des}tructors in general. (Of course, Haskell has the overloading thing even more -- though the containment of IO helps matters quite a bit in my opinion.) Golang explicitly chose to go the clarity way, and it got them some love and plenty of flak.
Maybe one should just conclude from this that Haskell is not a great language for corporate environments. On the other hand, I think it's great for small-team development due to its expressivity and generality. But these two claims do not contradict each other: not every language is good for every purpose.
I don't know if I would call it "surprisingly" fast. It is plenty fast, but it's a language that's AOT and these languages are usually quite fast, faster than most JIT'd and interpreted languages. Looking at the programming languages benchmark games and the techempower web framework benchmark, Haskell is around Java and Go. Which means that it can compete against the most advanced JIT and a reasonably good AOT, while being more expressive than both. That sounds reasonable to me. I may be underestimating what it takes to make something like Haskell fast though.
For Java and Go, that's true, though in both cases that's mostly because of decisions rather than tradeoffs. Go doesn't have a primitive type system because it makes it faster, but mostly because that's a design choice. Same thing for Java. I'd say you can get a good part of what makes Haskell good by using a ML as the basis for your language . Lack of ad-hoc polymorphism is usually a criticism of ML and its descendants, but Go and Java both lack it too, and both added generics 10 years after the language was created, which ML supports from the beginning. Rust seem to have achieved having parametric and ad-hoc polymorphism, but I don't know how easy or hard it would be to "extract" that "part" of Rust (without the borrow checker) and basically stick a GC on it. I also don't know how performant it would be. Lastly, Go, Java and OCaml all share fast compilation times, Haskell doesn't really and Rust is known for being slow.
Again, I'm far from an expert on all of that, but I think Haskell in the right place in terms of performance and expressivity. It's one of these cases where designing a language for performance in the first place instead of retrofitting it makes things much easier, I think.
They support AOT native-code compilation too, but they say the JIT generally performs better: https://download.racket-lang.org/docs/5.1/html/raco/ext.html but my experience in the past was that it didn't perform that well. Maybe it's improved.
> Go doesn't have a primitive type system because it makes it faster, but mostly because that's a design choice. Same thing for Java.
I agree: a primary goal for both languages was clarity, even at the expense of some generality. Java was very slow for a decade (HotSpot wasn't released until 01999 and wasn't very good until about 02002), but a few billion dollars and a Fortune-500 bankruptcy later, it's really pretty zippy! (As long as you don't care about startup time.) Golang, by contrast, was designed with higher performance goals, which it fell somewhat short of.
> Lack of ad-hoc polymorphism is usually a criticism of ML and its descendants, but Go and Java both lack it too
Ad-hoc polymorphism is absolutely fundamental to Java; one of its big differences from C++ was that nearly every callsite implied ad-hoc polymorphism, and that's where a lot of the optimization effort went. Golang isn't quite so radical about it, but its interface mechanism exists for almost nothing but ad-hoc polymorphism.
OCaml has ad-hoc polymorphism, FWIW, but people don't use it much.
> both added generics 10 years after the language was created
Golang was released in 02009 and still doesn't have generics, but it will this year. Not far from 10 years.
> Haskell ... It's one of these cases where designing a language for performance in the first place instead of retrofitting it makes things much easier, I think.
I wouldn't have listed Haskell as a language designed for performance. When it came out in 01990 the conventional wisdom was that garbage collection was inherently super slow, especially if you couldn't avoid allocating in your inner loops (by mutating instead).
Allen Wirfs-Brock says Tektronix Smalltalk for the 4405/4406 "may have been the first shipping commercial product, running on a off-the-self processor, to use a generational GC" http://www.wirfs-brock.com/allen/things/smalltalk-things/tek... in 01986, only four years before Haskell was designed. That was the key advance that made efficient pure functional languages feasible, and it was still too early to be sure how it would shake out. That's one reason Java (still Oak in 01992) entirely lacked implicit heap allocations: the conventional wisdom was still that heap allocation was very expensive because it required the GC to run more, so they didn't want to impose that on programmers. It was sort of a self-fulfilling prophecy, because even today the way to make your Java (or Golang) go fast is to avoid allocations in your inner loops. Not a big deal in SBCL, LuaJIT, OCaml, or pretty much anything else with a GC heavily tuned for allocation.
Other aspects of Haskell also involved a lot of performance research. Simon Peyton Jones invented the spineless tagless G-machine in the process of writing GHC, published in a paper in 01992, which was sort of a followup to his 01987 book on efficient implementation of pure functional languages. Even so, through the 01990s, Haskell still wasn't very fast. I think a lot of the stuff that makes Haskell reasonably fast is stuff that's been discovered in the last 25 years, after the basic language design was decided.
I'm also far from an expert on this stuff, though, so my picture of what happened might be missing some important aspects. I still know very little Haskell.
You can do the same in C++:
static bool isEven(int x) { return x % 2 == 0; }
bool foo(const std::vector<int>& v)
{
return v.end()
!= std::find_if(v.begin(), v.end(), isEven);
}It's immediately clear to me what each of the find_if snippets does, but I haven't heard of the other functions – and the evidence from the article is that the vast majority of other programmers haven't either (in fact that's out of the subset that bother to use find_if, which I would say means even less of general coders). Sure, it's fairly obvious what they do from the name, but I'd still bother to check their signature in case there's a subtlety. In other words, there may be fewer lines of code, but it's still more cognitive overhead.
In fact I'd go one step further and say it's better to use raw primitives, like for loops (range based where appropriate), where they don't need too much extra code.
one argument in favor of functions like any_of is that, once you get familiar with them, they provide additional documentation of intent. I'll concede this is a pretty minor benefit; most uses of any_of replace a pretty simple loop.
I don't think that's it. A lot of code ends up being calls to functions, and so other types of syntax add a bit of texture. Replacing those with function calls too reduces the code to a smooth paste. It's a bit like if the standard library had a lessThanThree(x) function; it doesn't matter how totally familiar I was with it, I'd still prefer to see x<3.
You might have a point if people are putting that in header files. But even in header files, "using std::string" is often a standard thing to do in e.g. game engines. It's far easier to change out your string implementation if you're writing "string" instead of "std::string".
The question was about find_if, which is a function, not string.