[ФП] Примеры работы с БОЛЬШИМИ файлами

>Читать последовательно read'ом в фиксированный буфер? Медленнее будет, я проверял.

Такого просто не может быть. Какой был размер буфера?

Да еще и кода больше получится.

Несколько больше, да.

>Интересно, а как оно SWAP(DBL_MAX,(DBL_MAX/10,0)) сделает?

А как ты себе вообще представляешь операцию присваивания rvalue?

Мальчик теоретик? Попробуй без девайнов делай, флаг в руки. Сам код dcraw используют во многих других проектах и все успешно рефакторят его под свои нужды, причём делает это не только опенсорс. Очень прямо таки мёртвый код.

>А, ну и да. Дебилов, которые посоветуют оставить С++ - не слушай.

дада, они идиоты, пиши на хаскеле, будешь всегда востребован и вообще вмиг уедешь из этой сраной страны, и каждая вторая будете тебе давать, а волосы твои станут мягкие и шелковистые

во-первых, не на хаскеле
во-вторых, ты дебил

обоснуйте, или ты просто пернул в лужу?

Т.е. у нас есть файл, и из него надо получить двумерный массив 32битных беззнаковых целых? Если четче обрисуешь задачу, покажу пример на CL.

Да, именно так, двумерный массив беззнаковых 32-битных целых, лежат «по строкам», размеры заданы. Давай пример на CL, начнём с простого, потом попробуем решить задачки поинтереснее, если не лень.

Ну, тут, в принципе, нормальная маркосистема поможет.

Макросистема? Да, возможно, тут больше толку от полноценных макросов, чем от функционального подхода как такового. Вот, кстати, задачка №2, после чтения массива. В массиве содержится цветное изображение в виде BAYER-паттерна (http://en.wikipedia.org/wiki/Bayer_pattern). Предположим, надо посчитать гистограмму для каждого из каналов. На Си это будет выглядеть так (для массива X*Y):

 // RED
 for (x=1; x < X; x += 2)
  for (y=1; y < Y; y += 2)
   red_hist[image[x][y]]++;

 // GREEN
 for (x=0; x < X; x++)
  for (y=(x+1)%2; y < Y; y += 2)
   green_hist[image[x][y]]++;

 // BLUE
 for (x=0; x < X; x += 2)
  for (y=0; y < Y; y += 2)
   blue_hist[image[x][y]]++;

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

> Не надо в память читать, надо просто использовать mmap.

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

У нас как раз спектрофотометрия (читай - Фурье), идентификация объектов (читай - вейвлеты) и так далее

> переписывай всё на CUDA

Вообще речь шла не об ускорении рассчётов, а об увеличении производительности труда программиста. Но раз уже зашла речь про CUDA, то вопрос: как у ФП-языков дела с CUDA и OpenCL? Удалось найти только ScalaCL, но Sclala тут не подходит по понятным причинам :(

> Там по ссылке 250кб в одном, повторю ещё раз в ОДНОМ, файле феерического быдлокода написанного на мерзком «Pure C» с активным использованием глобальных переменных. Видимо автор считает, что многопотоковые приложения не нужны.

Да, автор абсолютно упоротый чувак, дядька с жизнеутверждающей фамилией Coffin (ололо). Утверждает, что следует идеологии UNIX - поэтому сделал свой dcraw в виде консольной утилиты. На неоднократные просьбы оформить это дело в виде библиотеки посылает всех на три буквы

Но кстати у наших чувачков, которые тоже реализуют BAYER паттерн, код получаеться такой же корявый, хоть они и не копипастили (не совсем). И я решил поисследовать, может это дело в языке Си, и есть возможность сделать поэлегантнее

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

В данном случае это говорит о его любознательности и стремлении к эстетике программного кода :)
У нас нет какого-то одного большого проекта, есть много отдельных задачек. Задачки традиционно решаються на Си, что порождает вышепреведённые шедевры. Поэтому есть возможность опробывать «правильные» технологии на одной маленькой задачке, не будоража весь улей

Во первых заткнись уебок Во вторых еще раз заткнись иначе я тебя выебу в твою сраную жепу.

>А как ты себе вообще представляешь операцию присваивания rvalue?

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

>В массиве содержится цветное изображение в виде BAYER-паттерна

А нельзя ли при выгрузки данных с телескопа сохранить их сразу в более удобном виде?

С которым потом будет приятнее работать.

У нас как раз спектрофотометрия (читай - Фурье), идентификация объектов (читай - вейвлеты) и так далее

Ну так тем более, MIDAS вам в руки. Я, правда, им не пользуюсь (хоть и астрофизик), т.к. у меня другие занятия: проектирование и моделирование аппаратуры, разработка систем управления и удаленного доступа.

как у ФП-языков дела с CUDA и OpenCL?

Пишите на сях. Под CUDA уже есть интересные математические библиотеки. Во всяком случае, для обработки изображений сильно изобретать велосипеды не придется (в смысле - переписывать существующие библиотеки вроде GSL на CUDA).

Кстати, Ignatik, объясните мне, непутевому, как у вас профессиональная ПЗС-камера дает RAW-изображения, да еще цветные о_О? Во-первых, научная матрица цветной быть по-определению не может, а во-вторых, несмотря на то, что у каждого ПЗС-контроллера свои протоколы, все полученные данные обычно хранят в FITS-файлах.

Или вы просто щелкаете картинки с телескопа на цветной фотоаппарат? В этом случае научная ценность таких данных стремится к нулю.

> но Sclala тут не подходит по понятным причинам :(

ну кстати, а почему?

>Бинарный ввод/вывод в них тоже есть; его удобство, правда, опять же, различается(тут опять CL в лидерах).

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

Для вашей задачи может подойти OCaml. Он достаточно быстр, немногим уступает Сям в скорости исполнения. Но у окамла есть один важный недостаток - у его сборщика мусора есть проблемы с многопоточностью (оборотная сторона заключается в том, что этот сборщик очень быстр). Если у вас один поток обработки, то можно и переписать, но только если вам действительно так интересен опыт использования ФЯП. Никакую сложную задачу язык за вас не решит, хотя может избавить от рутины. Если же нужно просто сделать код красивее, то я бы переписал на тех же самых Сях или даже на Си++, но с плюсами надо быть очень аккуратным.

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

Тогда и с макросом никакой проблемы не будет.

[quote]Тогда и с макросом никакой проблемы не будет.[/quote]

Да ну? Проверил бы хоть. 8))

>Да, именно так, двумерный массив беззнаковых 32-битных целых, лежат «по строкам», размеры заданы. Давай пример на CL, начнём с простого, потом попробуем решить задачки поинтереснее, если не лень.

В CL данные в массивах тоже по строкам, кстати.

Можно вот так:

(deftype u32 () '(unsigned-byte 32))
(deftype non-negative-fixnum () '(integer 0 #.most-positive-fixnum))

(declaim (inline swap-u32-bytes))
(defun swap-u32-bytes (x)
  (declare (type u32 x))
  (logand
    #xffffffff
    (logior
      (ash (ldb (byte 8 24) x) 0)
      (ash (ldb (byte 8 0)  x) 24)
      (ash (ldb (byte 8 16) x) 8)
      (ash (ldb (byte 8 8)  x) 16))))

(defmacro with-array-data ((var array) &body body)
  "Binds ARRAY's data vector to VAR"
  #-sbcl
  (let ((a (gensym)))
    `(let* ((,a ,array)
            (,var (make-array (array-total-size ,a)
                    :element-type (array-element-type ,a)
                    :displaced-to ,a)))
       ,@body))
  #+sbcl
  (let ((start-var (gensym)) (end-var (gensym)))
    `(sb-kernel:with-array-data
         ((,var ,array) (,start-var) (,end-var) :force-inline t)
       (declare (ignore ,start-var ,end-var))
       ,@body)))

(deftype data-vector (type)
  `(#+sbcl simple-array #-sbcl array ,type (*)))

(defun read-u32-matrix (filename m n &optional reverse-endian)
  (declare (type (or pathname string) filename)
           (type non-negative-fixnum m n))
  (with-open-file (in filename :element-type 'u32)
    (if (= (file-length in) (* m n))
      (let* ((array (make-array (list m n) :element-type 'u32)))
        (declare (type (array u32 (* *)) array))
        (with-array-data (contents array)
          (declare (type (data-vector u32) contents))
          (read-sequence contents in)
          (when reverse-endian
            (map-into contents #'swap-u32-bytes contents))
          array))      
      (error "File size does not match requested matrix size"))))

А можно использовать CFFI и его интерфейс разделяемой памяти(with-pointer-to-vector-data) и считывать данные во внутренний вектор массива через, например, сисколлы(read etc.).

тут есть нюанс
максимальный размер массива обычно есть MOST-POSITIVE-FIXNUM, который, к примеру, в SBCL, представляет собой целое из (размер_машинного_слова - количество_битов_на_метку_типа), т.е. на 32битных машинах это целое из 29 бит, т.е. на 32битных машинах массив в 2.5 гигабайта создать нельзя.

Кошмар, у меня чуть глаза не выпали. На ассемблере должно быть читабельнее. Гора всяких незначащих ничего без зубрежки доков слов. Сколько тут разных функций замешано, сложно посчитать. Это на каждую есть документация. И для чего? Поработать с двухмерной матрицей?

Это просто смешно, даже обсуждать нечего. Гора непонятного говна и не более

Быстро показал мне на каком-либо высокоуровневом языке считывание двумерного массива 32битных целых из бинарного потока в четыре действия. То есть, как в приведенном примере. Причем, первое действие - открытие потока:

(with-open-file (in filename :element-type 'u32) 
 ...)

(let* ((array (make-array (list m n) :element-type 'u32))) 
 ...)

(with-array-data (contents array) 
 ...)

(read-sequence contents in) 

Или непонятным говном тут окажешься ты.

> Гора непонятного говна и не более

которая даже не сможет работать с данными больше чем 512Мб - т.е. не подходит сразу после прочтения постановки задачи, про скорость работы и говорить нечего, прав был Линус - «they don't try to do one thing well, they try to do _everything_ based on some loose principle( “LISP is good )”, т.е. им насрать будет ли это нормально работать( очевидно, что нет ) - главное чтоб на их любимом CL

Love5an в очередной раз шумно сливает,

1. На 64битных системах и 2.5 гига проглотит, и больше.

да- мы в курсе, что коммон-лисперы умеют писать костыльный код, пусть заказчики меняют ОС

2. Это работает ОЧЕНЬ быстро. Т.к. блочное чтение.

я про обработку данных - но до нее дело и не дойдет, т.к. данные просто не влезут в память

3. Ты дебил.

попробуй разнообразить лексику - «наркоман», «идиот» и «дебил» уже приелись, скоро тебя начнут забрасывать тухлыми помидорами

Я бы подключил cffi и создавал массивы через cffi:foreign-alloc. Массивы станут фактически совсем как в C, то есть без ограничений на размер, но зато и без проверок о выходе за границу (впрочем, это позволит сэкономить даже не включая (optimize (safety 0) (speed 3))). Такой подход позволит при необходимости заюзать низкоуровневые функции для работы с памятью (например, read из glibc) и в то же время не мешает макросистеме лиспа развернуться во всей красе при генерации обрабатывающего кода.

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

тут приводили пример кода на С - хотелось бы увидеть красоту макросистемы лиспа для его аналога

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

Во-первых, я бы «функциональщиной» это называть не стал.

Во-вторых, вот именно, что приведенный код оптимизирован как под производительность, так и под размер памяти.

Читабельность, при минимальном знании CL - отличная, не надо тут.

>я про обработку данных - но до нее дело и не дойдет, т.к. данные просто не влезут в память
Ништяк, то есть, ты даже не представляешь себе, как хранятся данные в, например, SBCL, что там представляют собой массивы, и какой машкод генерируется, но уже заочно знаешь, что все тормозит, и не влезает в память.

Я бы тебе ответил на это, но боюсь, за такой поток оскорблений меня совсем забанят.

Love5an в очередной раз шумно сливает,

Ты слил даже не начав.

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

тебя ткнуть в бенчмарки?

Ты слил даже не начав.

да - ты победил меня в выдуманном тобой споре, в нем же я полностью признал свое поражение, а тебе все стоя апплодируют

>да- мы в курсе, что коммон-лисперы умеют писать костыльный код, пусть заказчики меняют ОС

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

> Если твои «заказчики» находятся в прошлом веке

тебя ткнуть в статистику по ОС? такое ощущение, что ты живешь в параллельном мире и у тебя CL работает со скоростью С, а у всех используются 64-ные ОС

>даже не сможет работать с данными больше чем 512Мб
Не 512 мб недоумок, а 536870911 элементов.

> Не 512 мб недоумок, а 536870911 элементов.

ВНЕЗАПНО - если размер элемента развен 1 байт, то в сумме будет 536870911 байт( минимум )

> 32битные ОС, и особенно винда, не используются чтобы ворочать 2.5 гигабайтные массивы в памяти

ты в очередной раз не осилил погуглить? ну так попробуй посмотреть с какими файлами люди работают в том же фотожопе

> (defvar *a* (make-array most-positive-fixnum :element-type '(unsigned-byte 32)))

и эти люди ругают С

Я не понял, ты что, еще отрицаешь что-то?
Ты настолько тупой, что даже не знаешь, почему на 32битных системах 2.5 гигабайтный массив в памяти это нонсенс?

> Ты настолько тупой, что даже не знаешь, почему на 32битных системах 2.5 гигабайтный массив в памяти это нонсенс?

1. с чего ты носишься с этим 2.5Гб? я тебе говорил про 0.5Гб
2. man PAE
2. ты таки не умеешь гуглить? если у тебя не получится - я тебе накмдаю цитат и ссылок, где люди с удивлением узнают, что для картинок, например, в 10000х10000 вдруг начинает активно юзаться своп

бенчмарки

Ты про эти - http://shootout.alioth.debian.org/ ?

Там такая ситуация:

32 / 1 ядро

1) C и C++
2) Scala
3) Java
4) GHC
5) C#
6) OCaml
7) F#
8) SBCL
9) Erlang
10) Python, Ruby, PHP

32 / 4 ядра

1) C и C++
2) Java
3) Scala
4) F#
5) C#
6) OCaml
7) GHC
8) SBCL
9) Erlang
10) Python, Ruby, PHP

64 / 1 ядро

1) C и C++
2) GHC
3) Scala
4) Java
5) OCaml
6) C#
7) SBCL
8) F#
9) Erlang
10) Python, Ruby, PHP

64 / 4 ядра

1) C и C++
2) GHC
3) Java
4) Scala
5) C#
6) Ocaml
7) SBCL
8) F#
9) Erlang
10) Python, Ruby, PHP

Т.е. можно сказать, что есть группа из C и C++ (ну ещё Ada и ATS), группа JVM языков (Java 6 Server, Scala и т.п.) отдельно GHC и группа языков - OCaml, C#, F#, SBCL. Потом Erlang. И в конце идут Python, Ruby, PHP.

С другой стороны, в CL можно взять алиены для массивов - если посмотреть SBCL, то там такой алиен создаётся путём обычного malloc.

Да, и вообще - мы, лисперы, не доверяем этим вашим (подозрительным) бенчмаркам ;)

Напрашивается кодогенерация

// просьба не воспринимать всерьёз :)
#define MAKE_HIST_FOR_IMAGE(ACC,FOO1,FOO2,IMAGE) for (x=FOO1; x < X; x += 2)   \
                                                   for (y=FOO2; y < Y; y += 2) \
                                                     ACC[IMAGE[x][y]]++

MAKE_HIST_FOR_IMAGE(red_hist, 1, 1, image);
MAKE_HIST_FOR_IMAGE(green_hist, 0, ((x+1)%2), image);
MAKE_HIST_FOR_IMAGE(blue_hist, 0, 0, image);

CL тут может помочь тем, что она в нём полностью узаконена и безопасна (в отличии от примера выше):

(defmacro make-hist-for-image (acc foo1 foo2 image)
  `(for ((x ,foo1) (< x (xl ,image)) (incf x 2))
     (for ((y ,foo2) (< y (yl ,image)) (incf y 2))
       (,acc (aref ,image x y)))))

(make-hist-for-image red-hist 1 1 image)
(make-hist-for-image green-hist 0 (floor (1+ x) 2) image)
(make-hist-for-image blue-hist 0 0 image)

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

Лучше так:

(defmacro for (((i init) cond inc) &body body)
  `(do ((,i ,init))
       ((not ,cond))
     ,inc
     ,@body))  

(defmacro do-image (action image &key (delta 2) (initial-x 0) (initial-y 0))
  `(for ((x ,initial-x) (< x (length-x ,image)) (incf x ,delta))
     (for ((y ,initial-y) (< y (length-y ,image)) (incf y ,delta))
       (,action (aref ,image x y)))))

Тогда эта кодогенерация будет осуществляться так:

(macroexpand-1 '(do-image red-hist image :initial-x 1 :initial-y 1))

;; будет

(FOR ((X 1) (< X (LENGTH-X IMAGE)) (INCF X 2))
  (FOR ((Y 1) (< Y (LENGTH-Y IMAGE)) (INCF Y 2))
    (RED-HIST (AREF IMAGE X Y))))

(macroexpand-1 '(do-image blue-hist image))

(FOR ((X 0) (< X (LENGTH-X IMAGE)) (INCF X 2))
  (FOR ((Y 0) (< Y (LENGTH-Y IMAGE)) (INCF Y 2))
    (BLUE-HIST (AREF IMAGE X Y))))

(macroexpand-1 '(do-image green-hist image :initial-y (floor (1+ x) 2)))

(FOR ((X 0) (< X (LENGTH-X IMAGE)) (INCF X 2))
  (FOR ((Y (FLOOR (1+ X) 2)) (< Y (LENGTH-Y IMAGE)) (INCF Y 2))
    (GREEN-HIST (AREF IMAGE X Y))))

А полная вот так:

(macroexpand '(do-image red-hist image :initial-x 1 :initial-y 1))

;; будет

(BLOCK NIL
  (LET ((X 1))
    (TAGBODY
      (GO #:G979)
     #:G978
      (TAGBODY
        (INCF X 2)
        (FOR ((Y 1) (< Y (LENGTH-Y IMAGE)) (INCF Y 2))
          (RED-HIST (AREF IMAGE X Y))))
      (PSETQ)
     #:G979
      (UNLESS (NOT (< X (LENGTH-X IMAGE))) (GO #:G978))
      (RETURN-FROM NIL (PROGN)))))

Вот что касается последнего кода - я очень сомневаюсь что он будет отставать от Сишного варианта.