Чтение 100 000 данных с l oop и usort слишком медленный

Question

Приведенный ниже код соответствует решению, опубликованному здесь В алгоритме расписания Meetup для получения уникальной и доступной даты , но я не могу опубликовать его в качестве решения, пока оно не будет работать идеально.

Вопрос: Владелец стартапа ищет новых инвесторов, чтобы получить средства для своей компании. У каждого инвестора жесткий график, который владелец должен соблюдать. Учитывая графики дней, в которые инвесторы доступны, определите, сколько встреч владелец может запланировать. Обратите внимание, что владелец может проводить только одно собрание в день.

Расписания состоят из двух целочисленных массивов: firstDay и lastDay. Каждый элемент в массиве firstDay представляет первый день, в который инвестор доступен, и каждый элемент в lastDay представляет последний день, в который инвестор доступен, включая оба.

Пример:

firstDay = [1 , 2,3,3,3]

lastDay = [2,2,3,4,4]

Есть 5 инвесторов [I-0, I-1, I-2 , I-3, I-4] Инвестор I-0 доступен с 1 по 2 день включительно [1, 2] Инвестор I-1 доступен только на 2 день [2, 2]. Инвестор I-2 доступен только в день 3 [3, 3] Инвесторы I-3 и I-4 доступны только с 3-го дня до 4-го дня [3, 4] Владелец может встретить только 4 инвесторов из 5: I-0 в день 1, I-1 в день 2, I-2 в день 3 и I-3 в день 4. Графики c ниже показывают, что запланированные собрания отмечены зеленым, а заблокированные дни - серым.

Текущее решение Код работает с некоторыми тестовыми примерами, но не со всеми. Поэтому я подумал, может быть, нужно что-то улучшить или я все неправильно понял.

function countMeetings($firstDay, $lastDay) {
    $startToEndDate = [];
    $occupiedDate = [];

    // looping through 100,000 of data
    for($i=0; $i<count($firstDay); $i++){
        $startToEndDate[$i] = [$firstDay[$i], $lastDay[$i]];
    }

    // so $startToEndDate will be something like this
    // $startToEndDate = [ 
    //      0=>[1,3],
    //      1=>[2,2],
    //      2=>[1,1],
    //      3=>[2,3],
    //      4=>[2,3],
    // ];


    // sorting 100,000 of data
    usort($startToEndDate, function($a, $b){
        return ($a[1]-$a[0])  - ($b[1]- $b[0]);
    });


    // finally, looping through 100,000 of data again.
    foreach($startToEndDate as $date){
        list($start, $end) = $date;

        for($i=$start; $i<=$end; $i++){
            if(!isset($occupiedDate["day_$i"])){
                $occupiedDate["day_$i"] = "is used for $start-$end";
                break;
             }
        }
    }

    return count($occupiedDate);
}

// works with some small list
echo(countMeetings([1, 2, 1, 2, 2], [3, 2, 1, 3, 3]));

// but not with large list
//echo(countMeetings(
//    range(0, 100000),  
//    range(0, 100000)
//));

Сводка кода

• Я начал с добавления весь первый день и последний день в $ startToEndDate в виде массива, а затем отсортировал его.

• Затем я заполнил переменную $ busyDate уникальным днем.

Answer 1

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

for($i=0, $c=count($firstDay); $i<$c; $i++) {
   $startToEndDate[$i] = [$firstDay[$i], $lastDay[$i]];
}

и позже, когда вы используете ключ day_$i, вы можете подготовить его, чтобы не выполнять интерполяцию дважды.

foreach ($startToEndDate as $date) {
    list($start, $end) = $date;

    for ($i = $start; $i <= $end; $i++) {
        $key = 'day_' . $i;
        if (!isset($occupiedDate[$key])) {
            $occupiedDate[$key] = "is used for $start-$end";
            break;
        }
    }
}

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

Answer 2

Используйте foreach() для объединения связанных данных из двух массивов, так что вам не нужно count().

    $startToEndDate = [];
    foreach ($firstDays as $i => $firstDay) {  // notice that I am using plural variable names
        $dateRanges[] = [$firstDay, $lastDays[$i]];
    }

Я полагаю, что у вас есть ошибка c логики в вашем алгоритм сортировки. Вы не хотите упорядочивать строки на основе «разницы между начальной и конечной датой», вы на самом деле хотите упорядочить их по «первой дате AS C THEN конечной дате AS C» - оператор космического корабля делает это очень просто для кодирования.

usort($dateRanges, function($a, $b){
    // effectively: return [$a[0], $a[1]] <=> [$b[0], $b[1]];
    return $a <=> $b;
});

НО ЖДУ! Вам даже не нужна пользовательская функция сортировки! Доказательство: https://3v4l.org/iVI6H

sort($dateRanges);

Вам не нужно вызывать list(), существует современный способ объявить значения столбцов как отдельные переменные, если хотите. По правде говоря, вам не нужно объявлять переменные, вы можете просто ссылаться на элементы подмассива по их ключу (как я это делал в моем вызове usort()) - это просто означает, что вы увидите больше квадратных скобок в своем коде что некоторые разработчики могут найти более грязным.

$occupiedDate = [];
foreach ($dateRanges as [$start, $end]) {  // simpler listing syntax
    for ($i = $start; $i <= $end; ++$i) {
        if (!isset($occupiedDate["day_$i"])) {
            $occupiedDate["day_$i"] = "is used for {$start}-{$end}";
            break;
         }
    }
}