how to avoid ERROR: No random access

Questions and problems about using polymake go here.
qichen
Posts: 8
Joined: 09 Jul 2020, 02:01

how to avoid ERROR: No random access

Postby qichen » 08 Aug 2021, 11:27

When I use the types of data such as Set, Vector and Array,

for example

Code: Select all

$a=new Set<Int>(0,1,2,3); print $a->[2];
sometimes it is okay, sometimes it will show
ERROR: No random access
Why does it occur and how to avoid it? Thanks.

User avatar
joswig
Main Author
Posts: 269
Joined: 24 Dec 2010, 11:10

Re: how to avoid ERROR: No random access

Postby joswig » 09 Aug 2021, 09:45

Well, Vector and Array are random access data structures, i.e., you can use indices. And Set is not random access; pretty much as the error message says.

These different data structures exist because they help make several kinds of functions fast: While vector and Array allow to access an element at a given position in constant time, e.g., Set allows to decide if a given element is contained in logarithmic time. Sets are implemented as a certain type of balanced binary tree type (AVL trees).

You can always convert back and forth between these data structures:

Code: Select all

polytope > $a=new Set<Int>(0,1,2,3); polytope > $b=new Vector<Int>($a); polytope > print $a->[2]; polymake: ERROR: No random access polytope > print $b->[2]; 2
A Set object is always ordered. You can access the first and the last element in constant time.

Code: Select all

polytope > print $a->front(); 0 polytope > print $a->back(); 3
But these are the only ones.

qichen
Posts: 8
Joined: 09 Jul 2020, 02:01

Re: how to avoid ERROR: No random access

Postby qichen » 14 Aug 2021, 05:20

I think I know why my misunderstanding occurs. It is because of the following function and the documentation about it is incorrect. The type it returns is Set, but not Array or Vector, even if the first parameter is Array or Vector.

all_subsets_of_k(Any c, Int k)
Returns all subsets of size k of a given container as perl-array.

Parameters:
Any c: any container type, e.g. Set or Array

Int k: size of the subsets

Returns:
Array<Array<Any>>
By the way, another function in the documentation cannot be used.
all_subsets(Any c)
Returns all subsets of size k of a given container as perl-array.

Parameters:
Any c: any container type, e.g. Set or Array

Returns:
Array<Array<Any>>

qichen
Posts: 8
Joined: 09 Jul 2020, 02:01

Some operations on Array and Vector to realize data type change

Postby qichen » 14 Aug 2021, 06:27

I think one scheme to solve my problem is turn a Set<Set<Int>> data to Array<Set<Int>> or Vector<Set<Int>> type. But I find it lacks enough operations on Array or Vector.

For example, I may create

Code: Select all

$a=new Array<Set<Int>>();
, then add the elements of Set<Set<Int>> one by one, but it seems it lacks such operations of Array. I try to use

Code: Select all

push(@a, $b);
, where $b is a Set. It does not work.

I also try to create a Array<Set<Int>> with each element emptyset and the same size with Set<Set<Int>>, and then revise the elements one by one. But it also lacks such operations.

Any suggestions? Thanks.

qichen
Posts: 8
Joined: 09 Jul 2020, 02:01

Declare and initialize Array or Vector in two steps

Postby qichen » 14 Aug 2021, 09:03

When use an Array, in C++, we first declare it, then initialize it, for example

Code: Select all

int a[3]; for(int i=0;i<=2;i++){ a[I]=i; }
However, in polymake, we have to do it in one step.

Code: Select all

$a=new Array<Int>(0,1,2);
However, when we deal with some complicated long arrays, it seems it cannot be initialize in the first placed. Can we also make it in two steps as we do in C++?

User avatar
gawrilow
Main Author
Posts: 405
Joined: 25 Dec 2010, 17:40

Re: Declare and initialize Array or Vector in two steps

Postby gawrilow » 14 Aug 2021, 11:58

One word "array" has so many different meanings, it's indeed confusing and needs a more thorough documentation.

I'll try to address all your recent questions at one place.

There are at least five different entities that can be called "an array".
  1. The old plain C/C++ array, as in your example. It is static (non-resizable) and requires that its elements are default-constructible. When you write int a[3]; in your program, it's not just declared, it's also allocated on the stack (or pre-allocated in the global static memory segment, if the declaration stands outside of a function or class body). There is no initialization in your case, because int is a primitive built-in type; the memory is simply left as is (in static case it happens to be zero-initialized by the OS, but for the local array the contents will be some garbage). If you would take a user-defined class instead of int, e.g. polymake::Integer, every element will be initialized with the default constructor. For proper initialization, you have to use brace-initializer: int a[3] = { 0, 1, 2 }; The assignment operator in the loop below is no longer an initialization, it overwrites an old value with a new one. On the perl side of polymake, there is no interface to plain C/C++ arrays at all.
  2. The C++ class std::array. It's a fancy wrapper around the plain array from point 1, defining a container-like interface in STL style (and also a tuple interface). Otherwise the game rules are exactly the same as for plain arrays.
  3. The perl array. It supports fast random access by index and (not that fast) dynamic reshaping, including inserting and removing elements at any position. It's addressed as @a when it's used in a so called list context, that is, an operation impacting the entire array or returning several elements:

    Code: Select all

    @a=(1,2,3); push @a, 10, 20, 30; @b=@a[$i1..$i2]; for my $e (@a) { print $e,"\n"; }
    But when you address a single element, you have to use the dollar sign: $a[2] += 3; This is a perl peculiarity existing since its birth.

    perl arrays are not easily accessible in C++; although there is a wrapper class for that in polymake library, it should rarely be of any use for normal user.
  4. The C++ class polymake::Array. It's a poor small brother of standard std::vector. It has dynamically allocated storage (on the heap) and can be resized. Like std::vector, it offers fast random access to its elements by index, but altogether its API is much slimmer, in particular, it does not offer push_back or insert. Objects of this class can be created and manipulated from perl side as usual perl arrays, but you have to keep in mind the limitations:
    • $a=new Array<Int>(0, 1, 2); creates a C++ object and stores a reference to it in the scalar perl variable $a
    • $a->[$i] gives you the element with index $i, which is an lvalue, that is, it can be modified by assignment, +=, ++ etc. Note the arrow between $a and square brackets, necessary to follow the object reference. An alternative notation is $$a[$i].
    • for my $e (@$a) { do_something($e); } iterates over all elements; $e is again an lvalue, so you can modify elements within the loop. Note the dereferencing operator @$a.
    • @$a[$i1..$i2] gives a slice of the array, consisting of indexes $i1 up to $i2
    • There is no implementation for push @$a, pop @$a, shift @$a, unshift @$a, splice @$a - you'll get an error message about missing object methods if you try them.
    You can also create an Array object with the given number of default-constructed elements:
    $a=new Array<Set<Int>>(5); creates an Array with five empty Sets.
    Now you can modify single elements: $a->[2] += 200; print exists $a->[2]->{200};
  5. Collections of items returned from certain polymake functions are described as Arrays, albeit they are not really Arrays but only implement a tiny fraction of perl array API, namely the possibility to iterate over their elements. all_subsets_of_k is an example of such function:

    Code: Select all

    $s=new Set<Int>(10, 15, 20, 25); $a=all_subsets_of_k($s,2); for my $t (@$a) { print $t, "\n"; } @copy=@$a;
    The last line makes a real perl array as a full copy of the result of all_subsets_of_k, which you can then manipulate at your will.
    We should correct the documentation of such functions, replacing the word Array with something distinct, like Collection or Stream.

    Note that because of internal implementation details, iteration over a collection is equivalent to addressing its elements by increasing indices without gaps. That's why you may successfully execute $a->[0], $a->[1], $a->[2] exactly in this order, but get an exception "no random access" if you leap forward by 2 or more positions or go back to a smaller index ≠ 0.
Finally, a remark about polymake::Vector. It's not a generic container class, rather a species from linear algebra realm. It should only be used with sensible coordinate types having well-defined addition and multiplication operations.


Return to “Helpdesk”