LINUX.ORG.RU

lisp & большие списки данных


0

0

slime+sbcl
Вот простая ф-ция:

(setf MAS ()
      N 1000000))
  (dotimes (i N)
    (setf MAS (nconc MAS (list i))))

Всё работает, создаётся. Но при увиличении N ~ > 1000000 выдаёт на
любые дальнейшие действия:
;pipelined request..., (swank:interactive-eval "...")
ЭЭто что значит? Зависон? И как тогда работать с большими объёмами ?
anonymous

Re: lisp & большие списки данных

> Это что значит? Зависон?

Вроде того. У меня методично в фоне колбасит без лишних слов.

> И как тогда работать с большими объёмами ?

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

watashiwa_daredeska ★★★★ ()
Ответ на: Re: lisp & большие списки данных от watashiwa_daredeska

Re: lisp & большие списки данных

> Попытайся подумать, что происходит в цикле

Ну да. Поменял местами
(dotimes (i 1000000)
    (setf MAS (nconc (list i) MAS)))
Всё ОК.

Но вот не понятно почему виснит такой подход: ???
(setf MAS (make-list 1000000 :initial-element 0))
(dotimes (i 1000000)
  (setf (nth i MAS1) i))
Просто перебор эл-ов массива.......

Ну и вопрос остаётся в силе - как правильно (в смысле скорости и 
оптимальности) работать с большими объёмами данных ? Желательно
на примере, например, инициализация списка от 0 до N-1, где 
N > 1000000.

anonymous ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

> Ну да. Поменял местами

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

> Просто перебор эл-ов массива.

Почитай элементарные определения. Список != массив. Время доступа к
n-му элементу массива - O(1), а к n-му элементу списка - O(n).

> Желательно на примере, например, инициализация списка от 0 до N-1

(defvar mas nil)
(defvar n 100)

;; Инициализация "в лоб"
(let ((tmp nil))
  (dotimes (i n)
    (let ((new (cons i nil)))
      (if tmp
          (rplacd tmp new)
          (setf mas new))
      (setf tmp new))))

;; DEBUG
(print mas) ; Лучше не делать этого, если n велико
(setf mas nil)

;; Инициализация "задом наперед"
(dotimes (i n)
  (setf mas (cons (- n i 1) mas)))

;; DEBUG
(print mas) ; Лучше не делать этого, если n велико

watashiwa_daredeska ★★★★ ()
Ответ на: Re: lisp & большие списки данных от watashiwa_daredeska

Re: lisp & большие списки данных

> В этом случае, ты создаешь список в обратном порядке...

Это да, но это и ускоряет процесс, т.к. к списку (большому) добавляется число, а не наоборот, как я сразу сделал.

anonymous ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

> т.к. к списку (большому) добавляется число, а не наоборот, как я сразу сделал.

Можно делать и так и так, но тогда надо держать ссылку на хвост списка для скорости.

Вот, кстати, еще вариант:

(setf mas (loop for i below n collect i))

watashiwa_daredeska ★★★★ ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

Нашута тебе такой список??? Обычно при таких количествах данных
 чисто алгоритмически намного удобнее использовать массив. 

(time (let ((x nil)) (dotimes (n 100000) (setq x (cons n x)))))
Real time: 0.333217 sec.
Run time: 0.288018 sec.
Space: 800808 Bytes
NIL
[1]> (time (let ((x nil)) (dotimes (n 1000000) (setq x (cons n x)))))
Real time: 3.999284 sec.
Run time: 3.016188 sec.
Space: 8000776 Bytes
GC: 8, GC time: 0.316022 sec.
NIL

reverse например на таком списке уже не реально.

bugmaker ★★★★☆ ()
Ответ на: Re: lisp & большие списки данных от bugmaker

Re: lisp & большие списки данных

У меня на лимоне так:
Evaluation took:
  0.014 seconds of real time
  0.004001 seconds of user run time
  0.008001 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  8,003,584 bytes consed.

Почему такая разница (3.999284 sec. и 0.014 seconds of real time) ?
Проц - p-4 3Ghz

anonymous ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

У меня это был clisp и цел-1.7, видимо поэтому. 
clisp для несложных вещей, не требующих скорости,
я нахожу более юзабельным, поэтому пользуюсь им часто.
На sbcl 1.0.5 несколько более другой результат:

* (time (let ((x nil)) (dotimes (n 1000000) (setq x (cons n x)))))

Evaluation took:
  0.134 seconds of real time
  0.060004 seconds of user run time
  0.044003 seconds of system run time
  [Run times include 0.072 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  7,999,488 bytes consed.
NIL
* 

bugmaker ★★★★☆ ()
Ответ на: Re: lisp & большие списки данных от bugmaker

Re: lisp & большие списки данных

Или так:

* (declare (optimize (speed 3) (safety 0) (debug 0)))

NIL
* (time (let ((x nil)) (dotimes (n 1000000) (setq x (cons n x)))))

Evaluation took:
  0.024 seconds of real time
  0.024002 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  7,995,392 bytes consed.
NIL
* 

bugmaker ★★★★☆ ()
Ответ на: Re: lisp & большие списки данных от bugmaker

Re: lisp & большие списки данных

А вот поработал я с большим списком (массивом), как сейчас освободить эту память, не выходя из sbcl ?

И ещё - при создани списка при помощи dotime и nconc, кроме результирующего списка память не на что больше не жрётся ? А то у меня должно по подсчётам затратиться ~30MB, а реально ~70MB...

anonymous ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

> А вот поработал я с большим списком (массивом), как сейчас освободить эту память, не выходя из sbcl ?

(setq var nil). var - переменная, в которой список. Если несколько, нужно поступить так со всеми. Если на список не будет ссылок, сборщик помойки его соберёт.

> И ещё - при создани списка при помощи dotime и nconc, кроме результирующего списка память не на что больше не жрётся ?

Почему не должна? Элемент списка состоит из самого значения и указателя на следущий элемент. Указатель не в острале хранится, к сожелению :(

bugmaker ★★★★☆ ()
Ответ на: Re: lisp & большие списки данных от bugmaker

Re: lisp & большие списки данных

> (setq var nil)...

Ну я так и делал - нифига не освобождается... Указателей больше - нет! проверил! Можно ли как-то явно указать GC, что почистить ?

anonymous ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

А как проверял? Шаманство с gc в стандарт не входит, смотри по руководству к имплементации, которой пользуешся. ИМХО правильнее было бы implementation-dependend функциями выяснить, на куда израсходовалась память и почему не освобождается.

bugmaker ★★★★☆ ()
Ответ на: Re: lisp & большие списки данных от bugmaker

Re: lisp & большие списки данных

> А как проверял?

Запускаю slime, смотрю память. Создал список, указатель MAS только,
смотрю память - 70MB съело. (setf MAS ()), смотрю память не
освободило. (quit) - освободилось.
> правильнее было бы implementation-dependend функциями выяснить

А подробнее можно ? implementation-dependend функциями ???

anonymous ()
Ответ на: Re: lisp & большие списки данных от anonymous

Re: lisp & большие списки данных

> А подробнее можно ? implementation-dependend функциями ???

А чё подробно? Я же уже, смотри в руководстве по имплементации, которую используеш.

bugmaker ★★★★☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.