java - 为什么我的数据结构很慢(自定义数据结构)

Question

我正在尝试实现一个来自 www.topcoder.com 的挑战的数据结构，但我无法获得与他们相同的速度/效率。

这就是他们要问的。

问题:

实现一个实现 List 接口(interface)的 BlockedList 类。您可以使用 JCF 中的任何类。此类的构造函数采用整数 block 大小 b，并且实现应具有以下性能特征:get(i) 和 set(i,x) 每次操作的运行时间应该为 O(1)add(i,x) 和 remove(i) 应在每次操作的 O(b+ min{i, n-i}/b) 摊销时间内运行。

解决方案(不正确，它应该快得多:()

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.List;

/**
 * This is a copy of the JCF class ArrayList. It implements the List
 * interface as a single array a. Elements are stored at positions
 * a[0],...,a[size()-1]. Doubling/halving is used to resize the array
 * a when necessary.
 * 
 *
 * @param <T> the type of objects stored in the List
 */
class BlockedList<T> extends AbstractList<T> {
    /**
     * List which will store elements
     */
    private List<T> list;
    /**
     * keeps track of the class of objects we store
     */
    Factory<T> f;

    /**
     * The number of elements stored
     */
    int n;

    /**
     * The block size
     */
    int b;

    /**
     * Constructor
     * @param t the type of objects that are stored in this list
     * @param b the block size
     */
    public BlockedList(Class<T> t, int b) {
        this.f = new Factory<T>(t);
        this.n = 0;
        this.b = b;
        this.list = new ArrayList<T>();
    }

    public int size() {
        return n;
    }

    public T get(int i) {
        if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
        return list.get(i);
    }

    public T set(int i, T x) {
        if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
        return list.set(i, x);
    }

    public void add(int i, T x) {
        if (i < 0 || i > n) throw new IndexOutOfBoundsException();
        if (i >= b ) throw new IndexOutOfBoundsException();
        list.add(i,x);
        n+=1;
    }

    public T remove(int i) {
        if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
        T val = list.remove(i);
        n-=1;
        return val;
    }
}

目标

目标是按照他们的要求完成挑战，但我尝试了很多次，现在就放弃了。我想知道我做错了什么。另外，像我之前提到的 get(i) 和 set(i,x) 的速度应该在每次操作的 O(1) 时间内运行add(i,x) 和 remove(i) 应在每次操作的 O(b+ min{i, n-i}/b) 摊销时间内运行。

测试错误:

Executing: javac ListTest2.java
Running: java ListTest2 20
Running with n = 20
Correctness testing for topcoder.BlockedList...Exception in thread "main" java.lang.IndexOutOfBoundsException
    at topcoder.BlockedList.checkBounds(BlockedList.java:67)
    at topcoder.BlockedList.add(BlockedList.java:43)
    at java.util.AbstractList.add(AbstractList.java:108)
    at topcoder.sanityTests(ListTest2.java:30)
    at topcoder.main(ListTest2.java:115)

Program exited with non-zero status, test failed

Answer 1

它实际上并没有做任何阻塞。您应该将 n> b 个元素存储在 b 元素 block 中。您的实现只是拒绝支持n> b。

其实，仔细想想，我并没有回答“为什么这么慢？”这个问题。但这似乎比“不满足要求”更重要。