Stackoverflow со специализированным Hashtbl (через Hashtbl.make) - PullRequest
Новая
       20

Stackoverflow со специализированным Hashtbl (через Hashtbl.make)

4 голосов
/ 20 июля 2011

Я использую этот кусок кода, и перепуск стека будет запущен, если я использую Hashtbl Extlib, ошибка не происходит. Любые советы, чтобы использовать специализированный Hashtbl без stackoverflow? 

module ColorIdxHash = Hashtbl.Make(
  struct
    type t = Img_types.rgb_t
    let equal = (==)
    let hash = Hashtbl.hash
  end
)
(* .. *)
let (ctable: int ColorIdxHash.t) = ColorIdxHash.create 256 in
    for x = 0 to width -1 do
      for y = 0 to height -1 do
        let c = Img.get img x y in
        let rgb = Color.rgb_of_color c in
          if not (ColorIdxHash.mem ctable rgb) then ColorIdxHash.add ctable rgb (ColorIdxHash.length ctable)
      done
    done;
(* .. *)

Обратный след указывает на hashtbl.ml:

Неустранимая ошибка: исключение Stack_overflow Возникает в файле "hashtbl.ml", строка 54, символы 16-40 Вызывается из файла "img / write_bmp.ml", строка 150 символов 52-108 ...

Есть подсказки?

Ответы [ 2 ]

5 голосов
/ 20 июля 2011

Итак, вы используете физическое равенство (==) для сравнения цветов в вашей хеш-таблице. Если цвета являются структурированными значениями (я не могу сказать из этого кода), ни одно из них не будет физически равным друг другу. Если все цвета являются разными объектами, все они попадут в таблицу, которая может быть довольно большим количеством объектов. С другой стороны, хеш-функция будет основана на фактических значениях цвета R, G, B, поэтому вполне может быть большое количество дубликатов. Это будет означать, что ваши хэш-контейнеры будут иметь очень длинные цепочки. Возможно, некоторая внутренняя функция не является хвостовой рекурсивной, и поэтому переполняет стек.

Обычно длина самой длинной цепочки составляет 2 или 3, поэтому неудивительно, что эта ошибка возникает не часто.

Глядя на мою копию hashtbl.ml (OCaml 3.12.1), я не вижу ничего нерекурсивного в строке 54. Так что мое предположение может быть неверным. В строке 54 новый внутренний массив выделяется для хэш-таблицы. Поэтому другая идея состоит в том, что ваша хеш-таблица становится слишком большой (возможно, из-за нежелательных дубликатов).

Одна из попыток - использовать структурное равенство (=) и посмотреть, исчезнет ли проблема.

1 голос
/ 20 июля 2011

Одна из причин, по которой у вас могут быть невыполнения или переполнения стека, - если ваш тип содержит циклические значения.(==) завершается циклическими значениями (в то время как (=) может и не быть), но Hash.hash, вероятно, небезопасно для цикла.Поэтому, если вы манипулируете циклическими значениями типа Img_types.rgb_t, вы должны разработать свою единственную безопасную для цикла хеш-функцию - обычно вызывая Hash.hash только для одного из нециклических подполей / подкомпонентов ваших значений.

Я уже был укушен именно этой проблемой в прошлом.Не забавная ошибка, чтобы выследить.

...