python - F# 或 Ocaml 优化
问题描述
我试图理解为什么以下 Python 代码比 F# 和 Ocaml 版本运行得更快:
from sys import stdin, stdout
def read():
return stdin.readline().rstrip()
def readints():
return [int(x) for x in read().split()]
_, _, q = readints()
A = readints()
B = readints()
for _ in range(q):
arr = [0]*4001
l1, r1, l2, r2 = readints()
for i in range(l1-1, r1):
arr[A[i]] ^= 1
for i in range(l2-1, r2):
arr[B[i]] ^= 1
result = sum(arr)
stdout.write(str(result)+"\n")
这是我花了几个小时学习该语言的 Ocaml 版本:
let open Printf in
let parse_line () =
read_line()
|> String.trim
|> Str.split (Str.regexp_string " ")
|> Array.of_list
|> Array.map int_of_string in
let nmq = parse_line() in
let n = nmq.(0) in
let m = nmq.(1) in
let q = nmq.(2) in
let a = parse_line() in
let b = parse_line() in
for i = 1 to q do
let arr = Array.create 4001 0 in
let llrr = parse_line() in
let l1 = llrr.(0) in
let r1 = llrr.(1) in
let l2 = llrr.(2) in
let r2 = llrr.(3) in
for i = l1-1 to r1-1 do
arr.(a.(i)) <- arr.(a.(i)) lxor 1
done;
for i = l2-1 to r2-1 do
arr.(b.(i)) <- arr.(b.(i)) lxor 1
done;
printf "%d\n" (Array.fold_left (+) 0 arr)
done;
这是相同的,但在 F#
open System
open System.IO
let out = new StreamWriter(Console.OpenStandardOutput())
let readints () = [ for x in stdin.ReadLine().TrimEnd().Split() -> int(x) ]
let mutable [ _; _; q ] = readints()
let a = readints()
let b = readints()
for _ in 1..q do
let arr = Array.create 4001 0
let [ l1; r1; l2; r2 ] = readints()
for i in l1-1 .. r1-1 do
arr.[a.[i]] <- arr.[a.[i]] ^^^ 1
for i in l2-1 .. r2-1 do
arr.[b.[i]] <- arr.[b.[i]] ^^^ 1
out.WriteLine(Array.sum(arr))
out.Close()
示例输入:
5 5 2
76 56 34 52 12
10 91 86 10 91
1 5 2 5
2 2 2 5
输出:
7
3
关于如何提高 Ocaml 或 F# 程序的性能的任何想法?谢谢!
更新
实现@FyodorSoikin 和@JL0PD,F# 代码现在通过了 5 个测试用例中的 2 个:
open System
open System.IO
let out = new StreamWriter(Console.OpenStandardOutput())
let readints () = [| for x in stdin.ReadLine().TrimEnd().Split() -> int(x) |]
let mutable q = readints().[2]
let a = readints()
let b = readints()
for t=1 to q do
let arr = Array.zeroCreate 4001
let llrr = readints()
let l1 = llrr.[0]
let r1 = llrr.[1]
let l2 = llrr.[2]
let r2 = llrr.[3]
for i = l1-1 to r1-1 do
arr.[a.[i]] <- arr.[a.[i]] ^^^ 1
for i = l2-1 to r2-1 do
arr.[b.[i]] <- arr.[b.[i]] ^^^ 1
out.WriteLine(Array.sum(arr))
out.Close()
解决方案
这是一个更惯用的 OCaml 代码,虽然你没有告诉任务是什么,所以实现只是尽可能接近你的
open Printf
let parse_line () =
read_line () |> String.trim |>
String.split_on_char ' ' |>
List.map int_of_string |>
Array.of_list
let main () =
match parse_line () with
| [|n;m;q|] ->
let a = parse_line () in
let b = parse_line () in
let arr = Array.make 4001 0 in
for i = 1 to q do
match parse_line () with
| [|l1; r1; l2; r2 |] ->
Array.fill arr 0 (Array.length arr) 0;
for i = l1-1 to r1-1 do
arr.(a.(i)) <- arr.(a.(i)) lxor 1
done;
for i = l2-1 to r2-1 do
arr.(b.(i)) <- arr.(b.(i)) lxor 1
done;
printf "%d\n" (Array.fold_left (+) 0 arr)
| _ -> failwith "wrong input: expects four numbers"
done
| _ -> failwith "wrong input on line 1: expects three numbers"
let () = main ()
它使用了一个更高效的parse_line
函数,它不依赖于正则表达式进行字符串拆分,尽管我认为它并不重要,因为它不经常被调用(假设它q
很小)。另一个小的优化是我将数组创建移出循环并用零重新填充它,而不是在每次迭代时创建一个新的(也是一个小的优化,考虑到 OCaml 的速度有多快,我不希望它产生很大的影响) s GC 正在工作)。
更好的实现将完全避开中间arr
值。
另外,我真的不认为 Python 实现在绝对数字上比 OCaml 或 F# 快,我认为它没有通过测试,因为它比其他 OCaml 实现慢。
PS找到实际任务后,我可以看到它q
可能会很大并且parse_line
会成为瓶颈,这里有很大的改进空间。
此外,您的方法的最弱点是您正在执行 4k 迭代并创建一个 4k 条目数组,两者都是完全不必要的并且对性能至关重要。您只需要计算主题的数量,因此为每个可能的主题编号分配一个包含 4k 个条目的数组并不是最优的。您可以为此使用哈希表。
推荐阅读
- rx-java - 重用部分 RxJava 流
- node.js - 如何在 pug 模板中运行 moment.js?
- python - 作为 collections.Counter 的结果的字典切片
- javascript - 数据在 ajax 调用中作为空 json 数组对象传递
- html - 内部 div 如何占据视口高度的其余部分
- python - Python中DND字符的滚动统计
- reactjs - 为什么 React 不包含 shadow DOM?它不会比在 JS 解决方案中使用 CSS 更轻松吗?
- javascript - 如何使用 CSS 设置 mCustomScrollbar 的宽度
- php - 如何使用 foreach 循环中的函数修改数组?
- maven-3 - org.jooq.codegen.GeneratorException:读取 XML 配置时出错