Форум программистов, компьютерный форум, киберфорум
Языки JVM
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.74/19: Рейтинг темы: голосов - 19, средняя оценка - 4.74
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14

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

27.03.2014, 12:39. Показов 4034. Ответов 45
Метки нет (Все метки)

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

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

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
4
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
27.03.2014, 12:39
Ответы с готовыми решениями:

Количество элементов между минимумом и максимумом
Пожалуйста помогите вот с этой задачей!!! Написать программу, которая для целочисленной матрицы 10х20 определяет среднее...

Произведение элементов массива, расположенных между максимумом и минимумом
Добый день. Подскажите пожалуйста, что я сдалелал не так. Задание произведение элементов массива, расположенных между максимальным и...

Найти сумму элементов массива между максимумом и минимумом
Дан одномерный массив. Найти сумму элементов между максимумом и минимумом

45
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
30.03.2014, 13:46  [ТС]
Студворк — интернет-сервис помощи студентам
transformator.t, вот! У apply есть ограничение на длину списка параметров. А если за это ограничение не заходить, будет ли у reduce преимущество перед apply?
0
defun
603 / 617 / 44
Регистрация: 30.04.2011
Сообщений: 702
30.03.2014, 15:20
Catstail, мне достаточно того, что reduce просто работает =)
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
30.03.2014, 15:24
Цитата Сообщение от Catstail Посмотреть сообщение
У apply есть ограничение на длину списка параметров. А если за это ограничение не заходить, будет ли у reduce преимущество перед apply?
Вот, интересный вопрос.

SBCL

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
54
55
56
57
58
(defvar *z*)
(setq *z* (loop for i downfrom 30000 to 1 collect i))
;;;; REPL
CL-USER>
(time (dotimes (k 10000 'ok) (reduce #'+ *z*)))
Evaluation took:
  20.736 seconds of real time
  20.697293 seconds of total run time (20.637290 user, 0.060003 system)
  [ Run times consist of 1.664 seconds GC time, and 19.034 seconds non-GC time. ]
  99.81% CPU
  49,652,510,688 processor cycles
  4,799,857,968 bytes consed
  
OK
CL-USER> 
(time (dotimes (k 10000 'ok) (reduce '+ *z*)))
Evaluation took:
  23.909 seconds of real time
  23.857491 seconds of total run time (23.745484 user, 0.112007 system)
  [ Run times consist of 0.932 seconds GC time, and 22.926 seconds non-GC time. ]
  99.78% CPU
  57,252,075,200 processor cycles
  4,799,860,736 bytes consed
  
OK
CL-USER> 
(time (dotimes (k 10000 'ok) (apply #'+ *z*)))
Evaluation took:
  4.028 seconds of real time
  4.068254 seconds of total run time (3.992249 user, 0.076005 system)
  [ Run times consist of 0.724 seconds GC time, and 3.345 seconds non-GC time. ]
  100.99% CPU
  9,643,945,048 processor cycles
  2,400,000,000 bytes consed
  
OK
CL-USER> 
(time (dotimes (k 10000 'ok) (reduce #'(lambda (x y)
                                         (+ x y)) 
                                     *z*)))
Evaluation took:
  3.664 seconds of real time
  3.660228 seconds of total run time (3.660228 user, 0.000000 system)
  99.89% CPU
  8,773,295,584 processor cycles
  37,776 bytes consed
  
OK
CL-USER> 
(time (dotimes (k 10000 'ok) (loop for i in *z* sum i)))
Evaluation took:
  1.235 seconds of real time
  1.236077 seconds of total run time (1.236077 user, 0.000000 system)
  100.08% CPU
  2,958,274,578 processor cycles
  12,912 bytes consed
  
OK
Выходит, на небольших списках apply #'+ эффективнее reduce #'+. Интересно, надо знать. Почему? Очевидно, потому что #'+ - дорогая функция: принимает много типов, переменное число аргументов. Если число аргументов фиксировать, reduce выигрывает. А мораль сей басни такова: если нужна эффективность, надо использовать loop.
3
Заблокирован
30.03.2014, 16:39
Может создать отдельную тему по применению функций в лиспе, если ее еще нет??? а то тут оффтоп получается?
0
defun
603 / 617 / 44
Регистрация: 30.04.2011
Сообщений: 702
30.03.2014, 16:46
reduce
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
INSOMNIA> (defparameter *lst-10000000*
            (loop repeat 10000000 collect (random 10000000)))
*LST-10000000*
INSOMNIA> (time (reduce #'+ *lst-10000000*))
Evaluation took:
  0.273 seconds of real time
  0.271000 seconds of total run time (0.270000 user, 0.001000 system)
  99.27% CPU
  651,859,789 processor cycles
  416 bytes consed
  
50016422240396
loop
Lisp
1
2
3
4
5
6
7
8
9
10
11
INSOMNIA> (time
           (loop for a in *lst-10000000*
              sum a))
Evaluation took:
  0.070 seconds of real time
  0.069000 seconds of total run time (0.069000 user, 0.000000 system)
  98.57% CPU
  166,878,886 processor cycles
  0 bytes consed
  
50016422240396
2
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
30.03.2014, 19:13  [ТС]
Цитата Сообщение от helter Посмотреть сообщение
Выходит, на небольших списках apply #'+ эффективнее reduce #'+. Интересно, надо знать. Почему? Очевидно, потому что #'+ - дорогая функция: принимает много типов, переменное число аргументов. Если число аргументов фиксировать, reduce выигрывает. А мораль сей басни такова: если нужна эффективность, надо использовать loop.
- что-то в этом роде я и предполагал... Ведь apply (как мне кажется) это функция, встроенная в ядро. Она и должна быть эффективной.
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
30.03.2014, 21:30
Цитата Сообщение от Catstail Посмотреть сообщение
Ведь apply (как мне кажется) это функция, встроенная в ядро. Она и должна быть эффективной.
Ну и reduce ровно так же встроена в ядро. Разница в количестве вызовов суммирующей функции: apply вызывает её один раз, а reduce вызывает её столько раз, какая длина списка, плюс-минус. Впрочем, я весьма удовлетворён, что в конце концов reduce обошёл apply. Добро победило хак. :P
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
30.03.2014, 21:50  [ТС]
Цитата Сообщение от helter Посмотреть сообщение
Ну и reduce ровно так же встроена в ядро.
- а разве она не на Лиспе реализована?

Цитата Сообщение от helter Посмотреть сообщение
в конце концов reduce обошёл apply
- только за счет ограничения...
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
30.03.2014, 22:12
Цитата Сообщение от Catstail Посмотреть сообщение
- а разве она не на Лиспе реализована?
Это кухня конкретных реализаций, что они через что реализовывают. С точки зрения стандарта между reduce и apply нет юридической разницы.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
30.03.2014, 22:28  [ТС]

Не по теме:


Цитата Сообщение от helter Посмотреть сообщение
нет юридической разницы
- все-таки Вы - юрист в душе



А если так, то понятно, что простая apply сложит быстрее, чем навернутая многофункциональная reduce.
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
30.03.2014, 22:33
Цитата Сообщение от Catstail Посмотреть сообщение
А если так, то понятно, что простая apply сложит быстрее, чем навернутая многофункциональная reduce.
Дык не быстрее. apply: 4.028, reduce: 3.664
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
30.03.2014, 23:17  [ТС]
У меня в LispWorks результат обратный... (см. выше)
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
30.03.2014, 23:19
Цитата Сообщение от Catstail Посмотреть сообщение
У меня в LispWorks результат обратный... (см. выше)
Повторите мои тесты и выложите.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
31.03.2014, 15:01  [ТС]
Цитата Сообщение от helter Посмотреть сообщение
Повторите мои тесты и выложите.
- вот что получается у меня (apply в границах применимости):
Миниатюры
Clojure Суммирование элементов списка между максимумом и минимумом  
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
31.03.2014, 17:51
Я ж говорю: вы мои тесты повторите. reduce выигрывает у apply в том случае, когда не надо применять монструозный + (когда сложение обёртывается лямбдой). И это на самом деле выигрыш. Потому что вокруг apply всё равно придётся писать handler-case.

Кстати, LW сразу компилирует defun-ы?
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
31.03.2014, 18:18  [ТС]
Цитата Сообщение от helter Посмотреть сообщение
когда не надо применять монструозный +
- что означает "монструозный"?
Цитата Сообщение от helter Посмотреть сообщение
Кстати, LW сразу компилирует defun-ы?
- честно говоря, не знаю. Надо разобраться.

Добавлено через 8 минут
Вот мои тесты (LW):

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
CL-USER 3 > (time (dotimes (i 1000 'ok) (apply '+ *z*)))
Timing the evaluation of (DOTIMES (I 1000 (QUOTE OK)) (APPLY (QUOTE +) *Z*))
 
User time    =        0.015
System time  =        0.000
Elapsed time =        0.015
Allocation   = 2688 bytes
0 Page faults
Calls to %EVAL    14053
OK
 
CL-USER 4 > (time (dotimes (i 1000 'ok) (reduce '+ *z*)))
Timing the evaluation of (DOTIMES (I 1000 (QUOTE OK)) (REDUCE (QUOTE +) *Z*))
 
User time    =        0.078
System time  =        0.000
Elapsed time =        0.078
Allocation   = 2688 bytes
0 Page faults
Calls to %EVAL    14053
OK
 
CL-USER 5 > (time (dotimes (i 1000 'ok) (reduce #'(lambda (x y) (+ x y)) *z*)))
Timing the evaluation of (DOTIMES (I 1000 (QUOTE OK)) (REDUCE (FUNCTION (LAMBDA (X Y) (+ X Y))) *Z*))
 
User time    =        1.812
System time  =        0.000
Elapsed time =        1.813
Allocation   = 601031620 bytes
0 Page faults
Calls to %EVAL    1511053
OK
1
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
31.03.2014, 18:20
Цитата Сообщение от Catstail Посмотреть сообщение
что означает "монструозный"?
Это значит "функция, которая может принимать произвольное число аргументов разных типов, и чей вызов поэтому сравнительно дорог".

Компиляция - это существенно, потому что замеры быстродействия имеют смысл только для скомпилированного кода.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
31.03.2014, 18:24  [ТС]
Цитата Сообщение от helter Посмотреть сообщение
Компиляция - это существенно, потому что замеры быстродействия имеют смысл только для скомпилированного кода.
- согласен. И, похоже, не компилирует LW (по крайней мере мой).
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
31.03.2014, 18:26
Интересные тесты. Вот так, SBCL применил какую-то оптимизацию для лямбды, а в LW она как долго считала. Хотя если для LW это интерпретируемый код, то ничего нельзя сказать.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
31.03.2014, 19:07  [ТС]
А Вы в SBCL работаете? Он порождает очень быстрый код. Иногда почти не уступающий сишному.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
31.03.2014, 19:07

Обнуление элементов массива, находящихся между максимумом и минимумом
Создать функцию, которая в массиве обнуляет элементы, находящиеся между максимумом и минимумом.

Найти сумму элементов, стоящих между максимумом и минимумом
Дан массив A(N). Найти сумму элементов стоящих между максимумом и минимумом.

Найти сумму элементов массива, состоящих между максимумом и минимумом
Дан одномерный числовой массив размерности n. Найти сумму элементов, состоящих между максимумом и минимумом. сотировка массива.

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

Найти суму элементов одномерного массива между минимумом и максимумом
Найти суму элементов массива, которые расположены между первыми вхождениями максимального и минимального чисел. Помогите исправить...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Был там один разговор по поводу свободы в материальном мире.
kumehtar 19.08.2026
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .
Когда логика программы не спасает от человеческих ошибок
Maks 18.08.2026
В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .
Лето уходит
kumehtar 17.08.2026
Мысли в слух
kumehtar 17.08.2026
Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега
Maks 17.08.2026
Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .
Саморегулирующийся социальный контракт для сервера cross-section.
Hrethgir 14.08.2026
С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru