Python and Schools

[Tim Peters]

[David Eppstein]
> ...
> A simple example would be an algorithm that takes as input a sequence of
> values that are all (for whatever reason) guaranteed to be integers in
> range(n**2), and tests whether any two of them are the same:
>
> def anysame(seq):
>     allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
>         (is this possible in pure python?)

It shouldn't be possible:  if you find a way to do it, it would be
considered a security bug.  No memory is really uninitialized -- if Python
gave you read access to n**2 bytes in constant time, it would be revealing
to you the state left behind by some other function (or user, or process).
If you created a file with at least n**2 bytes beforehand, then you could
mmap the file in constant time, and that acts like an array object
initialized to whatever bytes happen to be sitting in the file.  But the O()
behavior of access to an mmap'ed region depends on the platform
implementation of mmap'ed regions.

>     for i,x in enumerate(seq):
>         if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
>             return True
>         A[x] = i
>     return False

Something must be missing here, right?  For example, suppose A just happens
to be uninitialized to all zeroes, and we pass in seq=[8, 8].  Then A[8] is
set to 0 in the first loop trip, and in the second

    A[8] is 0 so 0 <= A[x] < i is true
    A[A[x]] == A[A[8]] == A[0] == 0 != 8 so the if guard is false
    A[8] is set to 1

Then the loop ends and the function returns False.