Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

should call Less() fewer times when iterating #42

Open
caterchong opened this issue Apr 18, 2022 · 1 comment
Open

should call Less() fewer times when iterating #42

caterchong opened this issue Apr 18, 2022 · 1 comment

Comments

@caterchong
Copy link

caterchong commented Apr 18, 2022

when calling DescendRange methods, an iteration is performed.

All items between [lessOrEqual, greaterThan ) are iterated.

Suppose there're n items in the range, I though Less function is called log(n) times.

However, Less is called more than n times as a matter of

if stop != nil && !n.items[i].Less(stop) {
				return hit, false
			}

Why make comparisons this way? I though if parent node can decide all its children are in the range, most Less(stop) call can be optimized out.

Are there anything wrong with this idea?

@a180285
Copy link

a180285 commented Dec 31, 2022

@caterchong I have submitted a PR base on your idea.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants