AVL tree: Difference between revisions
Content added Content deleted
m (→{{header|J}}) |
m (→{{header|J}}: word of caution about this approach) |
||
Line 7,598: | Line 7,598: | ||
=={{header|J}}== |
=={{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: |
Implementation: |