Slow Kernel Functions

Functions ReplacePart, MapAt, Insert, AppendTo, and PrependTo are very slow when they are used to make a large number of changes to an expression. The other functions I list here are not extremly slow, but they are all much slower than the simpler form of the same function (eg. Sort[list,p] is much slower than Sort[list]).

ReplacePart, MapAt, Insert (when the last argument is a long list).

ReplacePart, MapAt, and Inset can be very slow.

Consider the expressions:

ReplacePart[expr, 1, lst]

MapAt[f,expr, lst]

Inset[expr, 1, lst]

Where (lst) has the form {{__Integer},{__Integer}, ...] and Length[lst]=n.

In that case each of these functions are O[n^2]. For those who aren't

familiar with this notation, O[n^2] means the evaluation time is proportional

to n^2. Hence if (lst) is a long list of lists these functions are very

slow.

Here is the evidence

395 | 0.05 Second |

780 | 0.22 Second |

1580 | 0.93 Second |

3108 | 4.01 Second |

6276 | 18.12 Second |

396 | 0.06 Second |

782 | 0.27 Second |

1593 | 1.26 Second |

3191 | 5.49 Second |

6272 | 24.28 Second |

237 | 0.06 Second |

472 | 0.11 Second |

951 | 0.49 Second |

1879 | 1.98 Second |

3786 | 8.4 Second |

Would a faster algorithm give "wrong" results?

It seems like there must be algorithms for (ReplacePart, MapAt, Insert) that

would evaluate much faster with a long list of parts. It may be that the

developers used slower methods which are needed to ensure that the result is

correct. A similar issue had to be addressed with Union. However, in the

case of Union the developers decided to use a method that is O[n Log[n]] and

they accepted the risk that the result might include some duplicates.

At http://support.wolfram.com/Kernel/Symbols/System/Union.html we see Union treats elements as duplicates only if they appear in adjacent positions after sorting. Apparently this method is O[n Log[n]], and Union would be O[n^2] if it compared all pairs of elements.

AppendTo, PrependTo

AppendTo and PrependTo are very slow when used on large expressions. Instead use a "linked list" as I discuss under programming for speed.

Sort[list,p]

Sort[list] is faster than Sort[list, p] but sometimes we can't avoid the

slower form.

Ordering[list,n,p]

Ordering[list, n, p] is slower than Ordering[list] or Ordering[list, n] but

sometimes we can't avoid the slower form.

Split[list,test]

Split[list, test] is slower than Split[list] but sometimes we can't avoid

the slower form.

MatrixQ[expr,test], VectorQ[expr,test]

MatrixQ[expr, test] is slower than MatrixQ[expr].

Likewise VectorQ[expr, test] is slower than VectorQ[expr].

However, sometimes we can't avoid the slower form of VectorQ and MatrixQ.

(SameTest→func) instead of (SameTest→Automatic)

The functions (Complement, FixedPoint, FixedPointList, Intersection, Union)

all have a SameTest option. When they are given a non-default setting for the

SameTest option they run much slower that with the default setting (SameTest

→Automatic). Sometimes we have no choice but to use these functions

with a non default SameTest setting. You should just be aware that this

slows down performance.

Created by Mathematica (May 17, 2004)