Aggregation or partition structure added to Iterables

[gissuebot]

Original issue created by em...@soldal.org on 2012-05-23 at 04:42 PM

---

In ref to https://groups.google.com/d/topic/guava-discuss/NfE09gFfPjU/discussion

This issue discusses the addition of the following three methods to Iterables:

Iterable<List<T>> partition(Iterable<T> iterable, Comparator<T> comparator)
Iterable<List<T>> parition(Iterable<T> iterable, Equivalence<T> equivalence)
Iterable<List<T>> parition(Iterable<T extends Comparable<? super T>> iterable)

The proposed function of these methods would be to group or chunk like items together without disrupting the order of the elements or their occurrence in the underlying iterable or boundaries in the underlying iterable.

As a side-effect of this it would also be prudent to add something to Equivalences like Equivalence<T> from(Comparator<T> comparator) for completeness.

[gissuebot]

Original comment posted by stephan202 on 2012-05-23 at 10:11 PM

---

This sounds very similar to Python's itertools.groupby [1]. +1 from me :)

[1] http://docs.python.org/library/itertools.html#itertools.groupby

[gissuebot]

Original comment posted by em...@soldal.org on 2012-05-26 at 01:04 AM

---

Jet-lagged brainwave:
These signatures would also naturally fit into FluentIterable, but in that instance groupBy() would seem to give more meaning.

[gissuebot]

Original comment posted by tomas.zalusky on 2012-05-29 at 10:29 AM

---

I would appreciate an aggregation method in Guava. I made my own utility class years ago, before Guava era. Let me share some observation from its usage and from reading the https://groups.google.com/forum/#!topic/guava-discuss/NfE09gFfPjU/discussion :

1. Multimaps.index is pretty close to aggregation method. Kevin's first entry in discussion perfectly fits to my usecases, however it always returns new multimap. Sometimes, for example when streaming large file, lightweight approach is more desirable. E.g. pass through iterable once and generate events like "open group" and "close group" to some builder, like for example during SAX xml parsing.
2. To use Equivalence for group boundary recognition is unnecessarily restrictive. The problem to be solved is just to decide if two neighboring elements are in the same group. The aggregation method would then be usable e.g. for finding continuous subsequences in list of integers [1,2,3,4,7,10,11] -> 1-4,7,10-11 or for some simple analysis. Hence Equivalence would be abused here since symmetry and transitivity would be violated. Predicate<Pair<T>> (if Guava had Pair) would IMHO be more appropriate.
3. Aggregation is often multilevel and the function on which data is aggregated is usually the same as the function on which data is sorted. The API should facilitate both in some convenient way.

Example of my API (real use case, original entities from telco domain):

class Person {String surname; String name; int number; ...}
List<Person> persons = Lists.newArrayList(
        new Person("Doe","Jack",1),
        new Person("Doe","Jack",2),
        new Person("Doe","Joe" ,1),
        new Person("Doe","Joe" ,2),
        new Person("Doe","Joe" ,3),
        new Person("Doe","Joe" ,5),
        new Person("Doe","Joe" ,6),
        new Person("Doe","Joe" ,7),
        new Person("Doe","Joe" ,8),
        new Person("Roe","Jane",1),
        new Person("Roe","Jane",2),
        new Person("Roe","Jane",3),
        new Person("Roe","Jane",5)
);
Builder<Person,String> bySurname = new Builder<Person,String>() {
    public String key(Person current) {return current.surname;}
    public void openGroup(Person first) {System.out.println(first.surname);}
};
Builder<Person,String> byName = new Builder<Person,String>() {
    public String key(Person current) {return current.name;}
    public void openGroup(Person first) {System.out.println("+" + first.name);}
};
Builder<Person,Integer> byNumber = new Builder<Person,Integer>() {
    private int firstNumber;
    public Integer key(Person current) {return current.number;}
    public boolean isSameGroup(Integer previousExpression, Integer currentExpression) {return previousExpression + 1 == currentExpression;}
    public void openGroup(Person first) {System.out.print("++" + (firstNumber = first.number));}
    public void closeGroup(Person last) {System.out.println(firstNumber == last.number ? "" : "-" + last.number);}
};
Grouping.group(persons).by(bySurname,byName,byNumber);

result:

Doe
+Jack
++1-2
+Joe
++1-3
++5-8
Roe
+Jane
++1-3
++5

My dream Guava API for this would then look like

FluentIterable
    .from(persons)
    .groupBy(Person.GET_SURNAME)
    .groupBy(Person.GET_NAME)
    .groupBy(Person.GET_NUMBER,EQUIVALENCE_FOR_DIFFERENCE_1)

(Just a shot, I didn't researched it deeply yet.)

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 10:43 AM

---

@tomas, I think there are two different things going on here.

"Group boundary recognition" is a totally different problem than the one I think Emily's addressing -- in particular, there's the case when we want to group contiguous elements, and the case when we want to group not-necessarily-contiguous elements together (e.g. by an Equivalence).

It's not clear to me that a "One True Aggregation API" could even exist, but I think there are definite possibilities for improvement.

The idea playing around in my head at the moment is some sort of fluent "Grouping" API that takes an Iterable<E> and returns an Iterable<Iterable<E>>. Groupings might be contiguous, they might be non-contiguous, they might be based on a function or an ordering or an equivalence...am I making sense?

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 10:44 AM

---

That is, let me clarify: I think groupings are too complicated to just get tacked on to e.g. FluentIterable; I think there are too many different ways to "group" to just have a couple of heavily overloaded methods.

[gissuebot]

Original comment posted by em...@soldal.org on 2012-05-29 at 10:47 AM

---

A full API built as opposed to a single method on FluentIterable? Me gusta.

Now that you mention it Louis, this does seem to make more sense. Since nested grouping using FluentIterable would result in Iterable<Iterable<Iterable...ad nausium, or at least it would risk it. Perhaps it could be solved by being able to combine Equivalences, when using a Comparator you could use Ordering.compound() to do this nesting for you.

Sorting the data is actually not a prerequisit for grouping, even though the two are often together.

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 11:14 AM

---

+1 for Equivalences.intersect (if not the name, at least the functionality).

My concern with "aggregation" has always been that it's such an open-ended, complicated thing that encompasses so many different ideas that designing an API to deal with them all is difficult. Just from this issue and off the top of my head, we have

• grouping by Equivalence (contiguous or not)
• grouping by HashFunction (?)
• grouping by Comparator (contiguous or not)
• grouping into chunks of K
• grouping into K chunks
• combinations of the above

There are a lot of different ways to take these ideas, and I'm still not sure we can fit them all into one unified API, but I think that a fluent "Grouping" API is the only way to even get close.

[gissuebot]

Original comment posted by em...@soldal.org on 2012-05-29 at 11:30 AM

---

• grouping by Equivalence (contiguous or not) / grouping by Comparator (contiguous or not)
      - I feel like we should only concern outselves with contiguous variants (and I hope I am using that word correctly...), any preliminary grouping of elements should be done by the user and it would feel presumptious to simply assume that the data should be structured. We could sort it beforehand but then you loose a lot of performance if you present yourself as a view and then the user iterates multiple times.
• grouping by HashFunction (?)
      - Isn't this the same as a equivalence with a hashing function infront of it? Interesting idea though
• grouping into chunks of K / grouping into K chunks
      - K chunks in N is tricky as you will have to judge the size of the iterable before figuring out how big a chunk should be

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 11:38 AM

---

"I feel like we should only concern outselves with contiguous variants (and I hope I am using that word correctly...), any preliminary grouping of elements should be done by the user"

I'm not sure I buy this? I would say that Multimaps.index does "aggregation," but it simply doesn't care what order the values come in, and I feel like that's a use case worth addressing -- especially for e.g. Equivalences where there isn't an obvious way to "sort."

That is, I think it's totally legit for a user to say, "I have these totally arbitrarily ordered values, and I want them grouped according to an Equivalence."

"grouping by HashFunction (?)
    - Isn't this the same as a equivalence with a hashing function infront of it? Interesting idea though"

Mostly I think of this as being like Multimaps.index, except using a custom hash function that might be more efficient/effective/have fewer collisions

"- K chunks in N is tricky as you will have to judge the size of the iterable before figuring out how big a chunk should be"
Indeed, that version would be strict -- and if we want to deal with noncontiguous groupings, those would be strict too.

[gissuebot]

Original comment posted by em...@soldal.org on 2012-05-29 at 11:45 AM

---

Sorting by equivalence feels iffy to me, although I guess theres nothing strictly speaking wrong with it if its made strict? o_O
You'd have to do some sort of intelligent sorting algorithm though, since you don't know if A is above or below B only that it is different. How would you sort a list where no elements are equal? Wouldn't it go into a loop?

[gissuebot]

Original comment posted by em...@soldal.org on 2012-05-30 at 08:38 AM

---

Most of what we've discussed so far seems to be related to the way you define a grouping rather than the operation of grouping itself. Even if we wish to do ordering, it occurs outside of the actual operation of grouping.

What if instead of a Grouping API we define a builder pattern for a grouping rule:

FluentIterable<List<Person>> groupedPeople = FluentIterable.from(people).grouping().by(Person.GET_SURNAME).by(Person.GET_NAME).group();

or

FluentIterable<List<Person>> groupedPeople = FluentIterable.from(people).grouping().by(Person.GET_SURNAME).by(Person.GET_NAME).sortedBy(Person.GET_SURNAME).group();

where sortedBy takes either a Comparator<T> or a Function<T,Comparable> which we can use with Ordering.natural().onResultOf()

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-30 at 08:44 AM

---

Hmmmm. I guess my thinking is that having actual Grouping objects would be nice -- like, a static final constant Grouping that you reuse.

"Sorting by equivalence feels iffy to me, although I guess theres nothing strictly speaking wrong with it if its made strict?"

I'm not suggesting sorting at all -- the ordering would be by "first seen," so the first element in a new equivalence class would determine the position of that equivalence class in the ordering.

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-30 at 08:45 AM

---

Or, heck, ordering by Equivalence could just give you an arbitrary ordering of the equivalence classes.

[gissuebot]

Original comment posted by em...@soldal.org on 2012-05-30 at 08:59 AM

---

So Iterable<T> -> Iterable<Grouping<T>> where Grouping holds a Predicate<T> composed of the Equivalence.equivalentTo(T) for the first instance of T now in another Grouping ?

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-30 at 09:10 AM

---

Wait, what?

I was thinking that Grouping would represent more of a "grouping rule," and then you'd call Grouping.group(iterable) and get back an Iterable<Iterable<T>>. So, something like

Grouping<PhoneBookRecord> SAME_PHONE_NUMBERS =
  Grouping.onEquivalence(Equivalences.equals()
    .onResultOf(GET_PHONE_NUMBER_FUNCTION));

Iterable<Iterable<PhoneBookRecord>>
  peopleUsingSamePhone = SAME_PHONE_NUMBERS.group(phoneBook);