Подробней о last

Поскольку в заметке про last отметились только профильные специалисты (в Телеграме), считаю, нужна его подробная версия. Я и сам понимаю, что для таких огрызков служит Твиттер, но чего нет — того нет.

Итак, дело вот в чем. Коллега спрашивает у Chat GPT, насколько дорого получить последний элемент вектора функцией last в Кложе. На это чат говорит — все тип-топ, у вектора доступ к последнему элементу работает за O(1).

Все бы ничего, но в ответе напутаны правда и ложь, и в целом он не верный. Чтобы в этом убедиться, откроем исходный код функции last:

(dеf
 ^{:doc "Return the last item in coll, in linear time"}
 last (fn ^:static last [s]
        (if (next s)
          (recur (next s))
          (first s))))

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

В коде нет проверок на тип коллекции, например, отдельно для вектора или списка. Все очень просто и линейно.

Наконец, докстринг функции как бы говорит нам: вернуть последний элемент коллекции за линейное время. Линейное, Карл, то есть такое, что растет с числом элементов, то есть O(N).

Поэтому буквальный ответ на вопрос таков: нет, функция last вернет последний элемент вектора за O(N) шагов. Что не подходит для больших векторов.

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

Можно предъявить Ричу Хикки: надо было сделать интерфейс Lastable с методом getLast. Обычные коллекции бегут с головы, а вектор берет с конца. Все это упаковано в last, который переключает на нужную логику. Все довольны и смеются. Но имеем то, что имеем, тем более что я согласен с текущим положением дел. Из всех коллекций только вектор может вернуть последний элемент. Остальным коллекциям это не положено по идеологическим причинам.

Скорее всего, чат прочитал вопросы на StackOverflow и слепил некую компиляцию. Вроде бы да, но вроде бы нет. В этом и состоит вред: чат выдает что-то, очень похожее на истину. Выглядит настолько правдоподобно, что принимаешь за чистую монету. Но если проверить, то окажется, что не в карты, а в нарды, и не корову, а машину, и не выиграл, и проиграл.

Поэтому я не пользуюсь чатом и аналогами, я в них даже не зарегистрирован. И вам советую прибегать к ним реже.