Re: A reference implementation of text2interval - off list

[Dmitry Nadezhin <dmitry.nadezhin@xxxxxxxxxx>]

Ian,

(iii) and (iv) were trade-offs between time and memory. They have the same accuracy.

Nevertheless, you are right: (iv) can be either string or stream, because O(n) memory allows
to store stream. "Input stream" is better.

  -Dima

----- Исходное сообщение -----
От: ianm@xxxxxxxxxx
Кому: dmitry.nadezhin@xxxxxxxxxx
Отправленные: Пятница, 12 Июль 2013 г 16:45:34 GMT +04:00 Абу-Даби, Маскат
Тема: Re: A reference implementation of text2interval - off list

Is there a typo in
    iii) Tightest when l <= u, detects l > u.
      Input string, O(1) memory, O(n^2) time.
   iv) Tightest when l <= u, detects l > u.
      Input string, O(n) memory, O(n log n log log n) time, difficult programming.
?  In particular, what's the difference between
    Tightest when l <= u, detects l > u.
      Input string,
and
    Tightest when l <= u, detects l > u.
      Input string,
Shouldn't one "string" be "stream"?

- Ian McIntosh          IBM Canada Lab         Compiler Back End Support and Development

Attachment: graycol.gif
Description: GIF image

Attachment: ecblank.gif
Description: GIF image