Java: This should be O(n), maybe an ArrayList problem?

I have some code that I believe to run in O(n), however when I time it, it seems to run in polynomial time. I'm trying to process ~200,000 records, so I did it in blocks of size MAX_COUNT so I wouldn't run out of heap space. That is, during the processing phase, a few things take place that make the records increase dramatically in size.

I copied in the important parts from my code. I feel like something is going on here that has to do with ArrayLists that I just don't understand.

This might not be the smartest way to go about things, but I don't see why it's taking longer to process each block than the previous. That is, each bock is size 5000 (except the 开发者_JAVA百科first block), but the 1st block processed takes ~5seconds, and the 20th block processed takes ~25seconds. I would expect them to all take the same amount of time.

// 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
    }

 }

This section

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

will reallocate the backing array behind recordBlock every time the backing array is filled. Rather declare it as

recordBlock = new ArrayList<Record>(numRecords);

Also, the loop syntax is incorrect.

As already mentioned by @mcfinnigan

recordBlock = new ArrayList<Record>(numRecords); 

In addition, replace

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

by

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

There is a problem with the for loop adding to the recordBlock.

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

should be

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

If I am not mistaken.

Edit:

Another mistake I found was in your if statement.

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

should be

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

Might I suggest simplifying it to:

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

since the first condition is just a special case when i = 1.

if the real code has if and for statements without braces then what you think the code does may not actually be what it does.