выбор структуры данных

Закешируй ссылку на объект с максимальным икс на каждой итерации пересчёта. Тебе же вроде не сортировка нужна.

Да, просто сохраняй ссылку на максимальное во время пересчёта. Словарей с хэшсетами каких-то нагородил...

А если на очередной итерации объект с максимальным «икс» пересчитался и теперь у него там записан 0. Какой искать очередной максимальный на следующей итерации?

Есть такое, кучей называется: https://en.wikipedia.org/wiki/Heap_(data_structure)

Реализуй max, как часть итерации пересчёта.

Псевдокод:

def recompute_x_field(listOfObjects) {
   maxObject = listOfObjects[0];
   
   for (var obj in listOfObjects) {
        obj.x = foo(obj);
        if (obj.x >= maxObject.x) maxObject = obj;
   }

   return maxObject;
}

Если пересчитыватся не все объекты из listObObjects, то добавить в функцию второй параметр - текущий максимум и обновлять его только если максимум обновился.

То, что надо. Спасибо!

На каждой итерации искать максимум? Объектов в списке может быть десяток тысяч. Итераций, примерно, столько же. Это очень накладно будет - делать n^2 операций

Ты дурной? Поиск максимума - это либо n в массиве, либо log_2(n) если у тебя структура с деревом двоичного поиска. Ну или может использоваться комбинация из этих методов.

Если у тебя один вызов max - это n операций сравнения.

Если у тебя куча - log_2(n) операций сравнения. Но! У тебя пересчёт, потому нужно оценить кол-во операций пересчёта на каждой итерации, потому что каждый пересчёт - это удаление + вставка элемента в кучу (привет log_2(n) на операцию).

Что будет быстрее - сильно зависит от кол-ва операций пересчёта на каждой итерации.

M итераций. N объектов и операций на поиск максимума внутри каждой итерации (в вашем псевдокоде). В моей задаче M и N очень близкие. Умножьте одно на другое, если вам не сложно. А куча дает поиск максимума за O(1).

Окей, про m*n соглашусь. Так и будет.

Но у меня к тебе тогда вопрос - а сколько по твоему будет стоить перестройка кучи на каждой итерации?

По алгоритму перестройка будет требоваться не всей кучи, а не больше 5-10% на каждой итерации. Но надо, конечно, проверять, сколько это все будет стоить в настоящей реализации

O(log n) :)

Ой, я был не прав. Тебе не нужна куча, если есть метод пересчёта, который всё ломает. Час объясню. :)

Понимаешь какой ньюанс, ты не сделаешь алгоритма который будет требовать меньше операций сравнения чем у тебя операций пересчёта иск. Потому что на каждый пересчёт иск тебе нужен один инсерт в кучу (в старую, в новую - не важно, там будет сравнение для сортировки элементов в любом случае + операции смены адресов). Минимальная стоимость инсерта и поиска минимума (инвертируем числа и вместо максимума ищем минимум) в куче - O(1) и O(1), это, например, фиббоначиева куча.

Внезапно, то, что предложил я это ровно столько же операций сравнения. Вот только в моем варианте ёмкостная сложность O(1). А с кучей - O(n) и может плавать.

Поэтому куча это далеко не идеально тут.

Дерево бинарного поиска?

В общем, Norgat дело говорит. Пересчитывания всё ломает. Я их не так понял сначала. Не имеет смысл при поиске максимального значения делать сортировку всего, проще найти этот максимальный элемент и обновлять его, если во время пересчитывания появилось значение >= текущему максимуму, или линейно найти заново, если во время пересчитывания текущий максимум было утрачен (понизилось значение старого объекта с ним), а новых кандидатов не появилось.

В общем, тут иллюстрация алгоритма, как я бы сделал. Знания PHP для понимания, надеюсь, не нужны. «Хитрое» присваивание чисто для красоты и наглядности, я так обычно не пишу. :)

function recalculate(&$data, &$oldMax, &$oldKey)
{
    list($newKey, $newMax) = [$oldKey, $oldMax];

    foreach ($data as $k => &$v) {
        $v = mt_rand(1, 10000); #random number
        if (($v > $newMax) || ($v === $newMax) && ($newKey === $oldKey)) {
            list($newKey, $newMax) = [$k, $v];
        }
    }
    unset($v);

    if ($data[$newKey] < $newMax) { #max value lost
        $newMax = $data[$newKey];
        foreach ($data as $k => $v) {
            if ($newMax < $v) {
                list($newKey, $newMax) = [$k, $v];
            }
        }
    }

    list($oldMax, $oldKey)  = [$newMax, $newKey];
}

Поясни подробнее про

есть метод, который на каждой итерации эти «иксы» выборочно пересчитывает

Ну я и ламер! Ведь по любому надо хоть одно сравнение для каждого элемента делать. Следовательно, оптимальный поиск максимума - в лоб, линейный, когда он, этот максимум, нужен. Вот это: Norgat (03.08.2017 20:34:00) - оптимально. Ровно одно необходимое сравнение для каждого элемента, и по лучше в общем случае не напишешь, разве что сам метод перечитывания как нибудь позволяет игнорировать некоторые объекты целиком, не проверяя ихние значения.

«Линейный поиск - оптимально». Т.е. n^2 для n>10k. Не хотел бы пользоваться вашим и Norgat'овским софтом. Но всем спасибо, я все-таки предпочел выбрать алгоритм за n*logn

Так на чём остановился?

Наивный албанский мальчик. Не будет у тебя там n*logn. Когда поймёшь почему - возвращайся и используй линейный поиск))

P.S. Ещё раз, может дойдёт - учти сколько тебе будет стоить перестройка кучи на каждой итерации (подсказываю, это будет дороже линейного поиска).

Ну так очевидно же, что вариант с кучей немного не катит, так как перестройка кучи будет занимать дофига времени.

Я это ему объяснить пытаюсь, а он не верит ни в какую вроде как :)

M итераций. N объектов и операций на поиск максимума внутри каждой итерации

Только я вижу тут сильно замаскированную сортировку пузырьком? :D