[Introduction to Java Data Structures] Create your own fast ArrayDeque for primitive types
When implementing breadth-first search or depth-first search in Java, I think that there are many people who implement it by storing the vertex number in ʻArrayDeque . However, this ʻArrayDeque <Integer>, Since it stores ʻInteger which is a wrapper class of ʻint, auto boxing / unboxing occurs frequently and the speed is not good.
Therefore, this time, I would like to easily implement a high-speed deque (ʻIntArrayDeque) dedicated to ʻint. It is recommended because it is highly effective for its easy implementation.
ʻThe minimum required functions for implementing the IntArrayDeque` class are as follows.
--Get first / last elements (ʻint getFirst () , ʻint getLast ())
--Add elements at the beginning / end (void addFirst (int v), void addLast (int v))
--Remove first / last elements (ʻint pollFirst () , ʻint pollLast ())
--Get size (ʻint size () ) (+ deque is empty (boolean isEmpty () `))
This time, in addition to these functions, I will add these functions.
--Get the $ i $ th element from the beginning / end with $ O (1) $ (ʻint getFromHead (int index) , ʻint getFromTail (int index))
--Iterator that scans from beginning to end (PrimitiveIterator.OfInt iterator ())
--Iterator that scans from the end to the beginning (PrimitiveIterator.OfInt descendingIterator ())
So, I would like to say that I implemented it here, but I think that those who can create their own data structures with these functions from the beginning are not the intended readers of this article, so I will explain what to think about implementing it. I will do it while doing it. It may seem verbose to those who know it, but please note that it is for beginners (if you are only interested in the final product, skip to the "Summary" section).
Operation to the end
We will consider the operation to the beginning later, but here we will consider only the operation to the end. One of the major features of Deque is that the more it is added, the larger the size. But suppose you forget this feature and know the maximum size from the beginning. If the maximum size is MAX, the size is MAX ʻint [] type. One variable (let the variable name is deq) and one ʻint type variable (let the variable name be tail) indicating the number of the deq to be stored next time. All you need is ok.
I will explain in order how to get / add / delete elements.
--Get: The place where the element is added next is deq [tail], so you can access deq [tail-1] to see the last element you put in.
--Add: The next place to add the element is deq [tail], so you can store the value you want to add in deq [tail]. Also, to advance the place to put the element by one. Let's say tail ++.
--Delete: The delete operation uses the deleted value as the return value. Since the last element is deleted, the return value is deq [tail-1]. In addition, there is one place to put the element next. To return it, use tail --. When implementing, you cannot write a return statement and then a tail --, so thereturn deq [tail]after the tail -- first. (Note that tail is -1 first).
The code that summarizes the above is as follows (the implementation is such that MAX is passed to the constructor).
IntArrayDeque.java
public class IntArrayDeque {
private int[] deq;
private int tail;
public IntArrayDeque(int max) {
this.deq = new int[max];
this.tail = 0;
}
public int getLast() {
return deq[tail - 1];
}
public void addLast(int v) {
deq[tail] = v;
tail++;
}
public int pollLast() {
tail--;
return deq[tail];
}
}
This is the basic form of a deque. Next, we will rewrite it so that the more elements we add, the larger the size of the deque.
Increase the size
In the implementation of the previous section, if you try to insert more than MAX, it will be out of the array.
Actually, the solution to this problem is simple, if you prepare a larger array and copy everything there, it's ok. The method to do this operation is void grow ().
You have to decide how big you want it to be, but this time let's make sure you have an array that is twice as large as the original size.
Also, when to call this method, it should be called if tail == deq.length when adding an element at the end (= if the next place to put is outside the array). For tail deletion and tail acquisition You don't have to call this.
From the above, first add the void grow () method. Since we do not want to call this from the outside, we will call it the private method.
IntArrayDeque.java
private void grow() {
int[] newDeq = new int[deq.length * 2]; //Secure twice the length
//First argument:Copy source array
//Second argument:From where in the source array to copy
//Third argument:Copy destination array
//Fourth argument:Which location in the destination array to copy as the starting point
//Fifth argument:Length to copy
System.arraycopy(deq, 0, newDeq, 0, deq.length);
deq = newDeq; //This doubles the length of deq while keeping the contents intact
}
And if you rewrite the void addLast (int v) method as follows, it looks as if the size increases automatically from the outside.
IntArrayDeque.java
public void addLast(int v) {
if (tail == deq.length) {
grow();
}
deq[tail] = v;
tail++;
}
Now you can do all the operations to the end. Next, we will add the operations to the beginning.
Operation to the beginning
The operation to the beginning is the same as the operation to the end. Like tail, we define a ʻint type variable called head, which indicates the position when we add it to the beginning next time. You can see that ʻint getFirst () ,void addFirst (int v), ʻint pollFirst ()` can be written as follows.
IntArrayDeque.java
public class IntArrayDeque{
private int[] deq;
private int tail;
private int head;
public IntArrayDeque(int max) {
this.deq = new int[max];
this.tail = 0;
this.head = -1;
}
/**
* getLast()Etc. are omitted
*/
public int getFirst() {
return deq[head + 1];
}
public void addFirst(int v) {
deq[head] = v;
head--;
}
public int pollFirst() {
head++;
return deq[head];
}
}
The reason why the initial value of head is $ -1 $ will be explained later.
Now, the problem is the processing of grow (). Here, there are two possible implementation strategies.
-
Extend the index in the negative direction like a number line and have a negative array
ndeq(let's say the positive array ispdeq). Andheadis at the end of the negative array When ʻaddFirst` is called in the state of arrival, the array in the negative direction is expanded in the same way as in the positive direction. -
Like
grow ()at the end,head == -1extendsdeq. However, to make room at the beginning, copy the original array to the end of the new array.
Personally, I think that 1 is easy to imagine, so I will select policy 1 this time. The figure is as follows.
Here, in pdeq, the subscript and the coordinates match, but in ndeq, the subscript and the coordinates (absolute value) are offset by $ 1 $, so be careful.
Also, from the above figure, the value stored in the coordinates $ x $ is pdeq [x] for $ x \ ge 0 $ and ndeq [-x-1] for $ x \ lt 0 $. You can see that you can access it with] .
To ease later implementations, we will implement the private method ʻint getByX (int x), which takes the coordinate $ x $ and returns the stored value. In addition, the value $ v $ at the coordinate $ x $ It also implements the private method void putByX (int x, int v) `to store.
The implementation looks like this:
IntArrayDeque.java
private int getByX(int x) {
if (x >= 0) {
return pdeq[x];
} else {
return ndeq[- x - 1];
}
}
private void putByX(int x, int v) {
if (x >= 0) {
pdeq[x] = v;
} else {
ndeq[- x - 1] = v;
}
}
By the way, the methods we have defined so far, such as getLast (), do not consider negative coordinates. However, by using getByX and putByX, we can rewrite those methods concisely. Masu.
If we also write an extension of the array in the negative direction, the whole class will be as follows.
IntArrayDeque.java
public class IntArrayDeque {
private int[] pdeq;
private int[] ndeq;
private int tail;
private int head;
private int defaultSize = 64; //Because MAX has disappeared,Decide on a default size
public IntArrayDeque() {
this.pdeq = new int[defaultSize];
this.ndeq = new int[defaultSize];
this.tail = 0;
this.head = -1;
}
public int getLast() {
return getByX(tail - 1);
}
public void addLast(int v) {
if (tail == pdeq.length) {
growPositive();
}
putByX(tail, v);
tail++;
}
public int pollLast() {
tail--;
return getByX(tail);
}
public int getFirst() {
return getByX(head + 1);
}
public void addFirst(int v) {
if (- head - 1 == ndeq.length) {
growNegative();
}
putByX(head, v);
head--;
}
public int pollFirst() {
head++;
return getByX(head);
}
private int getByX(int x) {
if (x >= 0) {
return pdeq[x];
} else {
return ndeq[- x - 1];
}
}
private void putByX(int x, int v) {
if (x >= 0) {
pdeq[x] = v;
} else {
ndeq[- x - 1] = v;
}
}
private void growPositive() {
int[] newPdeq = new int[pdeq.length * 2];
System.arraycopy(pdeq, 0, newPdeq, 0, pdeq.length);
pdeq = newPdeq;
}
private void growNegative() {
int[] newNdeq = new int[ndeq.length * 2];
System.arraycopy(ndeq, 0, newNdeq, 0, ndeq.length);
ndeq = newNdeq;
}
}
I'll explain why I set the initial value of head to $ -1 $. In fact, if head and tail are the same value, something a little wrong happens.
As an example, consider executing ʻaddLast (3) and ʻaddFirst (2) when head = tail = 0.
First, ʻaddLast (3)stores $ 3 $ in $ x = 0 $, which givestail = 1. And where does ʻaddFirst (2) store $ 2 $? Now, head is still $ 0 $, so it will be stored in a way that $ 2 $ overwrites $ x = 0 $.
Therefore, head needs to be offset by $ 1 $.
Now that all the operations to the beginning / end have been implemented, the only basic function left is to get the size (determine if + deque is empty).
Get size
The number of elements in a deque can be easily calculated using head and tail.
As explained in the previous section, when the number of elements is $ 0 $, tail --head = 1. When the number of elements increases by $ n $, the value of tail --head also increases by $ n $. Therefore, the elements The number $ n $ can be found by calculating tail --head --1.
To determine if the deque is empty, just determine if this size is $ 0 $.
The method to add is as follows.
IntArrayDeque.java
public int size() {
return tail - head - 1;
}
public boolean isEmpty() {
return size() == 0;
}
This completes the implementation of basic functions. Next, we will implement additional functions.
Get the i-th element from the beginning / end
Here, we consider 0-indexed. That is, the $ 0 $ th element from the beginning points to the first element.
The first element can be obtained with getByX (head + 1), so the $ i $ th element from the beginning can be obtained with getByX (head + 1 + i).
Also, by thinking in the same way, the $ i $ th element from the end can be obtained with getByX (tail -1 --i).
Therefore, the method to add is as follows.
IntArrayDeque.java
public int getFromHead(int index) {
return getByX(head + 1 + index);
}
public int getFromTail(int index) {
return getByX(tail - 1 - index);
}
Forward Iterator
Define ʻIntArrayDequeIterator as an inner class and ʻimplements`` PrimitiveIterator.OfInt. Have the coordinates x you are looking at as a member variable, and the initial value of x is the coordinates head of the first element. + 1. The methods to be implemented are boolean hasNext () and ʻint nextInt () `.
hasNext should determine if x is less than or equal to the last coordinate tail -1.
nextInt should returngetByX (x)and at the same time increment x.
From the above, the inner class ʻIntArrayDequeIterator` can be implemented like this.
IntArrayDeque$IntArrayDequeIterator.java
private class IntArrayDequeIterator implements PrimitiveIterator.OfInt {
private int x = head + 1;
public boolean hasNext() {
return x <= tail - 1;
}
public int nextInt() {
return getByX(x++); //Evaluation order is getByX(x) -> x++Order
}
}
Then, on the ʻIntArrayDeque side, define a method PrimitiveIterator.OfInt iterator () that calls this ʻIntArrayDequeIterator.
IntArrayDeque.java
public PrimitiveIterator.OfInt iterator() {
return new IntArrayDequeIterator();
}
Reverse Iterator
All you have to do is reverse the direction in which the coordinates are scanned. Define an inner class called DescendingIntArrayDequeIterator that ʻimplements`` PrimitiveIterator.OfInt`.
IntArrayDeque$DescendingIntArrayDequeIterator.java
private class DescendingIntArrayDequeIterator implements PrimitiveIterator.OfInt {
private int x = tail - 1;
public boolean hasNext() {
return x >= head + 1;
}
public int nextInt() {
return getByX(x--);
}
}
ʻDefine PrimitiveIterator.OfInt descendingIterator () to be called from the IntArrayDeque` side.
IntArrayDeque.java
public PrimitiveIterator.OfInt descendingIterator() {
return new DescendingIntArrayDequeIterator();
}
This completes the implementation of all the desired functions.
However, there are some things to be aware of regarding PrimitiveIterator.OfInt.
In order to incorporate ʻIntArrayDeque into the extended for statement, ʻIterable <Integer> must be ʻimplements, but in this case the for statement is only for ʻIterable <Integer>.
Therefore, auto boxing / unboxing will occur after all, and the meaning of writing PrimitiveIterator.OfInt to speed up ʻIterator` is lost.
If a class like PrimitiveIterable.OfInt is implemented in the standard library and supports the extension for statement, this problem will probably disappear, but there is no such thing at the moment.
Therefore, in order to take advantage of the speed of PrimitiveIterator.OfInt, it is necessary to directly operate PrimitiveIterator.OfInt as follows.
public class Main{
public static void main(String[] args){
IntArrayDeque dq = new IntArrayDeque();
// ...Operations such as adding to dq
PrimitiveIterator.OfInt iter = dq.iterator();
while (iter.hasNext()) {
//here, iter.next()Note that the return value will be an Integer type..
int val = iter.nextInt();
//Processing to be performed for each element val of dq
}
}
}
Summary
Finally, I'll end with the whole ʻIntArrayDeque` class with appropriate exception handling.
IntArrayDeque.java
import java.util.NoSuchElementException;
import java.util.PrimitiveIterator;
public class IntArrayDeque {
private int[] pdeq;
private int[] ndeq;
private int tail;
private int head;
private int defaultSize = 64;
public IntArrayDeque() {
this.pdeq = new int[defaultSize];
this.ndeq = new int[defaultSize];
this.tail = 0;
this.head = -1;
}
public int getLast() {
if (size() == 0) {
throw new NoSuchElementException();
}
return getByX(tail - 1);
}
public void addLast(int v) {
if (tail == pdeq.length) {
growPositive();
}
putByX(tail, v);
tail++;
}
public int pollLast() {
if (size() == 0) {
throw new NoSuchElementException();
}
tail--;
return getByX(tail);
}
public int getFirst() {
if (size() == 0) {
throw new NoSuchElementException();
}
return getByX(head + 1);
}
public void addFirst(int v) {
if (- head - 1 == ndeq.length) {
growNegative();
}
putByX(head, v);
head--;
}
public int pollFirst() {
if (size() == 0) {
throw new NoSuchElementException();
}
head++;
return getByX(head);
}
public int size() {
return tail - head - 1;
}
public boolean isEmpty() {
return size() == 0;
}
public int getFromHead(int index) {
return getByX(head + 1 + index);
}
public int getFromTail(int index) {
return getByX(tail - 1 - index);
}
private int getByX(int x) {
//IndexOutOfBoundsException gets thrown into an array
if (x >= 0) {
return pdeq[x];
} else {
return ndeq[- x - 1];
}
}
private void putByX(int x, int v) {
//IndexOutOfBoundsException gets thrown into an array
if (x >= 0) {
pdeq[x] = v;
} else {
ndeq[- x - 1] = v;
}
}
private void growPositive() {
int[] newPdeq = new int[pdeq.length * 2];
System.arraycopy(pdeq, 0, newPdeq, 0, pdeq.length);
pdeq = newPdeq;
}
private void growNegative() {
int[] newNdeq = new int[ndeq.length * 2];
System.arraycopy(ndeq, 0, newNdeq, 0, ndeq.length);
ndeq = newNdeq;
}
public PrimitiveIterator.OfInt iterator() {
return new IntArrayDequeIterator();
}
public PrimitiveIterator.OfInt descendingIterator() {
return new DescendingIntArrayDequeIterator();
}
private class IntArrayDequeIterator implements PrimitiveIterator.OfInt {
private int x = head + 1;
public boolean hasNext() {
return x <= tail - 1;
}
public int nextInt() {
return getByX(x++);
}
}
private class DescendingIntArrayDequeIterator implements PrimitiveIterator.OfInt {
private int x = tail - 1;
public boolean hasNext() {
return x >= head + 1;
}
public int nextInt() {
return getByX(x--);
}
}
}
reference
[Traps and Techniques for Competitive Programming in Java](https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4#%E3%82%AA%E3%83%BC%E3%83%88%E3%83] % 9C% E3% 82% AF% E3% 82% B7% E3% 83% B3% E3% 82% B0--% E3% 82% A2% E3% 83% B3% E3% 83% 9C% E3% 82 % AF% E3% 82% B7% E3% 83% B3% E3% 82% B0)
Recommended Posts