Author Topic: Speed up mapcar + and -  (Read 2841 times)

0 Members and 1 Guest are viewing this topic.

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Speed up mapcar + and -
« Reply #15 on: August 23, 2023, 05:42:01 AM »
focus on the important stuff.
That's what I wanted to say.

Saving 5 microseconds on a function only matters if that function is called thousands of times in the same routine.

Yes, command is slower than entmake (especially when CMDECHO is set to 1), but if you only have one call to command in a routine, the difference is insignificant.

A few years ago, there was a very interesting challenge from the point of view of optimizing execution speed.
In a drawing containing 10,000 points, the task was to connect every two points whose distance was less than 70.
The first answers used brute force (comparing the first point to all the following ones, then the second to all the following ones, etc.). Execution times for the first answers in LISP were between 35 and 50 seconds (2 seconds with .NET, 1 second with ARX). Initially, the question was to optimize what is executed in each iteration, i.e. to focus on the detail, whereas the important question was how to significantly reduce the number of iterations (the number of 'brute force' iterations = 9999 + 9998 + 9997 + ... + 1 = 49,995,000).
The answer was by organizing point, either by sorting them on X coordinate (ElpanovEvengiy LISP routine: 1.5 second) or by grouping them (qjchen divide and conqueer LISP routine: 0.79 seconds)*. When you divide the execution time of a routine by 50 with a better general algorithm, the time saved on each iteration becomes insignificant.
With .NET and ARX another algorithm using a kd-tree (which won't be efficient with LISP which only knows lists as data structure) gave more impressive results and requires to increase the number of points to 100,000 and 1,000,000.

* respctively 0.3125 seconds and 0.112 seconds with .NET

« Last Edit: August 23, 2023, 07:32:23 AM by gile »
Speaking English as a French Frog

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8712
  • AKA Daniel
Re: Speed up mapcar + and -
« Reply #16 on: August 23, 2023, 06:42:35 AM »