OCaml的有效输入

Question

假设我正在编写一个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，就很容易找到相关的子列表和它的最大值。问题是大数据流的初始预处理非常耗时。

是否有一种有效的方法可以直接从大流中定位小子列表，即与主过程一起处理输入?

Answer 1

OCaml的标准库相当小。它提供了必要和充分的正交特性集，就像任何好的标准库应该做的那样。但通常情况下，这对于普通用户来说是不够的。这就是为什么存在库，做这些事情，这是相当常见的。

我想提到两个最突出的图书馆:Jane Street的Core图书馆和Batteries included(又名Core and Batteries)。

两个库都提供了一些高级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 %dn" filename max_number

你可以用corebuild test.byte --编译和运行这个程序，假设代码在一个名为test.byte的文件中，并且安装了核心库(如果你使用opam，使用opam install core)。

此外，还有一个优秀的库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 %dn" filename
let () = Lwt_main.run program

如果在您的系统上安装了lwt库(opam install lwt)，则可以使用ocamlbuild -package lwt.unix test.byte --编译和运行该程序。

所以，这并不是说你的问题不能用OCaml解决(或者很难解决)，只是想说，你应该从一个合适的表示开始。但是，假设您不拥有该表示，并且无法更改它。让我们看看如何用OCaml有效地解决这个问题。正如前面的例子所示，一般来说，你的问题可以描述为通道折叠，即对文件中的每个值执行f函数的相应应用。因此，我们可以定义一个函数fold_channel，它将从通道中读取一个整数值，并对它和之前读取的值应用一个函数。当然，可以通过取消format参数来进一步抽象这个函数，但是出于演示目的，我想这就足够了。

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 %un" max_value

虽然，我应该注意到这个实现不是用于繁重的工作。它甚至不是尾递归的。如果您需要真正高效的词法分析器，您可以使用ocaml的词法分析器生成器，例如

<标题>更新1

由于标题中有一个词"高效"，并且每个人都喜欢基准测试，所以我决定比较这三种实现。当然，由于纯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 %un" 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 %un" !m;
    close_in ic

<标题>更新2 h1> 另一个使用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 %un" 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

注:你可以看到，在这种特殊情况下Lwt是一个异常值。这并不意味着Lwt慢，只是粒度问题。我想向您保证，根据我的经验，Lwt是一个非常适合高性能计算的工具。例如，在我的一个程序中，它实时处理30 MB/s网络流。

<标题> 3 更新

顺便说一下，我试图以抽象的方式解决问题，我没有为您的特定示例(j和k)提供解决方案。由于折叠是迭代的泛化，因此可以通过扩展状态(参数init)来保存计数器并检查它是否包含在用户指定的范围内来轻松解决。但是，这导致了一个有趣的结果:当你超出范围时该怎么办?当然，您可以继续到最后，只是忽略输出。或者您可以使用异常从函数非局部退出，例如raise (Done m)。Core库通过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 %dn" filename max_number

Answer 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 ()

你可以通过提取递归部分写出更灵活的组合子。我将把这个留给读者作为练习。