배열 또는 목록(Java).어느 쪽이 빠릅니까?
자바에서 직렬로 액세스하려면 수천 개의 문자열을 메모리에 저장해야 합니다.배열에 저장해야 합니까, 아니면 목록 같은 것을 사용해야 합니까?
어레이는 (목록과 달리) 모든 데이터를 연속된 메모리 청크에 보관하기 때문에 어레이를 사용하여 수천 개의 문자열을 저장하면 문제가 발생할 수 있습니까?
프로파일러를 사용하여 어느 쪽이 빠른지 테스트할 것을 권장합니다.
제 개인적인 의견은 Lists를 사용해야 한다는 것입니다.
저는 대규모 코드베이스에서 일하고 있으며, 이전 개발자 그룹은 어디에서나 어레이를 사용하고 있습니다.그 때문에 코드가 매우 유연하지 않게 되었습니다.Lists로 큰 덩어리를 변경한 후 속도 차이는 없었습니다.
Java 방식은 어떤 데이터 추상화가 사용자의 요구에 가장 적합한지 고려해야 합니다.Java에서 목록은 구체적인 데이터 유형이 아니라 추상적인 것입니다.문자열을 목록으로 선언한 후 ArrayList 구현을 사용하여 초기화해야 합니다.
List<String> strings = new ArrayList<String>();
이러한 추상 데이터 유형과 특정 구현의 분리는 객체 지향 프로그래밍의 주요 측면 중 하나입니다.
ArrayList는 배열을 기본 구현으로 사용하여 List Abstract Data Type을 구현합니다.액세스 속도는 어레이와 거의 동일하며 목록에 요소를 추가하거나 제외할 수 있다는 이점도 있습니다(이것은 ArrayList를 사용한 O(n) 작업이지만 나중에 기본 구현을 변경할 경우 변경할 수 있습니다).예를 들어 동기화된 액세스가 필요한 경우 모든 코드를 다시 쓰지 않고 구현을 벡터로 변경할 수 있습니다.
실제로 ArrayList는 대부분의 컨텍스트에서 낮은 수준의 어레이 구조를 대체하도록 특별히 설계되었습니다.현재 Java가 설계되어 있다면 어레이는 ArrayList 구축에 전혀 도움이 되지 않을 가능성이 있습니다.
어레이는 (목록과 달리) 모든 데이터를 연속된 메모리 청크에 보관하기 때문에 어레이를 사용하여 수천 개의 문자열을 저장하면 문제가 발생할 수 있습니까?
Java에서는 모든 컬렉션이 오브젝트에 대한 참조만 저장하고 오브젝트 자체는 저장합니다.어레이와 ArrayList는 모두 수천 개의 참조를 연속된 어레이에 저장하기 때문에 기본적으로 동일합니다.최신 하드웨어에서는 몇 천 개의 32비트 참조가 연속된 블록을 언제든지 사용할 수 있습니다.물론 이는 메모리가 완전히 소진되는 것을 보증하는 것은 아닙니다.단, 연속되는 메모리 블록의 fufiling은 어렵지 않습니다.
Array List 사용을 제안하는 답변은 대부분의 시나리오에서 타당하지만 실제 상대적인 퍼포먼스에 대한 질문은 아직 답변되지 않았습니다.
어레이를 사용하여 수행할 수 있는 작업은 다음과 같습니다.
- 작성하다
- 항목을 정하다
- 아이템을 입수하다
- 복제/복사
일반적인 결론
ArrayList 에서는 get 및 set 조작이 다소 느리지만(머신에서는 콜당1 나노초 및 3 나노초), 집약적이지 않은 용도로 어레이를 사용하는 경우보다 ArrayList를 사용하는 경우의 오버헤드는 거의 없습니다.다만, 몇개의 점에 주의해 주세요.
- 의 크기 변경(「」를 했을 경우)
list.add(...)는 비용이 많이 들기 초기 할 때 에 유의하십시오 - 기본 요소를 처리할 때 어레이는 많은 박스/언박싱 변환을 피할 수 있기 때문에 훨씬 더 빠를 수 있습니다.
- ArrayList 내의 값만 가져오거나 설정하는 애플리케이션(매우 일반적이지 않음)은 어레이로 전환함으로써 25% 이상의 퍼포먼스를 얻을 수 있습니다.
상세 결과
다음은 표준 x86 데스크톱 머신에서 JDK 7을 사용한jmh 벤치마크 라이브러리(나노초 단위)를 사용한3가지 작업에 대해 측정한 결과입니다.테스트에서 Array List의 사이즈는 조정되지 않습니다.이것에 주의해 주세요.벤치마크 코드는 이쪽입니다.
어레이/어레이 리스트 작성
4개의 테스트를 실행하여 다음 문장을 실행했습니다.
- 어레이1을 만듭니다.
Integer[] array = new Integer[1]; - createList1:
List<Integer> list = new ArrayList<> (1); - Array 10000: 어레이 10000을 만듭니다.
Integer[] array = new Integer[10000]; - createList10000:
List<Integer> list = new ArrayList<> (10000);
결과(콜당 나노초, 95% 신뢰):
a.p.g.a.ArrayVsList.CreateArray1 [10.933, 11.097]
a.p.g.a.ArrayVsList.CreateList1 [10.799, 11.046]
a.p.g.a.ArrayVsList.CreateArray10000 [394.899, 404.034]
a.p.g.a.ArrayVsList.CreateList10000 [396.706, 401.266]
결론: 눈에 띄는 차이는 없습니다.
수술을 받다
2개의 테스트를 실행하여 다음 문장을 실행했습니다.
- 목록 가져오기:
return list.get(0); - Array: 어레이 가져오기:
return array[0];
결과(콜당 나노초, 95% 신뢰):
a.p.g.a.ArrayVsList.getArray [2.958, 2.984]
a.p.g.a.ArrayVsList.getList [3.841, 3.874]
결론: 어레이에서 얻는 속도는 Array List에서 얻는 속도보다 약 25% 빠릅니다.단, 차이는 1나노초 정도입니다.
작업을 설정하다
2개의 테스트를 실행하여 다음 문장을 실행했습니다.
- setList:
list.set(0, value); - 어레이를 설정합니다.
array[0] = value;
결과(콜당 나노초 단위):
a.p.g.a.ArrayVsList.setArray [4.201, 4.236]
a.p.g.a.ArrayVsList.setList [6.783, 6.877]
결론: 어레이의 설정 조작은 리스트의 설정 조작보다 약 40% 고속이지만, 각 설정 조작은 몇 나노초 걸립니다.따라서 차이가 1초에 도달하려면 리스트/어레이 내의 항목을 수억 번 설정해야 합니다.
복제/복사
는 ArrayList에 합니다.Arrays.copyOf 퍼포먼스는 를 경유하여 합니다).clone,Arrays.copyOf ★★★★★★★★★★★★★★★★★」System.arrayCopy 퍼포먼스에 있어서 중요한 차이는 없습니다).
어레이보다 일반 유형을 선호해야 합니다.다른 사람들이 언급했듯이 어레이는 유연성이 낮고 범용 유형의 표현력이 없습니다.(다만, 런타임 타입 체크를 서포트하고 있습니다만, 범용 타입과 혼재하지 않습니다).
그러나 항상 그렇듯이 최적화할 때는 항상 다음 단계를 따라야 합니다.
- 깔끔하고 동작 가능한 버전의 코드를 입수할 때까지 최적화하지 마십시오.범용 타입으로의 변경은, 이 단계에서 충분히 동기 부여가 되고 있을 가능성이 있습니다.
- 깔끔하고 좋은 버전이 있을 때, 그것이 충분히 빠른지 판단하세요.
- 속도가 충분하지 않으면 성능을 측정하십시오.이 단계는 두 가지 이유로 중요합니다.측정하지 않으면 (1) 최적화의 영향과 (2) 최적화의 위치를 알 수 없습니다.
- 코드의 가장 핫한 부분을 최적화합니다.
- 다시 재다.이것은 이전과 마찬가지로 중요합니다.최적화로 상황이 개선되지 않으면 되돌립니다.최적화를 하지 않은 코드는 깨끗하고, 양호하며, 작동한다는 것을 기억하십시오.
원본 포스터는 C++/STL 배경에서 나온 것으로 추측되며, 이로 인해 혼란이 발생하고 있습니다. C++ 인std::list는 이중 링크 리스트입니다.
[java.util.]List는 구현이 필요 없는 인터페이스(C++ 용어의 순수 추상 클래스)입니다. List연결된 일 수 .java.util.LinkedList제공되고 있습니다. 가 할 때는 중 100번을 만듭니다.List 「 」를 하고 .java.util.ArrayList C++는 대략 C++의 입니다.std::vector에도 표준. 예를 , 에 의해 이 있습니다예를 들어 에 의해 반환되는 구현이 있습니다.java.util.Collections.emptyList() ★★★★★★★★★★★★★★★★★」java.util.Arrays.asList().
퍼포먼스의 관점에서는 인터페이스와 추가 오브젝트를 경유해야 하는 경우는 매우 적지만 런타임인라이닝은 거의 의미가 없습니다. 이 부분은 잊지 .String는는으 + 열다다다다다다 。따라서 각 엔트리에 대해 두 개의 다른 개체가 있을 수 있습니다. C++ 인std::vector<std::string>포인터 없이 값으로 복사해도 문자 배열은 문자열 개체를 형성합니다(일반적으로 공유되지 않습니다).
가 실제로 에 영향을 미치는 경우 할 수 .char[] array(또는 array))byte[]모든 스트링의 모든 문자에 대해서, 다음으로 오프셋의 배열을 나타냅니다.IIRC, javac, javac.
대부분의 경우 어레이보다 Array Lists의 유연성과 우아함을 선택해야 하며 대부분의 경우 프로그램 퍼포먼스에 미치는 영향은 미미합니다.
그러나 소프트웨어 그래픽 렌더링이나 커스텀 가상 머신에 대해 구조 변경(추가 및 삭제 없음)을 거의 하지 않고 지속적으로 반복하는 경우 시퀀셜 액세스 벤치마크 테스트 결과 ArrayLists는 시스템상의 어레이보다 1.5배 느립니다(iMac에서는 Java 1.6).
일부 코드:
import java.util.*;
public class ArrayVsArrayList {
static public void main( String[] args ) {
String[] array = new String[300];
ArrayList<String> list = new ArrayList<String>(300);
for (int i=0; i<300; ++i) {
if (Math.random() > 0.5) {
array[i] = "abc";
} else {
array[i] = "xyz";
}
list.add( array[i] );
}
int iterations = 100000000;
long start_ms;
int sum;
start_ms = System.currentTimeMillis();
sum = 0;
for (int i=0; i<iterations; ++i) {
for (int j=0; j<300; ++j) sum += array[j].length();
}
System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" );
// Prints ~13,500 ms on my system
start_ms = System.currentTimeMillis();
sum = 0;
for (int i=0; i<iterations; ++i) {
for (int j=0; j<300; ++j) sum += list.get(j).length();
}
System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" );
// Prints ~20,800 ms on my system - about 1.5x slower than direct array access
}
}
우선 comp sci data structures의 의미(링크 리스트)로 "list"를 의미하는지 java.util.List를 의미하는지 명확히 할 필요가 있습니다.java.util을 말하는 경우.리스트, 인터페이스야.어레이를 사용하려면 ArrayList 구현을 사용하면 어레이와 같은 동작과 의미를 얻을 수 있습니다.문제는 해결됐습니다.
배열과 링크된 목록을 의미하는 경우, Big O로 돌아가는 것은 약간 다릅니다(이것이 익숙하지 않은 용어의 경우 간단한 영어 설명입니다).
어레이
- 랜덤 액세스: O(1);
- 삽입: O(n);
- 삭제: O(n)
링크 리스트:
- 랜덤 액세스: O(n);
- 삽입: O(1);
- 삭제: O(1)
따라서 어레이 크기를 조정하는 방법에 가장 적합한 것을 선택합니다.크기 조정, 삽입 및 삭제를 많이 하는 경우 링크 목록이 더 나을 수 있습니다.랜덤 액세스가 드문 경우에도 마찬가지입니다.시리얼 액세스에 대해 언급하셨죠거의 변경하지 않고 주로 시리얼 액세스를 하고 있다면 어느 쪽을 선택하든 상관없습니다.
링크 리스트는, 말씀하신 것처럼, 인접하지 않은 메모리 블록과 (효과적으로) 다음 요소에 대한 포인터를 다루고 있기 때문에, 오버헤드가 약간 높아집니다.그러나 수백만 개의 엔트리를 처리하지 않는 한 이는 중요한 요소가 아닐 수 있습니다.
Array Lists와 Arrays를 비교하기 위해 약간의 벤치마크를 작성했습니다.구형 노트북에서는 5000개의 요소 어레이 목록을 통과하는 데 걸리는 시간이 동등한 어레이 코드보다 약 10밀리초 느렸습니다.
따라서 목록을 반복하는 것 외에 많은 작업을 수행하고 있다면 최적화할 가치가 있습니다.그렇지 않으면 코드를 최적화해야 할 때 더 쉽게 사용할 수 있기 때문에 목록을 사용할 것입니다.
N.b. 제가 알아차린 건for String s: stringsList이전 스타일의 for-loop을 사용하여 목록에 액세스하는 것보다 속도가 약 50% 느렸습니다.★★★★★★★★★★★★★★★★★★▼다음은 타이밍을 맞춘 두 가지 함수입니다. 배열과 목록은 5000개의 랜덤(다른) 문자열로 채워졌습니다.
private static void readArray(String[] strings) {
long totalchars = 0;
for (int j = 0; j < ITERATIONS; j++) {
totalchars = 0;
for (int i = 0; i < strings.length; i++) {
totalchars += strings[i].length();
}
}
}
private static void readArrayList(List<String> stringsList) {
long totalchars = 0;
for (int j = 0; j < ITERATIONS; j++) {
totalchars = 0;
for (int i = 0; i < stringsList.size(); i++) {
totalchars += stringsList.get(i).length();
}
}
}
아니요. 기술적으로는 어레이가 문자열에 대한 참조만 저장하기 때문입니다.문자열 자체는 다른 위치에 할당됩니다.천 개에 대해서는 리스트가 더 낫고 느리지만 유연성이 뛰어나고 사용하기 편합니다. 특히 크기를 조정할 경우에는 더욱 그렇습니다.
수천 개가 있다면 트리 사용을 고려해 보십시오.trie는 저장된 문자열의 공통 접두사를 병합하는 트리 같은 구조입니다.
예를 들어 문자열이 다음과 같은 경우
intern
international
internationalize
internet
internets
Trie는 다음을 저장합니다.
intern
-> \0
international
-> \0
-> ize\0
net
->\0
->s\0
문자열은 저장용으로 57자(null 터미네이터 '\0' 포함)와 문자열 객체의 크기에 상관없이 필요합니다. (실제로 모든 크기를 16의 배수까지 반올림해야 하지만...) 대략 57 + 5 = 62바이트라고 합니다.
trie에는 스토리지에 29개(늘 터미네이터 「\0」 포함)가 필요합니다.또한 trie 노드의 크기는 어레이에 대한 참조 및 하위 trie 노드의 목록입니다.
이 예에서는, 공통의 프리픽스가 있는 한, 수천의 경우는, 거의 같은 결과가 됩니다.
다른 코드에서 trie를 사용할 때는 String으로 변환해야 합니다.아마 String Buffer를 매개로 사용할 수 있습니다.많은 현이 동시에 Strings로 사용되고 있는 경우, 트리 밖에서 손실입니다.
다만, 예를 들면, 사전의 검색 등, 몇개 밖에 사용하지 않는 경우는, 트라이에 의해서 큰 공간을 절약할 수 있습니다.HashSet에 저장하는 것보다 훨씬 적은 공간입니다.
「시리얼」접속이라고 하는 것은, 알파벳 순으로 차례로 액세스 하는 경우, 깊이 우선으로 반복하는 경우, 트리에는 확실히 알파벳 순서도 무료로 부여됩니다.
여기에는 이미 좋은 답변이 많이 있기 때문에 삽입 및 반복 퍼포먼스 비교, Java에서의 primitive array vs Linked-list라는 실용적인 뷰에 대한 몇 가지 정보를 드리겠습니다.
이것은 실제 간단한 퍼포먼스 체크입니다.
따라서 결과는 기계의 성능에 따라 달라집니다.
이 작업에 사용되는 소스 코드는 다음과 같습니다.
import java.util.Iterator;
import java.util.LinkedList;
public class Array_vs_LinkedList {
private final static int MAX_SIZE = 40000000;
public static void main(String[] args) {
LinkedList lList = new LinkedList();
/* insertion performance check */
long startTime = System.currentTimeMillis();
for (int i=0; i<MAX_SIZE; i++) {
lList.add(i);
}
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
int[] arr = new int[MAX_SIZE];
startTime = System.currentTimeMillis();
for(int i=0; i<MAX_SIZE; i++){
arr[i] = i;
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
/* iteration performance check */
startTime = System.currentTimeMillis();
Iterator itr = lList.iterator();
while(itr.hasNext()) {
itr.next();
// System.out.println("Linked list running : " + itr.next());
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
startTime = System.currentTimeMillis();
int t = 0;
for (int i=0; i < MAX_SIZE; i++) {
t = arr[i];
// System.out.println("array running : " + i);
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
}
}
퍼포먼스 결과는 다음과 같습니다.
어레이보다 리스트를 사용하는 것이 퍼포먼스에 미치는 영향에 대해 더 잘 알고 싶어서 왔습니다.여기서 코드를 조정해야 했습니다.대부분 getters를 사용하여 최대 1000ints의 어레이/목록, 즉 array[j] vs. list.get(j)
비과학적인 방법으로 7의 장점을 취하면(처음에는 2.5배 느린 목록이 몇 개 있습니다) 다음과 같습니다.
array Integer[] best 643ms iterator
ArrayList<Integer> best 1014ms iterator
array Integer[] best 635ms getter
ArrayList<Integer> best 891ms getter (strange though)
- 어레이로 약 30% 고속화
지금 게시하는 두 번째 이유는 중첩된 루프를 사용하여 산술/행렬/시뮬레이션/최적화 코드를 실행할 경우 영향을 아무도 언급하지 않기 때문입니다.
네스트된 레벨이 3개 있고 내부 루프가 퍼포먼스의 8배에 해당하는 속도보다 2배 느리다고 가정해 보겠습니다.하루 만에 작동하는 것은 이제 일주일이 걸린다.
*EDIT 여기에서는 상당히 충격입니다.나는 재미삼아 Integer[1000]가 아닌 int[1000]를 선언하려고 했습니다.
array int[] best 299ms iterator
array int[] best 296ms getter
Integer[] vs. int[]를 사용하면 퍼포먼스가 2배로 향상됩니다.반복기를 사용하는 ListArray는 int[]보다 3배 느립니다.Java의 리스트 실장은 네이티브 어레이와 비슷하다고 생각했습니다.
참조용 코드(복수 호출):
public static void testArray()
{
final long MAX_ITERATIONS = 1000000;
final int MAX_LENGTH = 1000;
Random r = new Random();
//Integer[] array = new Integer[MAX_LENGTH];
int[] array = new int[MAX_LENGTH];
List<Integer> list = new ArrayList<Integer>()
{{
for (int i = 0; i < MAX_LENGTH; ++i)
{
int val = r.nextInt();
add(val);
array[i] = val;
}
}};
long start = System.currentTimeMillis();
int test_sum = 0;
for (int i = 0; i < MAX_ITERATIONS; ++i)
{
// for (int e : array)
// for (int e : list)
for (int j = 0; j < MAX_LENGTH; ++j)
{
int e = array[j];
// int e = list.get(j);
test_sum += e;
}
}
long stop = System.currentTimeMillis();
long ms = (stop - start);
System.out.println("Time: " + ms);
}
목록이 배열보다 느립니다.효율성이 필요한 경우 어레이를 사용합니다.유연성이 필요한 경우 사용 목록.
갱신:
Mark가 언급했듯이 JVM 예열 후 큰 차이는 없습니다(몇 가지 테스트 통과).어레이를 다시 작성하거나 매트릭스의 새로운 행으로 시작하는 새로운 패스를 확인.인덱스 액세스 기능이 있는 이 기호 단순 배열은 컬렉션에 유리하게 사용되지 않을 가능성이 매우 높습니다.
그러나 첫 번째 1-2 패스는 단순한 어레이가 2~3배 더 빠릅니다.
최초 투고:
주제에 대한 단어가 너무 많아서 확인하기가 너무 쉽다.어레이는 클래스 컨테이너보다 몇 배나 빠릅니다.퍼포먼스 크리티컬 섹션의 대안을 찾고 있습니다.다음은 실제 상황을 확인하기 위해 만든 시제품 코드입니다.
import java.util.List;
import java.util.Arrays;
public class IterationTest {
private static final long MAX_ITERATIONS = 1000000000;
public static void main(String [] args) {
Integer [] array = {1, 5, 3, 5};
List<Integer> list = Arrays.asList(array);
long start = System.currentTimeMillis();
int test_sum = 0;
for (int i = 0; i < MAX_ITERATIONS; ++i) {
// for (int e : array) {
for (int e : list) {
test_sum += e;
}
}
long stop = System.currentTimeMillis();
long ms = (stop - start);
System.out.println("Time: " + ms);
}
}
답은 다음과 같습니다.
어레이 기준(16행은 액티브):
Time: 7064
리스트에 근거해(17행은 액티브):
Time: 20950
'에 대해 더 말씀 ? 'faster'에 대해이것은 충분히 이해되고 있다.문제는 List의 유연성보다 3배 정도 빠른 것이 언제가 당신에게 좋을까 하는 것입니다.을 사용하다그런데 이것도 수작업으로 확인했습니다.ArrayList 결과 거의 같은 결과입니다.
ArrayList는 어레이를 캡슐화하므로 원시 어레이를 사용하는 것과 거의 차이가 없습니다(Java에서 사용하는 것이 훨씬 쉽다는 점을 제외).
Array List보다 어레이를 선호하는 것은 바이트, int 등의 프리미티브를 저장할 때 원시 어레이를 사용함으로써 얻을 수 있는 특정 공간 효율이 필요한 경우뿐입니다.
어레이와스트링 오브젝트를 저장하는 경우 성능을 고려할 때 목록 선택은 그다지 중요하지 않습니다.배열과 목록 모두 실제 개체가 아닌 문자열 개체 참조를 저장하기 때문입니다.
- 문자열 수가 거의 일정할 경우 배열(또는 ArrayList)을 사용합니다.단, 숫자가 너무 다르면 Linked List를 사용하는 것이 좋습니다.
- 중간에 요소를 추가하거나 삭제할 필요가 있는 경우 Linked List를 사용해야 합니다.
고정 사이즈로 사용할 수 있으면, 어레이의 처리 속도가 빨라져 필요한 메모리가 줄어듭니다.
요소의 추가와 삭제에 관한 리스트인터페이스의 유연성이 필요한 경우는, 어느 실장을 선택할 필요가 있는지에 대한 의문이 남습니다.대부분의 경우 ArrayList를 권장하고 사용하지만 목록 처음 또는 중간에 있는 요소를 제거하거나 삽입해야 하는 경우 ArrayList에서도 성능 문제가 발생합니다.
따라서 GapList를 소개하는 http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list을 참조해 주십시오.이 새로운 리스트 실장에서는 Array List와 Linked List의 장점을 조합하여 거의 모든 조작에 매우 뛰어난 퍼포먼스를 제공합니다.
데이터의 크기를 미리 알고 있으면 어레이의 처리 속도가 빨라집니다.
목록은 더 유연합니다.어레이에 의해 백업되는 ArrayList를 사용할 수 있습니다.
Java 1.5 이상에서는 제네릭스를 사용할 수 있으므로 List가 선호됩니다.어레이에는 제네릭을 사용할 수 없습니다.또, 어레이의 길이는 사전에 정의되어 있어 동적으로 확장할 수 없습니다.큰 사이즈의 어레이를 초기화하는 것은 좋지 않습니다.Array List는 범용 어레이를 선언하는 방법으로 동적으로 확장할 수 있습니다.그러나 삭제 및 삽입이 더 자주 사용되는 경우 링크드 리스트가 가장 빠르게 사용되는 데이터 구조입니다.
구현에 따라 다릅니다.기본 유형의 배열이 Array List보다 작고 효율적일 수 있습니다.이는 배열이 인접한 메모리 블록에 값을 직접 저장하는 반면 가장 단순한 ArrayList 구현은 각 값에 대한 포인터를 저장하기 때문입니다.특히 64비트 플랫폼에서는 이 점이 큰 차이를 만들 수 있습니다.
물론, jvm 구현에는 이러한 상황에 대한 특별한 사례가 있을 수 있으며, 이 경우 성능은 동일합니다.
목록 대신 어레이를 사용할 수 있습니다. 특히 항목 수와 크기가 변경되지 않을 경우 어레이를 사용할 수 있습니다.
Oracle Java의 베스트 프랙티스를 참조해 주세요.http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056
물론 컬렉션에서 개체를 여러 번 추가하고 제거해야 하는 경우 목록을 쉽게 사용할 수 있습니다.
여기에 기재되어 있는 많은 마이크로벤치마크에서는 어레이/ArrayList 읽기 등의 수치로 수 나노초의 값을 확인할 수 있습니다.모든 것이 L1 캐시에 있는 경우, 이것은 매우 합리적입니다.
상위 레벨의 캐시 또는 메인 메모리 액세스에서는 L1 캐시의 경우 1nS에 비해 10nS-100nS와 같은 크기의 횟수를 가질 수 있습니다.Array List 에 액세스 하면, 메모리 방향 전환이 추가되어 실제 애플리케이션에서는, 액세스간의 코드의 동작에 따라, 거의 전혀 하지 않는 것부터, 매번 이 코스트를 지불할 수 있습니다.물론 작은 Array Lists가 많으면 메모리 사용량이 증가하고 캐시 누락이 발생할 가능성이 높아집니다.
오리지널 포스터는 한 장만 사용하여 짧은 시간에 많은 콘텐츠를 볼 수 있기 때문에 큰 어려움은 없을 것 같습니다.그러나 다른 사람에 따라 다를 수 있으므로 마이크로벤치마크를 해석할 때는 주의해야 합니다.
그러나 Java String은 특히 작은 것을 많이 저장하는 경우(메모리 분석기로만 보면 몇 글자의 문자열에 대해 60바이트를 초과하는 것으로 보입니다).문자열 배열은 String 개체로, 다른 문자열 배열은 String 개체에서 문자열 자체를 포함하는 문자[]로 방향 지정됩니다.L1 캐시를 파괴할 가능성이 있는 것은 이것뿐입니다.이것들은 수천 또는 수만 개의 문자열과 조합되어 있습니다.따라서, 가능한 한 많은 퍼포먼스를 스크랩 하는 것에 대해 진지하게 생각하고 있다면, 다른 관점에서 생각해 볼 수 있습니다.예를 들어 모든 문자열이 포함된 char[]와 시작 부분에 오프셋이 있는 int[] 두 개의 배열을 사용할 수 있습니다.이것은 PITA를 사용하여 무엇이든 할 수 있는 것이므로, 거의 필요 없습니다.만약 그렇다면, 당신은 잘못된 언어를 선택한 것입니다.
같은 어레이를 여러 번 반복 스캔하는 등 관심 있는 정보가 없는 답변이 있었습니다.이를 위해 JMH 테스트를 작성해야 했습니다.
결과(Java 1.8.0_66 x32, 플레인 어레이 반복 속도는 Array List보다 최소 5배 빠름):
Benchmark Mode Cnt Score Error Units
MyBenchmark.testArrayForGet avgt 10 8.121 ? 0.233 ms/op
MyBenchmark.testListForGet avgt 10 37.416 ? 0.094 ms/op
MyBenchmark.testListForEach avgt 10 75.674 ? 1.897 ms/op
시험
package my.jmh.test;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
@State(Scope.Benchmark)
@Fork(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class MyBenchmark {
public final static int ARR_SIZE = 100;
public final static int ITER_COUNT = 100000;
String arr[] = new String[ARR_SIZE];
List<String> list = new ArrayList<>(ARR_SIZE);
public MyBenchmark() {
for( int i = 0; i < ARR_SIZE; i++ ) {
list.add(null);
}
}
@Benchmark
public void testListForEach() {
int count = 0;
for( int i = 0; i < ITER_COUNT; i++ ) {
for( String str : list ) {
if( str != null )
count++;
}
}
if( count > 0 )
System.out.print(count);
}
@Benchmark
public void testListForGet() {
int count = 0;
for( int i = 0; i < ITER_COUNT; i++ ) {
for( int j = 0; j < ARR_SIZE; j++ ) {
if( list.get(j) != null )
count++;
}
}
if( count > 0 )
System.out.print(count);
}
@Benchmark
public void testArrayForGet() {
int count = 0;
for( int i = 0; i < ITER_COUNT; i++ ) {
for( int j = 0; j < ARR_SIZE; j++ ) {
if( arr[j] != null )
count++;
}
}
if( count > 0 )
System.out.print(count);
}
}
"수천"은 큰 숫자가 아니다.수천 개의 단락 길이의 문자열은 크기가 몇 메가바이트 정도 됩니다.이들 시리얼에 접속하는 것만으로, 불변의 단일 링크 리스트를 사용할 수 있습니다.
어떤 것을 사용할지는 문제에 따라 다릅니다.빅 오를 살펴봐야 해
이미지 소스: https://github.com/egonSchiele/grokking_algorithms
적절한 벤치마킹 없이 최적화의 함정에 빠지지 마십시오.다른 사람들이 제안했듯이, 어떠한 가정도 하기 전에 프로파일러를 사용합니다.
열거한 데이터 구조마다 용도가 다릅니다.목록은 처음과 끝에 요소를 삽입하는 데 매우 효율적이지만 랜덤 요소에 액세스할 때 많은 문제를 겪습니다.어레이에는 고정 스토리지가 있지만 랜덤 액세스가 빠릅니다.마지막으로 Array List를 사용하면 어레이가 확장되기 때문에 어레이에 대한 인터페이스가 향상됩니다.일반적으로 사용되는 데이터 구조는 저장된 데이터의 액세스 방법 또는 추가 방법에 따라 결정됩니다.
메모리 소비에 대해서뭔가 섞이는 것 같아요.어레이는 보유하고 있는 데이터 유형에 대한 연속적인 메모리 청크만 제공합니다.Java에는 boolean, char, int, long, float 및 Object라는 고정 데이터 유형이 있다는 것을 잊지 마십시오.즉, String 문자열 [1000]또는 MyObject myObjects [1000]의 배열을 선언하면 객체의 위치(참조 또는 포인터)를 저장할 수 있는 크기의 메모리박스가 1000개밖에 남지 않습니다.오브젝트 크기에 맞도록 1000개의 메모리 박스가 있는 것은 아닙니다.오브젝트는 처음에 "new"로 작성된다는 것을 잊지 마십시오.메모리 할당이 완료되고 나중에 참조(메모리 주소)가 어레이에 저장됩니다.개체는 참조만 배열에 복사되지 않습니다.
스트링스에겐 별 차이가 없는 것 같아문자열 배열에서 연속되는 것은 문자열에 대한 참조이며 문자열 자체는 메모리의 임의의 위치에 저장됩니다.
어레이와목록은 개체가 아닌 원시 유형에 대해 차이를 만들 수 있습니다.요소의 수를 미리 알고 유연성이 필요하지 않은 경우, 수백만 개의 정수 또는 두 배의 배열이 목록보다 메모리에서 효율적이며 속도가 약간 빠릅니다. 왜냐하면 그것들은 실제로 연속적으로 저장되고 즉시 액세스되기 때문입니다.그렇기 때문에 Java는 여전히 문자열에 chars 배열, 이미지 데이터에 int 배열 등을 사용합니다.
어레이가 고속입니다.모든 메모리가 사전에 할당되어 있습니다.
접속 방법에 따라 다릅니다.
저장 후 삽입/삭제를 거의 또는 전혀 하지 않고 주로 검색 작업을 수행할 경우 Array로 이동합니다(배열에서는 검색이 O(1)로 이루어지지만 요소의 추가/삭제가 다시 필요할 수 있습니다).
저장 후 검색 조작을 거의 또는 전혀 하지 않고 문자열을 추가/삭제하는 것이 주된 목적이라면 List로 이동합니다.
어레이 - 결과를 신속하게 가져올 필요가 있을 때는 항상 유리합니다.
목록 - O(1)에서 수행할 수 있으므로 삽입 및 삭제 시 결과를 수행하고 데이터를 쉽게 추가, 가져오기 및 삭제할 수 있는 방법도 제공합니다.훨씬 사용하기 쉬워요.
그러나 데이터가 저장된 배열의 인덱스 위치를 알고 있으면 데이터 가져오기 속도가 빠릅니다.
이 작업은 어레이를 정렬하여 수행할 수 있습니다.따라서 데이터 가져오기 시간(즉, 데이터 저장 + 데이터 정렬 + 데이터가 발견된 위치에 대한 검색)이 증가합니다.따라서 데이터를 더 빨리 가져올 수 있더라도 어레이에서 데이터를 가져오기 위한 추가 지연 시간이 늘어납니다.
따라서 이 문제는 트라이 데이터 구조 또는 3진 데이터 구조로 해결할 수 있습니다.위에서 설명한 바와 같이, 특정 단어에 대한 검색은 데이터 검색에 매우 효율적일 것이다.시간이 중요한 경우(즉, 데이터를 신속하게 검색 및 검색해야 하는 경우)에는 trie 데이터 구조를 사용할 수 있습니다.
메모리 용량을 줄이고 성능을 향상시키려면 3진수 데이터 구조를 사용하십시오.둘 다 방대한 수의 문자열(예: 사전에 포함된 단어)을 저장하는 데 적합합니다.
언급URL : https://stackoverflow.com/questions/716597/array-or-list-in-java-which-is-faster
'programing' 카테고리의 다른 글
| Mac OS X에 특정 JDK를 설치하는 방법 (0) | 2022.07.30 |
|---|---|
| Vuex 모듈 구조 (0) | 2022.07.30 |
| 루트가 갱신될 때마다 함수를 호출합니다. (0) | 2022.07.29 |
| 돛과 함께 vue.js를 사용하는 방법 js (0) | 2022.07.29 |
| v-for의 요소에 액세스하는 방법 (0) | 2022.07.29 |