Re: subsequence storage
Isaac writes:
> then, if I said
> seq[3]=seq[3]&9
> then you'd only need to copy memblock2 to memblock3: 3,4,5,9
> and change the pointer in memblock1, without recopying the
> parent sequence or any of the other subsequences.
That's essentially how it's done. But think about your solution.
Your time goes up as N-squared because you are copying
ever-larger sequences.
Euphoria highly optimizes the most common case of
appending to a *simple* variable:
x = append(x, v)
to avoid (most of) the N-squared behavior,
but for cases involving subscripts, Euphoria uses
the slower, N-squared approach as in:
x[i] = append(x[i], v)
You can use x[i] = repeat(0, N) to avoid the
need for appending, or you can use a simple
variable temporarily while you are appending.
This issue has come up several times on this list.
Neither you nor most of the others came across
the problem independently while writing a "real" program.
It has mainly been pointed out by people who
"heard" of the problem and then constructed
an artificial program to demonstrate it. Even
David Cuny, who first reported it, saw it in
a Euphoria program that was *generated* in an artificial
way by his Basic to Euphoria translator. It wasn't in
hand-written Euphoria code.
When you compare an N-squared algorithm
against an order N algorithm, you can always
increase N until the difference in time becomes
huge. You didn't say what your value of N was.
It's on my list of things to better optimize,
but at the moment I'm working on other optimizations.
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
|
Not Categorized, Please Help
|
|
