Ocaml-Каков наиболее эффективный способ вычисления значений ha sh для всех подстрок в строке?

Question

Каков наиболее эффективный способ получения значений ha sh для всех подстрок в строке. Я попытался использовать:

let str1 = "AHTG...";;(*1000000 chars*)
let tam = 2;;
for i = 0 to String.length str1 - tam do
  let st = String.sub str1 i tam in
  Hashtbl.add hash_table (Hashtbl.hash st) i;
done;

для вычисления всех подстрок с размером = 2 (A C, CH, TA, ...) строки с размером = 1000000 и добавить значения в hash_table, но это Думаю, на завершение sh процесса уходит много времени. Мне было интересно, есть ли какой-нибудь процесс более эффективный и быстрый, чем представленный выше?

Answer 1

Во-первых, в строке много подстрок, я бы сказал, около n ^ 2/2. Это большое число при n = 1e6. Если ваша функция ha sh представляет собой черный ящик без известных свойств arithmeti c, и ваша строка также не имеет известных дополнительных свойств, вам в основном нужно выполнить O (n ^ 2) вызовов вашей функции ha sh, что займет много времени.

Если ваша функция ha sh имеет интересные арифметические свойства c, например, ha sh (a ^ b) = ha sh (a) + ha sh (b) mod K, возможно, у вас получится немного лучше. С другой стороны, такие свойства, вероятно, ослабят ha sh.

В качестве немедленного улучшения вы можете рассмотреть функцию ha sh, которая работает непосредственно с подстрокой. Это сэкономит вам много вызовов String.sub и связанных с ним consing и G C. (Вероятно, это не очень поможет, поскольку у OCaml действительно хороший G C для кратковременных значений.)