[room] Вопрос по Lisp

[Денис Смирнов]

On Sat, Jan 27, 2007 at 02:28:26PM +0300, Alexey Voinov wrote:

AV> Не, ты не понимаешь. :) Тупо - это вот так  (используем srfi-1):
AV> (define (trim-zeroes-right data)
AV>   (reverse (drop-while zero? (reverse data)))

Гм. Логично. В описании к тому же nyquist я почему-то drop-while не нашел
:-/

AV> Здесь по сути два полных прохода по списку и один проход только по
AV> нулям в хвосте. Памяти требует немного (оно tail-recursive).
AV> Можно это сократить до гарантированных двух проходов, за счёт
AV> несколько более громоздкого кода:
AV> (define (trim-zeroes-right data)
AV>   (let loop ((data   data)
AV>              (result '())
AV>              (zeroes '()))
AV>     (cond ((null? data)       (reverse result))
AV>           ((zero? (car data)) (loop (cdr data)
AV>                                     result
AV>                                     (cons 0 zeroes)))
AV>           ((null? zeroes)     (loop (cdr data)
AV>                                     (cons (car data) result)
AV>                                     zeroes))
AV>           (else               (loop (cdr data)
AV>                                     (cons (car data)
AV>                                           (append zeroes result))
AV>                                     '())))))

 AV> А если данные к нам приходят вектором, то получаем один проход по
 AV> нулям и одно копирование субвектора (используем srfi-43):

Увы, данные приходят именно что массивом.

Вернее не так. Это на самом деле свертка (convolution). Генерируется
свертка немеряной длины, потом по ней прогоняются фильтры, получается
результирующая свертка. Это array. Нули на конце только увеличивают
длительность работы (да ещё и нелинейно), потому их так важно все
отрезать.

 AV> (define (trim-zeroes-right data)
 AV>   (let loop ((newlen (vector-length data)))
 AV>     (let ((index (- newlen 1)))
 AV>       (cond ((zero? newlen)
 AV>              '#())
 AV>             ((zero? (vector-ref data index))
 AV>              (loop index))
 AV>             (else
 AV>              (vector-copy data 0 newlen))))))
 AV> Т.е. последняя функция осуществляет всего один полный проход по всем
 AV> элементам. В чём оно принципиально отличается от решения на C, я не
 AV> вижу, честно говоря.

Гм. А Кажется  ничем.

Только эту конструкцию я не смог прочитать:

AV>       (cond ((zero? newlen)
AV>              '#())
AV>             ((zero? (vector-ref data index))
AV>              (loop index))
>> Можно ли такое решить на голом лиспе, или нужно таки не выпендриваться и
>> написать на C?
>> ----------------------------------------------------------------------------
>> <Voins> посади дебианщика за alt так он сразу локали сломает! :)))
AV> Это ты специально фортунку со мной в такое письмо вставил? :))

У меня фортунка с модулями ясновидения и телепатии, а также умеет
самостоятельно составлять заклинания вызова :)

-- 
С уважением, Денис

http://freesource.info
----------------------------------------------------------------------------
Мастер достоин того, чтобы ради него купить DVD :)
		-- mithraen in community@