[Cs-dev] new array methods..
Date | 2015-07-23 10:10 |
From | Rory 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 |
Date | 2015-07-23 10:42 |
From | jpff |
Subject | Re: [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 |
Date | 2015-07-23 15:57 |
From | Steven Yi |
Subject | Re: [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 |
Date | 2015-07-23 16:00 |
From | Steven Yi |
Subject | Re: [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 |
Date | 2015-07-23 16:24 |
From | Felipe Sateler |
Subject | Re: [Cs-dev] new array methods.. |
On 23 July 2015 at 11:57, Steven Yi |
Date | 2015-07-23 16:47 |
From | jpff |
Subject | Re: [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 |
Date | 2015-07-23 19:22 |
From | Victor Lazzarini |
Subject | Re: [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 |
Date | 2015-07-23 19:35 |
From | Steven Yi |
Subject | Re: [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 |
Date | 2015-07-23 19:44 |
From | Steven Yi |
Subject | Re: [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 |
Date | 2015-07-23 20:00 |
From | Felipe Sateler |
Subject | Re: [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 |
Date | 2015-07-23 21:13 |
From | Rory Walsh |
Subject | Re: [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 |
Date | 2015-07-24 18:59 |
From | Steven Yi |
Subject | Re: [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 |
Date | 2015-07-24 19:44 |
From | Felipe Sateler |
Subject | Re: [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 |
Date | 2015-08-08 16:22 |
From | Steven Yi |
Subject | Re: [Cs-dev] new array methods.. |
Attachments | None None |
Hi all, Following up on this, could Rory or someone file an issue on github so we can track this? Thanks, On Fri, Jul 24, 2015, 2:45 PM Felipe Sateler <fsateler@gmail.com> wrote: Indeed, an optional second argument, which defaults to the initial |