Более эффективный способ написать этот алгоритм?

Ответ 1

• Используйте std::vector, если размер не очень большой.

Указатели всегда имеют стоимость, связанную с ними из-за косвенности. Поиск адреса и доступ к нему в памяти не могут быть оптимизированы компилятором и, следовательно, будут связаны с затратами на доступ к памяти. Доступ к памяти часто является узким местом для производительности в системах, поэтому лучше всего пытаться помещать вещи рядом друг с другом в память и пытаться структурировать ваши программы, чтобы вы меньше всего получали доступ к памяти.

2. Используйте систему баз данных, например SQL, если данные становятся чрезвычайно большими.

С другой стороны, мы можем отказаться от всей грязной работы и использовать установленную библиотеку или программу базы данных. Что-то вроде MySQL может легко управлять большим количеством данных с отличным языком программирования для доступа и управления им. Некоторые базы данных, такие как PostgreSQL, могут масштабироваться для больших наборов данных. Знакомство с ним также может быть весьма полезным. Например, даже некоторые мобильные приложения могут использовать MySQL для Android.

3. Используйте современный синтаксис итерации цикла for С++ 11 или выше.

Текущий синтаксис цикла for довольно непрозрачен и может иметь много крутизны. С++ 11 представил более чистый синтаксис цикла for для итерации в стандартных библиотечных контейнерах, таких как map или vector. Использовать: for(auto it : vector_name). Если вам нужно изменить каждый из них, используйте ссылочный классификатор для it - итератора.

4. Используйте синтаксис pre-increment для возможного минимального ускорения.

++i и i++ немного отличаются. ++i просто изменяет объект, где он появляется в выражении, прежде чем он продолжает его оценивать. i++ создает копию объекта, возвращает его и увеличивает оригинал. Создание копии значения или объекта имеет стоимость в С++, поэтому избегать этого может быть полезно в некоторых случаях, и это хорошо согласуется с этим в любом случае.

5. Перейдите на const &. Не путем обычной ссылки.

Аргументы функции передаются по значению по умолчанию в С++. Это означает, что С++ просто копирует объект. Однако, когда мутации применяются повторно к объекту, например, используя функцию для изменения значения целого числа во времени, вы можете пройти по ссылке. Ссылки в основном передают "реальный" объект, что означает, что любые изменения, которые вы делаете для ссылки, выполняются на "реальном" объекте.

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

6. Используйте std::unique_ptr или std::shared_ptr.

Умные указатели также являются отличной функцией, которая была введена с С++ 11 и включает указатели, которые автоматически освобождают себя, привязывая их время жизни к области видимости. Другими словами, нет необходимости использовать new или delete - просто создайте указатели, и вам не нужно будет отслеживать, когда выпустить память. Это может усложниться в определенных ситуациях, но в целом использование интеллектуальных указателей ведет к лучшей безопасности и меньшему изменению проблем управления памятью, поэтому они были введены в стандартную библиотеку в первую очередь.

Ответ 2

Есть несколько вопросов, на которые я могу ответить. Первое: может ли этот алгоритм быть более эффективным? И другое: может ли моя реализация алгоритма в С++ быть более эффективной?

К первому вопросу, я бы ответил нет. Основываясь на проблеме, это звучит так, как будто у вас нет дополнительной информации, которая позволила бы вам сделать лучше, чем O (n ^ 2).

Как упоминалось в комментариях, вы можете перебирать каждого человека и сортировать свои книги по срокам. На практике это может сэкономить некоторое время, но в теории книжный поиск все равно будет линейным временем O (n). Кроме того, вы добавляете накладные расходы на сортировку, делая свой алгоритм сейчас O (mnlog (n)), где m - количество посетителей, а n - количество книг. Если вы знаете, что у вас мало покровителей со многими книгами, сортировка может быть полезной. Если у вас будет много покровителей с небольшим количеством книг, это будет гораздо менее полезно.

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

currentDate++;
vector<Book*> ptr = members.at(i)->getCheckedOutBooks();
for(....)

Еще одна оптимизация, которая могла бы быть большой капитальный ремонт, заключалась бы в том, чтобы удалить библиотеку Vector. Вектор в С++ имеет возможность изменять размер "на лету", а также другие ненужные накладные расходы (для вашей задачи). Просто использование массива будет более эффективным с точки зрения памяти, хотя это эквивалентно время.

Вы упомянули о том, что находитесь в вашем первом семестре, поэтому вы, вероятно, еще не были знакомы с нотой Big O.

Ответ 3

если это единственная операция, которую вы оптимизируете, то сохраняйте вектор tuple <int, Book *, Patron * >, отсортированный по int, представляющий дату выполнения evey, извлеченного из книги Затем просто повторяйте до тех пор, пока дата выполнения не будет больше, чем текущая дата, налагающая штрафы на соответствующего Patron.

Ответ 4

Если у вас есть n извлеченные книги, m из которых просрочены, ваш алгоритм занимает O(n) время, чтобы добавить штрафы. Это связано с тем, что ваша структура данных хранит информацию, подобную этой

member -> list(checked out books)
book -> check-out length // presumably the due date for returning the book

Если в дополнение к вашей коллекции members вы также сохраняете следующую информацию:

check-out length -> list(checked out books with that due date)
book -> member who checked it out

то вы можете использовать отсортированное дерево, которое хранит все выписанные книги в установленный срок, чтобы просмотреть все просроченные книги в O(log n). Таким образом, общее асимптотическое время выполнения вашего алгоритма уменьшится с O(n) до O(log n + m).

Ответ 5

Возможно, вы захотите заменить vector контейнером std::map. Карты хранятся в виде отсортированных деревьев. Если вы определяете функцию компаратора, сравнивающую длину проверки (или, скорее, "истекшую дату" ), вам не нужно каждый раз сканировать весь список.

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

Это сложнее, потому что теперь добавление/удаление книг для каждого участника (или даже итерация по всем книгам, принадлежащим членам) сложнее и может потребовать сохранения вектора указателей для каждого пользователя в качестве вашего текущего подхода (в дополнение к карта глобальной книги).

Ответ 6

Прошло некоторое время с тех пор, как я использовал С++, но почти всегда стандартные библиотеки будут быстрее, чем ваша собственная реализация. Для справки ознакомьтесь со стандартными функциями, которые связаны с std::vector (этот сайт чрезвычайно полезен).

Возможно, вы скроете ptr.size() с помощью какой-либо другой логики фильтрации, чтобы вам не пришлось перебирать людей, у которых нет поздних книг (возможно, какая-то сортировка по книгам и сроки их выполнения?)

Ответ 7

Прямо сейчас вы исправляете штрафы в O (n) (n - getCheckOutLength(). size()), но вы можете сделать это в O (log (n)), поскольку вам нужно просто количество поздних книг, а не их объекты для штрафа, если у вас есть это число, то вы умножаете его на .01 и используете одну функцию штрафа для выполнения всего этого.

Итак, вот что я предлагаю:
Если вы сохраняете getCheckedOutBooks(), отсортированные по их getCheckOutLength() в векторе, то вы можете найти, какие даты больше, чем curDate, путем поиска std:: upper_bound в векторе, который дает вам первый элемент, который больше, чем currentDate, поэтому из этого индекса элемента в конец вектора указывается количество книг, которые должны быть оштрафованы, вот код:

int checkedDateComparator(Patron & leftHand, Patron & rightHand){
    return leftHand.getCheckedOutLength() < rightHand.getCheckOutLength();  
}
bool operator==(Patron & a, Patron & b){
    return a.getCheckedOutLength() < b.getCheckOutLength();
}
void Library::incrementCurrentDate()
{
    currentDate++;

    for (int i = 0; i < members.size(); i++)
    {
        vector<Book*> ptr = members.at(i)->getCheckedOutBooks();
        Book dummy; //dummy used for find the fines 
        dummy.setCheckedOutLength(currentDate);
        int overdue = ptr.end() - upper_bound(ptr.begin(), ptr.end(), dummmy, checkedDateComparator);
        members.at(i)->amendFine(overdue* .01);
   }
} 

Ответ 8

Давайте сделаем шаг назад и рассмотрим требования. Когда вы идете в библиотеку и имеете некоторые, возможно, поздние выписанные книги, вы, вероятно, спрашиваете библиотекаря, что вы должны. Библиотекарь просматривает вашу учетную запись и говорит вам. Именно в этот момент вы должны рассчитывать плату. То, что вы сейчас делаете, пересчитывает комиссионные каждую ночь (я предполагаю). Это часть, которая неэффективна.

Пусть вместо этого используется прецедент:

• Библиотекарь пытается проверить книги покровителей
• Система рассчитывает гонорары
• Патрон выплачивает любые неуплаченные взносы.
• Библиотекарь проверяет книги

Соответствующей частью вашего вопроса будет шаг № 2. Здесь псевдокод:

float CalculateFees(Patron patron)
{
    float result = 0;
    foreach(checkedOutBook in patron.GetCheckedOutBooks())
    {
        result += CalculateFee(checkedOutBook.CheckOutDate(), today);
    }
    return result;
}

float CalculateFee(Date checkOutDate, Date today)
{
    return (today.Day() - checkOutDate.Day()) * 0.10;
}

Весь прецедент может быть таким же простым, как:

void AttemptCheckout(Patron patron, BookList books)
{
    float fees = CalculateFees(patron);
    if(fees == 0 || (fees > 0 && PatronPaysFees(patron, fees)))
    {
        Checkout(patron, books);
    }
    else
    {
        RejectCheckout(patron);
    }
}

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