Нахождение k-го последнего элемента односвязного списка: объяснение ответа

Question

Когда вам нужно найти k-й последний элемент списка с одиночными ссылками, обычный наивный подход - выполнить два прохода.Первый, чтобы найти длину списка и второй, чтобы перебрать до элемента (length-k)th.

В то время как оптимизированная версия использует два указателя:

• p1, ссылаясь на заголовок списка
• p2, являющийся k th элементамивпереди p1

Это позволяет нам возвращать элемент p1, когда p2 достигает конца списка.Я не понимаю, почему второй подход быстрее первого, когда в обоих случаях у нас есть один указатель, повторяющийся по всему списку, а другой - до элемента (length-k)th.

Это из-за оптимизации кэша?

Спасибо.

Answer 1

Если вы оставите p2 точно k элементов позади p1, то это не очень поможет, так как вам придется делать одинаковое количество обходов все вместе.

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

Когда вы идете по списку, допустим, вы помните указатель на каждой (к / м)-й позиции, для некоторых m . Вам нужно только запомнить последние m + 1 из этих указателей. Затем, когда вы доберетесь до конца списка, вместо повторения с самого начала, начните с самого старого указателя, который вы запомнили. Он будет между k и k + (k / m) элементами за концом, поэтому вам нужно только продвинуть его вперед максимум на k / m позиций.

Answer 2

Рассмотрим неравномерное время доступа к памяти и односвязный список длины n :
- в подходе с подсчетом итераций доступ к одному и тому же узлу будет n доступов отдельно
- при подходе с запаздывающим указателем доступ к одному и тому же узлу будет k доступов отдельно
С кешем LRU (/ с каждым кешем LRU уровень ) первый с большей вероятностью будет вызывать пропускную способность , чем последний.