Repository: rust-itertools/itertools (language: rust)

Issue:
How does tree_reduce achieve O(ln(n)) operations? 
How does `Itertools::tree_reduce` achieve `O(ln(n))` operations? 

If we take the visualization from the documentation:

```
1 2 3 4 5 6 7
│ │ │ │ │ │ │
└─f └─f └─f │
  │   │   │ │
  └───f   └─f
      │     │
      └─────f
```

This looks like a full binary tree with `n` being the number of leaf nodes and the operations `f` being the internal nodes. A binary tree with `I` internal nodes has `L = I + 1` leaf nodes (if I'm not mistaken). That would mean the number of operations is always `n - 1`, which would be `O(n)` and the same as the normal `Iterator::reduce` operation.

What am I missing?



Discussion / hints:
From what I understand myself, the compiler can better optimize heavy things (such as `|a, b| format!("{a}{b}")`) than with `reduce` where things are done in strict order. ~EDIT~

His author @scottmcm will have a better explanation than me though.
If parallelization is the main benefit, we should probably update the documentation, as it currently states:

> otherwise if f is non-trivial like format!, you should use tree_reduce since it reduces the number of operations from O(n) to O(ln(n))
> How does `Itertools::tree_reduce` achieve `O(ln(n))` operations?

It definitely doesn't.  It's a tree *depth* of `O(lg(n))`, instead of a depth of `O(n)` for normal reduce, but you're absolutely right that it's still `n-1` calls to `f`.

So yeah, sounds like it needs a documentation update.

---

The way you *can* get an algorithmic improvement is if the `f` is itself `O(n)`.  For example, if `f` is `format!("{a}{b}")`, then `reduce(f)` is `O(n²)` but `tree_reduce(f)` is `O(n lg n)`.


Thanks for the answer! 

Could you elaborate on the example with `f` being `format!`? Isn't there a different `n` for `tree_reduce` and `format!`? For `tree_reduce` the `n` seems to be the number of elements that the iterator yields, for `format!` the `n` is either the number of arguments (which would be the same between `reduce` and `tree_reduce`) or the length of the given strings / the length of the result string.

The length of the arguments is different between `reduce` and `tree_reduce`, since for `reduce` one argument (the "accumulator") would constantly grow while the other one is always just the next element from the iterator. For `tree_reduce` both arguments grow. In the fist level of the tree all arguments are elements from the iterator, then results from the previous level and so on. For `format!("f({a}, {b})")` the result is different: `f(f(f(a, b), c), d)` vs `f(f(a, b), f(c, d))`. But the length of both results are the same, so the sum of all `n` given to format should be the same. Both variants do the same number of allocations (depends only on number of calls to `f`) and allocate the same number of overall bytes.

EDIT (summarizing):
If both `reduce(f)` and `tree_reduce(f)` call `f` `n - 1` times and given `f` is `format!`, how does `tree_reduce(f)` get `O(n lg n)` vs `O(n²)` for `reduce(f)`?
Because the sizes of the intermediate values are different.

Here's a demonstration: <https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=61f468dfab44cb92983d8c87f55702e5>
```rust
let mut total_capacity = 0;

let f = |a: String, b: String| {
    let s = format!("<{a} {b}>");
    total_capacity += s.capacity();
    s
};

let r = (0..100).map(|x| x.to_string())
    .reduce(f)
    //.tree_fold1(f)
    .unwrap();
dbg!(total_capacity, r.len());
// With reduce: 
// [src/main.rs:15:5] total_capacity = 47220
// [src/main.rs:15:5] r.len() = 487
// With tree_fold1: 
// [src/main.rs:15:5] total_capacity =  5310
// [src/main.rs:15:5] r.len() = 487
```

The total number of calls to `f` are the same either way, as is the size of the output, but the different order for `tree_reduce` means it's concatenating smaller strings on average.
Thanks, that makes sense! That example would be super helpful in the documentation. If you'd like I could prepare a PR for updating the doc.
Please do!  PRs always welcome 🙂 
@rbruenig Do you want to make a PR?
@Philippe-Cholet I'll prepare one this week. Didn't get around to it last week.

Fix patch:
diff --git a/src/lib.rs b/src/lib.rs
index 018f877e5..0e7e68fb8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2528,24 +2528,31 @@ pub trait Itertools: Iterator {
     ///
     /// If `f` is associative you should also decide carefully:
     ///
-    /// - if `f` is a trivial operation like `u32::wrapping_add`, prefer the normal
-    /// [`Iterator::reduce`] instead since it will most likely result in the generation of simpler
-    /// code because the compiler is able to optimize it
-    /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_reduce` since it
-    /// reduces the number of operations from `O(n)` to `O(ln(n))`
+    /// For an iterator producing `n` elements, both [`Iterator::reduce`] and `tree_reduce` will
+    /// call `f` `n - 1` times. However, `tree_reduce` will call `f` on earlier intermediate
+    /// results, which is beneficial for `f` that allocate and produce longer results for longer
+    /// arguments. For example if `f` combines arguments using `format!`, then `tree_reduce` will
+    /// operate on average on shorter arguments resulting in less bytes being allocated overall.
     ///
-    /// Here "non-trivial" means:
+    /// Moreover, the output of `tree_reduce` is preferable to that of [`Iterator::reduce`] in
+    /// certain cases. For example, building a binary search tree using `tree_reduce` will result in
+    /// a balanced tree with height `O(ln(n))`, while [`Iterator::reduce`] will output a tree with
+    /// height `O(n)`, essentially a linked list.
     ///
-    /// - any allocating operation
-    /// - any function that is a composition of many operations
+    /// If `f` does not benefit from such a reordering, like `u32::wrapping_add`, prefer the
+    /// normal [`Iterator::reduce`] instead since it will most likely result in the generation of
+    /// simpler code because the compiler is able to optimize it.
     ///
     /// ```
     /// use itertools::Itertools;
     ///
+    /// let f = |a: String, b: String| {
+    ///     format!("f({a}, {b})")
+    /// };
+    ///
     /// // The same tree as above
-    /// let num_strings = (1..8).map(|x| x.to_string());
-    /// assert_eq!(num_strings.tree_reduce(|x, y| format!("f({}, {})", x, y)),
-    ///     Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
+    /// assert_eq!((1..8).map(|x| x.to_string()).tree_reduce(f),
+    ///            Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
     ///
     /// // Like fold1, an empty iterator produces None
     /// assert_eq!((0..0).tree_reduce(|x, y| x * y), None);
@@ -2553,9 +2560,32 @@ pub trait Itertools: Iterator {
     /// // tree_reduce matches fold1 for associative operations...
     /// assert_eq!((0..10).tree_reduce(|x, y| x + y),
     ///     (0..10).fold1(|x, y| x + y));
+    ///
     /// // ...but not for non-associative ones
     /// assert_ne!((0..10).tree_reduce(|x, y| x - y),
     ///     (0..10).fold1(|x, y| x - y));
+    ///
+    /// let mut total_len_reduce = 0;
+    /// let reduce_res = (1..100).map(|x| x.to_string())
+    ///     .reduce(|a, b| {
+    ///         let r = f(a, b);
+    ///         total_len_reduce += r.len();
+    ///         r
+    ///     })
+    ///     .unwrap();
+    ///
+    /// let mut total_len_tree_reduce = 0;
+    /// let tree_reduce_res = (1..100).map(|x| x.to_string())
+    ///     .tree_reduce(|a, b| {
+    ///         let r = f(a, b);
+    ///         total_len_tree_reduce += r.len();
+    ///         r
+    ///     })
+    ///     .unwrap();
+    ///
+    /// assert_eq!(total_len_reduce, 33299);
+    /// assert_eq!(total_len_tree_reduce, 4228);
+    /// assert_eq!(reduce_res.len(), tree_reduce_res.len());
     /// ```
     fn tree_reduce<F>(mut self, mut f: F) -> Option<Self::Item>
     where


Test patch: