  We present a novel and systematic method, called Superfast Selection, for
selecting the "optimal split" for decision tree and feature selection
algorithms over tabular data. The method speeds up split selection on a single
feature by lowering the time complexity, from O(MN) (using the standard
selection methods) to O(M), where M represents the number of input examples and
N the number of unique values. Additionally, the need for pre-encoding, such as
one-hot or integer encoding, for feature value heterogeneity is eliminated. To
demonstrate the efficiency of Superfast Selection, we empower the CART
algorithm by integrating Superfast Selection into it, creating what we call
Ultrafast Decision Tree (UDT). This enhancement enables UDT to complete the
training process with a time complexity O(KM$^2$) (K is the number of
features). Additionally, the Training Only Once Tuning enables UDT to avoid the
repetitive training process required to find the optimal hyper-parameter.
Experiments show that the UDT can finish a single training on KDD99-10% dataset
(494K examples with 41 features) within 1 second and tuning with 214.8 sets of
hyper-parameters within 0.25 second on a laptop.
