Почему моя структура данных медленная (пользовательская структура данных)

Question

Я пытаюсь реализовать структуру данных, которая была проблемой от www.topcoder.com, но я не могу получить такую ​​же скорость / эффективность, как они.

Вот чтоони спрашивают.

ВОПРОС:

Реализация класса BlockedList, который реализует интерфейс List.Вы можете использовать любой из классов в JCF.Конструктор для этого класса принимает целочисленный размер блока b, и реализация должна иметь следующие характеристики производительности: get (i) и set (i, x) должны выполняться за O (1) раз за операцию add (i, x) и remove (i) должен работать за O (b + min {i, ni} / 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, ni} / 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

Попробуйте что-то вроде java.util.Map<Intger, T[]> blocks = new HashMap<>();.

И сделайте лучше, чем:

if (i >= b ) throw new IndexOutOfBoundsException();

Полный источник (немного проверено):

import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Map;
import java.util.Random;
import java.util.HashMap;

public class BlockedList<T> extends AbstractList<T> {

    static class Factory<T> {

        private final Class<T> clazz;

        public Factory(Class<T> clazz) {
            this.clazz = clazz;
        }

        public T[] createBlock(int b) {
            return (T[]) Array.newInstance(clazz, b);
        }
    }
    private int n;
    private final Map<Integer, T[]> blocks;
    private final int b;
    private final Factory<T> f;

    public BlockedList(Class<T> tclass, int b) {
        this.f = new Factory<>(tclass);
        this.n = 0;
        this.b = b;
        this.blocks = new HashMap<>();
    }

    @Override
    public int size() {
        return n;
    }

    public long capacity() {
        return blocks.size() * b;
    }

    @Override
    public void clear() {
        blocks.clear();
        n = 0;
    }

    @Override
    public T get(int i) {
        checkBounds(i);
        return blocks.get(i / b)[i % b];
    }

    @Override
    public T set(int i, T x) {
        checkBounds(i);
        final T[] block = blocks.get(i / b);
        final T retVal = block[i % b];
        block[i % b] = x;
        return retVal;
    }

    @Override
    public void add(int i, T x) {
        checkBoundsAdd(i);
        if (blocks.containsKey(i / b)) {
            blocks.get(i / b)[i % b] = x;
        } else {
            T[] tmp = f.createBlock(b);
            tmp[i % b] = x;
            blocks.put(i / b, tmp);
        }
        n++;
    }

    @Override
    public T remove(int i) {
        checkBounds(i);
        T val = blocks.get(i / b)[i % b];
        if (val != null) {
            n--;
        }
        return val;
    }

    private void checkBounds(int i) {
        if (i < 0 || i > n - 1) {
            throw new IndexOutOfBoundsException();
        }
    }

    private void checkBoundsAdd(int i) {
        if (i < 0 || i > n) {
            throw new IndexOutOfBoundsException();
        }
    }

    public static void main(String[] args) {
        test();
    }

    private static void test() {
        Random rnd = new Random();
        BlockedList<Integer> test = new BlockedList<>(Integer.class, 8);
        for (int i = 0; i < Short.MAX_VALUE - 7; i++) {//Integer.MAX_VALUE takes toooo long
            test.add(i, rnd.nextInt());
        }
        System.out.println(test.size()); //Short.MAX_VALUE - 7
        for (int i = 0; i < Short.MAX_VALUE - 107; i++) {
            test.remove(rnd.nextInt(test.size()));
        }
        System.out.println(test.size()); //expect: 100
        test.forEach((_item) -> {
            test.set(rnd.nextInt(test.size()), rnd.nextInt(1024));
        });
        System.out.println(test.size()); //expect: 100
        System.out.println(Arrays.toString(test.toArray()));
        test.set(0, 0);
        System.out.println(Arrays.toString(test.toArray()));
        Collections.sort(test);
        //test.toArray() uses test.get(int)
        System.out.println(Arrays.toString(test.toArray()));
    }
}

... сейчасмы должны были бы выбрать «самую хорошую» реализацию карты (я колеблюсь между TreeMap и HashMap).

Пока у нас есть до n / b записей / блоков, с резервированием bразмер на блок, который с помощью HashMap почти соответствует требованиям сложности:

• get: O(1) (из HashMap.get) + O(1) (из массива get).
  • с java.util.TreeMap, это будет O(log(2, n/b) + 1).
• set: O(1 + 1).
  • это также дороже с TreeMap: O(log(2, n / b) + 1).
• add: O(n / b + b).
  • TreeMap (я полагаю): O(log(2, n / b) + b) (что будет лучше!)
• удалить: O(n / b + b)
  • TreeMap: O(log(2, n / b) + b.(лучше)

---

А на самом деле O(min(i, n - i)) == O(n / 2) == O(n)!?

То есть HashMap для более быстрых операций получения и установки, TreeMap для более быстрого добавления и удаления, альтернативы?(LinkedHashmap? ...)

Answer 2

На самом деле он не блокирует.Вы должны хранить n > b элементов в блоках из b элементов.Ваша реализация просто отказывается поддерживать n > b .

На самом деле, поразмыслив, я не ответил на вопрос «почему это медленно?».Но это кажется второстепенным по отношению к «оно не удовлетворяет требованиям».