BZ>3-я задача: есть функция сжатия compress :: String -> String. ей на вход передаётся строка (или буфер и его размер — это непринципиально), а она возвращает сжатые данные. и есть аналогичная функция decompress. при этом они однопоточные. а у нас 4-процессорная машина. соответственно, нужно написать программу, читающую входные данные мегабайтными блоками, и упаковывающую "в 4 руки", и к ней программу распаковки

Гы, а что значит "однопоточные функции" без контекста языка программирования ?

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

BB>На плюсах.
BB>Вариант №1. Do not optimize prematurely...

Плюсы не так и плохо выглядят. Конечно, тут упрощено сильно всё, но всё же.
Это ещё раз доказывает, что задача -- не для функционального языка. Функциональные
задачи на С++ решаются хреновенько -- не тот язык. Хотя можно и там.

Здравствуйте, Basil B, Вы писали:

BB>На плюсах.

BB>

BB>ofstream* ofs[26];

BB>for(char c = 'a'; c <= 'z'; ++c)
BB>{
BB>    ofs[c - 'a'] =  new ofstream(string(1, c).c_str());
BB>}

BB>vector<string> words;

BB>for(int i = 0, end = words.size(); i != end; ++i)
BB>{
BB>    *ofs[words[i][0] - 'a'] << words[i] << ' ';
BB>}
BB>

А файлы закрывать кто будет ? А память удалять ? Не, там должно быть всё сложнее.

Здравствуйте, MasterZiv, Вы писали:


BZ>>3-я задача: есть функция сжатия compress :: String -> String. ей на вход передаётся строка (или буфер и его размер — это непринципиально), а она возвращает сжатые данные. и есть аналогичная функция decompress. при этом они однопоточные. а у нас 4-процессорная машина. соответственно, нужно написать программу, читающую входные данные мегабайтными блоками, и упаковывающую "в 4 руки", и к ней программу распаковки

MZ>Гы, а что значит "однопоточные функции" без контекста языка программирования ?

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

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

вот тесты мой собственной реализации этого процесса:

было:

D:\> Arc.exe create a enwik8 -m2 -t
Compressed 1 file, 100.000.000 => 26.576.090 bytes. Ratio 26.5%
Compression time 8.36 secs. Real time 8.92 secs, speed 11.212 kB/s
Testing time 10.69 secs. Real time 11.19 secs, speed 8.940 kB/s

стало:

C:\> Arc.exe create a enwik8 -m2 -t
Compressed 1 file, 100.000.000 => 26.576.090 bytes. Ratio 26.5%
Compression time 9.22 secs. Real time 2.63 secs, speed 37.965 kB/s
Testing time 14.12 secs. Real time 3.85 secs, speed 25.994 kB/s

MasterZiv пишет:

Или если попроще, так:

(defun cast-words-trivial (word-list)
   (mapc
    (lambda (word)
      (let ((file  (open (string (char word 0))
            :direction :output
            :if-does-not-exist :create
            :if-exists :append)))
        (unwind-protect
        (format file "~A~%" word)    
     (when file (close file)))))
    word-list))

BulatZiganshin пишет:

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

Какие функции, какое ядро, не понимаю ничего.

Здравствуйте, MasterZiv, Вы писали:

MZ>BulatZiganshin пишет:

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

MZ>Какие функции, какое ядро, не понимаю ничего.

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

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Во всех предложенных решениях, кроме, разве что совсем не кастомизируемых, выбор списка для представления элементов группы (а именно его иммутабельность) приводит к необходимости создания конструкции вида [(ID, String)], где ID — идентификатор группы (от вырожденных случаев где ID — имя файла, до сложных — где ID содержит информацию о способе обработки), и необходимости эту конструкцию преобразовывать к виду — [(ID, [String])].

Вообще-то другого здесь и не дано. По своей сути — это задача классификации.
А классификация — это установление зависимости между элементами и классами. Отсюда появляется [(ID, element)]
Классификация не нужна сама по себе. Мы должны что-то сделать с группами. Отсюда появляется [(ID, [element])]

NGG>Это иллюстрация того, как выбор "архитектурного решения" (дизайн, если хотите) оказывается взависимости от выбора языка реализации, хотя, казалось бы, такого быть не должно

Мне непонятно, что понимается под дизайном. И непонятна иллюстрация "того, как выбор "архитектурного решения" (дизайн, если хотите) оказывается взависимости от выбора языка реализации".
По-моему, при обобщении задачи классификации, так или иначе, решения на любом языке придут к чему-то похожему выше.
Разница лишь в том, как эти данные будут представлены языке. Как список в ФЯ или как класс группа, агрегирующий свои элементы, в ООП.

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

Про какие подзадачи идет речь? Вот например есть функция.

обработатьГруппы(элементы, классификатор, обработчик) = обработатьКаждуюГруппу(обработчик, разбитьНаГруппы(элементы, классификатор))

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

NGG>В случае ОО-декомпозиции, этого пытаются достич моделируя сущности/концепции (называйте как хотите) из предметной области в виде объектов и классов объектов, а отнощения между ними — в виде методов классов, статических методов или "синтетических" объектов. В итоге образуется набор "кубиков" из которых затем строится решение конкретной задачи. Поскольку изменения в предметной области случаются реже, чем формулируются новые задачи, вероятность использовать при решении новой задачи существующие "кубики" достаточна велика, что, в каком-то виде, гарантирует устойчивость решения к изменениям в требованиях и упрощение реализации новых требований через повторное использование не только результатов анализа предметной области, но и имеющегося кода.

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

NGG>В случае с ФП всё не так прозрачно. Есть требуется решить "конкретную" задачу, то всё понятно. Задачу крошим на подзадачи и красиво расписываем. Если нужно создать основу для решения родственных задач — тоже понятно — формулируется "конкретная" задача, где описываются вариации, далее задача решается "обычным" путём. Всё хорошо, но только "точки вариации" должны быть описаны _заранее_ (в отличии ОО подхода, когда "все возможные" вариации задач закладываются в модели предметной области (в классах и методах) без попытки перечислить их _все_ явно).

Мне не совсем понятно, где вариации описаные заранее. Вон в том же примере "обработатьГруппы".
Описаны требования (интерфейсы), но не сами вариации. То же самое и в ООП. Не вижу я разницы.

Здравствуйте, Beam, Вы писали:

B>Вообще-то другого здесь и не дано. По своей сути — это задача классификации.
B>А классификация — это установление зависимости между элементами и классами. Отсюда появляется [(ID, element)]
B>Классификация не нужна сама по себе. Мы должны что-то сделать с группами. Отсюда появляется [(ID, [element])]

NGG>>Это иллюстрация того, как выбор "архитектурного решения" (дизайн, если хотите) оказывается взависимости от выбора языка реализации, хотя, казалось бы, такого быть не должно

B>Мне непонятно, что понимается под дизайном. И непонятна иллюстрация "того, как выбор "архитектурного решения" (дизайн, если хотите) оказывается взависимости от выбора языка реализации".

"Задача классификации" — это всё-таки не наша задача.

Наша задача состоит в том, чтобы "раскидать" данные по обработчикам согласно определённому набору критериев.
Причём "в лоб" (в императивном стиле) эта задача решается с использованием O(1) доп.памяти и оценкой O(N) (если исключить монстрообразные критерии, требующие хранения состояния и сложных вычислений).

И нигде не звучит требования построить список [(ID, element)] или список [(ID, [element])] в явном виде, что тянет за собой как минумум O(N)/O(NlogN) по памяти/времени и, думается, с "хорошей" С перед оценкой времени.

Вопрос: чем руководствовался "дизайнер" принимая решение так разбить задачу на подзадачи? Вариантов ответа, конечно же, можно придумать много, как оскорбительных, так и наоборот . Имхо, мысль течёт примерно так:
— "грязь" с выводом в файл скрываем за функцией String -> [String] -> IO(),
— значит в "чистом" коде нужно получить перечисление [(String, [String])]
— инкрементально такую структуру не построить (добавляя по слову), значит нужно промежуточное представление, которое можно строить быстро. Такая структура есть [(String, String)]
— ну, а дальше sortBy, который затягивает все слова в память и даёт N*logN

Т.е. декомпозиция (выделение подзадач) основывается на особенностях языка (грязь отдельно, иммутабельные структуры данных, особенности синтаксиса), а не на анализе задачи.

Можно возразить, что решение демонстрирует как красиво/лаконично/и т.п. писать на ФЯ. Ок, но это значит, что решение тем более построенно исходя из выразительных особенностей языка реализации, а не на основе анализа задачи... ч.т.д

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

Я бы не стал утверждал, что в любом решении будет содержаться подзадача преобразовывать [(ID, element)] -> [(ID, [element])].

B>Про какие подзадачи идет речь? Вот например есть функция.
B>

B>обработатьГруппы(элементы, классификатор, обработчик) = обработатьКаждуюГруппу(обработчик, разбитьНаГруппы(элементы, классификатор))
B>

B>Где здесь подзадачи?. Эта функция решает обощенную задачу и определяет требования к классификатору и обработчику (аналог интерфейса).
B>А сами функции обработчик и классификатор будут написаны для каждой предметной области уже потом.

Как это где?

1) Построить классификатор и обработчик в соответствии с условием задачи (далеко не факт, что это элементарно сделать).
2) разбитьНаГруппы используя классификатор
3) обработатьКаждуюГруппу используя обработчик

B>В том-то и дело, что классы привязаны к предметной области, а вот функции нет (ну почти )
B>А чтобы отвязать их, появляются классы, которые имеют в себе лишь поведение (по сути функция), и классы хранящие только данные (параметры функций).

"Функция" может быть отвязана от предметной области, только если она принадлежит "нижележащему" уровню абстракции/обвязке решения, н-р, привязана к collection api языка.
Такие функции не требуется откуда-то отвязывать, т.к. это либо не имеет смысла (н-р, map, filter, foldr в java всё равно удобнее делать через цикл), либо уже давно отвязано и помещено в стандартные или общеупотебимые библиотеки.

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

NGG>>Всё хорошо, но только "точки вариации" должны быть описаны _заранее_ (в отличии ОО подхода, когда "все возможные" вариации задач закладываются в модели предметной области (в классах и методах) без попытки перечислить их _все_ явно).

B>Мне не совсем понятно, где вариации описаные заранее. Вон в том же примере "обработатьГруппы".
B>Описаны требования (интерфейсы), но не сами вариации. То же самое и в ООП. Не вижу я разницы.

Описав требования (интерфейсы), ты как раз и задал точки вариации для решения — то, как его можно расширять.
В ООП интерфейс является такой же точкой расширения, верно.

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

Проблема тут скорее теоретическая, чем практическая, т.к. на практике рулит кисс, сроки и чтобы работало

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>А теперь представь, что задача изменилась так, что недостаточно просто реализовать интерфейсы, чтобы получить решение.
NGG>В случае ООП, для решения новой задачи можно будет, как минимум, использовать классы из модели предметной области — базовый строительный материал.
NGG>А в случае ФП? Если декомпозиция на подзадачи велась исходя из деталей алгоритма решения конкретной задачи, нет никакой гарантии, что получившиеся подзадачи смогут пригодиться где-то ещё.

А в чем принципиальное различие? В случае ООП у нас есть классы, т.е. данные и функции для работы с ними. В случае ФП у нас есть то же самое — данные и функции для работы с ними. Иногда они объединены в одну синтаксическую структуру, например модуль, иногда просто описаны рядом. Как я понимаю, есть опасения, что в случае ФП функции для работы с данными не будут покрывать все возможные операции, а будут заточены на задачу. Но и в ООП случае гарантии универсальности описанных методов нет — для одной задачи данного набора методов оказалось достаточно, для другой могут потребоваться новые..

Здравствуйте, BulatZiganshin, Вы писали:

BZ>было:

BZ>D:\> Arc.exe create a enwik8 -m2 -t
BZ>Compressed 1 file, 100.000.000 => 26.576.090 bytes. Ratio 26.5%
BZ>Compression time 8.36 secs. Real time 8.92 secs, speed 11.212 kB/s
BZ>Testing time 10.69 secs. Real time 11.19 secs, speed 8.940 kB/s

BZ>стало:

BZ>C:\> Arc.exe create a enwik8 -m2 -t
BZ>Compressed 1 file, 100.000.000 => 26.576.090 bytes. Ratio 26.5%
BZ>Compression time 9.22 secs. Real time 2.63 secs, speed 37.965 kB/s
BZ>Testing time 14.12 secs. Real time 3.85 secs, speed 25.994 kB/s

Мне кажется, или Вы в итоге только проиграли за счет времени, проведенного в ядре (на блокировках, похоже)?

Здравствуйте, Mr.Cat, Вы писали:

MC>Мне кажется, или Вы в итоге только проиграли за счет времени, проведенного в ядре (на блокировках, похоже)?
Было-то 8.92, стало 2.63, как же проиграли? Прирост 3.4х. Не 4х, конечно, но всё же.

Здравствуйте, Mr.Cat, Вы писали:

BZ>>Compression time 8.36 secs. Real time 8.92 secs, speed 11.212 kB/s
BZ>>стало:
BZ>>Compression time 9.22 secs. Real time 2.63 secs, speed 37.965 kB/s

MC>Мне кажется, или Вы в итоге только проиграли за счет времени, проведенного в ядре (на блокировках, похоже)?

первая цифра — cpu time, время всех четырёх ядер. вторая — wall clock time, время от запуска программы до завершения. проигрыш в первом времени — обычное явление, результат нехватки пропускной способности памяти. грубо говоря, если бы память была бесконечно быстра, то первое время не возросло бы и мы бы смогли ускориться ровно вчетверо

Здравствуйте, D. Mon, Вы писали:

DM>А в чем принципиальное различие? В случае ООП у нас есть классы, т.е. данные и функции для работы с ними. В случае ФП у нас есть то же самое — данные и функции для работы с ними. Иногда они объединены в одну синтаксическую структуру, например модуль, иногда просто описаны рядом.


Разница в том, откуда берутся "данные" и "функции для работы с ними".
В ООП — из анализа предметной области (так говорит теория) => "классы" полученые для решения задачи А, останутся полезны для решения задачи Б из той же области (учитываем, что ооп применяется для создания систем, где основная сложность не алгоритмическая, а "размерная" — предметная область стоит из большого числа сущностей и отношений, а возникающие задачи относительно просты, но их много).
В ФП — как результат декомпопозиции _конкретной_ задачи на подзадачи (какими методами гуру пользуются в действительности — не знаю). Подзадачи же, в большой степени отражают алгоритм выбранный для решения исходной задачи, чем значимый аспект предметной области... (думаю, что гуру должны знать рецепты, как такого можно избежать, но статей на эту тему не видел).


DM> Как я понимаю, есть опасения, что в случае ФП функции для работы с данными не будут покрывать все возможные операции, а будут заточены на задачу. Но и в ООП случае гарантии универсальности описанных методов нет — для одной задачи данного набора методов оказалось достаточно, для другой могут потребоваться новые..

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

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

В случае ФП — х3. На простых примерах всё выглядит здорово, кисс работает. Что будет если использовать фп там, где сейчас используется java — могу только гадать.
Пока считаю, что овчинка выделки не стоит, но надежд на лучшее не теряю Будь возможность выбора, по вполне очевидным причинам, предпочёл бы на замену java'е скалу, а не хаскелл, что дало бы (на вскидку) двухкратное сокращение затрат на кодирование (для тех задач, что мне приходится решать).

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>В ООП — из анализа предметной области (так говорит теория) => "классы" полученые для решения задачи А, останутся NGG>В ФП — как результат декомпопозиции _конкретной_ задачи на подзадачи (какими методами гуру пользуются в

папа, а чем люди дышали до открытия кислорода?

Здравствуйте, BulatZiganshin, Вы писали:

BZ>

папа, а чем люди дышали до открытия кислорода?

Воздухом!

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

Здравствуйте, BulatZiganshin, Вы писали:
T>>>>4. Отфильтровать дерево, оставив только ветви содержащие дубликаты и сами дубликаты.
T>>Как подправить, сходу не соображу.
BZ>строй список дубликатов локально
Ага, разобрался. Красиво получается.

Возник ещё связанный вопрос:
При поиске дубликатов нужно сравнивать не полностью строку, а некоторую её часть.
Вроде бы ничего сложного — пишем функцию выделения существенной части строки (getIdent) и сипользуем именно её результат для поиска.

Строкиа имеет такой вид (prel):

/[\w\s]+(\([^)]+\)\s*)*/

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

Первый выриант getIdent был такой:

ltrim = dropWhile (==' ')
trim = reverse . ltrim . reverse . ltrim

getIdent = trim . takeWhile (/='(')

На моём объёме файла дерева ~8мб. выполнялось вполне шустро.

Теперь потребовалось включить в идентификатор первый символ из последней группы скобок, если она имеет такой вид (perl):

/\(\w,\s+[^)]+\)/

Т. е. getIdent стал такой:

getIdent str = first ++ getSmb other
  where
    first = trim $ takeWhile (/='(') str
    other = last $ splitBy (=='(') str
    getSmb (x:y:z:xs) | x == '(' && z == ',' = " (" ++ [y] ++ ")"
    getSmb xs = ""

splitBy _ [] = []
splitBy f x = fist : splitBy f other
  where
    (fist, other) = break f x

И вот окончания его работы дождатся не получается.

Как ускорить этот кусок, и вообще как лучше работать с большими объёмами строк?

Предлагаю продолжить на примере такой задачи:

1. Есть большой текстовый файл A (несколько гигов, заведомо не помещается в память), нужно сделать текстовый файл A1, содержащий все строки из А, но отсортированные в алфавитном порядке. Ограничение по памяти — 256 МБ.

2. Изменить первую программу так, чтобы будучи запущена с ключом -u она создавала файл А2, содержащий все уникальные строки из А в алфавитном порядке и количество повторений для каждой строки. Т.е. из

dd ee ff
aaa bbb ccc
aaa bbb ccc
dd ee ff
aaa bbb ccc

Получилось бы

3: aaa bbb ccc
2: dd ee ff

Ограничения на память те же.

Здравствуйте, Basil B, Вы писали:
dmz>>Ну так можно привести тривиальное сишное решение хотя бы первой задачи?
BB>Вариант №2.
Надо примерно так:

#include <iostream>
#include <fstream>
#include <iterator>
#include <cctype>

using namespace std;

typedef istream_iterator<string> word_iter_t;

int main() {
  ofstream ofs[26];
  for(char c[2] = "a"; c[0] <= 'z'; ++c[0]) 
    ofs[c[0] - 'a'].open(c);

  std::ifstream words("words.txt");
  for(word_iter_t cur(words), end; cur != end; ++cur)
    if (cur->size() > 0 && isalpha((*cur)[0]) && islower((*cur)[0]))
      ofs[(*cur)[0] - 'a'] << *cur << ' ';
}

Вроде как вполне компактно и прозрачно.
Все ресурсы закрываются, память не течёт.

Для трёх буквочек можно нарисовать примерно так:

#include <iostream>
#include <fstream>
#include <iterator>
#include <cctype>
#include <map>
#include <boost/shared_ptr.hpp>

using namespace std;

typedef istream_iterator<string> word_iter_t;
typedef boost::shared_ptr<ofstream> ostream_ptr_t;
typedef map<string, ostream_ptr_t> omap_t;

int main() {
  omap_t ofs;
  ifstream words("words.txt");
  for(word_iter_t cur(words), end; cur != end; ++cur) {
    string fname = cur->substr(0, 3);
    if (fname.size() == 0) //Остальные проверки валидности имени и слова.
      continue;
    if (ofs.find(fname) == ofs.end())
      ofs.insert(make_pair(
        fname, ostream_ptr_t(new ofstream(fname.c_str()))));
    ofstream& out = *ofs.find(fname)->second.get();
    out << *cur << ' ';
  }
}

Здравствуйте, Tonal-, Вы писали:
T>И вот окончания его работы дождатся не получается.
Нашел ошибочку.
Функция splitBy циклилась.
На самом деле она идентична первоначальной groupFrom без проверки критерия для первого элемента.

getIdent str = first ++ (getSmb $ latest end)
  where
    first = strip $ takeWhile (/='(') str
    end = groupFrom (=='(') str
    latest [] = ""
    latest xs = last xs 
    getSmb (x:y:z:xs) | x == '(' && z == ',' = " (" ++ [y] ++ ")"
    getSmb xs = ""

T>... как лучше работать с большими объёмами строк?
Но этот вопрос таки остаётся.
Нужен поиск и замена подстроки.