algorithm - 如何改进这个列表算法？

Question

给出一个数字列表(字符或任何其他)和另一个随机数(字符或与列表同类)，如果列表中有两个相邻值与最后一个相同(三个值相同)，则将它们淘汰，然后递归进行。
例如
(1 5 3 3 2 2 4 3) + 2 => (1 5 3 3 2 2 4 3 2) => ( 1 5 3 3 4 3) => (1 5 4)

(1 3 3 2) + 2 => (1 3 3 2 2)

我的解决方案是这样的:

一个。扫描列表并获取与列表最后一个相同的两个相同值第一次出现的位置，如果未找到则为#f。

删除那三个值

递归调用一个

(define scan ;; list->list (get the position)
  (lambda (lst)
    (let scan-loop ((lst lst) (n 0))
      (cond
       [(<= (length  lst) 2) #f]
       [(and (equal? (car lst) (cadr lst))
     (equal? (car lst) (last lst))) n]
       [else
     (scan-loop (cdr lst) (+ n 1))]))))

(define (Arrange lst k) ; list,k -> list (remove the value) 
   (remove-k (remove-k (remove-k lst k) k) (- (length lst) 3)))

(define (remove-k lst k)
 (let remove-loop ((init lst) (n k) (new '()))
  (cond
   [(null? init) (error "K is too big for list")]
   [(= n 0) (append new (cdr init))]
   [else
    (remove-loop (cdr init) (- n 1) (append new (list (car init)) ))])))

(define (eliminate lst) ; list ,num -> lst (the main function)
  (let ([flag (scan lst)])
     (if flag
         (eliminate (Arrange lst flag))
         lst)))

这可行。但是当列表很长时它会变得非常慢。
我有一个测试:

(define lst (build-list 10000 (lambda (x) (random 10))))
(eliminate lst)

在Drracket(6GB内存，2.3G hz cpu *4)中，根据性能分析，主要耗费的时间有这些:
调用 remove-loop ，11517101 次，花费 49283 毫秒
调用 scan-loop ，2450002 次，花费 121294 毫秒
调用 Arrange ，747 次，花费 713182 毫秒
调用 eliminate，748 次，花费 130611 毫秒

而且在运行过程中，我发现只有一个cpu几乎被100%使用(轮流)。
这个可以多线程运行吗？

而且我认为主要问题是我使用的算法效率低下。我认为它可以真正优化。可能使用动态算法，用一个表来存储每次发生和更新。
如何做到这一点？

非常感谢。

Answer 1

不要在 Dr Racket 中测量结果，因为 IDE 的开销非常高。始终从 shell 执行耗时的计算。

这是我的算法，对于包含 10,000 个元素的列表，该算法的执行时间不到半秒(而您的算法为 9.5 分钟):

(define (remn lst)
  (if (null? lst)
      lst
      (let* ((rlst (reverse lst)) (last (car rlst)))
        (let loop ((left null) (curn 0) (rght (reverse (cdr rlst))))
          (if (null? rght)
              (append (reverse left) (list last))
              (let ((e (car rght)))
                (if (equal? e last)
                    (if (= curn 1)
                        (remn (append (reverse (cdr left)) (cdr rght)))
                        (loop (cons e left) (add1 curn) (cdr rght)))
                    (loop (cons e left) 0 (cdr rght)))))))))

例子:

> (remn '(1 5 3 3 2 2 4 3 2))
'(1 5 4)
> (remn '(1 3 3 2 2))
'(1 3 3 2 2)
> (remn '(1 1 3 3 3 3 3 1))
'(3 3)