Clojure Суммирование элементов списка между максимумом и минимумом

@Catstail · Регистрация: 12.02.2012

Студворк — интернет-сервис помощи студентам

Дан список целых, в котором ровно один максимум и один минимум (но располагаться они могут где угодно). Вычислить сумму положительных элементов, расположенных между ними (без включения).

Вот мое решение:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defun sum-min-max (lst)
  (let ((min (car lst)) (pmin 0) (max (car lst)) (pmax 0))
       (iter (for i in lst) (for p from 0 to (- (length lst) 1))
             (when (> i max) (setq max i pmax p))
             (when (< i min) (setq min i pmin p)))
       (apply '+ (remove-if 'minusp (subseq lst (+ 1 (min pmin pmax)) (max pmin pmax))))))
 
 
==> sum-min-max
 
(sum-min-max '(1 2 -3 1 2 7 4 10 2))
 
==> 14
 
(sum-min-max '(1 2 10 1 2 7 4 -3 2))
 
==> 14

@korvin_ · 31.03.2014, 20:22

Сообщение от Catstail

И, похоже, не компилирует LW (по крайней мере мой)

В REPL'е не компилирует, но достаточно вызвать

Lisp
1
(compile 'func)

@helter · 31.03.2014, 20:34

Сообщение от Catstail

А Вы в SBCL работаете?

По настроению, но в нём удобно замеры времени производить, потому что не надо отдельно компилировать (он всё и всегда компилирует).

@korvin_ · 31.03.2014, 21:20

И так.

Lisp
1
2
3
4
5
6
7
8
9
10
(defun f-reduce ()
  (dotimes (i 10000 'ok)
    (reduce #'+ *z*)))
 
(defun f-apply ()
  (dotimes (i 10000 'ok)
    (apply #'+ *z*)))
 
(compile 'f-reduce)
(compile 'f-apply)

LispWorks:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defvar *z* (loop :for i :downfrom call-arguments-limit :to 1 :collect i)) ; 2047..1
 
(time (f-reduce))
; Timing the evaluation of (F-REDUCE)
; User time    =        1.446
; System time  =        0.006
; Elapsed time =        1.436
; Allocation   = 92752 bytes
; 0 Page faults
 
(time (f-apply))
; Timing the evaluation of (F-APPLY)
; User time    =        0.232
; System time  =        0.000
; Elapsed time =        0.224
; Allocation   = 82556 bytes
; 6 Page faults
OK

ClozureCL:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defvar *z* (loop :for i :downfrom call-arguments-limit :to 2 :collect i)) ; 65536..2
 
(time (f-reduce))
; (F-REDUCE)
; took 14,593,245 microseconds (14.593245 seconds) to run.
; During that period, and with 4 available CPU cores,
;      14,649,743 microseconds (14.649743 seconds) were spent in user mode
;          12,817 microseconds ( 0.012817 seconds) were spent in system mode
;  1,071 minor page faults, 1 major page faults, 0 swaps.
; OK
 
(time (f-apply))
; (F-APPLY)
; took 2,206,766 microseconds (2.206766 seconds) to run.
; During that period, and with 4 available CPU cores,
;      2,219,695 microseconds (2.219695 seconds) were spent in user mode
;          2,955 microseconds (0.002955 seconds) were spent in system mode
;  4 minor page faults, 0 major page faults, 0 swaps.
; OK

снова ClozureCL:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defvar *z* (loop :for i :downfrom 2047 :to 1 :collect i)) ; 2047..1
 
(time (f-reduce))
; (F-REDUCE)
; took 458,997 microseconds (0.458997 seconds) to run.
; During that period, and with 4 available CPU cores,
;      467,767 microseconds (0.467767 seconds) were spent in user mode
;          374 microseconds (0.000374 seconds) were spent in system mode
; OK
 
(time (f-apply))
; (F-APPLY)
; took 70,255 microseconds (0.070255 seconds) to run.
; During that period, and with 4 available CPU cores,
;      80,730 microseconds (0.080730 seconds) were spent in user mode
;         369 microseconds (0.000369 seconds) were spent in system mode
; OK

Обратите внимание, что константа call-arguments-limit в LW и CCL имеет разные по смыслу значения, поэтому в CCL список нужно делать на один элемент короче, чем значение этой константы, иначе получим ошибку при вызове.

Добавлено через 2 минуты

Сообщение от helter

По настроению, но в нём удобно замеры времени производить, потому что не надо отдельно компилировать (он всё и всегда компилирует).

Я в LispWorks сразу создаю буфер, а там уж можно и сразу компилировать (в примере выше добавил вызовы compile, чтобы в REPL удобней вставлять было, если кому понадобится), так удобней код редактировать и копипастить его куда-нибудь. В REPL'е только вызовы делаю по необходимости.

Добавлено через 29 минут

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
(defvar *z* (loop :for i :downfrom call-arguments-limit :to 1 :collect i))
 
(defmacro repeat (n form)
  (let ((i (gensym)))
    `(dotimes (,i ,n nil)
       ,form)))
 
(defparameter *n* 100000)
 
(defun f-apply ()
  (repeat *n* (apply #'+ *z*)))
 
(defun f-sum-list-1 ()
  (repeat *n* (sum-list-1 *z*)))
 
(defun f-sum-list-2 ()
  (repeat *n* (sum-list-2 *z*)))
 
(defun sum-list-1 (xs)
  (loop :for x :in xs :sum x))
 
(defun sum-list-2 (xs)
  (let ((sum 0))
    (dolist (x xs sum)
      (incf sum x))))
 
(defun main ()
  (time (f-apply))
  (time (f-sum-list-1))
  (time (f-sum-list-2)))
 
(main)
 
; Timing the evaluation of (F-APPLY)
; User time    =        1.505
; System time  =        0.005
; Elapsed time =        1.495
; Allocation   = 89584 bytes
; 0 Page faults
 
; Timing the evaluation of (F-SUM-LIST-1)
; User time    =        1.115
; System time  =        0.003
; Elapsed time =        1.112
; Allocation   = 12264 bytes
; 0 Page faults
 
; Timing the evaluation of (F-SUM-LIST-2)
; User time    =        0.899
; System time  =        0.004
; Elapsed time =        0.897
; Allocation   = 10328 bytes
; 0 Page faults

@Catstail · 31.03.2014, 21:42 **[ТС]**

korvin_, исчерпывающе!

@helter · 31.03.2014, 21:51

korvin_, вы можете для сравнения сделать тест для reduce #'(lambda (x y) (+ x y))?

@korvin_ · 01.04.2014, 07:24

helter,

Lisp
1
2
3
4
5
6
7
8
9
(defvar *z* (loop :for i :downfrom 2047 :to 1 :collect i))
 
(defun f-reduce-lambda ()
  (dotimes (i 10000 'ok)
    (reduce #'(lambda (x y) (+ x y)) *z*)))
 
(compile 'f-reduce-lambda)
 
(time (f-reduce-lambda))

LW:

Lisp
1
2
3
4
5
; User time    =        0.256
; System time  =        0.000
; Elapsed time =        0.250
; Allocation   = 78036 bytes
; 1 Page faults

CCL:

Lisp
1
2
3
4
; took 175,730 microseconds (0.175730 seconds) to run.
; During that period, and with 4 available CPU cores,
;      177,810 microseconds (0.177810 seconds) were spent in user mode
;          181 microseconds (0.000181 seconds) were spent in system mode

Новые блоги и статьи Все статьи Все блоги /
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .

@Catstail Супер-модератор 38212 / 21145 / 4313 Регистрация: 12.02.2012 Сообщений: 34,759 Записей в блоге: 14
	31.03.2014, 21:42 [ТС]
	korvin_, исчерпывающе! 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	31.03.2014, 21:51
	korvin_, вы можете для сравнения сделать тест для reduce #'(lambda (x y) (+ x y))? 0