[PD] fast way to append to [text] (was: [array quantile] explanation)

[Christof Ressi]

> I wonder whether a dedicated [text append] could help here, that lacks
> the functionality of [text set], but would be fast.

that would be a leaky abstraction. I think the [text set] / [text get] methods can be improved to get O(N) complexity. I think we only need to cache the line positions.

Christof

> Gesendet: Montag, 28. Oktober 2019 um 09:39 Uhr
> Von: "Roman Haefeli" <reduzent at gmail.com>
> An: Pd-List <pd-list at lists.iem.at>
> Betreff: [PD] fast way to append to [text] (was: [array quantile] explanation)
>
> While still not understanding the purpose of [array quantile], I was
> able to achieve this:
> 
> > I have n samples and input q while 0 < q < 1. I would like to know
> > the
> > value x for which q*100 percent samples are smaller than x and (1-
> > q)*100 percent bigger. 
> 
> Since [text define] got a 'sort'ing feature recently, I am using it to
> sort the array. Thus, I migrate the data from [array] to [text], sort
> it, transfer it back to the [array]. Once sorted, it is easy to get the
> median or any n-quantile. 
> 
> I noticed, that [text set] has a time complexity of O(n²), so for
> efficiently copying data around, I went [array get] -> [list store] ->
> [text fromlist] which has linear time complexity.
> 
> I see that [text set] is versatile and thus comes with a cost, but
> wouldn't it be nice to still have a way to append to the existing text
> with linear time complexity? I've been using [text] a few times and
> realize only now that because of this it is only feasible up to a
> certain number of lines, since adding lines is getting costlier the
> larger the stored text. Only when the whole text can be loaded at once
> (which is not always the case), the [list store] work-around can be
> used.
> 
> I wonder whether a dedicated [text append] could help here, that lacks
> the functionality of [text set], but would be fast. Or is it the data
> structure used by [text] itself that makes it impossible to append in
> linear time?
> 
> Roman
> _______________________________________________
> Pd-list at lists.iem.at mailing list
> UNSUBSCRIBE and account-management -> https://lists.puredata.info/listinfo/pd-list
>