Обновление игры записей в Java

Question

Мы игровые записи организованы следующим образом:

Игрок может играть в игру на разных уровнях и таблица рекордов хранится, чтобы показать список топ-10 игровые записи. Каждая запись игры в таблице рекордов содержит набор атрибутов, например имя игрока, общий результат и уровень, на котором был получен счет. Список игровых записей обычно сортируется от наивысшего до самого низкого, что указывает на рейтинг игроков от самого высокого до самого низкого уровня.

Мы должны реализовать

public GameRecord[] updateGameRecords(GameRecord[] oldRecords, GameRecord newRecord) 

следующим образом:

1. Если существует запись с таким же именем и тем же уровнем, как newRecord то обновить эту запись, если newRecord имеет больше и затем сортируем старые рекорды и возвращаем их. В противном случае перейдите к шагу 2

2. Если количество записей с таким же уровнем, что и newRecord являются менее 10, то вставить новую запись в oldRecords и сортировать его, а затем вернуть it.Otherwise, иди к шагу 3.

3. Если есть запись с более низким счетом на том же уровне, что и newRecord, то мы заменяем запись самой низкой оценкой этого уровня, так как количество записей для заданного уровня не может превышать 10, а затем мы сортируем и вернуть старые записи.

Это до сих пор мой код:

public GameRecord[] updateGameRecords(GameRecord[] oldRecords, GameRecord newRecord) { 
    int index = -1, r = 0; 
    boolean break_loop = false, same_name_level = false; 
    for (int i = 0; i < oldRecords.length; ++i) { 
     while (i < oldRecords.length && newRecord.getLevel() < oldRecords[i].getLevel()) { 
      ++i; 
      continue; 
     } 
     while (i < oldRecords.length && i < oldRecords.length && newRecord.getLevel() == oldRecords[i].getLevel()) { 
      if (r == 0) 
       index = i; 
      ++r;//r is number of records with same level 
      if (!break_loop && newRecord.getName().equals(oldRecords[i].getName())) { 
       same_name_level = true; 
       break_loop = true; 
       if (newRecord.getScore() > oldRecords[i].getScore()) { 
        oldRecords[i].setScore(newRecord.getScore()); 
       } 
      } 
      ++i; 
     } 
     if (break_loop == true) 
      break; 
    } 

    if (break_loop == true) { 
     Util.sort(oldRecords); 
     return oldRecords; 
    } 

    if (r > 0 && r < 10 && same_name_level == false) { 
     GameRecord[] temp = oldRecords.clone(); 
     oldRecords = new GameRecord[oldRecords.length + 1]; 
     System.arraycopy(temp, 0, oldRecords, 0, temp.length); 
     oldRecords[temp.length] = newRecord; 
     Util.sort(oldRecords); 
     return oldRecords; 
    } 

    if (r == 10) { 
     if (oldRecords[index + 9].getScore() < newRecord.getScore()) 
      oldRecords[index + 9].setScore(newRecord.getScore()); 
     Util.sort(oldRecords); 
     return oldRecords; 
    } 

    if (r == 0) { 
     GameRecord[] temp = oldRecords.clone(); 
     oldRecords = new GameRecord[oldRecords.length + 1]; 
     System.arraycopy(temp, 0, oldRecords, 0, temp.length); 
     oldRecords[temp.length] = newRecord; 
     Util.sort(oldRecords); 
     return oldRecords; 
    } else 
     return oldRecords; 
} 

Он работает нормально, но это линейное время сложность кода, что это занимает O (oldRecords.length) + время, затраченное Util. sort() функция, которая делает общее время работы нелинейным.

Можете ли вы предложить мне алгоритм линейного времени.

Answer 1

Чтобы сохранить отсортированный список при вставке или обновлении записи, нет необходимости снова сортировать весь список; достаточно переместить эту запись в нужное место. Более того, поскольку мы никогда не меняем уровень и только увеличиваем счет, мы знаем, что эта запись только движется вверх.

То есть, после того, как вы сделали вставку или обновлением записи, я бы вызвать следующий метод:

void moveToProperPlace(GameRecord[] records, int index) { 
    int newIndex = findCorrectIndex(records, index); 
    if (newIndex != index) { 
     GameRecord record = records[index]; 
     System.arrayCopy(records, newIndex, records, newIndex + 1, index - newIndex); 
     records[newIndex] = record; 
    } 
} 

int findCorrectIndex(records, index) { 
    int i = index; 
    do { 
     i--; 
    } while (i >= 0 && higher(records[index], records[i]); 
    return i + 1; 
} 

boolean higher(GameRecord x, GameRecord y) { 
    return x.getScore() > y.getScore() || (x.getScore() == y.getScore && x.getLevel() > y.getLevel()); 
} 

Поскольку данные отсортированы довольно часто, хорошо спроектированная реализация сортировки из стандартной библиотеки может на самом деле вернитесь к такой сортировке вставки, если она обнаруживает, что данные почти отсортированы, обеспечивая сортировку O (n) для входов, где в противном случае находится только постоянное число элементов, а O (n log n) в противном случае.В частности, реализованы java.util.Arrays.sort и java.util.Collections.sort. Если ваш Util.sort также реализован так, ваш алгоритм уже O (n).

В любом случае, если вы не регистрируете тысячи уровней и миллионов игр каждую секунду, разница между O (n) и O (n log n) вряд ли окажет заметное влияние на время выполнения вашей программы.

Answer 2

О (п) раствор:

static final int MAX = 10; 

static void bubbling(int[] recs) { 
    for (int i = recs.length - 1; i > 0; --i) 
     if (recs[i] > recs[i - 1]) { 
      int temp = recs[i]; 
      recs[i] = recs[i - 1]; 
      recs[i - 1] = temp; 
     } 
} 

static int[] updateRecord(int[] oldRecs, int newRec) { 
    int oldLen = oldRecs.length; 
    int newLen = oldLen < MAX ? oldLen + 1 : MAX; 
    int[] newRecs = new int[newLen]; 
    System.arraycopy(oldRecs, 0, newRecs, 0, oldLen); 
    if (newLen > oldLen || newRec >= newRecs[newLen - 1]) { 
     newRecs[newLen - 1] = newRec; 
     bubbling(newRecs); 
    } 
    return newRecs; 
} 

GameRecord изменяется на int упростить проблему.