openlang
Алгоритмы и структуры данных

Нужен ли этой очереди сохранённый счётчик?

Проверено частично
Разговор продолжается 2 ↓Посмотреть источники ↓

Предположим, очередь представлена одним неизменяемым списком OCaml, а каждое обновление возвращает новую очередь. Вызывающий код многократно проверяет List.length items > 8. Мы выбираем между хранением точного количества и отдельной операцией проверки порога.

В (items, count) образец пары даёт имена двум компонентам. Инвариант count = List.length items должен сохраняться при каждом обновлении. Добавление увеличивает счётчик на один, успешное извлечение уменьшает на один, а попытка извлечь элемент из пустой очереди оставляет ноль. Любая функция создания очереди, принимающая оба компонента, тоже должна сохранять их связь.

Нынешний вопрос прямо выражается как List.compare_length_with items 8 > 0. Согласно документации OCaml 5.4, это сравнение может остановиться, выполнив не более заданного числа итераций.

Вы бы сейчас добавили поле со счётчиком или сохранили представление и дали операции проверки порога короткое публичное имя?

Разговор продолжается 2

Следуя доводам
  1. Ссылка на ответ

    Я бы сначала предоставил exceedsLimit queue limit с требованием неотрицательного предела. Тогда вызывающий код задаёт нужный ему вопрос без ещё одного хранимого компонента. Для этого представления реализация может использовать List.compare_length_with.

    Если вызывающий код решает, принимать ли работу, варианты WithinLimit и OverLimit могли бы сделать ветви понятнее. Булево значение тоже подойдёт, когда окружающий if уже объясняет различие. Не стоит добавлять варианты только ради обёртки над сравнением.

    Если точное количество понадобится в других местах, счётчик можно добавить тогда. Я бы поместил создание и обновления за одним интерфейсом, чтобы вызывающий код не мог независимо заменять items или count.