Dictionaries might provide a useful optimization for compression algorithms
For example: https://rosettacode.org/wiki/LZW_compression#J See also: https://en.wikipedia.org/wiki/DEFLATE https://en.wikipedia.org/wiki/LZ77_and_LZ78 https://en.wikipedia.org/wiki/Prediction_by_partial_matching https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform Thanks, -- Raul On Mon, Nov 18, 2019 at 1:15 PM Devon McCormick <devon...@gmail.com> wrote: > > I would like to see examples of where a dictionary would be the preferred > way of dealing with some data. Does anyone know of any, not necessarily in > J, that are short and to the point? > > > On Mon, Nov 18, 2019 at 1:02 PM Danil Osipchuk <danil.osipc...@gmail.com> > wrote: > > > I quickly put together a minimal implementation along those lines, to have > > a subject for a discussion regarding performance and general usage > > An object 'Map has a hash list mapping hash value to other 2 lists -- boxed > > lists of boxed keys (per hash value) and boxed lists of boxed values. > > > > It is not thoroughly tested and not well thought through about argument > > boxing and ranks, but should be pretty close to what would be a > > straightforward implementation of the thing. > > 'get_Map key' should give a boxed value for a key or raise a error if key > > is absent > > 'somevalue get_Map key' should give a stored value or save and return > > somevalue if key is not there (but I can not catch an exception raised in a > > monad called from a dyad - something silly, but have to go home) > > 'key put__Map value' stores a value > > 'delkey__Map key' removes a key if there > > > > M=: 0 conew'map' > > > > 123 put__M 1230 > > > > 1230 > > > > 'strkey' put__M 'strval' > > > > strval > > > > (<'boxkey') put__M <'boxval' > > > > ┌──────┐ > > > > │boxval│ > > > > └──────┘ > > > > keys__M > > > > ┌─────┬────────┬──────────┐ > > > > │┌───┐│┌──────┐│┌────────┐│ > > > > ││123│││strkey│││┌──────┐││ > > > > │└───┘│└──────┘│││boxkey│││ > > > > │ │ ││└──────┘││ > > > > │ │ │└────────┘│ > > > > └─────┴────────┴──────────┘ > > > > hashes__M > > > > _1845511330 2120780259 _71755953 > > > > values__M > > > > ┌──────┬────────┬──────────┐ > > > > │┌────┐│┌──────┐│┌────────┐│ > > > > ││1230│││strval│││┌──────┐││ > > > > │└────┘│└──────┘│││boxval│││ > > > > │ │ ││└──────┘││ > > > > │ │ │└────────┘│ > > > > └──────┴────────┴──────────┘ > > > > get__M 123 > > > > ┌────┐ > > > > │1230│ > > > > └────┘ > > > > get__M 'not there' > > > > |uncaught throw.: get__M > > > > | get__M'not there' > > > > 'to set to something' get__M 'not there' > > > > |uncaught throw.: get > > > > | get y > > > > delkey__M 123 > > > > 1 > > > > get__M 123 > > > > |uncaught throw.: get__M > > > > | get__M 123 > > > > values__M > > > > ┌────────┬──────────┐ > > > > │┌──────┐│┌────────┐│ > > > > ││strval│││┌──────┐││ > > > > │└──────┘│││boxval│││ > > > > │ ││└──────┘││ > > > > │ │└────────┘│ > > > > └────────┴──────────┘ > > > > keys__M > > > > ┌────────┬──────────┐ > > > > │┌──────┐│┌────────┐│ > > > > ││strkey│││┌──────┐││ > > > > │└──────┘│││boxkey│││ > > > > │ ││└──────┘││ > > > > │ │└────────┘│ > > > > └────────┴──────────┘ > > > > пн, 18 нояб. 2019 г. в 16:10, Henry Rich <henryhr...@gmail.com>: > > > > > Right now I am thinking that the need for dictionaries could be met by a > > > class whose instances are associative memories. Key, values, > > > hashtables, chains if needed would be stored inside the instance. The > > > interface would be simply x Put y and Get y. I reckon this would be > > > fast enough without any special support from the interpreter beyond the > > > hash calculation that is there now. > > > > > > Henry Rich > > > > > > On 11/18/2019 6:10 AM, Danil Osipchuk wrote: > > > > symbols are essentially names optimized for lookup and comparison, as > > > such > > > > they are useful to implement locales efficiently, if one to build an > > map > > > > using those as keys, indeed one gets something resembling K > > dictionaries > > > > http://www.math.bas.bg/bantchev/place/k.html : > > > > > > > > "Another distinguishing feature of K is the use of dictionaries: > > > > associative tables whose keys are symbols, i.e., internalized strings. > > In > > > > turn, dictionaries are the building material of a hierarchically > > > organized > > > > global data space called the K-tree" > > > > > > > > https://github.com/kevinlawler/kona/wiki/Dictionaries > > > > > > > > This is important case of course, but still a restriction. Tables in > > Lua > > > > are more fundamental: > > > > > > > > "The table type implements associative arrays. An associative array is > > an > > > > array that can be indexed not only with numbers, but also with strings > > or > > > > any other value of the language, except *nil*. Moreover, tables have no > > > > fixed size; you can add as many elements as you want to a table > > > > dynamically. Tables are the main (in fact, the only) data structuring > > > > mechanism in Lua, and a powerful one. We use tables to represent > > ordinary > > > > arrays, symbol tables, sets, records, queues, and other data > > structures, > > > in > > > > a simple, uniform, and efficient way. Lua uses tables to represent > > > packages > > > > as well. When we write io.read, we mean "the read entry from the io > > > > package". For Lua, that means "index the table io using the string > > "read" > > > > as the key". > > > > > > > > > > > > > > > > пн, 18 нояб. 2019 г. в 13:11, 'Mike Day' via Programming < > > > > programm...@jsoftware.com>: > > > > > > > >> It's a long time since I played with s: - do J symbols have any > > > >> relevance to dictionaries/directories? > > > >> > > > >> APL/J cousin, K, appears to have the dictionary as pretty central to > > its > > > >> data organisation, but maybe > > > >> that's more akin to J's locales. > > > >> > > > >> Neither topic helpful probably relevant here, but might start a hare! > > > >> > > > >> Mike > > > >> > > > >> On 18/11/2019 02:49, Henry Rich wrote: > > > >>> In J I find myself coming back to simple arrays for most data > > > structures. > > > >>> > > > >>> Trees can be represented as boxes containing subtrees. That works, > > > >>> but is usually more trouble than simply managing an array. > > > >>> > > > >>> Linked lists are used only for efficiency, and in the cases where > > that > > > >>> matters you can easily have a list of indexes to an array of data > > > items. > > > >>> > > > >>> Stacks are just lists, as Devon said. > > > >>> > > > >>> The datatype I really want is a directory object that acts as an > > > >>> efficient and easy-to-use associative memory. You put key/values in > > > >>> and then retrieve a value by presenting its key. Has anyone written > > > >>> an addon for that? > > > >>> > > > >>> (Note: the primitive 128!:8 (create a hash for a noun) was added to > > > >>> J9.01 with this in mind) > > > >>> > > > >>> Henry Rich > > > >>> > > > >>> On 11/17/2019 8:16 PM, 'Bo Jacoby' via Programming wrote: > > > >>>> I failed to communicate the links before, but here they are. > > > >>>> Ordinal fractions are somewhat like infinite-dimensional arrays. > > > >>>> > > > >> > > > > > https://www.academia.edu/10031088/ORDINAL_FRACTIONS_-_the_algebra_of_data > > > >>>> > > > >>>> > > > >>>> http://www.statemaster.com/encyclopedia/Ordinal-fraction > > > >>>> Bo. > > > >>>> > > > >>>> Den søndag den 17. november 2019 22.07.28 CET skrev Devon > > > >>>> McCormick <devon...@gmail.com>: > > > >>>> Trees are simple to implement in J - > > > >>>> https://code.jsoftware.com/wiki/User:Devon_McCormick/Trees - as are > > > >>>> graphs > > > >>>> - > > > >>>> > > > >> > > > > > https://code.jsoftware.com/wiki/NYCJUG/2009-11-10/BreadthFirstGraphTraversal > > > >>>> . > > > >>>> A stack is simple to implement too but I'm not sure why you would > > > >>>> want to > > > >>>> as it's simply a vector with very restrictive rules to manipulate > > it. > > > >>>> 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. > > > >>>> > > > >>>> On Sun, Nov 17, 2019 at 8:24 AM 'Bo Jacoby' via Programming < > > > >>>> programm...@jsoftware.com> wrote: > > > >>>> > > > >>>>> ORDINAL FRACTIONS - the algebra of data > > > >>>>> > > > >>>>> > > > >>>>> > > > >>>>> | > > > >>>>> | > > > >>>>> | > > > >>>>> | | | > > > >>>>> > > > >>>>> | > > > >>>>> > > > >>>>> | > > > >>>>> | > > > >>>>> | | > > > >>>>> ORDINAL FRACTIONS - the algebra of data > > > >>>>> > > > >>>>> This paper was submitted to the 10th World Computer Congress, IFIP > > > 1986 > > > >>>>> conference, but rejected by the referee.... > > > >>>>> | > > > >>>>> > > > >>>>> | > > > >>>>> > > > >>>>> | > > > >>>>> > > > >>>>> > > > >>>>> > > > >>>>> > > > >>>>> Den søndag den 17. november 2019 07.12.02 CET skrev Raul > > > Miller < > > > >>>>> rauldmil...@gmail.com>: > > > >>>>> > > > >>>>> Arrays are roughly analogous to computer memory. > > > >>>>> > > > >>>>> Put different: I think you are asking the wrong question. > > > >>>>> > > > >>>>> (Partially: it's worth thinking about why you pick whichever data > > > >>>>> structures...) > > > >>>>> > > > >>>>> ((It can also sometimes be useful to look on rosettacode for > > > >>>>> examples of > > > >>>>> various daya structure handling mechanisms.)) > > > >>>>> > > > >>>>> Thanks, > > > >>>>> > > > >>>>> -- > > > >>>>> Raul > > > >>>>> > > > >>>>> On Sat, Nov 16, 2019 at 6:00 PM Jimmy Gauvin < > > jimmy.gau...@gmail.com > > > > > > > >>>>> wrote: > > > >>>>> > > > >>>>>> Hi, > > > >>>>>> > > > >>>>>> when dealing with data structures other than arrays such as trees, > > > >>>>> graphs, > > > >>>>>> stacks, linked lists what other programming language do you resort > > > >>>>>> to ? > > > >>>>>> > > > >>>>>> Or do stick with J for all endeavours? > > > >>>>>> > > > >>>>>> > > > >>>>>> Jimmy > > > >>>>>> > > > ---------------------------------------------------------------------- > > > >>>>>> 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 > > > >>>>> > > > >>> > > ---------------------------------------------------------------------- > > > >>> 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 > > > > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > -- > > Devon McCormick, CFA > > Quantitative Consultant > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
