성능 향상 사용자 지정 단일 연결 목록 밀어 내기

Question

Java에서 단독 연결 목록을 만들었습니다. 이 목록에는 푸시 된 첫 번째 항목이 갑자기 마지막으로 표시되는 항목이 있습니다.

터지는 성능은 대기열에 비해 좋습니다. 푸시 성능을 향상시키고 싶습니다. prepending 대신 push 방식으로 추가를 시도했지만 성능이 향상되지 않았습니다.

이 목록을 개선하는 방법에 대해 알고 계신가요?

푸시 팝 성능 (스택, ArrayList를하고 대기열은 java.util의 구현입니다) : 터지는

스택을 776.3ms :

1000 만 정수 10 개 실행

• 은 스택 충전에 대해 평균 : 207.2ms
• 의 ArrayList 충전물 : 35.3ms
• 큐 F :
• 팝핑의 ArrayList를 574.0ms illing : 96.9ms
• myList에 충전 :
• myList에 터지는 4811.2ms :
• 터지는 큐 2642.2ms 50.5ms

public class MyList<T> { 
    T head = null; 
    MyList<T> tail = null; 
    boolean isNil = true; 

    public T pop() { 
     if(isNil) { 
      return null; 
     } 
     else if(this.tail.isNil) { 
      this.isNil = true; 
      return head; 
     } 
     else { 
      T head = this.head; 
      this.head = this.tail.head; 
      this.tail = this.tail.tail; 
      return head; 
     } 
    } 

    public void push(T element) { 
     MyList<T> item = new MyList<T>(); 
     item.head = this.head; 
     item.tail = this.tail; 
     item.isNil = this.isNil; 
     this.head = element; 
     this.tail = item; 
     this.isNil = false; 
    } 
} 

Answer 1

아래의 테스트는 ArrayList를 < 정수를 사용하는 변경을> 내가 얻을 큰 젊은 세대 크기를 사용할 때 다음과 같습니다. -XX:NewSize=1g 이것은 GC가 큰 오버 헤드이고 큰 Eden 크기가 GC 수를 줄이기 때문에 도움이됩니다.

ArrayList push&pop 10000000 repeated 10 times took 1183 ms. 

참고 : ArrayList를 사용하면

---

당신은 TIntArrayList을 시도하거나 할 수있는, 마지막에 추가 (그리고 끝에서 제거)해야 할 효율적으로 동일한

TIntArrayList list = new TIntArrayList(); 
long start = System.nanoTime(); 
int values = 10 * 1000 * 1000; 
int runs = 10; 
for (int r = 0; r < runs; r++) { 
    for (int i = 0; i < values; i++) { 
     list.add(i); 
    } 
    for (int i = 0; i < values; i++) { 
     int last = list.remove(list.size() - 1); // get the last 
    } 
} 
long time = System.nanoTime() - start; 
System.out.println("TIntArrayList push&pop " + values + " repeated "+runs+" times took " + time/1000000 + " ms."); 

프린트

TIntArrayList push&pop 10000000 repeated 10 times took 577 ms. 

당신의 가장 큰 오버 헤드는 객체 할당 일 가능성이 큽니다. 이 속도를 높이려면 최소화하는 방법을 살펴 보시기 바랍니다. BTW : 다른 정수를 사용하는 데 걸리는 시간을 테스트해야합니다.

Answer 2

나는 목록의 성능이 ArrayList (그리고 Stack, which is based on Vector가)에서 훨씬 더 큰 덩어리를 할당하는 반면 ArrayList, 당신은 작은 물체를 많이 할당하는 것이 있음을 지연 이유라고 생각합니다.

이 코드 조각의 성능을 향상시키기 위해 설정 한 경우 큰 덩어리로 메모리를 미리 할당 한 다음 필요에 따라 MyList<T>으로 분할하여 자신의 룩 사이드 목록을 롤업 할 수 있습니다. 그러나 메모리 관리가 의미하는 바는 심각 할 것임을 기억하십시오 : 필요한 시간보다 훨씬 오래 메모리에 남아있는 블록을 생성하지 않아야하므로 사실상 메모리 누수가 발생합니다.

Answer 3

실제로는 이 없습니다. 많은 개선의 여지가 있지만, isNil 변수를 없애 버릴 수 있습니다. tail == null의 비교를 쉽게 사용할 수 있습니다. 이렇게하면 반복 할 때마다 할당 과제를 줄일 수 있습니다.

개체 생성에서 벗어날 수는 없지만 (배열 기반이 아닌 단일 연결이어야 함) 할당 수를 줄일 수 있습니다.