Method for adding sorted sequence in tree like data structures #105

New issue

Closed

opened 2019-03-17 14:21:42 +00:00 by Khadmium · 1 comment

Khadmium commented

2019-03-17 14:21:42 +00:00

(Migrated from github.com)

Functions like putAll(Map) in java or insertion_hint concept in c++ gives possibility to add some range of sorted values to map in more efficient way. Maybe I didn't notice something, but currently similar optimization cannot be achieved with existing interface.

emirpasic commented

2022-04-12 17:52:55 +00:00

(Migrated from github.com)

Generally speaking, even in Java, the only optimization usually this entails is to allocate enough memory from the start, but the elements are still usually inserted one by one.

In case of a TreeMap, digging deep into it there is this optimization when cloning another sorted data structure to a sorted tree: github.com/eagle518/jdk-source-code@91b771140d/jdk6u21_src/j2se/src/share/altclasses/java/util/TreeMap.java (L3280) (it does save a few clock cycles for sure, but it will take some time for this to become a bottleneck in any project)

That's correct, at the moment there is no PutAll() function for trees and I am not sure at the moment if we have the resources to implement that optimization. For now, doing single element insertions will have to suffice. Generally speaking, even in Java, the only optimization usually this entails is to allocate enough memory from the start, but the elements are still usually inserted one by one. In case of a TreeMap, digging deep into it there is this optimization when cloning another sorted data structure to a sorted tree: https://github.com/eagle518/jdk-source-code/blob/91b771140de051fb843af246ab826dd6ff688fe3/jdk6u21_src/j2se/src/share/altclasses/java/util/TreeMap.java#L3280 (it does save a few clock cycles for sure, but it will take some time for this to become a bottleneck in any project)