1
$\begingroup$

Many operations on arrays have $O(n)$ complexity.

If we represent arrays as accessors methods, many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of size $n$ is given by $reverse(A).i = A[n-1-i]$. So we can define reverse as:

$$reverse := \lambda A:array \ \lambda i:int. \ A[n-1-i]$$

and similarly for other operations like slicing, zipping, concatenation, and so on. This technique allows us to implement these complicated operations in constant time without touching the original memory at all.

  1. What is the formal name of this structure?

  2. What are the negative aspects of using this structure compared to the standard structure?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ Without knowing whether or not this is actually being done already: One consideration is that you're sacrificing random access speed for this. I'm guessing there aren't many applications for which this is worth the gain, as random access is used far more frequently, sometimes in deeply nested loops. --- Also, programmers expect to receive a copy when using an operation that returns a result, and you're passing references. This will cause unexpected behavior when the data is altered. Unless you implement copy-on-write, I suppose. $\endgroup$ – mhelvens Sep 28 '13 at 12:32
  • 1
    $\begingroup$ The operations in your proposal do not compose because they all operate on a fixed array and so they are just a flat interface. To make them useful you should write them so that we can easily compute, for example, the reverse of a slice of reverse of two concatenated arrays. For that sort of thing you will end up nesting lots of $\lambda$'s inside each other, and that means the cost of operations will depend on the number of array transformations performed. $\endgroup$ – Andrej Bauer Sep 29 '13 at 9:34
  • $\begingroup$ Downvoters, please explain. $\endgroup$ – David Richerby Sep 29 '13 at 9:37
  • 3
    $\begingroup$ @David, down-voters are not required to explain their votes, and we should not demand that they explain their votes, see this and this. $\endgroup$ – Kaveh Sep 29 '13 at 20:42
  • 3
    $\begingroup$ My downvote was based less on the confusing writeup with code in place of English (although it was indeed confusing) and more on the misleading question: It is not true that the most common operations in this structure are all $O(1)$. In particular array accesses become $\Theta($nesting level of transformations$)$. $\endgroup$ – David Eppstein Sep 29 '13 at 22:38
4
$\begingroup$

I call them nonstrict arrays.

They're not only not completely useless, but very useful and interesting. Operating on them is also not the worst in time efficiency, but can be asymptotically equivalent if done correctly. Further, if an array is just a lambda with a shape attached to it, then like transformations, pointwise operations are also not much more than function composition.

For a good start, look here:

Regular, shape-polymorphic, parallel arrays in Haskell, Gabriele Keller, Manuel Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, and Ben Lippmeier. ICFP 2010.

The authors present a multidimensional version of the arrays you're asking about, which are like NumPy's multidimensional arrays but in Haskell style. Arrays are just a lambda and a shape, and they don't cache computed elements for faster retrieval in the future. But at any time, a user can force one to compute and cache all of its elements.

These arrays force users to think in terms of whole-array operations. I consider that a plus, as it encourages a more declarative style of coding than writing loops that micromanage elements. I liked this style better when I was using NumPy as well. Others have different opinions.

The upside is automatic fusion of array operations, which reduces the memory cost of whole-array operations. It also helps immensely with parallelizing sequences of operations. Allocating space for intermediate arrays is a synchronization point. But if intermediate arrays are nonstrict, their elements don't require space, so that synchronization point disappears. Further, this "loop fusion" happens even when operations are in different functions, which would be very difficult, if not impossible, for a static optimizer to do.

One downside is that it's harder to reason about the performance of operations on nonstrict arrays. Another is that users have to decide which arrays to force to be strict. There are some simple rules of thumb, but they can't reduce the mental overhead to zero.

If you want to play with implementations, check out Haskell's Repa and Racket's math/array. (For the latter, you'll have to set a parameter to make the results of array operations nonstrict. The default is to return strict arrays because of the mental overhead problem.)

Improve this answer
$\endgroup$
  • $\begingroup$ That is awesome and made my day. For some reason I had not seem it before. Thank you very much. $\endgroup$ – MaiaVictor Jan 4 '14 at 17:52
6
$\begingroup$

This is not completely useless, and this sort of thing does indeed see a few niche uses, for instance when we want to access an array backwards it's faster to loop over array[n-i-1] rather than calling reverse(array) followed by a loop over array[i].

The flaw I'm seeing here is that this sort of thing will cause access times to scale with the number of times the data in the list have been fiddled with. After $k$ modifications to the data, you'll naturally take at least $O(k)$ time to access the data. If I want to perform $O(n^2)$ non-lookup list transformations I'm not going to be happy unless you flatten it back down to an array first. Changing the data from a function representation, proposed by you, to an array representation takes one access per element, so $O(nk)$ time.

How frequently should we change the representation back? If we rebuild the array after every $l$ operations on it, we need to spend $O(nl)$ time to rebuild every $l$ operations, so the amortised complexity of each operation becomes $O(n)$. The complexity of a lookup becomes $O(l)$ in the worst case. This is worse than an array representation in general.

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ Thanks for clarifying exactly why this is really not O(1) pet operation. It wasn't so clear from the original question. $\endgroup$ – David Eppstein Sep 29 '13 at 16:18
  • $\begingroup$ I don't see how this is worse than an array representation. Your worst cases cases for this representation are the best cases of an array, O(n) per operation and O(1) lookup... $\endgroup$ – MaiaVictor Sep 29 '13 at 21:09
  • 1
    $\begingroup$ I specified $O(n)$ per operation and $O(l)$ lookup. If you choose $l = 1$, then the situation is almost completely identical to a standard array - you don't defer list operations at all. If you choose an $l$ that does not increase with $n$, that is $l \in O(1)$, then you have $O(1)$ lookups, but the $O$-notation generally hides larger constants than before. If you choose, for example, $l = n$, so we rebuild an array of $n$ elements when $n$ operations are performed, we will spend, in the worst case, $n-1 \in O(n)$ time on a lookup, making it worse. $\endgroup$ – ymbirtt Sep 29 '13 at 22:13
  • $\begingroup$ @ymbirtt: Maybe there is a normal form addressing formula that can be maintained after every operation. For example, store a lowest index $l$, highest index $h$ and step-size $a$ and use polynomial $l + ai$ to access the data-store, where $i$ is the requested index. --- The reverse() operation could then consist of $(l, h, a) := (h, l, -a)$. The slice(x..y) operation could be $(l, h, a) := (l+x, l+y, a)$. Increasing stride by $s$ would be something like $(l, h, a) := (l, l+s\lfloor\frac{h-l}{s}\rfloor, sa)$. But the normal form needs to be tailored to the operations you want to support. $\endgroup$ – mhelvens Sep 30 '13 at 10:46
2
$\begingroup$

The issue is that you are not computing anything, you are simply postponing them for the time that the array items need to be accessed.

This is worst in general (regarding the time efficiency of the operations) because every time we need to perform an access operation we need to perform all of these computations again. Even if we are performing the access operation only once on each item, it can be more efficient to perform all similar operations at once.

It would only be useful if you are going to access very few elements of the array over time, in which case there is probably no point to perform these operations on the whole array. We can simply compute the index and access it directly. If you are not using the intermediate arrays in whole then don't compute them, only compute those which you need to access a considerable number of times.

ps: many pure functional programming language do not have environment so there is simply no way of storing the resulting values. However even there you can do either lazy evaluation or eager evaluation (or other evaluation strategies) and what you are describing seems to be similar to the lazy evaluation: not evaluating until we really need the value.

Improve this answer
$\endgroup$
  • $\begingroup$ Hopefully some programming language expert would also answer the question. $\endgroup$ – Kaveh Sep 29 '13 at 22:32
  • $\begingroup$ I'm not sure it is actually the same thing as postponing computation / lazy evaluation, as some operations would still be much faster this way. For example, print . reverse . (slice 0 2), to get the last 2 elements and print them. Even a lazy language would need to transverse the whole array. This wouldn't. I'm not sure though. Thanks for the inputs! $\endgroup$ – MaiaVictor Sep 29 '13 at 22:51
  • $\begingroup$ @Viclib: If you compare your approach to the most naive alternative possible, you're bound to end up on top. But no programmer would reverse and slice an array just to print the last two elements. They'd probably do something like print(-1, -2). My point is: if you want to advance your argument, try to find a use-case where your approach is superior to all alternatives and try to be critical of your own ideas. Perhaps you'll find out they aren't as practical as you thought. On the other hand, perhaps you'll find an ingenious use-case; in which case, please let us know. :-) $\endgroup$ – mhelvens Sep 30 '13 at 10:18
  • $\begingroup$ Haskell and functional programming mantra in general says: express what you want in a clear way that is intuitive for you, don't worry about performance because the compiler will take care of that. reverse . (slice 0 2) could be intuitive for someone. $\endgroup$ – MaiaVictor Sep 30 '13 at 11:09
  • $\begingroup$ (1) Unless you personally know that 'someone', come up with a more convincing use-case. (2) I know how tempting it is to invoke the sufficiently smart compiler argument, but there is no such compiler. Unless you can show me one, or personally develop and prove the necessary optimization algorithm. Then publish it. :-) (3) You're not being critical about your own ideas, you're still trying to defend them. You'll be much more convincing once you can show that you're aware of the (possible) arguments against your approach. $\endgroup$ – mhelvens Sep 30 '13 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.