Java：これはO（n）でなければなりません。多分ArrayListの問題でしょうか？

Question

私はO（n）で実行すると信じているコードをいくつか持っていますが、時間を計ると多項式時間で実行されるようです。私は〜200000レコードを処理しようとしているので、私はヒープスペースを使い果たしていないので、サイズMAX_COUNTのブロックでそれを行いました。すなわち、処理フェーズでは、レコードのサイズが劇的に増加するいくつかのことが起こります。

私のコードから重要な部分をコピーしました。ここで何かが起こっているように思えますが、それは私が理解していないArrayListsと関係があります。

これは物事について最も賢明な方法ではないかもしれませんが、なぜ以前のものよりも各ブロックを処理するのに時間がかかるのか分かりません。つまり、各ブロックのサイズは5000（最初のブロックを除く）ですが、処理される最初のブロックは約5秒かかり、20番目のブロックは約25秒かかります。私は彼らにはすべて同じ時間がかかると期待しています。

// Maximum block size 
final int MAX_COUNT = 5000; 

// Total number of records in need of processing 
int n = records.size(); 

// the number of blocks to process 
int numBlocks = (n/MAX_COUNT) + 1; 
if (n % MAX_COUNT == 0) numBlocks--; 

// The number of records to process in the block. 
int numRecords; 
ArrayList<Record> recordBlock = null; 


// Iterate backwards through the blocks. 
for (int i = numBlocks; i > 0; i--) { 
    // Make sure we don't process too many records. 
    if ((i == 1 && numBlocks = 1 && n % MAX_COUNT != 0) || 
     (i == numBlocks && n % MAX_COUNT != 0)) 
     numRecords = n % MAX_COUNT; 
    else numRecords = MAX_COUNT; 

    recordBlock = new ArrayList<Record>(); 

    //EDIT: Fixed loop syntax (typo!) 
    for (int j = numRecords -1; j >= 0; j--) 
     recordBlock.add(records.remove(j)); 

    recordBlock = ThreadHelper.processRecords(recordBlock,true,true); 

    while (recordBlock.size() != 0) { 
     Record r = recordBlock.remove(recordBlock.size() -1); 
     // write 'r' to MySQL 
    } 

} 

Answer 1

すでに述べたように、実際のコードは何その後、場合、カッコなしの文に対して持っている場合

for (Record r: recordBlock) {// write 'r' to MySQL } 
recordBlock.clear(); 

Answer 2

forループがrecordBlockに追加されることに問題があります。私は間違っていないよ場合

for (int j = numRecords -1; j >= j--) 
    recordBlock.add(records.remove(j)); 

は

for (int j = numRecords -1; j >= 0; j--) 
    recordBlock.add(records.remove(j)); 

でなければなりません。

編集：

私が見つけた別の間違いは、if文にあります。

if ((i == 1 && numBlocks = 1 && n % MAX_COUNT != 0) || 
    (i == numBlocks && n % MAX_COUNT != 0)) 

if ((i == 1 && numBlocks == 1 && n % MAX_COUNT != 0) || 
    (i == numBlocks && n % MAX_COUNT != 0)) 

私はそれを簡素化示唆する必要があります：最初の条件は、単に特殊なケースですので、ときI = 1

Answer 3

このセクションでは、

if(i == numBlocks && n % MAX_COUNT != 0) 

for (int j = numRecords -1; j >= j--) 
     recordBlock.add(records.remove(j)); 

は、バッキングアレイがいっぱいになるたびにバッキングアレイをrecordBlockの背後に再割り当てします。むしろ、

recordBlock = new ArrayList<Record>(numRecords); 

と宣言してください。また、ループの構文が正しくありません。

Answer 4

によって

while (recordBlock.size() != 0) {    
    Record r = recordBlock.remove(recordBlock.size() -1);    
    // write 'r' to MySQL   
} 

を置き換え、さらに@mcfinnigan

recordBlock = new ArrayList<Record>(numRecords); 

で言及コードは実際にはそうでないかもしれないと思います。