1

Opaで「文字列を逆にする」関数を実装するための最もパフォーマンスの高い方法は何ですか？

私は知っていString.reverse()ます。それは仕事を成し遂げますが、そのソースコードはいくつかの外部関数にバインドされています。文字列を並べ替えるのに最適な（最速の）ツールを理解したいと思います。

したがって、たとえば、これは機能しますが、特に高速ではありません。

reverse(s:string) =
  p = parser
    | x=(.) xs=(.*) -> Text.concat(reverse(Text.to_string(xs)), x)
    | x=(.*) -> x
  Parser.parse(p, s)

どうすればこれをより良く実行できますか？

編集：akoprowskiの回答に基づく別の実装

これが彼が考えていることだと思います。これはパーサーバージョンよりもはるかに高速ですString.reverseが、文字列を逆にするだけでよい場合は、組み込みの方法を使用できます。

reverse_list(l:list(string)):list(string) =
  match l with
  | [x|xs] -> reverse_list(xs) ++ [x]
  | _ -> []

reverse_string(s:string) =
  string_list = List.init((i -> String.get(i, s)), String.length(s))
  String.flatten(reverse_list(string_list))

編集：上記の実装は理想的ではありません

より良いオプションについては、受け入れられた回答を確認してください。

4

1 に答える 1

1

なぜあなたは使いたくないのですString.reverseか？(これは、文字列を反転するための推奨される方法です)。それともただの練習ですか？

List.init文字のリストを生成しString.get(文字列の n 番目の文字を取得する)、文字String.flattenのリストを文字列に変換するために使用することをお勧めします。

これは、解析ベースのアプローチよりも高速である必要があります。は二次的な複雑さを持っているため、遅いのも不思議ではありません。

編集：私が考えていた解決策：

reverse_string(s:string) =
  n = String.length(s)
  rev_list = List.init((i -> String.get(n - i - 1, s)), n)
  String.flatten(rev_list)
于 2011-10-26T09:36:04.563 に答える