作者H45 (!H45)
看板java
標題Re: [問題] 有沒有辦法取代或改善List的效率?
時間Wed May 23 12:37:13 2007
※ 引述《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