3 ms·
That's actually not the case - that's one effect, sure, but when you compared the compiled trees to the flattened trees (the strategy just described), the compi
by ajtulloch 11y ago
That's actually not the case - that's one effect, sure, but when you compared the compiled trees to the flattened trees (the strategy just described), the compiled trees are substantially faster across a range of parameters. See http://tullo.ch/articles/decision-tree-evaluation/ http://tullo.ch/articles/decision-tree-evaluation/ for a detailed evaluation.
- CyberDildonics 11y agoThat's really awesome that you put that together, but I have to think that 200 points and a depth < 2 would basically be a linear search over about 100 elements right? Fundamentally I can't think of any reason compiling a tree would be a good approach in a general sense. Another optimization is to put make splits multiple levels instead of just one. How many might depend on how many you can squeeze into a cache line. If you split position is a float and the dimension is a byte, each split would be 5 bytes. You can squeeze 12 of these into a cache line. You can go 3 level down instead of one by packing 7 of them into a chunk (1 split + 2 splits + 4 splits). This still leaves room for a 32 bit index or pointer for each of the 4 leaves.