Java: это должно быть O (n), может быть проблема с ArrayList? - PullRequest
Новая
       15

Java: это должно быть O (n), может быть проблема с ArrayList?

1 голос
/ 10 сентября 2011

У меня есть некоторый код, который, я полагаю, запускается в O (n), однако, когда я его измеряю, кажется, что он выполняется за полиномиальное время.Я пытаюсь обработать ~ 200 000 записей, поэтому я сделал это блоками размером 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
    }

 }

Ответы [ 4 ]

3 голосов
/ 10 сентября 2011

Этот раздел 

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

будет перераспределять резервный массив за recordBlock каждый раз, когда резервный массив заполнен.Вместо этого объявите его как 

recordBlock = new ArrayList<Record>(numRecords);

Кроме того, синтаксис цикла неверен.

1 голос
/ 10 сентября 2011

Как уже упоминалось @ mcfinnigan 

recordBlock = new ArrayList<Record>(numRecords);

Кроме того, замените 

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

на 

for (Record r: recordBlock) {// write 'r' to MySQL }
recordBlock.clear();
1 голос
/ 10 сентября 2011

Возникла проблема с добавлением цикла for в блок записи. 

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) )

Могу предложить упростить его до: 

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

, поскольку первое условие - это особый случай, когда i = 1.

0 голосов
/ 10 сентября 2011

если в реальном коде есть операторы if и for без фигурных скобок, то, по вашему мнению, код может на самом деле не быть тем, что он делает.

...