AVL tree: Difference between revisions
m
→{{header|J}}: word of caution about this approach
m (→{{header|J}}) |
m (→{{header|J}}: word of caution about this approach) |
||
Line 7,598:
=={{header|J}}==
Caution: AVL trees are not cache friendly. Linear search is significantly faster (roughly six times faster for a list of 1e8 numbers on current machines and arbitrary data), and using small cached copies of recent updates allows time for updates to be inserted into a fresh copy of the larger list (on a different thread, or failover machine -- search the current "hot copy" before searching the larger "cold copy"). Use [[wikipedia:AoS_and_SoA#Structure_of_arrays|structure of arrays]] for best performance with that approach. (Typical avl implementation also uses memory equivalent to several copies of a flat list.)
Implementation:
| |||