Csound Csound-dev Csound-tekno Search About

[Cs-dev] new array methods..

Date2015-07-23 10:10
FromRory Walsh
Subject[Cs-dev] new array methods..
Would it be difficult to add some kind of insert/append/remove methods
for arrays? I find myself longing for some kind of linked list type
interface where I can drop or add elements to an array on the fly. Any
thoughts?

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 10:42
Fromjpff
SubjectRe: [Cs-dev] new array methods..
It woud be possible to provide tese operations, but Steven I tink had 
proposed lists for the next major rewrite. would suggest you need 
insert/delete element and joint lists.  Any others?
==John ff

On Thu, 23 Jul 2015, Rory Walsh wrote:

> Would it be difficult to add some kind of insert/append/remove methods
> for arrays? I find myself longing for some kind of linked list type
> interface where I can drop or add elements to an array on the fly. Any
> thoughts?
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel
>

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 15:57
FromSteven Yi
SubjectRe: [Cs-dev] new array methods..
Lists and arrays are somewhat different things and have different data
structures.  I think one could implement an array-backed list in
user-code with Csound 7 using structs and arrays, i.e.:

struct ArrayList  length:k, data:k[]

opcode list_append(list:ArrayList, value:k)
...
endop

opcode list_insert(list:ArrayList, index:k, value:k)
...
endop

opcode list_slice(list:ArrayList, index0:k, index1:k)
...
endop

etc.

but one couldn't do linked lists as we do not have references at the moment.

We should also be able to create a new list datatype using the type
system and add opcodes for list operations.

I think though that we should make it clear that arrays are not lists.
They have different performance characteristics and would often be
used differently.


On Thu, Jul 23, 2015 at 5:10 AM, Rory Walsh  wrote:
> Would it be difficult to add some kind of insert/append/remove methods
> for arrays? I find myself longing for some kind of linked list type
> interface where I can drop or add elements to an array on the fly. Any
> thoughts?
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 16:00
FromSteven Yi
SubjectRe: [Cs-dev] new array methods..
BTW: There's already a github issue to track adding new datastructures:

https://github.com/csound/csound/issues/446

Maybe we can add comments there as to what operations should be added.

On Thu, Jul 23, 2015 at 10:57 AM, Steven Yi  wrote:
> Lists and arrays are somewhat different things and have different data
> structures.  I think one could implement an array-backed list in
> user-code with Csound 7 using structs and arrays, i.e.:
>
> struct ArrayList  length:k, data:k[]
>
> opcode list_append(list:ArrayList, value:k)
> ...
> endop
>
> opcode list_insert(list:ArrayList, index:k, value:k)
> ...
> endop
>
> opcode list_slice(list:ArrayList, index0:k, index1:k)
> ...
> endop
>
> etc.
>
> but one couldn't do linked lists as we do not have references at the moment.
>
> We should also be able to create a new list datatype using the type
> system and add opcodes for list operations.
>
> I think though that we should make it clear that arrays are not lists.
> They have different performance characteristics and would often be
> used differently.
>
>
> On Thu, Jul 23, 2015 at 5:10 AM, Rory Walsh  wrote:
>> Would it be difficult to add some kind of insert/append/remove methods
>> for arrays? I find myself longing for some kind of linked list type
>> interface where I can drop or add elements to an array on the fly. Any
>> thoughts?
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 16:24
FromFelipe Sateler
SubjectRe: [Cs-dev] new array methods..
On 23 July 2015 at 11:57, Steven Yi  wrote:
> but one couldn't do linked lists as we do not have references at the moment.

I don't think linked lists are a useful thing to implement. See eg
[1]. A variable-size array is all that is needed usually.

[1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html

-- 

Saludos,
Felipe Sateler

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 16:47
Fromjpff
SubjectRe: [Cs-dev] new array methods..
+1

Love lsts n their plsace (ie in LISP)

On Thu, 23 Jul 2015, Felipe Sateler wrote:

> On 23 July 2015 at 11:57, Steven Yi  wrote:
>> but one couldn't do linked lists as we do not have references at the moment.
>
> I don't think linked lists are a useful thing to implement. See eg
> [1]. A variable-size array is all that is needed usually.
>
> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>
> -- 
>
> Saludos,
> Felipe Sateler
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel
>

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 19:22
FromVictor Lazzarini
SubjectRe: [Cs-dev] new array methods..
What is array with amortized doubling?

Victor Lazzarini
Dean of Arts, Celtic Studies, and Philosophy
Maynooth University
Ireland

> On 23 Jul 2015, at 16:47, jpff  wrote:
> 
> +1
> 
> Love lsts n their plsace (ie in LISP)
> 
>> On Thu, 23 Jul 2015, Felipe Sateler wrote:
>> 
>>> On 23 July 2015 at 11:57, Steven Yi  wrote:
>>> but one couldn't do linked lists as we do not have references at the moment.
>> 
>> I don't think linked lists are a useful thing to implement. See eg
>> [1]. A variable-size array is all that is needed usually.
>> 
>> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>> 
>> -- 
>> 
>> Saludos,
>> Felipe Sateler
>> 
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 19:35
FromSteven Yi
SubjectRe: [Cs-dev] new array methods..
Thanks Felipe, that's an interesting article! One thing that concerns
me though is that there's not much data there in terms of test code
and benchmarks.  It's hard to know whether the points that are
speculated about are true. On the other hand, it all seems very
plausible to me. (At least with small list sizes, which would probably
be what most Csounder's use).

I think there's two things to think about. One, what can the user
implement themselves, and two, what should we implement natively.

With CS7, users can create array-backed list data structures. In the
pseudo-code I posted, I was thinking of something similar to Java's
ArrayList implementation.  I assume that is what the article's author
was thinking of too in terms of using arrays to back a list
implementation for inserts, slicing, etc. as the person mentioned
copying of values on inserts.

If a user wanted to create their own linked list though, we'd need
references in the language.  Whether they *should*, I don't know. I'd
rather the mechanism of references be there and let the user decide to
implement what they want.

For what's in Csound itself, I suppose we could also add those
operations Rory mentioned for arrays, but also have a List data
structure as a separate thing.  Or just don't bother with separate
Lists and just make variable-length arrays be what we have in Csound
and commit to array-backed lists as the default list-like thing we
support.

As a separate note, the following is a possible list (ha!) of
operations to have; please add any missing options:

* push(array, val) - add to end of list
* append(array,val) - add to end of list (I guess we should choose
whether to have append or push)
* pop(array) - remove from end of list, return last item
* insert(array, index, val) - insert at index in list
* remove(array, index) - remove item from list
* remove(array, index1, index2) - remove a range from list
* slice - I think this is implemented already by John
* get(array, index) - already implemented for arrays
* set(array, index, val) - already implemented for arrays

With lists, we do have one scenario where things are possibly tricky,
which is sequentially accessing a list and wanting to remove items
while iterating. i.e.:

karray[] init 40
kindx = 0
ksize = array_length(karray)
while(kindx < ksize) loop
  if(karray[kindx] > 0.5)
    remove(karray, kindx) ;; uh oh, this will be bad...
  end
  kindx += 1
pool

I suppose in this case, we would have to tell users don't do that. :P
We could offer guidance such as to not mutate the original array and
instead push into a new array:

karray[] init 40
kres[] init 0
kindx = 0
kindx2 = 0
ksize = array_length(karray)
while(kindx < ksize) loop
  if(karray[kindx] < 0.5)
    push(kres, karray[kindx2])
    kindx2 += 1
  end
  kindx += 1
pool
karray = kres

Anyways, I've got it in my head that lists and arrays are different
things, but I'm happy to abandon that notion if modifying arrays in
Csound will do the job just fine for everyone.

On Thu, Jul 23, 2015 at 11:24 AM, Felipe Sateler  wrote:
> On 23 July 2015 at 11:57, Steven Yi  wrote:
>> but one couldn't do linked lists as we do not have references at the moment.
>
> I don't think linked lists are a useful thing to implement. See eg
> [1]. A variable-size array is all that is needed usually.
>
> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>
> --
>
> Saludos,
> Felipe Sateler
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 19:44
FromSteven Yi
SubjectRe: [Cs-dev] new array methods..
I think this has to do with array list implementations where the list
is initially backed by an array with a given or default size.  When
items get appended or inserted and its greater than the size of the
array, a new array that is double the size of the current one is
created, items copied, then new values inserted into the new array.

Java's ArrayList implementation uses this in its ensureCapacity
method.  A version of that is here:

http://developer.classpath.org/doc/java/util/ArrayList-source.html

I think then the cost is amortized as most appends and inserts won't
trigger the array doubling, only when it hits the limit.  On the other
hand, the size in memory of the array backing the list can become
quite a bit larger than the number of actual items in the list.
Probably not an issue with today's hardware compared to benefits, and
also for the amount of items in a list that might be typically used in
Csound user code.

(Then again, I could be wrong and the author was referring to
something else. :P)

On Thu, Jul 23, 2015 at 2:22 PM, Victor Lazzarini
 wrote:
> What is array with amortized doubling?
>
> Victor Lazzarini
> Dean of Arts, Celtic Studies, and Philosophy
> Maynooth University
> Ireland
>
>> On 23 Jul 2015, at 16:47, jpff  wrote:
>>
>> +1
>>
>> Love lsts n their plsace (ie in LISP)
>>
>>> On Thu, 23 Jul 2015, Felipe Sateler wrote:
>>>
>>>> On 23 July 2015 at 11:57, Steven Yi  wrote:
>>>> but one couldn't do linked lists as we do not have references at the moment.
>>>
>>> I don't think linked lists are a useful thing to implement. See eg
>>> [1]. A variable-size array is all that is needed usually.
>>>
>>> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>>>
>>> --
>>>
>>> Saludos,
>>> Felipe Sateler
>>>
>>> ------------------------------------------------------------------------------
>>> _______________________________________________
>>> Csound-devel mailing list
>>> Csound-devel@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 20:00
FromFelipe Sateler
SubjectRe: [Cs-dev] new array methods..
Yes, amortized doubling is that you double the array size whenever the
list grows beyond the current capacity.

Steven, the second implementation of multiple remove is also better in
that it avoids multiple compactions of the arrays (ie, each time
remove is called), although at the cost of a second array allocation
(which should be created with the same initial capacity as the source
array to avoid multiple allocations).



On 23 July 2015 at 15:44, Steven Yi  wrote:
> I think this has to do with array list implementations where the list
> is initially backed by an array with a given or default size.  When
> items get appended or inserted and its greater than the size of the
> array, a new array that is double the size of the current one is
> created, items copied, then new values inserted into the new array.
>
> Java's ArrayList implementation uses this in its ensureCapacity
> method.  A version of that is here:
>
> http://developer.classpath.org/doc/java/util/ArrayList-source.html
>
> I think then the cost is amortized as most appends and inserts won't
> trigger the array doubling, only when it hits the limit.  On the other
> hand, the size in memory of the array backing the list can become
> quite a bit larger than the number of actual items in the list.
> Probably not an issue with today's hardware compared to benefits, and
> also for the amount of items in a list that might be typically used in
> Csound user code.
>
> (Then again, I could be wrong and the author was referring to
> something else. :P)
>
> On Thu, Jul 23, 2015 at 2:22 PM, Victor Lazzarini
>  wrote:
>> What is array with amortized doubling?
>>
>> Victor Lazzarini
>> Dean of Arts, Celtic Studies, and Philosophy
>> Maynooth University
>> Ireland
>>
>>> On 23 Jul 2015, at 16:47, jpff  wrote:
>>>
>>> +1
>>>
>>> Love lsts n their plsace (ie in LISP)
>>>
>>>> On Thu, 23 Jul 2015, Felipe Sateler wrote:
>>>>
>>>>> On 23 July 2015 at 11:57, Steven Yi  wrote:
>>>>> but one couldn't do linked lists as we do not have references at the moment.
>>>>
>>>> I don't think linked lists are a useful thing to implement. See eg
>>>> [1]. A variable-size array is all that is needed usually.
>>>>
>>>> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>>>>
>>>> --
>>>>
>>>> Saludos,
>>>> Felipe Sateler
>>>>
>>>> ------------------------------------------------------------------------------
>>>> _______________________________________________
>>>> Csound-devel mailing list
>>>> Csound-devel@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>
>>> ------------------------------------------------------------------------------
>>> _______________________________________________
>>> Csound-devel mailing list
>>> Csound-devel@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel



-- 

Saludos,
Felipe Sateler

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-23 21:13
FromRory Walsh
SubjectRe: [Cs-dev] new array methods..
> structure as a separate thing.  Or just don't bother with separate
> Lists and just make variable-length arrays be what we have in Csound

Sound good to me :)

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-24 18:59
FromSteven Yi
SubjectRe: [Cs-dev] new array methods..
The problem with arrays as lists here is that we initialize the number
of elements in an array, but not the initial capacity.  In this case
we have 0 so that the array is truly empty to start and we are only
adding real items to the array.  Otherwise, we'd have to keep track of
elements added and then pop off the "unused" spots of the array.

Things like ArrayLists in Java tend to have initial capacity
arguments.  Perhaps we should add an extra param for initial capacity
for the array version of the init opcode?

On Thu, Jul 23, 2015 at 3:00 PM, Felipe Sateler  wrote:
> Yes, amortized doubling is that you double the array size whenever the
> list grows beyond the current capacity.
>
> Steven, the second implementation of multiple remove is also better in
> that it avoids multiple compactions of the arrays (ie, each time
> remove is called), although at the cost of a second array allocation
> (which should be created with the same initial capacity as the source
> array to avoid multiple allocations).
>
>
>
> On 23 July 2015 at 15:44, Steven Yi  wrote:
>> I think this has to do with array list implementations where the list
>> is initially backed by an array with a given or default size.  When
>> items get appended or inserted and its greater than the size of the
>> array, a new array that is double the size of the current one is
>> created, items copied, then new values inserted into the new array.
>>
>> Java's ArrayList implementation uses this in its ensureCapacity
>> method.  A version of that is here:
>>
>> http://developer.classpath.org/doc/java/util/ArrayList-source.html
>>
>> I think then the cost is amortized as most appends and inserts won't
>> trigger the array doubling, only when it hits the limit.  On the other
>> hand, the size in memory of the array backing the list can become
>> quite a bit larger than the number of actual items in the list.
>> Probably not an issue with today's hardware compared to benefits, and
>> also for the amount of items in a list that might be typically used in
>> Csound user code.
>>
>> (Then again, I could be wrong and the author was referring to
>> something else. :P)
>>
>> On Thu, Jul 23, 2015 at 2:22 PM, Victor Lazzarini
>>  wrote:
>>> What is array with amortized doubling?
>>>
>>> Victor Lazzarini
>>> Dean of Arts, Celtic Studies, and Philosophy
>>> Maynooth University
>>> Ireland
>>>
>>>> On 23 Jul 2015, at 16:47, jpff  wrote:
>>>>
>>>> +1
>>>>
>>>> Love lsts n their plsace (ie in LISP)
>>>>
>>>>> On Thu, 23 Jul 2015, Felipe Sateler wrote:
>>>>>
>>>>>> On 23 July 2015 at 11:57, Steven Yi  wrote:
>>>>>> but one couldn't do linked lists as we do not have references at the moment.
>>>>>
>>>>> I don't think linked lists are a useful thing to implement. See eg
>>>>> [1]. A variable-size array is all that is needed usually.
>>>>>
>>>>> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>>>>>
>>>>> --
>>>>>
>>>>> Saludos,
>>>>> Felipe Sateler
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> _______________________________________________
>>>>> Csound-devel mailing list
>>>>> Csound-devel@lists.sourceforge.net
>>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>>
>>>> ------------------------------------------------------------------------------
>>>> _______________________________________________
>>>> Csound-devel mailing list
>>>> Csound-devel@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>
>>> ------------------------------------------------------------------------------
>>> _______________________________________________
>>> Csound-devel mailing list
>>> Csound-devel@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>
>
>
> --
>
> Saludos,
> Felipe Sateler
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-07-24 19:44
FromFelipe Sateler
SubjectRe: [Cs-dev] new array methods..
Indeed, an optional second argument, which defaults to the initial
number of elements.

On 24 July 2015 at 14:59, Steven Yi  wrote:
> The problem with arrays as lists here is that we initialize the number
> of elements in an array, but not the initial capacity.  In this case
> we have 0 so that the array is truly empty to start and we are only
> adding real items to the array.  Otherwise, we'd have to keep track of
> elements added and then pop off the "unused" spots of the array.
>
> Things like ArrayLists in Java tend to have initial capacity
> arguments.  Perhaps we should add an extra param for initial capacity
> for the array version of the init opcode?
>
> On Thu, Jul 23, 2015 at 3:00 PM, Felipe Sateler  wrote:
>> Yes, amortized doubling is that you double the array size whenever the
>> list grows beyond the current capacity.
>>
>> Steven, the second implementation of multiple remove is also better in
>> that it avoids multiple compactions of the arrays (ie, each time
>> remove is called), although at the cost of a second array allocation
>> (which should be created with the same initial capacity as the source
>> array to avoid multiple allocations).
>>
>>
>>
>> On 23 July 2015 at 15:44, Steven Yi  wrote:
>>> I think this has to do with array list implementations where the list
>>> is initially backed by an array with a given or default size.  When
>>> items get appended or inserted and its greater than the size of the
>>> array, a new array that is double the size of the current one is
>>> created, items copied, then new values inserted into the new array.
>>>
>>> Java's ArrayList implementation uses this in its ensureCapacity
>>> method.  A version of that is here:
>>>
>>> http://developer.classpath.org/doc/java/util/ArrayList-source.html
>>>
>>> I think then the cost is amortized as most appends and inserts won't
>>> trigger the array doubling, only when it hits the limit.  On the other
>>> hand, the size in memory of the array backing the list can become
>>> quite a bit larger than the number of actual items in the list.
>>> Probably not an issue with today's hardware compared to benefits, and
>>> also for the amount of items in a list that might be typically used in
>>> Csound user code.
>>>
>>> (Then again, I could be wrong and the author was referring to
>>> something else. :P)
>>>
>>> On Thu, Jul 23, 2015 at 2:22 PM, Victor Lazzarini
>>>  wrote:
>>>> What is array with amortized doubling?
>>>>
>>>> Victor Lazzarini
>>>> Dean of Arts, Celtic Studies, and Philosophy
>>>> Maynooth University
>>>> Ireland
>>>>
>>>>> On 23 Jul 2015, at 16:47, jpff  wrote:
>>>>>
>>>>> +1
>>>>>
>>>>> Love lsts n their plsace (ie in LISP)
>>>>>
>>>>>> On Thu, 23 Jul 2015, Felipe Sateler wrote:
>>>>>>
>>>>>>> On 23 July 2015 at 11:57, Steven Yi  wrote:
>>>>>>> but one couldn't do linked lists as we do not have references at the moment.
>>>>>>
>>>>>> I don't think linked lists are a useful thing to implement. See eg
>>>>>> [1]. A variable-size array is all that is needed usually.
>>>>>>
>>>>>> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>>>>>>
>>>>>> --
>>>>>>
>>>>>> Saludos,
>>>>>> Felipe Sateler
>>>>>>
>>>>>> ------------------------------------------------------------------------------
>>>>>> _______________________________________________
>>>>>> Csound-devel mailing list
>>>>>> Csound-devel@lists.sourceforge.net
>>>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> _______________________________________________
>>>>> Csound-devel mailing list
>>>>> Csound-devel@lists.sourceforge.net
>>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>>
>>>> ------------------------------------------------------------------------------
>>>> _______________________________________________
>>>> Csound-devel mailing list
>>>> Csound-devel@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>
>>> ------------------------------------------------------------------------------
>>> _______________________________________________
>>> Csound-devel mailing list
>>> Csound-devel@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>
>>
>>
>> --
>>
>> Saludos,
>> Felipe Sateler
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel



-- 

Saludos,
Felipe Sateler

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net

Date2015-08-08 16:22
FromSteven Yi
SubjectRe: [Cs-dev] new array methods..
AttachmentsNone  None  

Hi all,

Following up on this, could Rory or someone file an issue on github so we can track  this?

Thanks,
Steven


On Fri, Jul 24, 2015, 2:45 PM Felipe Sateler <fsateler@gmail.com> wrote:
Indeed, an optional second argument, which defaults to the initial
number of elements.

On 24 July 2015 at 14:59, Steven Yi <stevenyi@gmail.com> wrote:
> The problem with arrays as lists here is that we initialize the number
> of elements in an array, but not the initial capacity.  In this case
> we have 0 so that the array is truly empty to start and we are only
> adding real items to the array.  Otherwise, we'd have to keep track of
> elements added and then pop off the "unused" spots of the array.
>
> Things like ArrayLists in Java tend to have initial capacity
> arguments.  Perhaps we should add an extra param for initial capacity
> for the array version of the init opcode?
>
> On Thu, Jul 23, 2015 at 3:00 PM, Felipe Sateler <fsateler@gmail.com> wrote:
>> Yes, amortized doubling is that you double the array size whenever the
>> list grows beyond the current capacity.
>>
>> Steven, the second implementation of multiple remove is also better in
>> that it avoids multiple compactions of the arrays (ie, each time
>> remove is called), although at the cost of a second array allocation
>> (which should be created with the same initial capacity as the source
>> array to avoid multiple allocations).
>>
>>
>>
>> On 23 July 2015 at 15:44, Steven Yi <stevenyi@gmail.com> wrote:
>>> I think this has to do with array list implementations where the list
>>> is initially backed by an array with a given or default size.  When
>>> items get appended or inserted and its greater than the size of the
>>> array, a new array that is double the size of the current one is
>>> created, items copied, then new values inserted into the new array.
>>>
>>> Java's ArrayList implementation uses this in its ensureCapacity
>>> method.  A version of that is here:
>>>
>>> http://developer.classpath.org/doc/java/util/ArrayList-source.html
>>>
>>> I think then the cost is amortized as most appends and inserts won't
>>> trigger the array doubling, only when it hits the limit.  On the other
>>> hand, the size in memory of the array backing the list can become
>>> quite a bit larger than the number of actual items in the list.
>>> Probably not an issue with today's hardware compared to benefits, and
>>> also for the amount of items in a list that might be typically used in
>>> Csound user code.
>>>
>>> (Then again, I could be wrong and the author was referring to
>>> something else. :P)
>>>
>>> On Thu, Jul 23, 2015 at 2:22 PM, Victor Lazzarini
>>> <Victor.Lazzarini@nuim.ie> wrote:
>>>> What is array with amortized doubling?
>>>>
>>>> Victor Lazzarini
>>>> Dean of Arts, Celtic Studies, and Philosophy
>>>> Maynooth University
>>>> Ireland
>>>>
>>>>> On 23 Jul 2015, at 16:47, jpff <jpff@codemist.co.uk> wrote:
>>>>>
>>>>> +1
>>>>>
>>>>> Love lsts n their plsace (ie in LISP)
>>>>>
>>>>>> On Thu, 23 Jul 2015, Felipe Sateler wrote:
>>>>>>
>>>>>>> On 23 July 2015 at 11:57, Steven Yi <stevenyi@gmail.com> wrote:
>>>>>>> but one couldn't do linked lists as we do not have references at the moment.
>>>>>>
>>>>>> I don't think linked lists are a useful thing to implement. See eg
>>>>>> [1]. A variable-size array is all that is needed usually.
>>>>>>
>>>>>> [1] http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
>>>>>>
>>>>>> --
>>>>>>
>>>>>> Saludos,
>>>>>> Felipe Sateler
>>>>>>
>>>>>> ------------------------------------------------------------------------------
>>>>>> _______________________________________________
>>>>>> Csound-devel mailing list
>>>>>> Csound-devel@lists.sourceforge.net
>>>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> _______________________________________________
>>>>> Csound-devel mailing list
>>>>> Csound-devel@lists.sourceforge.net
>>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>>
>>>> ------------------------------------------------------------------------------
>>>> _______________________________________________
>>>> Csound-devel mailing list
>>>> Csound-devel@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>>
>>> ------------------------------------------------------------------------------
>>> _______________________________________________
>>> Csound-devel mailing list
>>> Csound-devel@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>>
>>
>>
>> --
>>
>> Saludos,
>> Felipe Sateler
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Csound-devel mailing list
>> Csound-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/csound-devel
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Csound-devel mailing list
> Csound-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/csound-devel



--

Saludos,
Felipe Sateler

------------------------------------------------------------------------------
_______________________________________________
Csound-devel mailing list
Csound-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/csound-devel