Здравствуйте, D. Mon, Вы писали:
DM>Пусть 1-я функция разбивает по количеству файлов, а вторая — по суммарному размеру. Тогда их разбиения могут выглядеть так: DM>1) 11112222333344445555 DM>2) 11222233334444555567 DM>Что будет результатом комбинирования?
подумай. я тебе по секрету скажу, что у меня так и работает. ключевое слово — ленивые списки
Ленивые списки — подход к реализации. Если результатом комбинирования
11112222333344445555
11222233334444555567
будет
11223344556677... (пересечение)
То это явно неверный ответ. А если не пересечение, то пойду думать..
Здравствуйте, D. Mon, Вы писали:
DM>Ленивые списки — подход к реализации.
ленивые списки — это другая парадигма программирования. к примеру, минимум в списке можно узнать как head.sort . при этом время вычисления будет O(N) — нет нужды вычислять остаток отсортированного списка, так как он всё равно не используется
Б> к примеру, минимум в списке можно узнать как head.sort . при этом время вычисления будет O(N)
Только, если функция сортировки достаточно ленивая. Одних ленивых списков недостаточно.
Сделал решение на ленивых списках. Из каждого компонента строки-параметра получается функция, которая берет ленивый список файлов и возвращает в виде ленивого списка файлов его начало — столько, сколько удовлетворяют критерию помещения в один блок (будь то количество, размер или что-то еще). Комбинация этих функций строится путем простой композиции. Результат композиции — функция, возвращающая столько файлов из начала данного ей списка, сколько удовлетворяют всем критериям. Все происходит лениво, лишние файлы не обрабатываются. Используя такую функцию формирования блока, главная функция откусывает от исходного списка файлов по блоку до тех пор, пока тот не исчерпается.
(* определение файла и функция парсинга параметров те же, их не привожу*)
(* универсальная функция выбора одного блока из начала списка файлов по критериям, заданным функциями-параметрами *)
(* принимает ленивый список файлов, возвращает тоже ленивый список файлов *)
(* ленивый список определен как type 'a llist = Nil | Cons of 'a * 'a llist Lazy.t;; *)let split_by accfun pred init file_llist =
let rec split acc = function
| Nil -> Nil
| Cons(h,t)-> let acc' = accfun acc h in
if pred acc' then Cons(h, lazy(split acc' (Lazy.force t))) else Nil in
split init file_llist;;
(* функции формирования блока, полученные путем уточнения предыдущей *)let split_by_size size_limit = split_by (fun sz h-> sz + h.size) (fun sz-> sz <= size_limit) 0;;
let split_by_num num_limit = split_by (fun n h-> n+1) (fun n-> n <= num_limit) 0;;
let split_by_ext = function
| Nil -> Nil
| Cons(h,t) -> Cons(h, lazy(split_by (fun _ f -> f.ext) ((=) h.ext) "" (Lazy.force t)));;
(* главная функция, интерфейс не менялся: превращает список в файлов в список списков *)let make_blocks2 param_str =
let num_opt, size_opt, ext_opt = parse_param_string param_str in(* разбираем параметры *)let split = (* строим одну комбинированную функцию получения блока как композицию *)
[Option.map split_by_num num_opt; (* функций, определенных параметрами *)
Option.map split_by_size size_opt;
if ext_opt then Some split_by_ext else None]
|> List.fold_left (fun spt so-> Option.map_default ((>>) spt) spt so) Std.identity in
let rec loop blocks flist = (* формируем список блоков *)let block = split flist in let len = length block in
if len=0 then blocks else loop (to_list block :: blocks) (drop len flist) in
of_list >> loop [] >> List.rev;;
Результат работы тот же, что раньше.
Использовал самописные ленивые списки:
type 'a llist = Nil | Cons of 'a * 'a llist Lazy.t;;
let rec of_list = function
| [] -> Nil
| h::t -> Cons(h, lazy (of_list t));;
let rec to_list = function
| Nil -> []
| Cons(h,t) -> h :: to_list (Lazy.force t);;
let rec take n lst =
if n = 0 then Nil else
match lst with
| Nil -> Nil
| Cons(h,t) -> Cons(h, lazy(take (n-1) (Lazy.force t)));;
let rec drop n lst =
if n = 0 then lst else
match lst with
| Nil -> Nil
| Cons(h,t) -> drop (n-1) (Lazy.force t);;
let rec iter f = function
| Nil -> ()
| Cons(h, t) -> f h; iter f (Lazy.force t);;
let rec filter p = function
| Nil -> Nil
| Cons(h,t)-> if p h then Cons(h, lazy (filter p (Lazy.force t))) else filter p (Lazy.force t);;
let rec map f = function
| Nil -> Nil
| Cons(h,t) -> Cons(f h, lazy(map f (Lazy.force t)));;
let rec append a b =
match a with
| Nil -> b
| Cons(h,t) -> Cons(h, lazy (append (Lazy.force t) b));;
let (++) = append;;
let rec length = function
| Nil -> 0
| Cons(h,t) -> 1 + length (Lazy.force t);;
let rec sort = function
| Nil -> Nil
| Cons(s,t) -> let xs = Lazy.force t in
(sort (filter (fun x-> x<s) xs)) ++ Cons(s, lazy (sort (filter (fun x-> x>=s) xs)));;
let rec nats_from n = Cons(n, lazy (nats_from (n+1)));;
let rec random k = Cons(k mod 100, lazy (rnd ((k*4021+6619) mod 10000)));;
let print_list lst = iter (Printf.printf "%d ") lst; print_endline "";;
Здравствуйте, D. Mon, Вы писали:
DM>Сделал решение на ленивых списках. Из каждого компонента строки-параметра получается функция, которая берет ленивый список файлов и возвращает в виде ленивого списка файлов его начало — столько, сколько удовлетворяют критерию помещения в один блок (будь то количество, размер или что-то еще). Комбинация этих функций строится путем простой композиции. Результат композиции — функция, возвращающая столько файлов из начала данного ей списка, сколько удовлетворяют всем критериям.
ах, красавчег. а я до этого не додумался, использовал (take.min.map length). с использованием твоего трюка полное решение на хаскеле выглядит так:
data File = File {size :: Integer, ext :: String}
-- |Разбивает список файлов по комплексному критерию типа "e10f1000b"
chopper crits = recursively (\xs -> xs.$ splitAt (length (headByCrits crits xs) `max` 1))
-- |Преобразует список критериев в функцию, возвращающую начало списка, которое им всем удовлетворяет
headByCrits = reverse -- -> b0001f01e
>>> recursively (break1 isAlpha) -- -> b0001,f01,e
>>> map headByCrit -- -> takeBytes 1000, take 10, takeOneExt
>>> flip (foldr ($)) -- -> takeBytes 1000 . take 10 . takeOneExt
-- |Преобразует (реверсированный) критерий в функцию, возвращающую соответствующее начало списка
headByCrit "e" = head . groupOn ext
headByCrit ('f':n) = take (read $ reverse n)
headByCrit ('b':n) = takeBytes (read $ reverse n)
-- |Возвращает префикс списка файлов с суммарной длиной не более bytes байт
takeBytes bytes files = files.$ take (files.$ prefixLen size (+) (<=bytes))
-- |Возвращает длину префикса списка, удовлетворяющего заданной комбинации условий
prefixLen mapper combinator tester = length . takeWhile tester . scanl1 combinator . map mapper
-- |Аналог break, который безусловно включает первый символ в первый список
break1 p (x:xs) = mapFst (x:) (break p xs)
BZ> сравнить фп и императивные решения на "рабочих" языках
вот "рабочий" язык шелл:
> есть список слов. надо записать в файл "a" все слова, начинающиеся на букву 'a', в файл "b" — слова на 'b' и т.д. вплоть до z
cat words | tr -dc a-z\\n | sed 's/^\(.\)\(.*\)$/echo \1\2 >> \1/' | sh -s
>> есть список слов. надо записать в файл "a" все слова, начинающиеся на букву 'a', в файл "b" — слова на 'b' и т.д. вплоть до z D>cat words | tr -dc a-z\\n | sed 's/^\(.\)\(.*\)$/echo \1\2 >> \1/' | sh -s
Здравствуйте, D. Mon, Вы писали:
DM>Предлагаю продолжить на примере такой задачи:
DM>1. Есть большой текстовый файл A (несколько гигов, заведомо не помещается в память), нужно сделать текстовый файл A1, содержащий все строки из А, но отсортированные в алфавитном порядке. Ограничение по памяти — 256 МБ.
— генераторы очень помогли в процессе.
Свойства получившейся программы: использует строго не более N Мб ОЗУ (по умолч. 128). Сливаются одновременно не более D (= 4) отсортированных файлов. Максимальный размер строки не более ((N << 19) / D). Ключем считается вся строка вместе с терминальным '\n', дубликаты строк отбрасываются.
Тесты:
Файл (исходники .cs) 50М, после сортировки 16М, N = 1: 6.53 sec; сортировка отсортированного 16М файла, N = 1: 4.21.
Те же файлы, N = 16: 3.29 и 1.64 сек.
Файл (.mp3) 2900M, после сортировки 2680М, N = 256: 17 mins; сортировка отсортированного 2680М файла, N = 256: 12 mins.
Файл (строки Фибоначчи случайной длины, программа генерации) 1024М, после сортировки 884M, N = 128: 200 sec.
