假设我正在编写一个OCaml程序,我的输入将是一个由空格分隔的大整数整数,即
let string = input_line stdin;;
将返回一个看起来像例如"2 4 34 765 5 ..."的字符串.现在,程序本身将采用另外两个值i和j,它们指定此输入的小子序列,主程序将在该子序列上发生(让我们说主程序是找到这个子列表的最大值).换句话说,整个流将被输入到程序中,但程序将最终仅作用于输入的一小部分.
我的问题是:将输入流的相关部分转换为可用的东西(即一串整数)的最佳方法是什么？一种选择是将整个输入字符串转换为使用的int列表
let list = List.map int_of_string(Str.split (Str.regexp_string " ") string;;
然后一旦输入了界限i和j,就可以轻松找到相关的子列表及其最大值.问题是大流的初始预处理非常耗时.
是否有一种直接从大流中定位小子列表的有效方法,即处理输入和主程序？
OCaml的标准库相当小.它提供了必要且充分的正交特征集,就像任何好的标准库一样.但是,通常,这对于临时用户来说还不够.这就是为什么存在库,做这些东西,这是相当普遍的.
我想提到两个最着名的图书馆:简街的核心图书馆和电池包括(又名核心和电池).
两个库都提供了一堆高级I/O函数,但是存在一些问题.尝试解决库中的任何用例是不可能的,甚至是不合理的.否则,图书馆的界面不会简洁易懂.你的情况是非标准的.数据工程师之间存在约定,即默认协议,用文件中的一组行表示一组事物.用线代表一个"东西"(或一个特征).因此,如果您有一个数据集,其中每个元素都是标量,则应将其表示为由换行符分隔的标量序列.单行上的多个元素仅适用于多维特征.
因此,通过适当的表示,您的问题可以像(使用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,它为I/O提供了一个高级别的接口.使用此库,您可以通过以下方式解析一组标量:
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的词法分析器.
由于标题中有一个"高效"字样,并且每个人都喜欢基准测试,我决定比较这三个实现.当然,由于纯OCaml实现不是尾递归,因此无法与其他实现相比.你可能想知道,为什么它不是尾递归的,因为所有的调用fold_channel都处于尾部位置.问题在于异常处理程序 - 在每次调用fold通道时,我们需要记住该init值,因为我们将返回它.这是递归和异常的常见问题,您可以将其谷歌搜索更多示例和解释.
所以,首先我们需要修复第三个实现.我们将使用具有选项值的常见技巧.
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实现作为基线,以及C实现的OCaml克隆:
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
使用的另一种实现方式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是HPC非常适合的工具.例如,在我的一个程序中,它30 MB/s实时处理网络流.
顺便说一下,我试图以抽象的方式解决这个问题,而且我没有为你的特定例子(用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
您可以使用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 ()
您可能可以通过提取递归部分来编写更灵活的组合器。我将把这个作为练习留给读者。