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

[H45 (!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