лучше быстрая схема функции?

Question

Таким образом, для нахождения максимального элемента в списке требуется сложность времени O (n) (если в списке есть n элементов). Я попытался реализовать алгоритм, который выглядит быстрее.

(define (clever-max lst) 
    (define (odd-half a-list) 
    (cond ((null? a-list) (list)) 
      ((null? (cdr a-list)) 
      (cons (car a-list) (list))) 
      (else 
      (cons (car a-list) 
       (odd-half (cdr (cdr a-list))))))) 
    (define (even-half a-list) 
    (if (null? a-list) 
     (list) 
     (odd-half (cdr a-list)))) 
    (cond ((null? lst) (error "no elements in list!")) 
     ((null? (cdr lst)) (car lst)) 
     (else 
     (let ((l1 (even-half lst)) 
       (l2 (odd-half lst))) 
      (max (clever-max l1) (clever-max l2)))))) 

Действительно ли это происходит быстрее? Что бы вы сказали, асимптотическая временная сложность (жесткая привязка)?

Answer 1

Учитывая список данных, о которых вы ничего не знаете, нет возможности найти максимальный элемент без изучения каждого элемента и, следовательно, время O(n), потому что, если вы его не проверите, вы можете его пропустить. Так что нет, ваш алгоритм не быстрее, чем O(n), это фактически O(n log n), поскольку вы в основном просто запускаете сортировку слияния.

Здесь больше данных на Selection problem

Я думал об этом и понял, что я должен, вероятно, сделать что-то немного больше, чем просто указать это как факт. Поэтому я закодировал быстрый тест скорости. Теперь полное раскрытие, я не программист Схемы, так что это в Common Lisp, но я думаю, что я верно преобразовал ваш алгоритм.

;; Direct "iteration" method -- theoretical O(n) 
(defun find-max-001 (list) 
    (labels ((fm (list cur) 
      (if (null list) cur 
       (let ((head (car list)) 
        (rest (cdr list))) 
       (fm rest (if (> head cur) head cur)))))) 
    (fm (cdr list) (car list)))) 

;; Your proposed method 
(defun find-max-002 (list) 
    (labels ((odd-half (list) 
      (cond ((null list) list) 
        ((null (cdr list)) (list (car list))) 
        (T (cons (car list) (odd-half (cddr list)))))) 
      (even-half (list) 
      (if (null list) list (odd-half (cdr list))))) 
    (cond ((null list) list) 
      ((null (cdr list)) (car list)) 
      (T (let ((l1 (even-half list)) 
        (l2 (odd-half list))) 
       (max (find-max-002 l1) (find-max-002 l2))))))) 

;; Simplistic speed test    
(let ((list (loop for x from 0 to 10000 collect (random 10000)))) 
    (progn 
    (print "Running find-max-001") 
    (time (find-max-001 list)) 
    (print "Running find-max-002") 
    (time (find-max-002 list)))) 

Теперь вы можете спросить себя, почему ваш вы я только использую 10000 для размера списка, потому что на самом деле, что довольно мало для асимптотических расчетов. Истина заключается в том, что sbcl признает, что первая функция является хвостовой рекурсивной и, следовательно, абстрагирует ее в цикле, тогда как она не со второй, так что она настолько велика, насколько я мог бы получить, не убивая мой стек. Хотя, как видно из приведенных ниже результатов, это достаточно просто, чтобы проиллюстрировать суть.

"Running find-max-001" 
Evaluation took: 
    0.000 seconds of real time 
    0.000000 seconds of total run time (0.000000 user, 0.000000 system) 
    100.00% CPU 
    128,862 processor cycles 
    0 bytes consed 

"Running find-max-002" 
Evaluation took: 
    0.012 seconds of real time 
    0.012001 seconds of total run time (0.012001 user, 0.000000 system) 
    [ Run times consist of 0.008 seconds GC time, and 0.005 seconds non-GC time. ] 
    100.00% CPU 
    27,260,311 processor cycles 
    2,138,112 bytes consed 

Даже на этом уровне мы говорим об огромном замедлении. Он увеличил примерно до миллиона предметов до прямой проверки каждого элемента, как только метод замедляется до оценки 10k вашего алгоритма.

(let ((x (loop for x from 0 to 1000000 collect (random 1000000)))) 
    (time (find-max-001 x))) 

Evaluation took: 
    0.007 seconds of real time 
    0.008000 seconds of total run time (0.008000 user, 0.000000 system) 
    114.29% CPU 
    16,817,949 processor cycles 
    0 bytes consed 

Заключительные мысли и выводы

Так что следующий вопрос, который нужно задать почему второй алгоритм действительно принимает, что гораздо больше. Не вдаваясь в подробности о tail recursion elimination, есть несколько вещей, которые действительно выпрыгивают.

Первый номер cons. Теперь да, cons - O(1), но это еще одна операция для прохождения системы. И это требует, чтобы система выделяла и освобождала память (приходится запускать сборщик мусора). Вторая вещь, которая действительно выпрыгивает, состоит в том, что вы в основном используете сортировку слияния, за исключением того, что вместо того, чтобы просто захватывать нижнюю и верхнюю половину списка, вы захватываете четные и нечетные узлы (это также займет больше времени, потому что вы должны итерации каждый время для создания списков). Что у вас здесь есть алгоритм O(n log n) в лучшем случае (помните, что это сортировка слияния, которая действительно хороша для сортировки), но она несет много дополнительных накладных расходов.