OK thanks Raul. Fast append is no issue, appends can be very fast as you suggest. The issue is to maintain an ordering attribute that is fast/custom for each use case (in my case an incoming order).
Linked Lists work very effectively, although having said that I would not try to write a fast matching engine in J. The overhead associated with the multi key indexing you describe below is impractical for low latency matching, and avoided by managing a free space list for bucket re-use. I still believe that both an ordering attribute and also a dictionary, would be very useful assets to an array language, but would need to be implemented “natively” within the language to be fully useful (not an add-on, but part of the language notation, as per kdb+ for dictionaries for example). Thanks Raul, Rob > On 20 Nov 2019, at 8:01 am, Raul Miller <rauldmil...@gmail.com> wrote: > > Fast append can be implemented on an array language without linked > lists -- the mechanism involves leaving some empty memory at the end > of arrays and using that for append when there's only one reference to > the array and that reference is being updated. > > For multi-key indexing, what you would do instead is maintain multiple > "generations" of the data. The big/slow instance gets updated rarely > (folding in the fast/small instance and doing the sorts then during > those updates). At read time you check both of them. The update > overhead here winds up being analogous to the garbage collection > overhead for linked lists. And the traversal overhead can vary - both > linked lists and arrays have overhead, though the details differ, but > in my experience it's straightforward to get the array code to perform > quickly. > > Thanks, > > -- > Raul > > On Tue, Nov 19, 2019 at 3:49 PM 'Rob Hodgkinson' via Programming > <programm...@jsoftware.com> wrote: >> >> I disagree on this point Devon, linked lists are a very powerful data >> structure and can be “overlaid” atop dynamic arrays to maintain a desired >> index order. >> >> Without such a structure the only practical way is to append and (re)sort to >> maintain an array in a suitable form. >> >> An example of this is the construction of an order book in a real time >> trading system, VERY impractical in an array only language. >> However if the array could overlaid with a linked list, then the orders >> could be “appended” on receipt (fast) and a linked list used to update the >> sort order, so the order book can be traversed very efficiently by >> attributes such as Price/Time. >> Without it, one must sort the order book to find the best Price/Time for >> matching … and repeat that on each new order received. >> >> I do use C for this for matching engine rules, but have often thought a >> linked list overlay would be a very powerful way to maintain an ordered >> array for such a purpose. >> >> …/Regards Rob >> >>> On 18 Nov 2019, at 8:06 am, Devon McCormick <devon...@gmail.com> wrote: >>> >>> Linked lists make no sense in a language with dynamic arrays for much the >>> same reason since a linked list is mainly a way of implementing dynamic >>> arrays but has benefit only in a language which lacks these natively. >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
