LINUX.ORG.RU

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


5

0

Всем привет, хочу продолжить тему работы с файлами в ФП. Тут недавно были примеры, но очень тривиальные, прочитать-записать. Вопрос такой, как в ФП-языке считать в память огромный файл как двумерный массив, и чтобы он а) занимал в памяти столько же места сколько на диске б) доступ к элементам был быстрый (О(1))?

Предистория такова, мы обрабатываем изображения с телескопов, там счёт идёт на сотни мегапикселей, и глубина пикселя 32 бита. Так что типичное изображение ~ два с половиной гигабайта, для этих целей специально собраны счётные узлы с 4 Гб RAM. Это чтобы изображение поместилось целиком в память, и оставалось на промежуточные буферы для накопления результатов. Естественно, все рассчёты написаны на Си и С++, работает быстро, памети хватает. Но код некрасивый, много повторяющихся конструкций и т.п. Народ в основном закостенелый из старшего поколения, ничего кроме Си и фортрана не знают, а я хочу попробывать более современные языки.

Так что буду благодарен за примеры чтения массивов для Haskell и особенно Scheme. И чтобы можно было посмотреть, сколько памяти реально израсходовано. Спасибо!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Т.е. у нас есть файл, и из него надо получить двумерный массив 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 разумееться

Ignatik
() автор топика
Ответ на: комментарий от Reset

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

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

Ignatik
() автор топика
Ответ на: комментарий от Eddy_Em

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

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

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

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

Ignatik
() автор топика
Ответ на: комментарий от pathfinder

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

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

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

Ignatik
() автор топика
Ответ на: комментарий от ahonimous

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

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

Ignatik
() автор топика
Ответ на: комментарий от Love5an

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

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

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

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

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

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

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

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

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

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

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

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Ignatik

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

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

Eddy_Em ☆☆☆☆☆
()

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

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

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Love5an

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

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

cvb
()

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

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

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

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

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

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

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

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

>Да, именно так, двумерный массив беззнаковых 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"))))
Массив заполняется целыми 32битными числами в native endian(т.е. на LE последовательность байтов 00 00 00 01 в файле будет считана как число #x01000000).

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

Love5an
()
Ответ на: комментарий от Love5an
-(declare (type (array u32 (* *)) array))
+(declare (type (simple-array u32 (* *)) array))
Love5an
()
Ответ на: комментарий от Love5an

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

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

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

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

Быстро показал мне на каком-либо высокоуровневом языке считывание двумерного массива 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) 

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

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

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

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

ahonimous
()

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

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


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

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


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

3. Ты дебил.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

Love5an
()

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

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

ahonimous
()

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

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

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

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

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

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

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

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

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

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

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

бенчмарки

Ты про эти - 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.

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

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

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

// просьба не воспринимать всерьёз :)
#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)

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

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

Лучше так:

(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)))))
quasimoto ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.