Why sort all value of one feature when run exact greedy algorithm?


#1

I read section about paper and it said in section3: Algorithm 1: Exact Greedy Algorithm for Split Finding:

In order to do so efficiently,
the algorithm must first sort the data according to feature
values and visit the data in sorted order to accumulate the
gradient statistics for the structure score in Eq (7).

I don’t know why sort before greedy search? If don’t sort, greedy search will be very slow?

Can anyone explain in a easy way?

thx