Нахождение 3-го элемента от конца связного списка в Java

[alexxisr]

вот да — чем это отличается от «посчитать кол-во элементов в списке, потом дойти до нужного»? кол-во операций такое же получается.

[niamster]

Локальностью данных. Если данные не локальные или не помещаются в кэш первого уровня.
Хотя если честно все подобные задачи имеют академический характер в 80% случаях.

[poxvuibr]

Локальностью данных

При чём тут локальность данных? Это же linked list.

[niamster]

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

[grossws]

Если мы говорим про Java, то за упоминание в одном предложении локальности и LinkedListа в приличном обществе бьют канделябром. У вас объекты, составляющие linked list валяются в разных кусках tlab'ов, а какой локальности речь?! Также рекомендую написать парочку микробенчмарков и сравнить производительность ArrayList и LinkedList.

[poxvuibr]

У вас объекты, составляющие linked list валяются в разных кусках tlab'ов, а какой локальности речь?!

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

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

[niamster]

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

grossws, я не зацикливался на привязке Java/LinkedList, а постарался абстрагироваться и представить какие еще бывают случаи применения данного алгоритма.
Мне кажется, что если стоит такая строгая задача (Java/LinkedList), то почему бы не изменить условия и не использовать другую структуру данных с помощью которой алгоритм реализуется проще. Я понимаю, что есть спортивный интерес, а кто этот код потом поддерживать будет?

У вас объекты, составляющие linked list валяются в разных кусках tlab'ов, а какой локальности речь?!

Главное чтоб cache line тэги не конфликтовали, а там пусть лежат где угодно.

[igormich88]

Ну по идее для честного одного прохода проще использовать очередь на N элементов. Но это в том случае когда N не большое.

[Lure_of_Chaos]

А на собеседовании не редкость последовательность вопросов: 1. напишите код, решающий какую-то задачу. 2. как можно улучшить этот код?

[xmetropol]

Ну так если хвост списка определять путём пробега всего списка от головы и до, собственно, хвоста. Ничего удивительного, что вставка элементов в конец списка так затрагивает производительность. Тут бы указатель на хвост хотя бы иметь, ладно уже там колличество)))

[poxvuibr]

График идёт вниз, потому что устал :). У меня к нему другой вопрос. Почему он так резко скакнул вверх? Что там случилось? Такое впечатление, что в игру вступил какой-то внешний фактор, который постепенно сошёл на нет. Такое поведение воспроизводится?

[poxvuibr]

А кода, который делает этот график вы не выкладывали? Я бы у себя попробовал.

[bearded_guy]

Если испытания происходили последовательно, то мб все страницы попали в страничный кеш?

[soft-ice]

Если список окажется зацикленным на каком-либо элементе, то алгоритм уйдет в небытие.

[caesar_84]

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

[Lure_of_Chaos]

Уважаемый переводчик, а минусы огребаете Вы. Учтите, пожалуйста, этот момент в последующих переводах :)

[pozitrone23]

Мне неприятно что в коментах люди вечно обсирают автора. Варварство

[poxvuibr]

Действительно варварство. Хорошо, что в комментариях к этой конкретной статье никто ничего плохого про автора не сказал.