Skip to main content
Engineering LibreTexts

2.2: FastArrayStack - An Optimized ArrayStack

  • Page ID
    8438
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Much of the work done by an ArrayStack involves shifting (by \(\mathtt{add(i,x)}\) and \(\mathtt{remove(i)}\)) and copying (by \(\mathtt{resize()}\)) of data. In the implementations shown above, this was done using \(\mathtt{for}\) loops. It turns out that many programming environments have specific functions that are very efficient at copying and moving blocks of data. In the C programming language, there are the \(\mathtt{memcpy(d,s,n)}\) and \(\mathtt{memmove(d,s,n)}\) functions. In the C++ language there is the \(\texttt{std::copy(a0,a1,b)}\) algorithm. In Java there is the \(\texttt{System.arraycopy}\mathtt{(s,i,d,j,n)}\) method.

        void resize() {
            T[] b = newArray(Math.max(2*n,1));
            System.arraycopy(a, 0, b, 0, n);
            a = b;
        }
        void add(int i, T x) {
            if (i < 0 || i > n) throw new IndexOutOfBoundsException();
            if (n + 1 > a.length) resize();
            System.arraycopy(a, i, a, i+1, n-i); 
            a[i] = x;
            n++;
        }
        T remove(int i) {
            if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
            T x = a[i];
            System.arraycopy(a, i+1, a, i, n-i-1);
            n--; 
            if (a.length >= 3*n) resize();
            return x;
        }
    

    These functions are usually highly optimized and may even use special machine instructions that can do this copying much faster than we could by using a \(\mathtt{for}\) loop. Although using these functions does not asymptotically decrease the running times, it can still be a worthwhile optimization.

    In the Java implementations here, the use of the native \(\texttt{System.arraycopy}\mathtt{(s,i,d,j,n)}\) resulted in speedups of a factor between 2 and 3, depending on the types of operations performed. Your mileage may vary.


    This page titled 2.2: FastArrayStack - An Optimized ArrayStack is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .