Associative Arrays and Mobile Automata in Octave

An associative array, also called a dictionary, map, mapping, or hash desk, is a robust knowledge construction that’s constructed into many fashionable programming languages resembling Python, Perl, Ruby, and plenty of others. An associative array is a type of content material addressable reminiscence (CAM). For instance, if you see somebody’s face, you usually keep in mind many different information. That is John Smith. John Smith is your neighbor and lives at 123 Elm Avenue. John’s spouse is Amanda who has lengthy blond hair and so forth.  As associative array associates an object, usually referred to as a key, with one other object, usually referred to as a price.

In lots of programming languages the secret’s a string of characters resembling "John Smith" and the worth is one other string resembling "Handle:123 Elm Avenue;Spouse:Amanda" and so forth. In some object oriented laptop programming languages, the important thing may be any type of object and the worth may be any type of object resembling the important thing <John Smith's Face Object> and the worth <John Smith's Figuring out Info Object>. An associative array is basically equal to a single desk in a relational database (RDBMS). In precept, a community of associative arrays can characterize advanced summary data and reasoning.

Technically, associative arrays are often carried out utilizing a hash desk. A hash desk makes use of modulo arithmetic to map an object resembling a string of characters to the numerical index of an array of values. This array of values just isn’t a easy one dimensional array as a result of there may be collisions the place two keys, objects resembling strings of characters, “hash” to the identical array index. If this occurs, there are numerous strategies resembling hanging a linked record of components off the array to deal with the collision.  Utilizing a hash desk implies that the time to lookup a price is sort of fixed (O(1)) whatever the measurement of the hash desk.

The hash desk might have hundreds of thousands of entries, nevertheless it takes the identical small variety of operations to lookup the related worth. First, compute the array index utilizing modulo arithmetic on the numeric worth of the “key”. Second, deal with any collisions. The hash desk needs to be massive sufficient that collisions are uncommon. In precept, an associative array may very well be carried out in different methods, however hash tables of some variety are typically the quickest, most versatile solution to implement an associative array.  Therefore, the phrases associative array, dictionary, map, mapping, and hash desk are sometimes used interchangeably.

Octave is a free, open-source numerical programming atmosphere that’s principally appropriate with MATLAB. Octave is basically constructed round matrices (two dimensional arrays) and N (2,3,and many others.) dimensional arrays. By default, matrices and N-D arrays in Octave are of the kind double (often a 64 bit IEEE-754 double precision floating level quantity).

That is as a result of historical past of MATLAB (quick for Matrix Laboratory) which began life as an interactive atmosphere for performing two dimensional matrix algebra and computations. At first look, Octave lacks associative arrays which is a big deficiency for some varieties of programming together with some varieties of mathematical programming. Octave does, in truth, have associative arrays. This text reveals learn how to use associative arrays in Octave and use associative arrays to implement mobile automata, a sort of discrete mathematical mannequin.

Associative Arrays in Octave

Whereas Octave lacks an explicitly recognized associative array, dictionary, map, mapping, or hash desk knowledge kind, Octave does have knowledge constructions or structs much like constructions within the C household of programming languages. For instance, in Octave one can outline a construction interactively like this:

octave-3.2.3:2> a.key = 'worth'
a =
{
key = worth
}

octave-3.2.3:3> a.key2 = 'value2'
a =
{
key = worth
key2 = value2
}

The construction a now has two fields “key” and “key2” with values ‘worth’ and ‘value2’. In Octave, the information constructions are carried out utilizing a hash desk and might act as a completely purposeful associative array. Octave offers a number of capabilities to entry and manipulate constructions, making it straightforward to make use of a construction in Octave as an associative array.

Constructed-in Operate: struct ("subject", worth, "subject", worth,...)
Constructed-in Operate: isstruct (expr)
Constructed-in Operate: rmfield (s, f)
Operate File: [k1,..., v1] = setfield (s, k1, v1,...)
Operate File: [t, p] = orderfields (s1, s2)
Constructed-in Operate: fieldnames (struct)
Constructed-in Operate: isfield (expr, title)
Operate File: [v1,...] = getfield (s, key,...)
Operate File: substruct (kind, subs,...)

All of those capabilities are helpful. Most vital for the needs of this text are struct("subject", worth, "subject", worth,...) which creates an information construction explicitly, setfield(structure_name, key, worth,...) which assigns a price to a key, and getfield(structure_name, key) which retrieves the worth related to key. These are used within the examples on this article to implement mobile automata.

Mobile Automata

A mobile automaton (plural, mobile automata, typically abbreviated as CA) is a discrete mathematical mannequin. A typical mobile automaton consists of a grid of cells with a number of dimensions. Typically, the cells have two doable values, 0 and 1, which are sometimes displayed as black and white pixels graphically.  The mobile automaton evolves over time in discrete time steps. With every time step or replace, a cell adjustments to 0 or 1 based mostly on the values of the cells in its neighborhood. A mobile automaton has a rule that specifies the way it updates.

Mobile automata have been utilized in leisure (they make fairly footage), arithmetic, physics, and numerous different fields. In all probability probably the most well-known mobile automaton is the “Sport of Life”, a two dimensional mobile automaton with many entertaining and attention-grabbing properties invented by the mathematician John Conway within the 1970’s.

Stephen Wolfram, the creator of the Mathematica laptop algebra system and mathematical analysis device, has had a protracted standing curiosity in mobile automata. His ebook, A New Type of Science, speculates that the universe may be a kind of mobile automaton and be “computationally undecidable” (in layman’s phrases, math and science don’t have all of the solutions). Matthew Cook dinner, who assisted Wolfram within the analysis for A New Type of Science, proved {that a} significantly easy mobile automaton referred to as “rule 110” can perform as a normal function laptop similar to extra advanced programs such because the Pentium laptop chip. An implementation of the “rule 110” mobile automaton is likely one of the examples on this article.

The rule for a mobile automaton may be simply represented as an associative array that maps every doable neighborhood to a brand new worth. That is quite simple and intuitive. It’s straightforward to implement mobile automata in programming languages with built-in associative array knowledge sorts. That is illustrated in Octave within the examples on this article.

automata.m

% Description:
%
% implementation of rule 30 and rule 110 mobile automata utilizing an
% associative array in Octave
%
% Writer: John F. McGowan, Ph.D.
% E-Mail: [email protected]
%

universe_size = 600;
seed_start = universe_size/2;

rule30 = struct("III", "O", "IIO", "O", "IOI", "O", "IOO", "I", ...
"OII", "I", "OIO", "I", "OOI", "I", "OOO", "O"); % use Octave struct as an associative array (additionally knowns as dictionary or mapping or hash desk)

myseed = repmat('O', 1, universe_size);
myseed(seed_start) = 'I';

myimage = simulate_ca(myseed, rule30, seed_start);
determine(1);
imshow(myimage);
title('Rule 30 Mobile Automaton');
print('rule30.jpg');

% rule 110
% confirmed to be Turing Full
%

rule110 = struct("III", "O", "IIO", "I", "IOI", "I", "IOO", "O", ...
"OII", "I", "OIO", "I", "OOI", "I", "OOO", "O");

myimage = simulate_ca(myseed, rule110, seed_start);
determine(2)
imshow(myimage);
title('Rule 110 Mobile Automaton');
print('rule110.jpg');

disp('ALL DONE');

which makes use of the perform simulate_ca outlined within the following code:

simulate_ca.m

perform [result] = simulate_ca(myseed, rule, niter)
% simulate_ca(myseed, rule, niter)
%
% simulate <niter> iterations of a 1D mobile automaton specified by <rule>
% rule beginning with the seed <myseed>
%
% Writer: John F. McGowan, Ph.D.
% E-Mail: [email protected]
%
rule_name = inputname(2);

replace = repmat('O', 1, size(myseed));

earlier = myseed;

nx = size(myseed);
ny = niter + 1

outcome = zeros(ny, nx, "uint8");
lut = ones(1, 26)*255; % white background
lut(9) = 0; % map I to min grey scale stage

printf("rule: %sn", rule_name);
fflush(stdout);
printf("%sn", earlier);
fflush(stdout);

index = uint8(earlier) - uint8('A') + 1;
binary = lut(index);
outcome(1,:) = binary;

for iter = 1:niter % iterations
for i = 1:size(myseed)-3 % loop over cells
key = earlier(i:i+2);
replace(i+1) = getfield(rule, key);
finish % loop over cells
printf("%sn", replace);
fflush(stdout);
earlier = replace;
index = uint8(earlier) - uint8('A') + 1;
binary = lut(index);
outcome(iter+1,:) = binary;
finish % iterations

finish % perform simulate_ca

The Timing of Associative Arrays in Octave

The code beneath exams the timing of associative arrays in Octave. As anticipated if a hash desk is used to implement an associative array, the lookup time is basically unbiased of the scale of the associative array in Octave, which is nice. As with many options in Octave and different mathematical scripting instruments, the lookup time is kind of gradual.

For instance, on a 3GHz Macintosh operating OS X, the lookup time various between 1 and 10 milliseconds. That is a lot slower than a compiled implementation of a hash desk within the C programming language or one other quick compiled language. Though languages resembling Octave are slowly closing the velocity of execution hole with compiled languages resembling C, the compiled languages nonetheless win handily in some circumstances.

dictionary_time.m

%
% measure timing of associative arrays in Octave
% display lookup time just isn't slowed by variety of keys (fields)
% within the associative array/dictionary. Works like a hash desk.
%
% Writer: John F. McGowan, Ph.D.
% E-Mail: [email protected]
%
%

clear small_dict;
small_dict = struct('key', 'worth'); % be certain a is outlined

clear big_dict;
big_dict = struct('key', 'worth'); % be certain a is outlined

offset = uint8('A') -1;

n = 3;

if(n > 26) % 26 characters in English alphabet
n = 26;
finish

[total, user, system] = cputime();
for i = 1:n
for j = 1:n
for ok = 1:n
key = char([i j k] + offset);
worth = ['value' key];
%     printf("key: %s worth: %sn", key, worth);
small_dict = setfield(small_dict, key, worth);
finish
finish
finish
[total1, user1, system1] = cputime();

printf("CPU TIME: %fn", total1 - whole);

printf("creating huge dictionaryn");
fflush(stdout);

% create huge dictionary (associative array)

n = 26;

if(n > 26) % 26 characters in English alphabet
n = 26;
finish

[total, user, system] = cputime();
for i = 1:n
printf("creating fields beginning with %sn", char(i + offset));
fflush(stdout);
for j = 1:n
for ok = 1:n
key = char([i j k] + offset);
worth = ['value' key];
%     printf("key: %s worth: %sn", key, worth);
big_dict = setfield(big_dict, key, worth);
finish
finish
finish
[total1, user1, system1] = cputime();

printf("CPU TIME: %fn", total1 - whole);

% measure entry time

[total, user, system] = cputime();
blatz = getfield(small_dict, 'AAA');
[total1, user1, system1] = cputime();
printf("%f seconds to retrieve %s for AAA from small dictn", total1 -
whole, blatz);

[total, user, system] = cputime();
blatz = getfield(big_dict, 'AAA');
[total1, user1, system1] = cputime();
printf("%f seconds to retrieve %s for AAA from huge dictn", total1 -
whole, blatz);

disp('ALL DONE');

Conclusion

There are associative arrays, also called dictionaries, maps, mappings, or hash tables, in Octave. That is poorly documented each within the official documentation and most on-line details about Octave. One can carry out the identical duties and implement the identical algorithms with the associative arrays (knowledge constructions or structs) in Octave that one can with the explicitly recognized associative array knowledge sorts in Perl, Python, Ruby, Java, and plenty of different fashionable programming languages. Associative arrays are very helpful for implementing sure sorts of arithmetic in Octave resembling, however not restricted to, mobile automata.

© 2011 John F. McGowan

In regards to the Writer

John F. McGowan, Ph.D. is a software program developer, analysis scientist, and guide. He works primarily within the space of advanced algorithms that embody superior mathematical and logical ideas, together with speech recognition and video compression applied sciences. He has intensive expertise growing software program in C, C++, Visible Fundamental, Mathematica, MATLAB, and plenty of different programming languages. He’s most likely finest identified for his AVI Overview, an Web FAQ (Often Requested Questions) on the Microsoft AVI (Audio Video Interleave) file format. He has labored as a contractor at NASA Ames Analysis Heart concerned within the analysis and growth of picture and video processing algorithms and expertise. He has printed articles on the origin and evolution of life, the exploration of Mars (anticipating the invention of methane on Mars), and low cost entry to house. He has a Ph.D. in physics from the College of Illinois at Urbana-Champaign and a B.S. in physics from the California Institute of Expertise (Caltech). He may be reached at [email protected].

Admin’s message: Searching for some nice mathematical reads? Try our record of must-read math books.