Опа: Какой самый быстрый способ перевернуть строку? - PullRequest
Новая
       34

Опа: Какой самый быстрый способ перевернуть строку?

1 голос
/ 26 октября 2011

Каков наиболее эффективный способ реализации функции «перевернуть строку» в Opa?

Мне известно о String.reverse().Он выполняет свою работу, но его исходный код привязан к некоторой внешней функции.Я хочу понять, какие самые лучшие (самые быстрые) инструменты для изменения порядка строк.

Так, например, это работает, но не особенно быстро: 

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

Как я могузаставить это работать лучше?

Редактировать: Другая реализация, основанная на ответе Акопровского

Я думаю, это то, что он имеет в виду.Эта версия намного быстрее, чем версия парсера, но встроенный 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))

Редактировать: вышеприведенная реализация не являетсяИдеально

Проверьте принятый ответ для лучшего варианта.

1 Ответ

1 голос
/ 26 октября 2011

Почему вы не хотите использовать 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)
...