0
\$\begingroup\$

Given a list of, say, integers, one way to implement such a list is to rely on an array under the hood. When we are adding elements to the array list, we might need to make the internal array larger. Here, we have at least two array expansion schemes:

  1. (Arithmetic scheme) Expand the array by a fixed number of elements. (Let it be \$d \in \mathbb{N}\$.)
  2. (Geometric scheme) Expand the array by multiplying its size by a constant. (Let that constant be \$q > 1\$.)

In this post, we will, however, ignore the second scheme.

What happens in the arithmetic scheme, is that we ask along the \$d\$ also a positive integer \$m\$ that denotes the initial array capacity.

Now, our claim is that the equality for arithmetic scheme holds:

\begin{aligned} C(n, m, d) &= \frac{d}{2} \Bigg\lceil \frac{n - m}{d} \Bigg\rceil^2 + \Bigg( m - \frac{d}{2} \Bigg)\Bigg\lceil \frac{n - m}{d} \Bigg\rceil + n \\ &= \frac{d}{2} \Bigg\lceil \frac{n - m}{d} \Bigg\rceil \Bigg( \Bigg\lceil \frac{n - m}{d} \Bigg\rceil - 1\Bigg) + m \Bigg\lceil \frac{n - m}{d} \Bigg\rceil + n. \end{aligned} where \$m \in \mathbb{N}\$ is the initial array capacity, \$d \in \mathbb{N}\$ is the number of array components by which we extend the array every time we need to expand it, and, finally, \$n \geq m\$ is the number of elements we add to the array list. To recap, \$C(n, m, d)\$ is the work done when adding \$n\$ elements to the array list that had an initial capacity of \$m\$ and upon each expansion, the internal array were made \$d\$ array components larger. Below is code:

ArithmeticSchemeValidator.java:

import java.math.BigDecimal;

public class ArithmeticSchemeValidator {
    
    private static final int MAX_D = 200;
    private static final int MAX_M = 200;
    private static final int MAX_N = 1_000;

    public static int getC(int n, int m, int d) {
        int y = myCeil(n, m, d);
        
        BigDecimal bigY = BigDecimal.valueOf(y);
        BigDecimal bigN = BigDecimal.valueOf(n);
        BigDecimal bigM = BigDecimal.valueOf(m);
        BigDecimal bigD = BigDecimal.valueOf(d);
        BigDecimal bigTwo = BigDecimal.valueOf(2);
        BigDecimal BigDPerTwo = bigD.divide(bigTwo);
        
        return BigDPerTwo.multiply(bigY)
                      .multiply(bigY)
                      .add(bigY.multiply(
                              bigM.subtract(BigDPerTwo)))
                      .add(bigN)
                      .intValue();
    }
    
    private static int myCeil(int n, int m, int d) {
        int t = n - m;
        int ret = t / d;
        
        if (t % d != 0) {
            ret++;
        }
        
        return ret;
    }
    
    public static void main(String[] args) {
        int mismatches = 0;
        int totalIterated = 0;
        
        for (int d = 1; d <= MAX_D; d++) {
            for (int m = 1; m <= MAX_M; m++) {
                List list = new List(m, d);
                
                // Loading before the first expansion:
                for (int n = 0; n < m; n++) {
                    list.add();
                }
                
                for (int n = m; n <= MAX_N; n++) {
                    int compareTo = getC(n, m, d);
                    
                    if (compareTo != list.getWorkUnits()) {
                        mismatches++;
                    }
                    
                    list.add();
                    totalIterated++;
                }
            }
        }
        
        System.out.println("Mismatches: " + mismatches);
        System.out.println("Total iterated: " + totalIterated);
    }
}

class List {
    
    private final int d;
    private int size;
    private int capacity;
    private int workUnits;
    
    List(int m, int d) {
        this.capacity = m;
        this.d = d;
    }
    
    void add() {
        expandIfNeeded();
        size++;
        workUnits++;
    }
    
    int getWorkUnits() {
        return workUnits;
    }
    
    private void expandIfNeeded() {
        if (capacity <= size) {
            workUnits += size;
            capacity += d;
        }
    }
}

ArithmeticSchemeValidatorTest.java:

import static junit.framework.Assert.assertEquals;
import org.junit.Test;

public class ArithmeticSchemeValidatorTest {
    
    @Test
    public void smallTest() {
        int c = ArithmeticSchemeValidator.getC(6, 1, 2);
        assertEquals(15, c);
        
        List ll = new List(1, 2);
        
        for (int n = 0; n < 6; n++) {
            ll.add();
        }
        
        assertEquals(15, ll.getWorkUnits());
    }
    
    @Test
    public void smallBruteForceTest() {
        for (int m = 1; m <= 3; m++) {
            for (int d = 1; d <= 4; d++) {
                List list = new List(m, d);
                
                for (int i = 0; i < m; i++) {
                    list.add();
                }
                
                for (int n = m; n <= 10; n++) {
                    list.add();
                    int expected = ArithmeticSchemeValidator.getC(n + 1, m, d);
                    
                    assertEquals(expected, list.getWorkUnits());
                }
            }
        }
    }
}

Output

Mismatches: 0
Total iterated: 36020000

Critique request

As always, I am glad to hear anything that comes to mind. Thank you in advance.

\$\endgroup\$
0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.