LINUX.ORG.RU

Racket Scheme. Разделить каждый элемент первого списка на каждый элемент второго списка.

 ,


3

4

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


Ответ на: комментарий от stzky

Теперь возник новый вопрос, как сделать так, что в ответе были результаты деления двух списков и они же, но уже со знаком минус. Т.е, если результат деления списка на список (1 2 3 6), то мне надо, чтобы на выходе было как-то так (1 2 3 6 -1 -2 -3 -6).

stzky ()
Ответ на: комментарий от no-such-file

Декартово произведение? В рэкете нет cartesian-product?

Гугл говорит, что есть https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._cartesian-product%29%29

Потом каждую пару-список поделить

Американцы «Поехали!»

anonymous ()
(define xs '(1 2 3))
(define ys '(3 2 1))

;; divide all the elements of xs by all the elements of ys
(define cartesian-division
  (lambda (xs ys)
    (flatten (map (lambda (x)
                    (map (lambda (y)
                           (/ x y)) ys)) xs))))

;; negate all the elements of xs and append them to xs
(define negate-and-append
  (lambda (xs)
    (let ((negated-xs (map - xs)))
          (append xs negated-xs))))

(negate-and-append (cartesian-division xs ys))

Неужели в наших вузах где-то учат лиспам?

Nervous ★★★★★ ()
Последнее исправление: Nervous (всего исправлений: 2)
Ответ на: комментарий от stzky

Судя по этой реализации, декартово произведение вообще не нужно, тупо поэлементное деление. Если списки неодинаковой длины, лишние элементы добавляются в результат как есть.

Учитывая, что map в ракете не умеет в списки разной длины, рекурсивное решение выглядит вполне по-царски.

Nervous ★★★★★ ()
Последнее исправление: Nervous (всего исправлений: 3)
Ответ на: комментарий от Nervous

Все там есть.

cartesian-division

Даже есть «декартово деление»! Сам придумал, иль кто подсказал?

Лучше бы написал (define cartesian-product-1 (lambda (product-func xs ys) ... )), где product-func будет собирать «произведение»: умножать, делитьб соединять и тд и тп.

anonymous ()
Ответ на: комментарий от anonymous

А для произвольного количества списков?

Трах-тибидох!

(define cartesian-product-2
  (lambda (f xs ys . rest)
    (map (lambda (pair)
           (apply f pair))
         (apply cartesian-product
                (append (list xs ys) rest)))))
(cartesian-product '(1 2) '(3 4) '(5 6))
;; => '((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

(cartesian-product-2 max '(1 2) '(3 4) '(5 6))
;; => '(5 6 5 6 5 6 5 6)
Nervous ★★★★★ ()
Последнее исправление: Nervous (всего исправлений: 1)
Ответ на: комментарий от anonymous

Теперь пулл-реквест рэкетирам на «правильную» версию декартово произведения.

Я думал, теперь будет «снять ограничение на минимум два списка» %) А то

(cartesian-product)
;; => '(())

Но на сегодня магия иссякла.

Nervous ★★★★★ ()
Последнее исправление: Nervous (всего исправлений: 1)
Ответ на: комментарий от Nervous

Я думал, теперь будет «снять ограничение на минимум два списка»

В ходе обсуждения пул-реквеста договоритесь, что и как должно быть там внутрях.

anonymous ()
Ответ на: комментарий от no-such-file

Декартово произведение

Не эффективно.

Ты не лиспер. Лиспер не думает про эффективность, он думает по эффектность. Про эффективность пусть «компилятор» думает, чай не только хвостовые рекурсии умеет оптимизировать.

Если всё таки нужна эффективность, я уже предложил написать «правильную» версию декартово произведения.

anonymous ()
Ответ на: комментарий от no-such-file

Тру-лисп это хаки уровня Си+ассемблер.

Это макрос/дсл на макросе/дсле макросом/дслем погоняет. ДСЛем вполне может быть эффектная пародия на какой-нибудь хацкерский язык.

anonymous ()
Ответ на: комментарий от Nervous

обобщенную эффективность

Перевожу с русского на русский - «эффектность».

Нет обощенной эффективности. Есть конкретный результат за определенные потраченные ресурсы. И зависит от того какой результат нужен, и какие есть ресурсы.

Личный вопрос, раз тема уже съехала: ты случаем не «эффективный менеджер»?

anonymous ()
Ответ на: комментарий от anonymous

Нет обощенной эффективности. Есть конкретный результат за определенные потраченные ресурсы.

Ну как нет. Алгоритм с вычислительной сложностью О(n) в общем случае эффективнее алгоритма со сложностью O(n!), не так ли? Но в каждом конкретном случае могут быть свои нюансы.

ты случаем не «эффективный менеджер»

С какой целью интересуешься?

Nervous ★★★★★ ()
Ответ на: комментарий от Nervous

обобщенную эффективность

такого не существует. на gpu эффективно совсем другое чем однопоточная поделка, которую обычно лепят для код гольфа и её нужно будет полностью переделывать

anonymous ()
Ответ на: комментарий от anonymous

О-нотация - это не про общий случай

Когда я говорю «в общем случае», я имею в виду «для всех алгоритмов с одинаковой сложностью независимо от конкретной реализации (константы, множители и прочее)». Для всех алгоритмов с вычислительной сложностью O(n) затраты времени растут медленнее, чем для О(n!) -> такие алгоритмы в общем случае (для любой выбранной пары конкретных алгоритмов) эффективнее. Эн факториал с ростом n рано или поздно всосет.

Успеет ли этот момент наступить в конкретном юзкейсе (частном случае) — это уже совсем другой вопрос.

Nervous ★★★★★ ()
Последнее исправление: Nervous (всего исправлений: 1)
Ответ на: комментарий от anonymous

на gpu эффективно совсем другое чем однопоточная поделка

Открытие века — на нескольких вычислителях иногда можно посчитать быстрее, чем на одном.

Это ведь не значит, что О(n!) в конце концов не всосет у О(n) на одном и том же вычислителе — хоть на GPU, хоть на чем, не так ли? %)

Nervous ★★★★★ ()
Ответ на: комментарий от Nervous

Когда я говорю «в общем случае», я имею в виду «…»

Подмена цели.

Для всех алгоритмов с вычислительной сложностью O(n)

О-нотация - это всего лишь одно из отображений сложности алгоритма. У тебя еще более частный случай - сложность по времени работы алгоритма.

растут медленнее -> эффективнее

Помена «общей» цели конкретной.

Если хочешь более математично говорить про эффективность, то думаю надо перейти к задаче оптимизации, где над некоторой конкретной областью задается целевая функция и ищется экстремум. И как часто бывает - ищется локальный экстремум, что еще больше отдаляет от «общего случая».

anonymous ()
Ответ на: комментарий от Nervous

Когда я говорю «в общем случае», я имею в виду «для всех алгоритмов с одинаковой сложностью независимо от конкретной реализации (константы, множители и прочее)». Для всех алгоритмов с вычислительной сложностью O(n) затраты времени растут медленнее, чем для О(n!) -> такие алгоритмы в общем случае (для любой выбранной пары конкретных алгоритмов) эффективнее. Эн факториал с ростом n рано или поздно всосет.

Только с математической точки зрения. Вот есть алгоритм Копперсмита—Винограда. Умножает матрицы с вычислительной сложностью O(n^2.3755). Но для всех применяемых случаев умножения матриц он медленнее. «Рано или поздно» для него наступает только когда размеры матриц превышают терабайты.

monk ★★★★★ ()
Ответ на: комментарий от monk

А как бы здесь помог zip? Он каждый с каждым не сопоставляет.

>>> a = [1, 2, 3, 4, 5]
>>> b = [6, 7, 8, 9]
>>> list(map(lambda x: x[0]/x[1], (zip(a,b))))
[0.16666666666666666, 0.2857142857142857, 0.375, 0.4444444444444444]

upd:

Ему не поэлементно надо, а все перестановки

ууу, я тред не читал

upd2:

хорошо, когда есть стандартные библиотеки

>>> from itertools import product
>>> a = [1, 2, 3, 4, 5]
>>> b = [6, 7, 8, 9]
>>> c = list(map(lambda x: x[0]/x[1], (product(a,b))))
>>> len(a)
5
>>> len(b)
4
>>> len(c)
20
>>> c
[0.16666666666666666, 0.14285714285714285, 0.125, 0.1111111111111111, 0.3333333333333333, 0.2857142857142857, 0.25, 0.2222222222222222, 0.5, 0.42857142857142855, 0.375, 0.3333333333333333, 0.6666666666666666, 0.5714285714285714, 0.5, 0.4444444444444444, 0.8333333333333334, 0.7142857142857143, 0.625, 0.5555555555555556]

https://github.com/python/cpython/blob/2b201369b435a4266bda5b895e3b615dbe28ea6e/Modules/itertoolsmodule.c#L2094 прям видно, что ребята старались. Сразу выделяют под весь результат память и фигачат перебором.

melkor217 ★★★★★ ()
Последнее исправление: melkor217 (всего исправлений: 6)
Ответ на: комментарий от melkor217

list(map(lambda x: x[0]/x[1], (zip(a,b))))

#lang racket
(define a '(1 2 3 4 5))
(define b '(6 7 8 9))
(for/list ([x a] [y b]) (/ x y))
; => '(1/6 2/7 3/8 4/9)

Если очень хочется можно и zip

#lang racket
(require srfi/1)
(define a '(1 2 3 4 5))
(define b '(6 7 8 9))
(map (curry apply /) (zip a b))

Или даже

#lang python
a = [1, 2, 3, 4, 5]
b = [6, 7, 8, 9]

> map(lambda x: x[0]*1.0/x[1], zip(a,b))
[0.16666666666666666, 0.2857142857142857, 0.375, 0.4444444444444444]
monk ★★★★★ ()
Ответ на: комментарий от monk

Чем дольше я читаю тред, тем меньше понимаю, что хочет ТС :(

Я, конечно, в Racket Scheme ни ногой, но просто интересно понять, из какой серии вопрос - об идее алгоритма, синтаксических конструкциях схемы, библиотечных функциях или о чём-то ещё.

melkor217 ★★★★★ ()
Последнее исправление: melkor217 (всего исправлений: 1)
Ответ на: комментарий от melkor217

Шо, в Scheme не придумали zip?

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

anonymous ()

xорошо когда нет залитых эпоксидкой «функциональных» библиотек

(define (pa/pb la lb)
  (define (rec r e l)
    (if (null? l)
	r
	(rec (cons (/ e (car l)) r)
	     e
	     (cdr l)
	     )
	)
    )
  (define (rec* r a)
    (if (null? a)
	(reverse r)
       	(rec* (rec r (car a) lb)
	      (cdr a)
	      )
	    )
	)
  (rec* '() la)
  )
> (begin
   (define r (pa/pb '(1 2 3 4 5) '(6 7 8 9)))
   (display (length r)) (newline)
   r)

20
(1/6 1/7 1/8 1/9 1/3 2/7 1/4 2/9 1/2 3/7 3/8 1/3 
2/3 4/7 1/2                                     
     4/9 5/6 5/7 5/8 5/9)
anonymous ()
Ответ на: комментарий от melkor217

Python вообще классный язык, мне очень «нравится».

Бог с ним с лямбдами, кому нужна эта лапша.

А как расширить стек под рекурсию(?) - очень просто - нужно всего лишь пересобрать интерпретатор.

А стоит ли писать рекурсивно или банально абстрагировать на функциях(?)- конечно не стоит - результата вычислений можно просто не дождаться.

anonymous ()
Ответ на: комментарий от anonymous

Как по мне, размер стека вызовов не должен зависеть от размерности задачи (а должен только от алгоритма). Если очень нужно - заводишь стек на куче (если речь про питон, то там вроде лист для этого сгодится) и хранишь в нём узлы твоей структуры (а не фреймы). Что касается рекурсии, то это просто математический трюк, он не был придуман специально для компьютеров и является далеко не единственной вещью, которая плохо ложится на модель вычислений в мейнстримных процессорах. Ты же не будешь пересобирать питон, чтобы сделать числа по 256 бит, например?

dsxl ()
Ответ на: комментарий от dsxl

Если очень нужно - заводишь стек на куче (если речь про питон, то там вроде лист для этого сгодится) и хранишь в нём узлы твоей структуры (а не фреймы).

ну правильно, через явный стек, яж говорю - весело.

А что было придумано специально для компьютеров? Машина Тьюринга, как модель? Рекурсия очевидна как абстракция композиции, и там где диктуется - компилятор все ожидаемо оптимизирует, не дороже цикла в лоб.

anonymous ()
Ответ на: комментарий от anonymous

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

А что было придумано специально для компьютеров

Вычислительная математика.

dsxl ()
Ответ на: комментарий от dsxl

Это часть гарантированной семантики(в том числе и в реализации) так что от хорошей. Что может быть сложного в тупом хвостовом вызове? Это синтактически даже ближе к goto, чем формы всяких циклов.

вычислительная математика

ну тогда лучше взять фортран, в нем даже функционально красивее будет чем в питоне.

anonymous ()
Ответ на: комментарий от dsxl

Совершенно очевидно, что компилятор это оптимизирует только в функциональных языках без циклов, а не от хорошей жизни.

Очень давно оптимизирует в большинстве компиляторов Common Lisp, хотя циклы там есть. Современный GCC тоже оптимизирует.

monk ★★★★★ ()