Эффективный ввод в OCaml
Предположим, я пишу программу на OCaml, и мой ввод будет большим потоком целых чисел, разделенных пробелами, т.е.
let string = input_line stdin;;
вернет строку, которая выглядит, например, как "2 4 34 765 5 ...". Теперь сама программа примет еще два значения i и j, которые задают небольшую подпоследовательность этого ввода, в которой будет выполняться основная процедура (давайте скажем, что основной процедурой является поиск максимума этого подсписка). Другими словами, весь поток будет введен в программу, но программа будет действовать только на небольшом подмножестве ввода.
Мой вопрос: каков наилучший способ перевести соответствующую часть входного потока в нечто полезное, то есть строку целых чисел? Одним из вариантов будет преобразование всей входной строки в список целых, используя
let list = List.map int_of_string(Str.split (Str.regexp_string " ") string;;
и затем, как только введены границы i и j, легко найти соответствующий подсписок и его максимум. Проблема заключается в том, что первоначальная предварительная обработка большого потока занимает очень много времени.
Существует ли эффективный способ определения местоположения небольшого подсписка непосредственно из большого потока, т. Е. Обработка ввода вместе с основной процедурой?
2 ответа
Вы можете использовать Scanf модуль семейства функций. Например, Scanf.fscanf Позволяет вам читать токены из канала в соответствии со строковым форматом (который является специальным типом в OCaml).
Ваша программа может быть разложена на две функции:
- тот, который пропускает число
iтокенов из входного канала, - тот, который извлекает максимальное целое число из числа
jиз канала
Давайте напишем это:
let rec skip_tokens c i =
match i with
| i when i > 0 -> Scanf.fscanf c "%s " (fun _ -> skip_tokens c @@ pred i)
| _ -> ()
let rec get_max c j m =
match j with
| j when j > 0 -> Scanf.fscanf c "%d " (fun x -> max m x |> get_max c (pred j))
| _ -> m
Обратите внимание на пробел после индикатора формата токена в строке, которая указывает сканеру также проглотить все пробелы и возврат каретки между токенами.
Все, что вам нужно сделать сейчас, это объединить их. Вот небольшая программа, которую вы можете запустить из CLI, которая принимает i а также j параметров, ожидает поток токенов и выводит максимальное значение по желанию:
let _ =
let i = int_of_string Sys.argv.(1)
and j = int_of_string Sys.argv.(2) in
skip_tokens stdin (pred i);
get_max stdin j min_int |> print_int;
print_newline ()
Возможно, вы могли бы написать более гибкие комбинаторы, извлекая рекурсивную часть. Я оставлю это как упражнение для читателя.
Стандартная библиотека OCaml довольно мала. Он обеспечивает необходимый и достаточный набор ортогональных функций, как и любая хорошая стандартная библиотека. Но, как правило, этого недостаточно для обычного пользователя. Вот почему существуют библиотеки, которые делают вещи, это довольно часто.
Я хотел бы упомянуть две наиболее выдающиеся библиотеки: базовую библиотеку Джейн Стрит и включенные батареи (также называемые ядром и батареями).
Обе библиотеки предоставляют набор функций ввода / вывода высокого уровня, но существует небольшая проблема. Невозможно или даже разумно пытаться обратиться к любому варианту использования в библиотеке. В противном случае интерфейс библиотеки не будет лаконичным и понятным. И твой случай нестандартный. Существует соглашение, молчаливое соглашение между инженерами данных, чтобы представлять набор файлов с набором строк в файле. И представлять одну "вещь" (или особенность) с помощью линии. Итак, если у вас есть набор данных, где каждый элемент является скаляром, вы должны представить его как последовательность скаляров, разделенных новой строкой. Несколько элементов в одной строке предназначены только для многомерных объектов.
Таким образом, при правильном представлении вашу проблему можно решить так же просто, как (с помощью Core):
open Core.Std
let () =
let filename = "data" in
let max_number =
let open In_channel in
with_file filename
~f:(fold_lines ~init:0
~f:(fun m s -> Int.(max m @@ of_string s))) in
printf "Max number is %s is %d\n" filename max_number
Вы можете скомпилировать и запустить эту программу с corebuild test.byte -- при условии, что код находится в имени файла test.byte и основная библиотека установлена (с opam install core если вы используете opam).
Также существует отличная библиотека LwtЭто обеспечивает монадический высокоуровневый интерфейс для ввода / вывода. С помощью этой библиотеки вы можете разобрать набор скаляров следующим образом:
open Lwt
let program =
let filename = "data" in
let lines = Lwt_io.lines_of_file filename in
Lwt_stream.fold (fun s m -> max m @@ int_of_string s) lines 0 >>=
Lwt_io.printf "Max number is %s is %d\n" filename
let () = Lwt_main.run program
Эта программа может быть скомпилирована и запущена с ocamlbuild -package lwt.unix test.byte --, если lwt библиотека установлена в вашей системе (opam install lwt).
Таким образом, это не означает, что ваша проблема не может быть решена (или ее трудно решить) в OCaml, это просто упомянуть, что вы должны начать с правильного представления. Но, предположим, вы не являетесь владельцем представления и не можете его изменить. Давайте посмотрим, как это можно эффективно решить с помощью OCaml. Как показывают предыдущие примеры, в целом ваша проблема может быть описана как свертывание канала, т.е. последующее применение функции f каждому значению в файле. Таким образом, мы можем определить функцию fold_channel, которая будет читать целочисленное значение из канала и применять к нему функцию и ранее прочитанное значение. Конечно, эту функцию можно дополнительно абстрагировать, подняв аргумент формата, но для демонстрационных целей, я полагаю, этого будет достаточно.
let rec fold_channel f init ic =
try Scanf.fscanf ic "%u " (fun s -> fold_channel f (f s init) ic)
with End_of_file -> init
let () =
let max_value = open_in "atad" |> fold_channel max 0 in
Printf.printf "max value is %u\n" max_value
Хотя, я должен отметить, что эта реализация не для тяжелой работы. Это даже не хвостовая рекурсия. Если вам нужен действительно эффективный лексер, вы можете, например, использовать генератор лексеров в ocaml.
Обновление 1
Поскольку в названии есть слово "эффективный", и всем нравятся тесты, я решил сравнить эти три реализации. Конечно, поскольку чистая реализация OCaml не является хвостовой рекурсией, она не сравнима с другими. Вы можете задаться вопросом, почему это не хвостовая рекурсия, так как все призывы к fold_channel находится в хвостовой позиции. Проблема в обработчике исключений - при каждом обращении к каналу свертки мы должны помнить init значение, так как мы собираемся вернуть его. Это распространенная проблема с рекурсией и исключениями, вы можете найти ее в Google для получения дополнительных примеров и объяснений.
Итак, сначала нам нужно исправить третью реализацию. Мы будем использовать общий трюк со значением параметра.
let id x = x
let read_int ic =
try Some (Scanf.fscanf ic "%u " id) with End_of_file -> None
let rec fold_channel f init ic =
match read_int ic with
| Some s -> fold_channel f (f s init) ic
| None -> init
let () =
let max_value = open_in "atad" |> fold_channel max 0 in
Printf.printf "max value is %u\n" max_value
Итак, с новой хвостовой рекурсивной реализацией, давайте попробуем их всех на больших данных. 100_000_000 цифр - большие данные для моего 7-летнего ноутбука. Я также добавил реализации C в качестве базовой линии и клон OCaml реализации C:
let () =
let m = ref 0 in
try
let ic = open_in "atad" in
while true do
let n = Scanf.fscanf ic "%d " (fun x -> x) in
m := max n !m;
done
with End_of_file ->
Printf.printf "max value is %u\n" !m;
close_in ic
Обновление 2
Еще одна реализация, которая использует ocamllex, Он состоит из двух файлов, спецификации лексера lex_int.mll
{}
let digit = ['0'-'9']
let space = [' ' '\t' '\n']*
rule next = parse
| eof {None}
| space {next lexbuf}
| digit+ as n {Some (int_of_string n)}
{}
И реализация:
let rec fold_channel f init buf =
match Lex_int.next buf with
| Some s -> fold_channel f (f s init) buf
| None -> init
let () =
let max_value = open_in "atad" |>
Lexing.from_channel |>
fold_channel max 0 in
Printf.printf "max value is %u\n" max_value
И вот результаты:
implementation time ratio rate (MB/s)
plain C 22 s 1.0 12.5
ocamllex 33 s 1.5 8.4
Core 62 s 2.8 4.5
C-like OCaml 83 s 3.7 3.3
fold_channel 84 s 3.8 3.3
Lwt 143 s 6.5 1.9
PS Вы можете видеть, что в данном конкретном случае Lwt является выбросом. Это не значит, что Lwt медленный, это просто не его гранулярность. И я хотел бы заверить вас, что, по моему опыту, LWT является подходящим инструментом для высокопроизводительных вычислений. Например, в одной из моих программ он обрабатывает 30 MB/s сетевой поток в режиме реального времени.
Обновление 3
Кстати, я попытался рассмотреть проблему абстрактно, и я не дал решения для вашего конкретного примера (с j а также k). Поскольку свертывание является обобщением итерации, ее можно легко решить, расширив состояние (параметр init) удерживать счетчик и проверять, содержится ли он в диапазоне, указанном пользователем. Но это приводит к интересному следствию: что делать, когда вы опередили диапазон? Конечно, вы можете продолжать до конца, просто игнорируя вывод. Или вы можете не локально выйти из функции с исключением, что-то вроде raise (Done m), Базовая библиотека обеспечивает такую возможность with_return функция, которая позволяет вам выйти из ваших вычислений в любой точке.
open Core.Std
let () =
let filename = "data" in
let b1,b2 = Int.(of_string Sys.argv.(1), of_string Sys.argv.(2)) in
let range = Interval.Int.create b1 b2 in
let _,max_number =
let open In_channel in
with_return begin fun call ->
with_file filename
~f:(fold_lines ~init:(0,0)
~f:(fun (i,m) s ->
match Interval.Int.compare_value range i with
| `Below -> i+1,m
| `Within -> i+1, Int.(max m @@ of_string s)
| `Above -> call.return (i,m)
| `Interval_is_empty -> failwith "empty interval"))
end in
printf "Max number is %s is %d\n" filename max_number