[問題] 有沒有辦法取代或改善List的效率?

[M***@ptt.cc]

目前的程式需要處理1000K以上的node,
這部份的運作程式如下

ArrayList<Integer> originalRandomArray = new ArrayList<Integer>();
protected ArrayList<Integer> randomArray = new ArrayList<Integer>();

public void GenerateRandomArray( int nodeNumber )
{
originalRandomArray.clear(); // initialize;

for( int i = 0 ; i < nodeNumber; i++ )
{
originalRandomArray.add( i );
}

Collections.shuffle( originalRandomArray );

randomArray.clear(); // initialize
for( int i = 0 ; i < originalRandomArray.size() ; i++ )
{
if( i < nodeNumber * CHANCE_MOVE )
{
randomArray.add( originalRandomArray.get( i ) );
}
}
}

這部份code的目的是將originalRandomArray裡取出來的CHANCE_MOVE%個nodes存到
randomArray去. 但整個程式在nodeNumber = 1000000時, 處理時間多了2小時
(原本是1小時, 但是是用簡單的方法做出一個不完全的random).
請問有辦法改進效率嗎? 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.180.59
※ 編輯: Mewra 來自: 123.193.180.59 (05/22 18:31)

[小安]

※ 引述《Mewra ()》之銘言：
: 目前的程式需要處理1000K以上的node,
: 這部份的運作程式如下
: ArrayList<Integer> originalRandomArray = new ArrayList<Integer>();
: protected ArrayList<Integer> randomArray = new ArrayList<Integer>();
: 這部份code的目的是將originalRandomArray裡取出來的CHANCE_MOVE%個nodes存到
: randomArray去. 但整個程式在nodeNumber = 1000000時, 處理時間多了2小時
: (原本是1小時, 但是是用簡單的方法做出一個不完全的random).
: 請問有辦法改進效率嗎? 謝謝

其實 ArrayList 內部是透過陣列實作， (預設長度是 10)
而當陣列大小不夠用時，
就會再重新產生一個長度為原先 1.5 倍的陣列，
並且將陣列中所有元素複製過去。

所以我的想法是...
如果能夠一開始就指定適當的 initialCapacity，
也許就能夠省去一大堆不必要的時間。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.71.204

[M***@ptt.cc]

※ 引述《tkcn (小安)》之銘言：
: ※ 引述《Mewra ()》之銘言：
: : 目前的程式需要處理1000K以上的node,
: : 這部份的運作程式如下
: : ArrayList<Integer> originalRandomArray = new ArrayList<Integer>();
: : protected ArrayList<Integer> randomArray = new ArrayList<Integer>();
: : 這部份code的目的是將originalRandomArray裡取出來的CHANCE_MOVE%個nodes存到
: : randomArray去. 但整個程式在nodeNumber = 1000000時, 處理時間多了2小時
: : (原本是1小時, 但是是用簡單的方法做出一個不完全的random).
: : 請問有辦法改進效率嗎? 謝謝
: 其實 ArrayList 內部是透過陣列實作， (預設長度是 10)
: 而當陣列大小不夠用時，
: 就會再重新產生一個長度為原先 1.5 倍的陣列，
: 並且將陣列中所有元素複製過去。
: 所以我的想法是...
: 如果能夠一開始就指定適當的 initialCapacity，
: 也許就能夠省去一大堆不必要的時間。

謝謝指教
我等下來試試看直接指定大小來處理.
還有shuffle雖好用, 但我剛發現它也增加了25%的處理時間
待我稍微改進後再來跟大家報告


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.180.59

[我開始困惑了]

※ 引述《Mewra ()》之銘言：
: ※ 引述《tkcn (小安)》之銘言：
: : 其實 ArrayList 內部是透過陣列實作， (預設長度是 10)
: : 而當陣列大小不夠用時，
: : 就會再重新產生一個長度為原先 1.5 倍的陣列，
: : 並且將陣列中所有元素複製過去。
: : 所以我的想法是...
: : 如果能夠一開始就指定適當的 initialCapacity，
: : 也許就能夠省去一大堆不必要的時間。
: 謝謝指教
: 我等下來試試看直接指定大小來處理.
: 還有shuffle雖好用, 但我剛發現它也增加了25%的處理時間
: 待我稍微改進後再來跟大家報告

後面這一段
if( i < nodeNumber * CHANCE_MOVE ) {
randomArray.add( originalRandomArray.get( i ) );
}

不知道可不可以先把randomArray處理完畢
然後再透過system.arraycopy處理

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.107.161

[小安]

※ 引述《Mewra ()》之銘言：
: for( int i = 0 ; i < originalRandomArray.size() ; i++ )
: {
: if( i < nodeNumber * CHANCE_MOVE )
: {
: randomArray.add( originalRandomArray.get( i ) );
: }
: }
: }

剛剛才仔細看了程式碼，

如果說 nodeNumber 很大，
而 CHANCE_MOVE 不怎麼大的話 (意即最後所需的亂數數量)

那麼我會建議換另一種寫法，
直接產生亂數，並且檢查這個亂數是不是已經產生過了
重複的話就重新產生一次

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.71.204

[勁過呂布]

※ 引述《Mewra ()》之銘言：
: Collections.shuffle( originalRandomArray );
: randomArray.clear(); // initialize
: for( int i = 0 ; i < originalRandomArray.size() ; i++ )
: {
: if( i < nodeNumber * CHANCE_MOVE )
: {
: randomArray.add( originalRandomArray.get( i ) );
: }
: }

這一部份的 codes... 可以改成為:

Random randMachine = new Random(System.currentTimeMillis());
randomArray.clear();

for (int i=0; i<nodeNumber * CHANCE_MOVE; i++) {
if (i >= originalRandomArray.size()) break; // prevent overflow
int ranInt = randMachine.nextInt(originalRandomArray.size() - i) + i;

int ranTarget = originalRandomArray.get(ranInt);
// get the number in pos [ranInt]

int curPos = originalRandomArray.get(i);
// get the number in pos [i];

originalRandomArray.remove(ranInt);
if (ranInt != i) originalRandomArray.remove(i);
originalRandomArray.add(i, ranTarget);
if (ranInt != i) originalRandomArray.add(ranInt, curPos);
// swap two numbers in pos ranInt and i

randomArray.add(ranTarget);
// add the random number to the result
}


這就做到了 random 抽出 nodeNumber * CHANCE_MOVE 個數的目的，而且是 O(n)

--
《為了要得到真相，就要向原 PO 伸圖》

那就是伸圖魔人的沒圖沒真相原則，那時我們堅信那就是逼逼死的真實

 靠么，圖咧？


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.8.130.225

[!H45]

※ 引述《superlubu (勁過呂布)》之銘言：
: ※ 引述《Mewra ()》之銘言：
: : Collections.shuffle( originalRandomArray );
: : randomArray.clear(); // initialize
: : for( int i = 0 ; i < originalRandomArray.size() ; i++ )
: : {
: : if( i < nodeNumber * CHANCE_MOVE )
: : {
: : randomArray.add( originalRandomArray.get( i ) );
: : }
: : }

經測試，你的 Code 運作速度比原程式碼還慢

nodeNumber = 100,000
CHANCE_MOVE = 0.05

原 PO 的版本： 217ms
你的版本： 3000ms

請問是不是哪裡有漏掉了呢？
(文末附上我的測試碼)

: 這一部份的 codes... 可以改成為:
: Random randMachine = new Random(System.currentTimeMillis());
: randomArray.clear();
: for (int i=0; i<nodeNumber * CHANCE_MOVE; i++) {
: if (i >= originalRandomArray.size()) break; // prevent overflow
: int ranInt = randMachine.nextInt(originalRandomArray.size() - i) + i;
: int ranTarget = originalRandomArray.get(ranInt);
: // get the number in pos [ranInt]
: int curPos = originalRandomArray.get(i);
: // get the number in pos [i];
: originalRandomArray.remove(ranInt);
: if (ranInt != i) originalRandomArray.remove(i);
: originalRandomArray.add(i, ranTarget);
: if (ranInt != i) originalRandomArray.add(ranInt, curPos);
: // swap two numbers in pos ranInt and i
: randomArray.add(ranTarget);
: // add the random number to the result
: }
: 這就做到了 random 抽出 nodeNumber * CHANCE_MOVE 個數的目的，而且是 O(n)
: 剛測試過... 若是 nodeNumber = 1000000, CHANCE_MOVE = 0.05
: 時間是五分三十八秒 XD

public void test() {
long startTime;
long endTime;
startTime = System.currentTimeMillis();
// GenerateRandomArray1(100000);
GenerateRandomArray2(100000);
endTime = System.currentTimeMillis();
System.out.println("Cost time: " + (endTime - startTime));
}

private final static double CHANCE_MOVE = 0.05;

ArrayList<Integer> originalRandomArray = new ArrayList<Integer>();

protected ArrayList<Integer> randomArray = new ArrayList<Integer>();

public void GenerateRandomArray1(int nodeNumber) {
originalRandomArray.clear(); // initialize;

for (int i = 0; i < nodeNumber; i++) {
originalRandomArray.add(i);
}

Collections.shuffle(originalRandomArray);

randomArray.clear(); // initialize
for (int i = 0; i < originalRandomArray.size(); i++) {
if (i < nodeNumber * CHANCE_MOVE) {
randomArray.add(originalRandomArray.get(i));
}
}
}

public void GenerateRandomArray2(int nodeNumber) {
originalRandomArray.clear(); // initialize;

for (int i = 0; i < nodeNumber; i++) {
originalRandomArray.add(i);
}

Random randMachine = new Random(System.currentTimeMillis());
randomArray.clear();

for (int i = 0; i < nodeNumber * CHANCE_MOVE; i++) {
if (i >= originalRandomArray.size())
break; // prevent overflow
int ranInt = randMachine.nextInt(originalRandomArray.size() - i)
+ i;

int ranTarget = originalRandomArray.get(ranInt);
// get the number in pos [ranInt]

int curPos = originalRandomArray.get(i);
// get the number in pos [i];

originalRandomArray.remove(ranInt);
if (ranInt != i)
originalRandomArray.remove(i);
originalRandomArray.add(i, ranTarget);
if (ranInt != i)
originalRandomArray.add(ranInt, curPos);
// swap two numbers in pos ranInt and i

randomArray.add(ranTarget);
// add the random number to the result
}
}

呼叫 test() 即可。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.85

[勁過呂布]

※ 引述《H45 (!H45)》之銘言：
: ※ 引述《superlubu (勁過呂布)》之銘言：
: 經測試，你的 Code 運作速度比原程式碼還慢
: nodeNumber = 100,000
: CHANCE_MOVE = 0.05
: 原 PO 的版本： 217ms
: 你的版本： 3000ms
: 請問是不是哪裡有漏掉了呢？
: (文末附上我的測試碼)

Orz... 我忘了 ArrayList 頻繁的 remove 和 add 動作所需的時間要很多 Orz
該用 set(index, element) 才對，只要把 swapping 那幾句換成:

originalRandomArray.set(i, ranInt);
originalRandomArray.set(ranInt, curPos);
// swap two numbers in pos ranInt and i

就可以把時間縮短為 78ms (原 PO 版本 109ms)


題外話: 若換成用 int[] 來作同一個問題，時間只用 19ms 囧rz


謝謝 H45 板友的覆查 <(_ _)>


注: 這個 algorithm 若 CHANCE_MOVE >= 0.5 時就會比原 PO 的方法還要慢了
對不起 <(_ _)>

--
勁過呂布的勁過相薄...

http://www.wretch.cc/album/superlubu

亂七八糟的，不好意思 m(_ _)m

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.8.130.225
※ 編輯: superlubu 來自: 147.8.130.225 (05/23 12:55)
※ 編輯: superlubu 來自: 147.8.130.225 (05/23 13:05)

[!H45]

※ 引述《superlubu (勁過呂布)》之銘言：
: ※ 引述《H45 (!H45)》之銘言：
: : 經測試，你的 Code 運作速度比原程式碼還慢
: : nodeNumber = 100,000
: : CHANCE_MOVE = 0.05
: : 原 PO 的版本： 217ms
: : 你的版本： 3000ms
: : 請問是不是哪裡有漏掉了呢？
: : (文末附上我的測試碼)
: Orz... 我忘了 ArrayList 頻繁的 remove 和 add 動作所需的時間要很多 Orz
: 該用 set(index, element) 才對，只要把 swapping 那幾句換成:
: originalRandomArray.set(i, ranInt);
: originalRandomArray.set(ranInt, curPos);
: // swap two numbers in pos ranInt and i
: 就可以把時間縮短為 78ms (原 PO 版本 109ms)
: 題外話: 若換成用 int[] 來作同一個問題，時間只用 19ms 囧rz
: 謝謝 H45 板友的覆查 <(_ _)>

嗯，沒錯，這樣一改確實快多了！

但我有其他的疑問 ._./
既然只是做出一個很大的隨機 Array
為何不使用 Random 給值就好了呢？ 這樣快很多吧！

雖然會有循環數列的問題 (每 2^32 循環一次, 而且有規律...)
但我認為可以交由 setSeed 來解決
也就是每隔一段時間就換一個 seed 來產生亂數
如此一來，循環數列就不容易存在了(?

以下是我修改的 Code, 雖然效能很棒，但是不知道夠不夠亂？？
(我已經捨棄 originalRandomArray 了)

public void GenerateRandomArray(int nodeNumber) {
Random random = new Random();

// 每隔 1000 個數列就換一個 seed
int threshold = 1000;

// 計算大迴圈要跑的次數
int loopCount = (int) (nodeNumber / threshold * CHANCE_MOVE);

randomArray.clear();

// 開始填亂數到 randomArray
for (int j = 0; j < loopCount; j++) {
random.setSeed(System.currentTimeMillis());
for (int i = 0; i < threshold; i++) {
randomArray.add(random.nextInt());
}
}

// 把剩下的部分也補完
loopCount = (int) (nodeNumber * CHANCE_MOVE % threshold);
random.setSeed(System.currentTimeMillis());
for (int i = 0; i < loopCount; i++) {
randomArray.add(random.nextInt());
}
}

nodeNumber = 100,000
CHANCE_MOVE = 0.05
Cost Time: 21 (比前兩個方法都快)

各位板友覺得如何呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.85

[小安]

※ 引述《H45 (!H45)》之銘言：
: nodeNumber = 100,000
: CHANCE_MOVE = 0.05
: Cost Time: 21 (比前兩個方法都快)
: 各位板友覺得如何呢？

應該還是要檢查一下數字有沒有重複吧


另外

System.out.println(randomArray.size());
System.out.println(new HashSet(randomArray).size());

我用這兩行去檢查，發現數字分別是 5000, 1000

主要的原因是跑完一千個亂數，
System.currentTimeMillis() 還來不及改變

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.71.204

[挑戰]

看到原PO的程式碼，不曉得亂數範圍是否需落在0~nodeNumber裡面。
所以就插一腳寫了個亂數有落在範圍內，且不重複的版本。
我也捨棄了originalRandomArray，有寫錯不要鞭我...囧

private List<Integer> randomArray;
private void GenerateRandomArray(int node , double chance)
{
final int size = (int)(node * chance);
Random random = new Random();
HashSet<Integer> set = new HashSet<Integer>(size , 1.0f);
while(set.size() < size)
for(int i = size - set.size() ; i >= 0 ; --i)
set.add(random.nextInt(node));
randomArray = new ArrayList<Integer>(set);
Collections.shuffle(randomArray);
}

node = 1,000,000
chance = 0.99
time = 10,250 ms

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.229.166.204