I have a student variant of the array collection type Set , and I was given the task to increase the speed of the add method. But I don’t understand how to do it.

How to increase insertion speed?

Code:

 public class ArraySimpleSet<E> implements SetArray<E> { private E[] values; public ArraySimpleSet() { values = (E[]) new Object[0]; } @Override public Iterator<E> iterator() { return new Iterator<E>() { private int index = 0; @Override public boolean hasNext() { return index < values.length; } @Override public E next() { return values[index++]; } }; } @Override public boolean add(E e) { Objects.requireNonNull(e); if (notExistDuplicate(e)) { try { E[] temp = values; values = (E[]) new Object[temp.length + 1]; System.arraycopy(temp, 0, values, 0, temp.length); values[values.length - 1] = e; sortByHashCode(); return true; } catch (ClassCastException ex) { ex.printStackTrace(); } } return false; } @Override public int size() { return values.length; } private boolean notExistDuplicate(E elem) { for (E e : values) { if (e.equals(elem)) return false; } return true; } private void sortByHashCode() { int len = (values.length - 1); for(int i = len; i >= 0; i--) { for (int j = 0; j < i; j++) { if (values[j].hashCode() < values[j + 1].hashCode()) { E temp = values[j + 1]; values[j + 1] = values[j]; values[j] = temp; } } } } }

    2 answers 2

    You can make several improvements:

    1. implement notExistDuplicate as a binary search , since this is possible because your array is sorted by hashcods of objects
    2. implement sortByHashCode with quick sort , or merge sort , or any other algorithm with better asymptotics than O (n ^ 2)
    3. You can make the insertion trickier - do not sort the new array every time. Those. notExistDuplicate returns the index of the element - if the element is found or - ((position + 1) if the object is not found. Then it will only be necessary to copy the elements from the array, while inserting a new element into the cell with the index position .
    • thanks for the answer. Regarding paragraph 3, I did not understand how notExistDuplicate will know the necessary cell? So there will still need to sort the sort? Then what difference does it affect performance there or here? Or did I somehow misunderstand you? - Pavel
    • one
      @Pavel method will perform a binary search, during which the source index of the element will be clarified or the position at which it should be. Yes, sorting is required. The method is called once, but due to the fact that it will return the index, and not the boolean value, we can further reduce the number of operations, due to this, the whole boost itself - Artem Konovalov
    • >>> Yes, sorting is required. The method is called once <<< and when it is called at the beginning when the first element is added there is no sense there is nothing else to sort, and then when this one comes once? - Pavel
    • one
      You have a sorted array (the default empty array is sorted). call the notExistDuplicate method, we get the index, if the index with a plus sign is that the element already exists in the array. Otherwise, it is not there, then we create an array of length + 1 and perform copying, taking into account the position at which the new element should appear. The sortByHashCode method is not needed in this case. but if not to carry out item 3 then it is possible to manage item 1-item 2. according to the idea, the first option should be faster, but it all depends on the size of the array, if it is not large, then there will be no difference. - Artem Konovalov

    Do not sort the array with each insert. It is already sorted. Find a place for a new item using binary search. Expand the array and insert.