Почему на собеседованиях так часто спрашивают про связные списки

Автор оригинала: Hillel Wayne
  • Перевод
Примечание переводчика: оригинальная статья опубликована в серии твитов

Вероятно, вы уже читали кучу объяснений, почему обработка связных списков — плохой вопрос для собеседования. Я же в первую очередь хочу объяснить, откуда он вообще взялся. Всем пристегнуться, погружаемся в теорию игр ИСТОРИЮ!

Хотя индустрия программного обеспечения процветала в 80-е годы, но действительно взлетела в 90-е. В это десятилетие число работников отрасли в США утроилось и превысило миллион человек. Со взрывным ростом пришла необходимость нанимать массу сотрудников и оценивать их.

Что нужно оценить? Ну, в первую очередь, знание языков. Согласно TIOBE, в 1986−2006 годы самым популярным языком в мире был C, далее следовал C++. К 2006 году Java вышла на первое место, но C остался рядом.

C работал близко к железу без лишних абстракций. Пустой словарь Python расходует аж 288 байт, то есть 5% всего объёма памяти первого поколения Apple II. Абстракции слишком дороги, слишком много накладных расходов. Если вам нужна сложная структура данных, вы должны построить её самостоятельно с помощью массивов, структур и указателей.

(C++ оказался получше в этом отношении, поскольку там появилась стандартная библиотека шаблонов, но её официально приняли только в 1998 году, а повсеместно использовать начали гораздо позже. Помню, как читал аргументы о накладных расходах даже в 2005 году).

Связные списки — необходимая структура данных, которая позволяет производить динамическое выделение памяти с меньшими рисками переполнения буфера. И нужно было писать эти связные списки вручную. Это означает, что вы должны были вручную манипулировать указателями в связных списках.

Другими словами, в 90-е годы вопрос «Как развернуть связный список» — это не проверка алгоритмического мышления или знания структур данных, это вопрос «Вы программировали на C?». Если да, то для вас ответ тривиален. Если нет, ответить (в идеале) невозможно.

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

Вероятно, ситуацию помог зацементировать бестселлер «Взлом собеседования по программированию». Её автор Гейл Лакман Макдауэлл работала по специальности в 2000−2008 годы и, вероятно, написала книгу на основе собственного опыта. Книга стала настольным справочником компаний, которые проводят собеседования — и связные списки укрепились в списке стандартных вопросов.

Без исторического контекста связные списки стали преподносить как вопрос на «навыки решения проблем». Но это полностью противоречит изначальной цели: если вы проверяете знание языка, вы не хотите, чтобы на вопрос могли ответить (то есть «решить проблему») люди, не знакомые с этим языком.

Например, вопрос «Определите, есть ли в связном списке цикл». Предполагается, что кандидат должен придумать решение типа «черепаха и заяц», опубликованное в обильно цитируемой научной статье 1967 года. Вы просите кандидата повторить научное исследование за 30 минут!

Возможно, когда мы перешли к вопросам типа «решение проблем», то откалибровали сложность, взяв связные списки в качестве ориентира. Что совершенно искажает шкалу.

(Кстати: ещё один аргумент для связных списков — это «проверка фундаментальных знаний информатики». Ну если так, то почему у всех не спрашивают про детерминированные конечные автоматы? Теорему Райса? Как работает компилятор? Структуры данных — очень небольшая часть компьютерной науки и часто нерепрезентативная).

Подводя итог, вопрос о связном списке был хорошей проверкой умения писать на С, а теперь стал плохой проверкой «Умеете ли вы решать проблемы?»

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

Ещё одна мораль: из истории можно многому научиться.

(Третья мораль: если видите наполовину завершённую статью и думаете «Эх, легче запустить проект в серии твитов», это ловушка, не попадайтесь в неё)
Поддержать автора
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 358

    +1
    Вероятно, вы уже читали кучу объяснений, почему обработка связных списков — плохой вопрос для собеседования.

    А что делать, если знание этих алгоритмов важно для нашей работы?
    Подводя итог, вопрос о связном списке был хорошей проверкой умения писать на С
    Почему *был*? Он и сейчас в этом плане неплох.
    Что нужно оценить? Ну, в первую очередь, знание языков. Согласно TIOBE, в 1986−2006 годы самым популярным языком в мире был C, далее следовал C++. К 2006 году Java вышла на первое место, но C остался рядом.

    С и сейчас не очень далеко. Правда это не останавливает людей писать статьи о том, что вопросы на знание алгоритмов и структур данных «устарели». Конечно, ведь сегодня, чтобы программировать не нужно знать алгоритмы и структуры данных. Ведь можно слабать на электроне очередной недо-мессенджер просто написав
    const { remote } = require('electron')
    remote.getCurrentWindow().loadURL('https://github.com')
      +2
      Ну если это важно, то спросите.
      Суть в том, что для большинства JS/DBA это не важно.
        +1
        Если большинству JS/DBA это не важно, то почему они лезут на вакансии, где это требуется?
          +6
          Мне задачу которая решается зайцем и черепахой задавали при устройстве на работу которая была связана с версткой UI в игре.
          Это я не туда полез или все таки собеседующий идиот?
            –3
            Не знаю. Судя по тому, как работают многие популярные сайты (какой-нибудь) — скорее первое.
              +3
              А при чем тут сайты?
              Ну и отдельный момент — как идя на собеседование на верстальщика UI я должен был догадаться, что от меня требуется алгоритмическая подготовка, чтобы «не лезть»?

              P.S. Отдельно замечу что с алгоритмической подготовкой у меня всё приемлемо. Но речь не об этом, а о самом неуместном вопросе на рассматриваемую должность.
                0
                Притом что их тоже делают вот те самые JS/DBA, которым «нинужна» в алгоритмы.

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

                В подавляющем большинстве случаев нажатие куда угодно заставляет усомниться в том, что у тебя в руках — устройство, способное выполнять миллиарды операций в секунду. Потому что они пары-тройки простых операций за секунду, зачастую, неспособно выполнить…
                  0
                  Это в какой игре у вас проблемы с UI?
                  Ну и отдельные момент — в современных движках UI верстается в редакторах, кода там нет от слова «вообще». Максимум есть обработчики нажатий кнопок, но они к верствке не относятся. Даже всякие анимации делаются в редакторах, с использованием минимума кода типа «запустить анимацию/остановить анимацию».
                    –2
                    Может быть авторы используют «несовременный движок UI»?

                    Так-то я про это знаю. И потому вообще не понимаю зачем нужен отдельный человек на подобную должность и какого масштаба должна быть игра, чтобы можно было выделить на это отдельную штатную единицу…
                      +1
                      Может быть авторы используют «несовременный движок UI»?

                      UE4

                      зачем нужен отдельный человек

                      Инструментом тоже нужно уметь пользоваться. Просто рандомный человек такого наворотит…
                        0
                        Инструментом тоже нужно уметь пользоваться. Просто рандомный человек такого наворотит…
                        Это понятно. Но у меня нет уверенности в том, что от вас хотели только «UI в редакторах, кода там нет от слова «вообще»».

                        Скорее всего было понимаение, что какой-то процент времени (не знаю сколько: день в неделю или месяц… неважно) человек должен верстать пресловутый UI — а остальное время он будет кодить что-то другое.

                        А если вы можете решить только часть задачи — то логично же поискать кого-то, кто сможет решить её всю.
        +2
        Этому алгоритму можно научиться за один вечер. В вашем случае, лучше тестировать умение и желание человека обучаться, а не знание какого-то алгоритма
          0
          del
            0
            Возможно, но придумать конкретный алгоритм за 10 минут на собеседовании — не всегда могут даже те, кто этими алгоритмами активно пользовался несколько лет назад.

            Если примерно помнишь — то нагуглить не проблема. Если догадываешься о существовании алгоритма — то нагуглить можно. Если вообще не догадываешься о существовании алгоритмов, то такого человека можно на собеседовании определить разными способами.
              +3
              За один вечер можно много чему обучиться. Например яблочный пирог готовить. Если я научусь яблочный пирог готовить, возьмете программистом? Мало того, что есть желание обучаться, так еще и широкие интересы. И даже огонь (от духовки) в глазах видно!
              0
              А что делать, если знание этих алгоритмов важно для нашей работы?

              Ну если реально важно — то конечно учить.
              Но в большинстве случаев выгоднее взять готовую библиотеку.
                +2
                Но в большинстве случаев выгоднее взять готовую библиотеку.

                А как эта «готовая библиотека» поймет, какой, например, вид списков или деревьев наиболее выгоден с точки зрения быстродействия или памяти для вашей конкретной ситуации? Или она просто возьмет то, что в нее накодил автор-программист (неизвестного качества)? А, ну тогда неудивительно, что некоторые программы выжирают всю ОЗУ и долбят процессор, например для того, чтобы отрисовать на экране таблицу из 100 строк…

                Попробуйте, например, сделать тестовый файл в 2-3 МБ с текстом, а потом попробуйте заменить в своем любимом редакторе буку о на заглавную. Почему большинство редакторов при этом намертво зависают, а оставшиеся 5% делают это 2-3 минуты?
                  0
                  Потому-что реально замена выполняется за доли секунды, а остальное время редактор пытается оценить, какие изменения попадают в окно пользователя, и перерендерить его содержимое? То есть вещам, которые надо выполнить чтобы пользователь увидел замену?
                    0
                    Нет, потому что тот же самый рендер он делает несколько раз в секунду когда вы мотаете документ или открываете его впервые.
                    0
                    Почему большинство редакторов при этом намертво зависают, а оставшиеся 5% делают это 2-3 минуты?
                    О каких редакторах речь? Только что проверил — и vim и emacs укладываются в пару секунд. Примерно столько же, сколько открытие такого файла занимает: всякие подсветки и прочее нужно же пересчитать…
                      0
                      Речь не про консольные редакторы. Gedit от такой операции просто умирает, mousepad пыхтит минуты три, виндовый блокнот вешается, notepad++ пыхтит минуты три. Kate умирает.
                        0
                        Emacs вообще-то и не был никогда чисто консольным и GVim тоже отлично справляется. Как и Sublime. То, что Gedit написан через задний проход (как и многое другое в GNome) — увы, медицинский факт.

                        P.S. Тут правда сказывается моё нежелание в принципе работать с редакторами, которые тормозят. Но я знаю, что я почти уникален, да: когда я как-то кинул в репу автосгенерённый файл на 5 мег — вой был слышен чуть не на луне, когда народ стал на меня баллоны катить, за то, что я им всё сломал.
                          0
                          Потому что надо было не в репу, а в артефактори. Смысл в репу если он всё равно автосгенерённый и сравнивать с предыдущей версией никто никогда не будет.
                      0
                      Война и мир Толстого, 4 тома, вместе с разными хедерами/футерами сайта, с которого копировался текст. Объём — 5.665.344 байт. Sublime text 3, visual studio code: время замены меньше полутора секунд
                  +11

                  Если кандидат не разбирается в односвязных списках, то он, как правило, не разбирается в структурах данных вообще.


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


                  И пишет потом в прод:


                  xs = list(...)
                  ys = list(...)
                  
                  for y in ys:
                      if x in xs:
                          ...

                  и тому подобное.


                  Односвязные списки – отличный фильтр, с которого можно начать блок вопросов про структуры данных.

                    +6
                    > И пишет потом в прод:

                    А что не так?
                      +1

                      Осмелюсь предположить, что во-первых x не определен, a во-вторых x in list имеет линейную сложность и лучше использовать set.

                        0
                        Ну set допустим только для xs насколько я понимаю. Или имелось ввиду что-то иное?
                        +3

                        Поиск в списке – O(n). Для проверки принадлежности нужно использовать множество, дающее амортизированную O(1).

                          +5
                          А, всё, понял, там if в последней строчке. Ну это уже зависит от размеров xs и ys и частоты вызова оного кода. Может так статься, что там вообще придётся выкинуть питон и переписать на С, сразу производительность вырастет в 50 раз.
                            +18

                            Лол, я тоже там вместо if прочитал for.


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

                              +4

                              Да и да! Однажды убил полчаса на собеседовании на дискуссию, что для решения задачи необходим контекст. И если она формулируется как "написать оптимальное решение", то контекст просто необходим и без него нельзя говорить, что то же решение со списком не оптимально.

                                +1
                                А потом ещё окажется, что для удовлетворительного решения данный проблемы вообще не важны эти 2.5 наносекунды. Где-то там же идёт вызов веб-сервиса и потери в первом случае нивелируются.
                                Потому что «Преждевременная оптимизация — корень всех зол» (с)
                                  +1

                                  На самом деле, полная цитата звучит иначе


                                  We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil…
                                  Yet we should not pass up our opportunities in that critical 3%…
                                  A 12% improvement, easily obtained, is never considered marginal

                                  Получается совсем другой смысл, не так ли?
                                  Эта вырваная из контекста фраза часто используется как оправдание для того чтобы пропустить этап обдумывания, и зафигачить линейный поиск по большому списку там, где можно было бы спокойно использовать HashMap.

                                    +1

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

                                      0
                                      Да, смысл меняется. Если точно знаешь, данный вариант лучше и не отнимет времени — нет смысла не сделать.
                                      По конкретному случаю: Ну вот использовал здесь один разраб hashMap. Времени лишнего не потратил, но и на конечный результат не повлиял. Другой не задумался на решением или не знал другого варианта и использовал List. Результат — тот же. Но ведь время более квалифицированного разраба дороже?
                                      И другое дело, если список _действительно_ большой и результат имеет значение.
                                        +4
                                        Другой не задумался на решением или не знал другого варианта и использовал List.


                                        … и через несколько лет, когда при масштабировании этот код внезапно отожрал всю память или начал тормозить на казалось бы обычных операциях, придется потратить еще больше времени дорогих специалистов на профилирование, поиск проблемы, отладку и переписывание с учетом регрессии.
                                          –6
                                          Гипотетическая проблема. Всё не предусмотришь. В данном случае вероятность такого исхода довольно мала.
                                          Хотелось бы писать хорошо структурированный код с хорошей архитектурой и тестами. Но реальность такова, что бизнесу нужен результат. И нужно найти золотую середину между стоимостью, качеством и временем разработки.
                                            +2
                                            Это очень сильно зависит от проекта и специфики. Есть проекты где это неважно (типичный веб), есть проекты где про это все нужно думать постоянно даже на очень простом коде (я сейчас на таком).
                                            +1
                                            Но с гораздо большей вероятностью, эта строчка кода никогда не использовалась, кроме тестов и проект умер через пару лет навсегда.
                                              0
                                              И команда пошла искать специалиста по оптимизации, чтобы найти проблему, который стоит еще дороже :) А так да, всегда нужно держать в уме базовые принципы оптимизации, в основном это массивы и циклы, и если сомневаешься с будущим количеством данных — сделай хэштаблицу, не ленись. А то потом через неделю/месяц/год придется с профайлером искать где же залипает приложение
                                  –9
                                  А почему, кстати, О(1)? Уже придумали алгоритм, ищущий быстрее двоичного поиска?
                                    +29

                                    Ну да, хэш-таблицы.

                                      –3
                                      А если ключи — строки? А если хэш-таблица не влезает в оперативку? А если таблицу надо часто перестраивать?
                                        +4
                                        А если значения — байты?
                                          +4

                                          Тогда массив из 256 элементов с честным доступом за O(1) вместо амортизации.


                                          Хотя это изоморфно хеш-таблице с perfect hash function.

                                          +8

                                          Тогда мы все умрем.

                                            +1

                                            То все равно за O(1).


                                            Если быть чуть более дотошным, то время работы O(hashTime).
                                            Т.е. если у нас есть N строк с длиной L, хэш-таблица отработает за O(L). Но заметьте, что поиск в отсортированном массиве был бы O(L * log(N)), а поиск в неупорядоченном массиве был бы O(L * N).

                                              0

                                              Речь в комментарии на который я отвечал шла о том "какой алгоритм быстрее", а не о том сложность какого алгоритма быстрее растет при росте n.


                                              "хэш-таблица отработает за O(L)"


                                              Все равно за O(1).

                                                0

                                                Дочитайте мой комментарий до конца.


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

                                                  +1

                                                  Я повторю ещё раз.


                                                  Речь в комментарии на который я отвечал шла о том "какой алгоритм быстрее", а не о том сложность какого алгоритма быстрее растет при росте n.


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

                                                    +3

                                                    Оригинальный комментарий:


                                                    А почему, кстати, О(1)? Уже придумали алгоритм, ищущий быстрее двоичного поиска?

                                                    Да, придумали. Хэш-таблица.


                                                    Вы привели контр-пример про строки (корректный, но являющийся скорее придиркой в данном контексте) — я на него ответил.


                                                    А если хэш-таблица не влезает в оперативку?

                                                    Это не влияет на ассимптотику.


                                                    А если таблицу надо часто перестраивать?

                                                    Это не влияет на ассимптотику.


                                                    А дальше попрошу сходить в любую книжку по алгоритмам и разобраться с понятием амортизированной сложности алгоритма

                                                    Я осознаю, что в случае хэш-таблицы это сложность в среднем, а в бин. поиске — в худшем случае. Но, как вы сказали, мы обсуждаем "какой алгоритм быстрее".


                                                    Так нормально? Вы меня не отсылайте в книжки, покажите где я по вашему неправ.
                                                    Я умею хэшировать строки и писать хэш-таблицы. И теорию тоже сдавал:) Так что давайте дискутировать предметно.

                                                      +2
                                                      Хорошо, извините за резкий тон и спасибо за адекватную реакцию.

                                                      Давайте подробно, по порядку.
                                                      Что по вашему такое «асимптотика функции»?

                                                      Я осознаю, что в случае хэш-таблицы это сложность в среднем, а в бин. поиске — в худшем случае. Но, как вы сказали, мы обсуждаем «какой алгоритм быстрее».


                                                      Не совсем «в среднем», это предел от «среднего» при n -> бесконечность.
                                                      В вашем примере с хэшфункцией по строке со сложностью O(L) получается:
                                                      image

                                                      Это не говорит о том быстрее или медленнее работает хэш-таблица, это говорит о том, что при росте n хэш-таблица в общем случае не становится медленнее.
                                                        0

                                                        А, все, я понял о чем мы спорим.


                                                        Вы под "быстрее/медленнее" подразумеваете произваодительность в миллисекундах (измеряемую). А я подразумеваю сравнение вычислительной сложности.


                                                        Мое понимание ситуации взялось из оригинального комментария "А почему, кстати, О(1)? — тут речь шла явно именно про асимптотику.


                                                        Вы видимо зацепились за "Уже придумали алгоритм, ищущий быстрее двоичного поиска?"


                                                        Я же развернул этот вопрос так(из теории): найдется такое n0, что для любого N > n0 хэштэйбл работает быстрее двоичного поиска (в миллисекундах). При этом, из практики, находится это n0 довольно быстро:)

                                                          0
                                                          Вы под «быстрее/медленнее» подразумеваете производительность в миллисекундах (измеряемую).


                                                          Да, конечно, ту которую можно измерить, и которая реально влияет на пользовательский опыт.

                                                          Вы видимо зацепились за «Уже придумали алгоритм, ищущий быстрее двоичного поиска?»


                                                          Именно так.

                                                          Вообще, я хотел высказать идею, что принимать решение о выборе алгоритма только на основании его асимптотик (как часто просят на «неправильных» собеседованиях поклонники карго-культа и зубрежки) — неправильно.
                                                            0

                                                            Ок, тут согласен на все 100%.
                                                            Если есть априорное понимание того, что список объектов будет коротким нужно писать на списке. Хотя лучше написать реализацию ArraySet, чтобы каждый раз самому не писать:)


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


                                                            За 5 лет разработки игр я 1 раз видел в профайлере OrderedSet, который надо было заменить на массив чтобы стало быстрее. Ни разу я не видел в такой роли HashSet. И я видел с сотню раз линейный/бинарный поиск, который надо было заменить на HashSet.

                                              0
                                              Если строки (или набор байт произвольной длины) в качестве ключа, можно использовать префиксное дерево
                                              0

                                              От реализации правда зависит, количества элементов, их распределения. Может доходить и до логарифмической сложности.

                                                0
                                                хэш-таблица гарантированно ищет за O(n)
                                                меньше только если с ключами повезло и она не выродилась в список
                                                а если не повезло, то выходит так ocert.org/advisories/ocert-2011-003.html
                                                  0
                                                  Можно взять хэш-таблицу с открытой адресацией и двойным хешированием, чтобы радикально уменьшить верятность вырождения в список
                                                    –1
                                                    а до 2011 года это была засекреченная информация или все авторы перечисленных реализцаций просто прогуляли в школе урок по хештаблицам? если вашей структурой может пользоваться только секюрити эксперт после оборачивания ее несколькими рядами костылей, зачем ее кому-то в интернете вообще советовать?
                                                      +1
                                                      Как-то за вашей агрессией мысль не уловил.
                                                      По ссылке описана атака на отказ в обслуживании через подбор и засылку данных, которые заранее известной хешфункцией дают коллизии, в связи с чем поиск вырождается в линейный для разрешения коллизий цепочками, логарифмический для цепочек лежащих в дереве поиска, линейный для хеширования с открытой адресацией с линейным/квадратичным пробированием и хз для двойного хеширования.

                                                      Т.е. не будет разницы между поиском по массиву по связному списку и по хештаблице с любым типом разрешения коллизий.

                                                      если вашей структурой может пользоваться только секюрити эксперт после оборачивания ее несколькими рядами костылей

                                                      Какой структурой, хештаблицей?
                                                      А чем еще пользоваться-то, сбалансированными деревьями поиска? Ну, они при такой атаке покажут амортизированную логарифмическую сложность поиска, но также будут неплохо сдыхать на перебалансировке.
                                                      Ну, и вне данной атаки производительность будет хуже.
                                                +3
                                                Это на самом деле очень сложный вопрос.
                                                Хэш-таблицы имеют хорошую амортизированную асимптотику, но это совсем не значит, что в общем случае они ищут быстрее или медленнее.
                                                  +1
                                                  Не понял, можете пояснить?
                                                  Как выбор значения «по ключу» может быть нe быстрее поиска по списку? Особенно учитывая что про сам список нам никакие особые условия не даны.
                                                    +4

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


                                                    Сравните:


                                                    1. Вы держите книгу в руках и ищете страницу 100 последовательно переворачивая страницы.
                                                    2. Вы пишете письмо другу в другой город с просьбой прислать страницу 100 и неделю ждёте ответа с одной страницей.

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

                                                      +1

                                                      Ключевое тут — "хорошо локализованного" и "влезшего в кэш процессора". Минимально разросшийся список в кеш уже не влезет, ну а локализованность в Питоне — оксюморон.

                                                        +1

                                                        Конечно, правда говорят, что массивы в numpy как раз хорошо локализованы. Но я не питонист, не знаю :(


                                                        Это просто пример того, что O-нотация и реальная жизнь сложнее чем "O(1) быстрее O(n)".

                                                          0

                                                          Не могу с вами не согласиться:)

                                                  –4
                                                  С хеш таблицами это обман. Либо большой перерасход памяти, либо реальная худшая сложность О(н). Если хотите что-то быстрее, то, например, дерево Ван Эмде Боаса может отвечать на ваши запросы за логарифт по основанию w, где w это длина числа (ключа) в битах. Из-за большой константы имеет смысл использовать только на больших данных, но при этом памяти расходует сколько нужно и ведет себя более определенно по сравнению с хеш таблицами
                                                    0
                                                    «Уже» придумали и описали в 30-ых годах прошлого века. Ссылки в книгах Д. Кнута, Вам в помощь:)
                                                –11
                                                уточните, кандидат на должность по какому языку? Например, зачем мне на python или javascript знать как организовывать связанные списки(за исключением саморазвития и расширения кругозора)?
                                                Скорее всего, среднестатистическому программисту на интерпретируемых языках это вообще никогда не понадобится.
                                                  +8
                                                  Например, зачем мне на python или javascript знать как организовывать связанные списки(за исключением саморазвития и расширения кругозора)?

                                                  Например, для того, чтобы делать осознанный выбор, в каком случае для хранения данных использовать список, в каком — хеш-таблицу, а в каком массив, чтобы ваше приложение из пары форм нормально работало, а не еле ворочалось на топовой конфигурации, как некоторые ухитряются делать.
                                                    +6
                                                    Честно скажу, по моему вы слишком утрируете.
                                                      0
                                                      Не утрирует. Я постоянно переписываю код на python за студентами и стажерами. У большинства начинающих разработчиков на python вообще нет понимания в чем разница между структурами данных. Хеш-таблица интуитивно понятно выполнена, список тоже. Поэтому я видел абсолютно бесчеловечные попытки реализовать выдуманные велосипеды, ведь проект нужно было сдать еще вчера. В итоге мне на полном серьезе приходится объяснять что не надо искать уникальные элементы списка через ключи хеш-таблицы когда есть множества (set).

                                                      Но опять же. Ты получаешь то что контролируешь. Хочешь чтобы кандидат знал структуры данных, спрашивай его про структуры данных. Если ты спрашиваешь у кандидата решение задачи про «мышей и яд» то он это ответит, но не факт что он будет знать структуры данных
                                                        +2
                                                        что не надо искать уникальные элементы списка через ключи хеш-таблицы когда есть множества

                                                        Я за бывшими PHP'шниками постоянно такое замечаю. Последствия "единой структуры данных для всего".

                                                      +2
                                                      использовать список, в каком — хеш-таблицу, а в каком массив

                                                      Не будем забывать что в js "настоящего" связного списка нет, он будет делатся через объект(который хеш таблица).


                                                      Также не будем забывать что на фронтенде объем данных редко превышает 200 единиц, почти никогда 2000.


                                                      А на таких объемах условныйn log n против n выиграет всего-то навсего в 10 раз. И не исключенно что упущенные константы будут 1 * n * log n против 20 * n

                                                        +4
                                                        А на таких объемах условныйn log n против n выиграет всего-то навсего в 10 раз. И не исключенно что упущенные константы будут 20 n log n против 1 * n

                                                        Но ведь лучше это явно понимать.

                                                          +13

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


                                                          На фронтенде производительность очень редко будет упиратся в структуры данных или алгоритмы. Пример простой и распространненой задача на фронтенде это получить данные от бекенда -> отобразить эти данные. ё


                                                          А сложные задачи возникают так редко что их может тех лид / сто помочь решить / отловить на ревью

                                                            –7
                                                            Пример — фронтенд, на который несколько сотен раз в секунду поступает насколько сотен рекордов, в каждом по 500 полей. Все это дело динамически подсвечивается в зависимости от настроек и данных, сортируется и фильтруется.
                                                            Удачи вам, без структур данных и алгоритмов )
                                                              +6

                                                              И вы уверены, что узкое место тут именно данные, а не рендеринг?

                                                                +1
                                                                Как раз хотел написать, что работая с таким реальным проектом (быстро обновляющаяся таблица) — всё время, потраченное на оптимизацию, сначала ушло в транспорт (и вот эти «сотни раз в секунду» обрезались на этом этапе, потому что столько обновлений на фронте просто не надо, а значит и пересылать их тоже не надо, надо заранее группировать и причёсывать), а когда транспорт стал более-менее весело бегать, остальное ушло на очень простенькую оптимизацию рендера, чтоб хотя бы стабильные 30 fps были.
                                                                Про структуры данных вообще никто не вспоминал.

                                                                Хорошие структуры данных однозначно полезны и на фронте, но совсем даже не для оптимизации (я за 10+ лет фронтэндерства местами на довольно больших объемах данных про big O вспоминал примерно один раз, да и то в целях «а не стоит ли этот момент отдать на бэк?»), а для читаемости кода.
                                                                  0
                                                                  Тут есть одна проблема.
                                                                  Вы рассказываете, как это все надо было сделать правильно, и это все конечно так. А я — как это было первоначально сделано по разным причинам (начиная от полного игнорирования пункта про саначала анализ требований, а потом их выполнение, заканчивая чуток загадочным подходом менеджмента к процессам).
                                                                    0
                                                                    Но при чём тут правильные структуры данных?
                                                                    Плохо сделанную вещь надо делать нормально — и это начинается не с замен структур данных.
                                                                      0
                                                                      Структуры данных тут при том, что они будут прописаны как требование для айчаров и прочих учасников найма.
                                                                      И еще раз, «правильно» — понятие сильно относительное.
                                                                      Для Вас, правильно — это корректно работающее приложение с логичной структурой.
                                                                      Для менеджера (да, есть исключения, но в больших конторах эти исключения редко задерживаются), правильно — это проект на котором задействовано максимально большое количество людей на максимально длительный срок.
                                                                      И возвращаясь к изначальной теме — угадайте, кто влияет на методики подбора кандидатов больше? Вы, или менеджер?
                                                                        0
                                                                        Ничего не понял.
                                                                        Если у нас «проект, на котором задействовано максимально большое количество людей на максимально длительный срок» — то структуры данных вам точно не помогут. Просто получайте ваши сотни обновлений данных в секунду и как-нибудь показывайте их на фронте. Желательно силами большой скрам-команды со всеми песнями, плясками, эпиками, доской, и всем таким. Желательно долго. Начните с тормозного варианта, а потом в течении десятка лет оптимизируйте по паре процентов в месяц. Все будут довольны (особенно менеджер). Ну а уж если вам таки хорошие структуры данных в итоге будут нужны, то за этот десяток лет будет время самообразоваться.
                                                                          0
                                                                          Вы опять зачем-то используете логику нормального человека. Оно не применимо для эфективного аутсорса )
                                                                +4
                                                                У вас на фронтенде 50 тысяч(!) полей, изменяющиеся несколько сотен(!) раз в секунду. Отличный пример.
                                                                А зачем вам фронтенд, всё равно человек на такое смотреть не сможет чисто физически, а роботу через API какое всяко удобнее…
                                                                  0
                                                                  Вот вам «всё равно человек на такое смотреть не сможет чисто физически» это очевидно. И мне очевидно.
                                                                  Но тут у нас имеют место быть ньюансы работы эффектывных аутсорсинговых компаний. Которым надо работу работать, и как можно дольше, особенно если можно прикрытся требованиями от заказчика. Так что вышенаписанное год пилили, пока все не поняли, что это будет невозможно использовать на практике…
                                                                    0
                                                                    Для данной проблемы нужно проявлять не знание структур данных и алгоритмов, а те самые софт скиллы, чтобы вовремя пояснить и сэкономить человекочасы.
                                                                      0
                                                                      Да, только вас уволят в течении имнимально возможного времени, как только узнают что вы решили «сэкономить человекочасы». Ибо вы нанесете таким образом прямой финансовый урон вашей галере )))
                                                                      0
                                                                      Вот вам «всё равно человек на такое смотреть не сможет чисто физически» это очевидно. И мне очевидно.


                                                                      Это очевидно любому человеку, ну обычный здравый смысл.

                                                                      надо работу работать, и как можно дольше


                                                                      Это называется «попил бабла», к алгоритмам и структурам данных отношения не имеет.
                                                                  +2
                                                                  Сортировки в таблицах, отображение master-detail на 2+ уровня, подсветка строк «значение есть/нет в списке»?
                                                                    +1
                                                                    Я когда-то тоже любил фразу про преждевременную оптимизацию. На деле же оказалось что к тебе через неделю подойдут и спросят «а может твой код обработать в 1000 раз больше данных? а в 10000?» ты начинаешь пытаться оптимизировать программу и понимаешь что у тебя не одно узкое место, а вся программа сплошное узкое место.
                                                                    И на самом деле большинству достаточно по профилировать свои программы пару раз. чтобы понять какие решения работают медленно а какие быстро и в следующий раз они уже так делать не будут. Не будет больше решений в стиле «а давайте создадим 10 млн экземпляров классов на python» или «давайте сделаем цикл в цикле для поиска уникальных элементов связанного списка на javascript»
                                                                      +1
                                                                      На фронтенде производительность очень редко будет упиратся в структуры данных или алгоритмы.
                                                                      Зайдите на популярный Patreon (хотя бы сюда), отмотайте ленту, скажем, на пару лет назад… а потом возвращайтесь сюда и мы сможем продолжить дискуссию.

                                                                      Лучше находишь бутылочное горлышко и учится писать качественный, а не производительный код.
                                                                      Лучше — не создавать «бутылочных голышек» в количестве 100500 штук.

                                                                      Да, это плохо влияет на KPI: вы не сможете рапортовать о том, что ускорили Frontend на 50% каждый год 10 лет подряд… но зато то, что вы сотворили — не будет вызывать у пользователя ненависти.

                                                                      P.S. И да, тот факт, что Patreon — при всей его жутчайшей убогости — весьма популярен… говорит не о том, что на фронте не нужны люди со знанием алгоритмов. А о том, что вообще качество программистов для фронта — дело вообще десятое. Маркетинг и дизайнеры — важнее. Нет никакой дихотомии между написанием «качественного» и «производительного» кода. Возможно при выжимании последних 2-3-5% производительности… но никак не при добавлении трёх кнопочек на веб-страницу. Вы либо пишите качественный и производительный код, либо… дешёвый. И то и другое бывает нужно — но только не надо рассказывать сказок про качественный, но не производительный код. Не на фронте.
                                                                        –1
                                                                        Зайдите на популярный Patreon (хотя бы сюда), отмотайте ленту, скажем, на пару лет назад… а потом возвращайтесь сюда и мы сможем продолжить дискуссию.

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

                                                                        И структуры данных тут опять же не при чём, кстати.
                                                                          +2
                                                                          Это всего лишь потому, что сценарий достаточно долгого проматывания модной бесконечно скроллящейся ленты в подавляющем большинстве случаев использования этих самых модных лент никого не интересует.
                                                                          А с чего вы так решили, извините? И как вообще добраться до первый страниц комикса, про который вы только что узнали?

                                                                          Там сейчас вообще забавная вещь происходит: творчество некоторых авторов увидеть целиков вообще нельзя, в принципе, потому что при попытки домотать туда примерно через пару часов сайт просит обновить куку… и забывает про всё, что вы успели намотать.

                                                                          И структуры данных тут опять же не при чём, кстати.
                                                                          Что значит «не при чём»? Тот факт, что каждое нажатие на «Load more» отрабатывает дольше, чем предыдущее (до такой степени, что Firefox начинает предлагать «убить вкладку») — просто орёт про то, что кто-то где-то куда-то вкрутил, в очередной раз, алгоритм маляра Шлемеля.

                                                                          Просто потому, что так пойдет делать ничтожно малый процент пользователей, на интересы которых дешевле наплевать, чем что-то делать.
                                                                          Вот только не надо рассказывать мне — что это был сознательный выбор. Просто при написании этого кода учитывалась что угодно, кроме, собственно, эффективности и реального удобства пользования.
                                                                            –1
                                                                            А с чего вы так решили, извините?

                                                                            Предлагайте свои варианты. Я не настаиваю.

                                                                            И как вообще добраться до первый страниц комикса, про который вы только что узнали?

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

                                                                            В Спортлото напишите.

                                                                            Тот факт, что каждое нажатие на «Load more» отрабатывает дольше, чем предыдущее (до такой степени, что Firefox начинает предлагать «убить вкладку») — просто орёт про то, что кто-то где-то куда-то вкрутил, в очередной раз, алгоритм маляра Шлемеля.

                                                                            А, ну у кого-то очень кривые руки. Как будто что-то новое. Учитывая, что на патреоне с бэком вроде бы всё в порядке, насколько я могу видеть, а тормоза проявлятся на самом onclick, еще даже до того момента, как будут сделаны запросы на бэк — это один из случаев криворукого построения фронтэнда. Сказать, что там дело именно в структурах данных — я бы очень сильно поостерегся. Может быть именно и в них, но проблемы там явно не от структур данных начались, а от непонимания того, что происходит со страницей, когда на ней пара тысяч постов.

                                                                            Вот только не надо рассказывать мне — что это был сознательный выбор.

                                                                            Нет, сознательный выбор — это ничего не делать, когда неизбежно придут те 2.5 человека, которым это надо, и начнут жаловаться. И это опять же только лишь гипотеза, основанная на наблюдении. С радостью её отброшу, как только где-нибудь кто-то починит свою убогую ленту по жалобам пользователей.
                                                                              0
                                                                              Может быть именно и в них, но проблемы там явно не от структур данных начались, а от непонимания того, что происходит со страницей, когда на ней пара тысяч постов.
                                                                              Погодите — а как вы поймёте «что происходит со страницей, когда в ней пара тысяч постов» если вы про алгоритмы и структуры данных не в курсе?

                                                                              Вы вообще — на каком языке будете это своё понимание описывать? Я вот, извините, не могу просто себе представить человека, который понимает «что происходит со страницей, когда на ней пара тысяч постов» — но при этом не умеет «в алгоритмы и структуры данных».

                                                                              Ну просто потому что у человека же даже словаря не будет в голове со словами, которые нужны, чтобы это вот всё описать!

                                                                              Сказать, что там дело именно в структурах данных — я бы очень сильно поостерегся.
                                                                              В алгоритмах и стурктурах данных. 100%. Задача — добавить на страницу несколько картинок ну никак не должна требовать триллионов операций (именно столько CPU исполняет за то время, пока отрабатывает onclick). Никак. Она может это делать только когда кто-то что-то сделал не думаю о сложности от слова «совсем».
                                                                                0
                                                                                Вы спорите с какими-то своими фантазиями. Я всего лишь о том, что тема, поднятая в комментариях о «замените список на мапу и всё у вас станет хорошо» во фронтэнде в подавляющем большинстве случаев смысла не имеет. Алгоритмы-то тут при чём? Я про них не говорил. Вы хотите спорить с тем, кто написал
                                                                                На фронтенде производительность очень редко будет упиратся в структуры данных или алгоритмы.

                                                                                — вот с ним и спорьте (но едва ли в этом много пользы, потому что написанное им просто бессмысленно; производительность всегда будет упираться в алгоритмы).
                                                                              0
                                                                              А с чего вы так решили, извините? И как вообще добраться до первый страниц комикса, про который вы только что узнали?


                                                                              Скачать его с ресурса, на котором он выложен с нормальной постраничной разбивкой :-)
                                                                              acomics.ru/~LwHG например
                                                                                0
                                                                                Скачать его с ресурса, на котором он выложен с нормальной постраничной разбивкой :-)
                                                                                acomics.ru/~LwHG например
                                                                                Этот ресурс, конечно, хорош — но там много всякого премиум-контента недоступно. Только сам комикс.

                                                                                Да и вопрос не в том, как это в принципе сделать (можно, в конце-концов, понять какие запросы фронт Patreon'а шлёт на сервере), а в качестве кода. Дерьмо это, а не код — и мне для того, чтобы сделать это высказывание совершенно даже не нужно на него смотреть.
                                                                                0
                                                                                А с чего вы так решили, извините? И как вообще добраться до первый страниц комикса, про который вы только что узнали?

                                                                                Неужели… нужно включить фильтрацию по месяцу? Или сортировку от старых к новым?

                                                                              0
                                                                              Зайдите на популярный Patreon (хотя бы сюда), отмотайте ленту, скажем, на пару лет назад… а потом возвращайтесь сюда и мы сможем продолжить дискуссию.

                                                                              Ну да, ну пролистал, ну рендер начинает дохнуть от такого количество нод (один только значок замочка — 4 вложенных друг в друга дива, что вообще-то делать нельзя).


                                                                              Это всё конечно классно, но я не понимаю как тут могут помочь алгоритмы? Тут может помочь только нормальная вёрстка, а не использование react styled components на каждом новом посте.


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

                                                                                +1
                                                                                Это всё конечно классно, но я не понимаю как тут могут помочь алгоритмы? Тут может помочь только нормальная вёрстка, а не использование react styled components на каждом новом посте.
                                                                                Понимаете какая история. Отмотав куда-нибудь достаточно далеко (насколько дадут, к началу отмотать не получится, как я уже сказал)… можно это вот всё — со всеми четырёхвложенными Div'ами и прочим — записать в файл. А потом — прочитать его. И он откроется за пару секунд.

                                                                                Что это значит? Что вся эта «ненормальная» вёрстка браузером пережёвывается нормально. Да, она ужасна. Да, у людей создавших это — руки из жопы растут. Но тормоза — не оттуда. Тормоза — из применений технологий, «цену» которым вы не знаете.

                                                                                Всё что там происходит с DOM'ом — при некотором желании я могу воспроизвести на технологиях нулевых, а если немного напрячься — то и на технологиях прошлого века. И оно не будет тормозить. Это несложно. Ну вот просто тупо сделать всё на строках, а потому один раз innerHTML присвоить.

                                                                                Сложно — сделать это, применяя хайпхайп современного фронтэнда. Но, чёрт побери, если вам это технологии мешают делать вещи, которые люди прекрасно делали и без них 20 лет назад — то чего вообще, вот это вот знание, которое нам предлагают оценивать вместо «разворачивания списков» — стоит?
                                                                                  0
                                                                                  Но, чёрт побери, если вам это технологии мешают делать вещи, которые люди прекрасно делали и без них 20 лет назад — то чего вообще, вот это вот знание, которое нам предлагают оценивать вместо «разворачивания списков» — стоит?

                                                                                  Я где-то на хабре давно писал, что заказчику важно не насколько качественно сделано, а насколько быстро и дёшево. Во фронте это везде. Потому что рынок такой.


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


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


                                                                                  Для примера "хорошо сделанного" возьмём coub.com, люди как к бизнесу так и к коду и технологиям относятся. Хотят сделать хорошо — делают. Но только у них весь бизнес — одна эта лента и от её реализации напрямую зависит количество денег, которые получает компания. В медиуме статейки являются источником бабла. Поэтому они сделаны оптимально и быстро. Там может быть сколько угодно картинок и сколько угодно анимаций, всё сделано хорошо, потому что люди знали, что делают на совесть.


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


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

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

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

                                                                                    Почему довод «любой каприз за ваши деньги» работает в сторону объяснения «почему порождённый вами код — такое дерьмо», но не работает в сторону «хотите, чтобы я знал про „зайца и черепаху“ — выучу»?
                                                                                      0
                                                                                      но не работает в сторону «хотите, чтобы я знал про „зайца и черепаху“ — выучу»?

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


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


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

                                                                                        0
                                                                                        Про фронтэнд я начал потому,
                                                                                        Про фронтенд начали не вы, а совсем даже knotri вот тут:
                                                                                        Лучше находишь бутылочное горлышко и учится писать качественный, а не производительный код. Лучшее враг хорошего, а преждевременная оптимизация зло.

                                                                                        На фронтенде производительность очень редко будет упиратся в структуры данных или алгоритмы.
                                                                                        Я просто показал, что это, мягко говоря, неправда. Свинья везде грязь найдёт — и незнание алгоритмов может сделать ваш фронтенд полным дерьмом. Нельзя «писать качественный, а не производительный код». Это не дихотомия. Качественный код — он же и производительный тоже. Если только вы не пытаетесь выжать «грязными трюками» уж последние 5-10% производительности.

                                                                                        вы привели пример плохого продукта из фронтэнда, который как раз сделан для закалачивания
                                                                                        А с чего вы так решили? «Заколачивать» они как раз вполне себе заколачивали и три и пять лет назад. У них был вполне себе шустрый сайт с реально работавшей бесконечной лентой (но без модных хайповых технологий… jQuery был, конечно, куда без него).

                                                                                        и желательно побыстрее и на аутсорсе.
                                                                                        А вот это уже — классическая история: пару лет назад у них случился редизайн. Скорее всего у них появились деньги и они смогли нанять «приличную дизайн-студию». Которая, разумеется, выдала им кусок дерьма с наполнителем из дерьма, приправленный сверху дерьмом же.

                                                                                        В любом случае вопрос «нужен нам качественный, быстрый код» или «нам нужен дешёвый код… и побольше-побольше-побольше» — это уже другой вопрос.

                                                                                        Изначальный тезис был: на фронте знания алгоритмов и структур данных просто не нужны, а качество кода, магически — в чём-то другом (дальше можно произносить много разных умных слов). На самом деле — знание алгоритмов и структур данных на фронте тоже нужны… если вам нужен качественный код, конечно. Если он не нужен (а так бывает часто, на самом деле, с этим я согласен) — ну тут всё понятно.

                                                                                        А точнее на собеседованиях задают задания, которые проверяют навыки, не требующиеся на вакансии на самом деле.
                                                                                        Ну тут я отчасти согласен. Сейчас время такое, дурное. Платят не за качественно сделанную работу, а за высоко поднятый хайп.

                                                                                        В позднем СССР тоже так было.
                                                                                          0
                                                                                          Свинья везде грязь найдёт — и незнание алгоритмов может сделать ваш фронтенд полным дерьмом.

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

                                                                                            0
                                                                                            У нас есть одна большая проблема со структурами, а точнее с одним типом структур — деревом. Оно медленное и неповоротливое.
                                                                                            Ну нет же! Оно, как раз, работает с такой скоростью, что человек не успевает заметить как его тысячу раз поменяют. То есть — да, оно дико медленное и неповоротливое, если сравнивать его с каким-нибудь WinAPI прошлого века, но дело не в нём.

                                                                                            Поэтому мы и придумываем разные хаки, чтобы побороть медленную плюсовую реализацию этого самого дерева.
                                                                                            Вашими бы устами… Увы, но эти хаки — они о другом: когда наваляли такой большой ком дерьма, что даже эффективная реализация DOM-дерева перестаёт с ним справняться — можно попроовать засунуть его под пресс и постараться сделать блин потоньше.

                                                                                            Если вы вместо двух-трёх операций с DOM-деревом выполняете миллион — то да, они-таки начинает тормозить «и с этим приходится что-то делать».

                                                                                            Почему-то, правда, «наивное детское решение» — «не выполнять миллион операций там, где нужно десять» в голову не приходит… а да, это ж «преждевременная оптимизация», на неё у нас табу, как же я мог забыть…
                                                                                              0

                                                                                              del

                                                                                                0

                                                                                                Я с вами в корне не согласен в том, что dom реализован эффективно. Он реализован по стандарту, а стандарт далеко не эффективный и никогда к этому не стремился.


                                                                                                *прыгаем по веткам*


                                                                                                Меня совершенно удивляет ваша святая вера в эффективность element.innerHTML += stringFromServer. Во-первых, это выдаёт вашу некомпитентность (ибо в js как раз для пропускания этапа парсинга html придумали DocumentFragment, который как бы перекладывает на программиста то, что вслепую делает плюсовая "эффективная" реализация), во-вторых, stringFromServer — один из самых типичных проколов, это прямо зияющий XSS.


                                                                                                А ещё меня уже начинает немного напрягать, что проблему большого количества списков вы причисляете к проблемам, которые "возникают из-за не знания алгоритмов". Это проблема тонкости реализации, и наша задача, как фронтэндеров, знать не алгоритмы, а решения проблем, которые появляются в нашей области. Если будут проблемы, которые решаются алгоритмами — значит они решаются алгоритмами, если решаются всеми известной либой — значит либой. Если руками — значит руками.


                                                                                                Алгоритмы — не серебряная пуля, так же как и библиотеки для виртуализации списков. Просто есть специфика области. И статья как раз про то, что "связные списки" начинают пихать туда, где нет такой специфики, нет задачи, которая так решается.
                                                                                                from del

                                                                                                  –1
                                                                                                  Меня совершенно удивляет ваша святая вера в эффективность element.innerHTML += stringFromServer.
                                                                                                  Это не вера. Это знание.

                                                                                                  ибо в js как раз для пропускания этапа парсинга html придумали DocumentFragment, который как бы перекладывает на программиста то, что вслепую делает плюсовая «эффективная» реализация
                                                                                                  Вы хотя бы по ссылке-то сходить пробовали? Вот прям на той странице, куда вы ссылаетесь: Оптимизация, о которой здесь идёт речь, важна в первую очередь для старых браузеров, включая IE9-. В современных браузерах эффект от нее, как правило, небольшой, а иногда может быть и отрицательным.

                                                                                                  Кто там говорил про некомпетентность?

                                                                                                  во-вторых, stringFromServer — один из самых типичных проколов, это прямо зияющий XSS.
                                                                                                  Вы уж меня извините, но если вы сами со своего сервера выдаёте данные, которым не доверяете, то а каких XSS может идти речь? Да, конечно, чтобы XSS не было — нужно, чтобы сервер правильно производил обработку. Но вот беда: наматывание слоёв абстракции эту необходимость совершенно не уничтожает. Наоборот — чем больше вы добавляете «наворотов», тем больше шанс, что вы пропустите какую-нибудь банальность на стыке ваших 100500 плагинов.

                                                                                                  А ещё меня уже начинает немного напрягать, что проблему большого количества списков вы причисляете к проблемам, которые «возникают из-за не знания алгоритмов».
                                                                                                  «Алгоритмов и структур данных» да. Известная книжка не зря именно так называется. В данном случае второе — важнее, чем первое.

                                                                                                  Это проблема тонкости реализации
                                                                                                  Нет, чёрт побери. Это не «тонкости реализации». Вы тут почти правильно всё сказали:
                                                                                                  Он реализован по стандарту, а стандарт далеко не эффективный и никогда к этому не стремился.
                                                                                                  DOM и CSS — это редкостное дерьмо. Иногда вообще возникает ощущение, что они задуманы так, чтобы всё происходило максимально медленно и с максимальными затратами ресурсов. Браузеры очень стараются всё сделать быстро, но поскольку ошибка там в ДНК, то их возможности ограничены.

                                                                                                  Тем не менее, если в ответ на действия пользователя вы производите одну манипуляцию с DOM'ом (или даже десять, но не миллион) — современные браузеры всё будут делать достаточно быстро. Ваша задача — придумать, как сделать так, чтобы любые действия пользователя не требовали множества обращений к DOM'у. Если учесть, что данных там у вас на страничке будет несколько мегабайт — от силы (даже если вы откроете тысячи картинок в «ленте» за несколько лет), то скорости JS должно более, чем хватать. А дальше — да, innerHTML и скорости движка тоже должно более, чем хватать.

                                                                                                  Если будут проблемы, которые решаются алгоритмами — значит они решаются алгоритмами, если решаются всеми известной либой — значит либой. Если руками — значит руками.
                                                                                                  Ещё раз: не бывает задач, которые не решаются правильными алгоритмами и структурами данных, но решаются «известной либой» или «руками». Потому что всё, что вы можете сделать «известной либой» или «руками» — это реализовать ту или иную структуру данных или алгоритм.

                                                                                                  Если вы «забьёте» на всё специфику отрасли и всё сделаете на основе базовых структур — то, всего лишь, потратите время на изобретение велосипеда. Что плохо, но не смертельно. Будет несколько дороже, чем в идеальном случае — но приемлемо.

                                                                                                  Если же вы всё делаете «SOLIDно», «идеоматично» и так далее (я уверен, что авторы этого самого ужаса на Patreon'е приведут ещё 100500 классных buzzword'ов), но вы не понимаете какие структуры данных за всем этим стоят и какие алгоритмы задействованы — то вам под силу «спалить» любой бюджет, но в результате — у вас всё равно будет глючное поделие, которое тормозит и жрёт ресурсы как не в себя.

                                                                                                  И статья как раз про то, что «связные списки» начинают пихать туда, где нет такой специфики, нет задачи, которая так решается.
                                                                                                  Почему, чёрт побери, вы в этом так уверены? Вот где на том же самом Patreon'е что-то принципиально отличное от того, что было в GMail 2004го года выпуска? Не в смысле вёрстки (там, как раз, есть вещи, которые технологиями прошлого века не решить… мне так лично кажется, что и не очень надо, ну да ладно — я не верстальщик, туда лезть не хочу и не буду), а вот именно в смысле функциональности? Какая-такая «специфика» там выросла и почему, если там «нет задачи, которая так решается» — то результат столь убог?
                                                                                                    –1
                                                                                                    Кто там говорил про некомпетентность?

                                                                                                    Прошу прощения конечно, но я привык верить бенчмаркам (DIY), а не какому-то Кантору)


                                                                                                    Вы уж меня извините, но если вы сами со своего сервера выдаёте данные, которым не доверяете

                                                                                                    Между мной и сервером ещё целая цепь "людей", которым я не могу доверять:


                                                                                                    1. Браузер
                                                                                                    2. ОС клиента
                                                                                                    3. Хакер на вайфае
                                                                                                    4. Провайдер клиента
                                                                                                    5. Провайдер оборудования для сервера
                                                                                                    6. ОС сервера и прокси провайдера железяки

                                                                                                    Они могут менять данные как захотят, и https, к сожалению, не спасает. Так что нет, я не доверяю никому, ни юзеру, ни браузеру, ни серверу — всё обманывают, все хотят меня сломать.


                                                                                                    Тем не менее, если в ответ на действия пользователя вы производите одну манипуляцию с DOM'ом

                                                                                                    Бизнесу нужно, чтобы при нажатии на кнопку "купить" фоточка товара "летела в корзинку", и везде менялись циферки и всё это шустро и одновременно и с анимацией.


                                                                                                    Это 1 изменение дома — это просто идеальный случай, которых уже не существует. Нужно и анимацию и пересчёт всего и сразу.


                                                                                                    Потому что всё, что вы можете сделать «известной либой» или «руками» — это реализовать ту или иную структуру данных или алгоритм.

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


                                                                                                    то результат столь убог?

                                                                                                    В РФ вроде живём, на вопрос "почему результат столь убог" принято отвечать "ну он хотя бы есть")


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

                                                                                                      –2
                                                                                                      Кто там говорил про некомпетентность?
                                                                                                      Прошу прощения конечно, но я привык верить бенчмаркам (DIY), а не какому-то Кантору)
                                                                                                      Бенчмарки показывают то, что и должны были показывать: appendChild работает куда быстрее и innerHTML и DocumentFragment, однако разница не критична. Да, когда вы говорим о том, что операция, которая должна занимать доли секунды, на самом деле исполняется за минуты трёхкраная разница не критична.

                                                                                                      Вот когда то, что должно исполняться за доли секунды — будет-таки исполняться за доли секунды… можно уже и об оптимизациях и бенчмарках начинать думать.

                                                                                                      Они могут менять данные как захотят, и https, к сожалению, не спасает. Так что нет, я не доверяю никому, ни юзеру, ни браузеру, ни серверу — всё обманывают, все хотят меня сломать.
                                                                                                      И чего вы этим добиваетесь? Того, что всё получается такое феншуйно-хайповое? Если вот эти вот «все» могут что-то менять по дороге от сервера к клиенту — то они запросто могут поменять и первоначально скачиваемую страницу. И ваша игра проиграна. Если же не могут — то они и в дополнительный скачанный фрагмент ничего не смогут добавить.

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

                                                                                                      Вот где-где, а в вопросах безопасности — карго-культ точно не нужен.

                                                                                                      Бизнесу нужно, чтобы при нажатии на кнопку «купить» фоточка товара «летела в корзинку», и везде менялись циферки и всё это шустро и одновременно и с анимацией.
                                                                                                      Расскажите где конкретно на Pantreon'е фоточки «летают в корзину». Потом — можно будет уже и обдумать как конкретно их туда отправить.

                                                                                                      Потому что про «шустро и одновременно с анимацией» — возможно продавцы того ужаса, что мы там наблюдаем, кому-то в уши и лили. Но на практике — никакого «шустро» там нет. Нигде.

                                                                                                      Это 1 изменение дома — это просто идеальный случай, которых уже не существует.
                                                                                                      Извините — но я вам дал вполне конкретный пример. Вот найдите там анимацию (и да — она там такие есть, хотя в глаза бросаются только бесконечно крутящиеся круги, которых, как раз, скорее хорошо, чтобы не было бы) и подумайте — нужно ли ради неё грузить шесть мегабайт JavaScript'а?

                                                                                                      Нужно и анимацию и пересчёт всего и сразу.
                                                                                                      Ну да, конечно. А иметь возможность всем этим пользоваться — не нужно, конечно.

                                                                                                      Так зачем, если в либе уже реализовано, а руки не отсохнут пару строчек написать?
                                                                                                      А шесть мегабайт дерьма куда при этом исчезнут?

                                                                                                      Почему вы эти алгоритмы превозносите в абсолют и приравниваете к сакральным знаниям?
                                                                                                      Это не «сакральные» знания. Не необходимые знания. Если вы знаете алгоритмы и структуры данных, но не знаете «специфики фронтэнда» — то вы поиспользуете «устаревший» innertHTML (который да, действительно работает вдвое-втрое медленнее чем appendChild), но вы с лёгкость скомпенсируете это тем, что ваш код будет в принципе исполнять раз в десять меньше работы.

                                                                                                      Хотя код будет писаться долго, да.

                                                                                                      Если вы знаете алгоритмы и структуры данных, а также ещё и «специфику»… ну это ваще класс: вы сможете всё делать быстро и хорошо.

                                                                                                      Если вы знаете только «специфику» — то вы обречены порождать исключительно тормозное и жрущее ресурсы, как не в себя, дерьмо… хотя кому-то, может быть, этого и будет достаточно…

                                                                                                      А если серьёзно, то результат убог потому, что деньги дали, а когда очухались, что подсовывают говно, обратно деньги уже не вернуть. Ну и выкатили то, что получилось, ибо дешевле выкатить говно чем проходить ещё через 20 таких же компаний и в каждой оставлять кругленькую сумму за один и тот же кусок творчества.
                                                                                                      Ну вот если вы устраиваетесь в компанию, которая специлизируется на впаривании подобных «продуктов» — тогда вам и будет достаточно только «специфики». А списки тогда разворачивать действительно не нужно.
                                                                                                        0
                                                                                                        Бенчмарки показывают то, что и должны были показывать: appendChild работает куда быстрее и innerHTML и DocumentFragment

                                                                                                        Вы очень странно читаете результаты этого бенчмарка, давайте я прочитаю их за вас правильно:


                                                                                                        1. DocumentFragment 49.6 ops/sec
                                                                                                        2. appendChild 36.3 ops/sec
                                                                                                        3. innerHTML 21.1 ops/sec
                                                                                                          (more = better)

                                                                                                        Того, что всё получается такое феншуйно-хайповое?

                                                                                                        Причём тут хайп? Я просто сказал, что серверу доверять нельзя ни в коем случае. Чтобы потом не оказываться в ситуации, когда есть очевидный XSS, а я переложил всю ответственность на бек, а он переложил на меня. Так не делается. Если есть возможность защитить от опасности прямо сейчас, то делать это надо прямо сейчас и не полагаться на других, потому что кто-то в цепи обязательно положится на другого и это всё выльется в огромные проблемы.


                                                                                                        Расскажите где конкретно на Pantreon'е фоточки «летают в корзину».

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


                                                                                                        Извините — но я вам дал вполне конкретный пример.

                                                                                                        Давайте лучше поступим иначе, вместо того чтобы обсуждать очевидное говно вы покажите пример, который сделан "на технологиях прошлого века" и даёт точно такой же функционал, при этом будет использовать только ваши алгоритмы и обычный innerHTML. Я таких примеров не знаю, потому что все, кому надо было, уже давно переписали на более быстрое решение, более поддерживаемое и в принципе более соответствующее реалиям, чем ваш гепотетический проект, который сделан профессором информатики на одних только алгоритмах.


                                                                                                        А иметь возможность всем этим пользоваться — не нужно, конечно.

                                                                                                        Я вам открою большущую тайну, но примерно 40% этих 6 метров js являются полифилами, которые отвечают за то, чтобы этим сайтом могли пользоваться все пользователи одинаково. Медленно и неэффективно — ну и ладно, зато люди с маком будут пользоваться патреоном и будут видеть те же самые лагающие анимации, но они их хотя бы будут видеть. А если убрать эти полифилы, то резко пропадёт целый пласт пользователей. Это так, немного жизни из фронтэнда.


                                                                                                        Ну вот если вы устраиваетесь в компанию

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

                                                                                  0
                                                                                  Зайдите на популярный Patreon (хотя бы сюда), отмотайте ленту, скажем, на пару лет назад…


                                                                                  Отмотал на пару недель, открыл девтулз и увидел там, что ренедерятся все элементы, а не те которые отображаются(нет виртуального скроллинга)
                                                                                  Как эту проблему решит знание алгоритомов? Это проблема браузера и знания его api/проблем
                                                                                    +2
                                                                                    Как эту проблему решит знание алгоритомов?

                                                                                    Вообще-то это всё — самые что ни на есть алгоритмы. Другое дело, что это куда более глубокая тема, чем «просто возьми хэш-таблицу».
                                                                                      0
                                                                                      Отмотал на пару недель, открыл девтулз и увидел там, что ренедерятся все элементы, а не те которые отображаются(нет виртуального скроллинга)
                                                                                      А почему это проблема? Современные браузеры умеют «дропать» из памяти картинки, которые находятся не во viewport'е, умеют подгружать их «правильно», если они уходят из него, но близко к нему и так далее. Времена MS IE 6 прошли.

                                                                                      Проведите эксперимент: сделайте страницу с десятью тысячами картинок (вот просто картинок, без CSS и прочего), откройте её и попробуйте пролистать. Возможно для вас это будет откровением и удивлением, но её можно будет прекрасно просматривать в то время, как ваши десять тысяч картинок будут «медленно и печально» грузиться через GPRS (по крайней мере в Chrome). Firefox сейчас хуже такие вещи обрабатывает — но только вот именно загрузку страницы в которой десять тысяч картинок с самого начала присутствуют… если они туда добавляются постепенно — то и Firefox отлично всё отрабатывает.

                                                                                      При этом десять тысяч картинок — это больше, чем в ленте почти у всех авторов там.
                                                                                      Как эту проблему решит знание алгоритомов? Это проблема браузера и знания его api/проблем
                                                                                      Нет — это проблема именно знания алгоритмов. Если вы эту страницу реализуете с использованием технологий прошлого века (вот совсем прошлого века, без всяких кавычек), но, при этом, задумываясь о качестве результата — то всё будет «летать» (хотя как раз если скачать браузер прошлого века и попробовать её там открыть… эффекто может оказаться несколько другим).

                                                                                      А вот если применять хайпхайп технологии и не думать об этом… получите то, что получите.

                                                                                      P.S. И да: я не против виртуального скроллинга и вообще всячески за поддержку старых браузеров. Но это уже следующий этап! Сделайте чтобы оно, блин, не тормозило хотя бы в новых! Не можете? Ну и нечего тогда утверждать, что на «на фронтенде производительность очень редко будет упиратся в структуры данных или алгоритмы». Это не так.
                                                                                        0
                                                                                        Проведите эксперимент: сделайте страницу с десятью тысячами картинок (вот просто картинок, без CSS и прочего), откройте её и попробуйте пролистать. Возможно для вас это будет откровением и удивлением, но её можно будет прекрасно просматривать в то время, как ваши десять тысяч картинок будут


                                                                                        Но ведь проблема не в картинках, а в том, что в дом дереве постоянно рендерятся новые элементы. И если я также буду выводить 10к точек(каждая в отдельном дом-узле, в котором еще дом узел и тд) то получу туже проблему

                                                                                        Нет — это проблема именно знания алгоритмов.


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

                                                                                        Сделайте чтобы оно, блин, не тормозило хотя бы в новых! Не можете? Ну и нечего тогда утверждать, что на «на фронтенде производительность очень редко будет упиратся в структуры данных или алгоритмы». Это не так.


                                                                                        Фикс — github.com/bvaughn/react-virtualized, github.com/aurelia/ui-virtualization и тысячи их(в ванильной или же под любой фреймворк). И если на код ревью попадет самописная реализация — ее заверну. Поэтому повторюсь, каким образом знание алгоритмов поможет быстро пофиксить это(или аналогичную) проблему?
                                                                                          +1
                                                                                          Фикс — github.com/bvaughn/react-virtualized, github.com/aurelia/ui-virtualization и тысячи их(в ванильной или же под любой фреймворк).

                                                                                          Вы идеализируете сторонние решения — они не решают конкретно ваших проблем (а иногда и вообще ничего не решают), и всегда добавляют своих собственных внутренних проблем.

                                                                                          Возвращаясь к вашим фиксам, теперь у вас изначальная проблема (длинный список без тормозов) и вторая проблема (issues той либы, которую вы взяли). И хорошо, если первую проблему эта либа полностью решит — тогда вы «всего лишь» останетесь со второй проблемой. Но это не всегда бывает.

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

                                                                                          ЗЫ: Когда вы подключите 100500 библиотек и вам кто-нибудь скажет, что ваш фронт теперь неподъемен и не грузится на плохом канале — вы что будете делать? Еще одну либу подключите?

                                                                                          ЗЗЫ: Я со своей колокольни предложил бы гораздо более простой фикс: нефиг показывать на одной странице столько, что браузер начинает тупить или отжирает всю память клиента (это к вопросу о всяких virtualized-либах, памяти они жрут дай боже, и вполне реально сожрать её всю, если клиент не на ПК с кучей памяти). Добавьте пажинацию и поиск, и внезапно, вам уже не надо рендерить миллионы дивов только чтоб пользователь нашел нужное ему.
                                                                                            0
                                                                                            ЗЫ: Когда вы подключите 100500 библиотек и вам кто-нибудь скажет, что ваш фронт теперь неподъемен и не грузится на плохом канале — вы что будете делать? Еще одну либу подключите?
                                                                                            Маркетологов подключит. И они объяснят заказчику, что конфетка получается по рецепту «взять дерьма, нафаршировать дерьмом, посыпать сверху дерьмом и завернуть в дерьмо».

                                                                                            А что результат плохо пахнет — так это потому что вы неспециалист и не понимаете всех последний веяний создания фронтэндов.
                                                                                            +1
                                                                                            И если я также буду выводить 10к точек(каждая в отдельном дом-узле, в котором еще дом узел и тд) то получу туже проблему
                                                                                            Не получите. Если породите их одним приcвоением innerHTML. Или даже 10.

                                                                                            И как это поможет пофиксить проблему? Приведите, пожалуйста, пример. И оцените сколько по времени займет его имплементация.
                                                                                            Одна строка:
                                                                                            document.getElementById("mytext").innerHTML += answerFromServer

                                                                                            Не знаю сколько потребуется на реализацию — зависит от того, сколько вы бессмысленного феншуя нагенерировали на стороне сервера.

                                                                                            Но знаю, что если вы добавите таким образом мегабайтный HTML с тучей нод (пусть даже 100-вложенных) — это отработает меньше, чем за секунду. Я когда-то слышал, лет 10 назад, когда был «молодой и зелёный» о том, как создатели GMail воевали с MS IE 6, который не допускал больше 255 вложенных Div'ов (и вообще любых элементов — там, похоже, «глубина дерева» как байт хранилась). Да, были проблемы. Тормозов не было. Во всяком случае таких как мы наблюдаем сегодня.

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

                                                                                            Поэтому повторюсь, каким образом знание алгоритмов поможет быстро пофиксить это(или аналогичную) проблему?
                                                                                            Если от требования «использовать только хайп, а ещё лучше хайпхайп» отходить нельзя — то никак, конечно. Ну тут проблема не с алгоритмами. А в том, что гланды требуется вырезать только автогеном и только через задний проход.

                                                                                            В этих случаях — алгоритмы бессильны, тут уже ничего не поделать.
                                                                                              0
                                                                                              Но знаю, что если вы добавите таким образом мегабайтный HTML с тучей нод (пусть даже 100-вложенных) — это отработает меньше, чем за секунду.

                                                                                              Такой хардкор (унесем всё на бэк) в подавляющем большинстве случаев опять же даже и не нужен — мегабайты HTML и реакт какой-нибудь нагенерит, и сделает это весьма быстро (по крайней мере настолько быстро, чтоб пользователь не возмутился). Всё что тут нужно — дать возможность и реакту и браузеру спокойно отработать, не нагружая их каким-нибудь безумным маразмом типа синхронного запиливания миллионов узлов в DOM, или ненужных многократных перерисовок.
                                                                                              Конкретно для реакта — это вообще классические грабли, например: перерисовывать весь список тогда, когда нужно перерисовать один его элемент. Сначала так пишется, потому что не тормозит и вообще «ачотакова?», а потом на боевых объемах всё дохнет. И хотя в теории и туториалах этот момент всегда разжёвывается, на практике — обычно всё миллионы раз завёрнуто одно в другое («композиция круче наследования», — говорили они), и неудивительно, что в этом оберточном цирке даже и адекватный программист пропускает неадекватно большую перерисовку.
                                                                                                0
                                                                                                Возможно тут влияет руль моё первоначальное образование (математик).

                                                                                                Такой хардкор (унесем всё на бэк) в подавляющем большинстве случаев опять же даже и не нужен — мегабайты HTML и реакт какой-нибудь нагенерит, и сделает это весьма быстро (по крайней мере настолько быстро, чтоб пользователь не возмутился).
                                                                                                В данном случае речь шла о том — можно ли сделать так, чтобы без измнения вёрстки и без использования «виртуального скроллинга» сделать так, чтобы вот эта вот «бесконечная лента» не тормозила так безбожно. Ответ: да, это возможно — и, собственно
                                                                                                document.getElementById("mytext").innerHTML += answerFromServer
                                                                                                это конструктивное доказетельство.

                                                                                                Нужно ли так делать? Ну — это уже второй вопрос. Да, действительно, возможны варианты и, да, очень может быть что использование полезных либ — не будет лишним.

                                                                                                Да собственно почти наверняка оно будет не лишним: сейчас, всё-таки на дворе не 2000й и даже не 2004й год, Pentium II на 200MHz не является типичной конфигурацией, и, в общем, MS IE 6 — тоже в прошлом. А грамотное использование библиотек позволяет достичь хорошего результата быстрее. Однако, парадоксальным образом, не уменьшает необходимости знать основы!

                                                                                                И хотя в теории и туториалах этот момент всегда разжёвывается, на практике — обычно всё миллионы раз завёрнуто одно в другое («композиция круче наследования», — говорили они), и неудивительно, что в этом оберточном цирке даже и адекватный программист пропускает неадекватно большую перерисовку.
                                                                                                Но если результат — дерьмо, то зачем тогда всё это сакратльное знание, скрытое «в специфике отрасли» и почему оно должно цениться выше, чем банальное умение развернуть список?

                                                                                                Увы, абстракции текут — и ничего с этим поделать нельзя.
                                                                                                  0
                                                                                                  Но если результат — дерьмо, то зачем тогда всё это сакратльное знание, скрытое «в специфике отрасли» и почему оно должно цениться выше, чем банальное умение развернуть список?

                                                                                                  Если результат приносит деньги — он не дерьмо. Наверное тут тоже играет роль моё образование (экономист, пусть и с программерским уклоном). Здесь мы как раз приходим к «если это всё говно, но тем не менее приносит прибыль, то почему бы и не продолжать в том же духе». Не говно будет еще больше прибыли приносить? Очень даже вероятно, но его сначала надо сделать, и потратить на это какие-нибудь большие деньги (потому что из «быстро, дешево, качественно» тут придётся поступиться именно «дешево»).

                                                                                                  Вот именно поэтому кодер, который как-то там смог в реакт на уровне «почитаю Дэна и сделаю всё как пишут» для бизнеса часто интереснее того, кто знает, как сделать всё хорошо, правильно, и без явных и скрытых проблем — но и стоит дороже, да и еще дополнительно требует дорогой же команды, потому что первоначальные трудозатраты на качественные решения — существенно выше первоначальных затрат на говнокод.
                                                                                                    0
                                                                                                    Наверное тут тоже играет роль моё образование (экономист, пусть и с программерским уклоном).
                                                                                                    Ну эконмисты разные бывают. Некоторые всерьёз верят, что в замкнутой подсистеме можно создать безконечно расширяющаюся подсистему.

                                                                                                    Очень даже вероятно, но его сначала надо сделать, и потратить на это какие-нибудь большие деньги (потому что из «быстро, дешево, качественно» тут придётся поступиться именно «дешево»).
                                                                                                    Как раз этот вариант и невозможен. Бизнес очень-очень часто хочет «быстро и качественно» (и обычно, хотя и не всегда, даже готов за это платить). Но получает всегда «быстро и плохо». Потому что качественный софт создаётся десять лет. Ну или не создаётся — ну это если его некому создавать.

                                                                                                    Не говно будет еще больше прибыли приносить?
                                                                                                    «Не говно» будет кому-то нужно через десять лет. Про говно все забудут.

                                                                                                    Если ваш горизонт планирования — два-три года, то вам ни алгоритмы, ни качественные разработчики, на самом деле, не нужны. Пролема в том, что сейчас, на волне хайпа, даже компании, которые не собираются «хапнуть и разбежаться» через пару лет — тоже покупаются на обещания «серебрянной пули».

                                                                                                    Вот именно поэтому кодер, который как-то там смог в реакт на уровне «почитаю Дэна и сделаю всё как пишут» для бизнеса часто интереснее того, кто знает, как сделать всё хорошо, правильно, и без явных и скрытых проблем — но и стоит дороже, да и еще дополнительно требует дорогой же команды, потому что первоначальные трудозатраты на качественные решения — существенно выше первоначальных затрат на говнокод.
                                                                                                    Я с этим где-то спорю? Наоборот — я ж токо за! Однако. Вся ветка началась с ответа на вот эту реплику
                                                                                                    Лучше учится писать качественный, а не производительный код. Лучшее враг хорошего, а преждевременная оптимизация зло.

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

                                                                                                    По моему дискуссия себя давно исчерпала: кажется все согласны с тем, что если ваша цель — дешёвый код (пусть и дерьмовый), то отказ от знания алгоритмов и структур данных и многих других «излишеств» — оправдан. Меня просто покоробило предложение писать «качественный, а не производительный код» опираясь на то, что «производительность очень редко будет упиратся в структуры данных или алгоритмы». Это притом, что мы видим везде и всюду как именно это она и делает.

                                                                                                    Ну вот нет у фронтенда никакой специфики. Вы можете в банальной утилите поиска подстроки в файле создать процедуру сравнения букв без учёта регистров, добавить пару индирекций — и получить такое же замедление, как ваши классические грабли с перерисовкой всего списка, вместо одного элемента. А можете в билд-системе устроить O(N²) — ровно по той же схеме.

                                                                                                    Потому если вас волнует качество результата — вы должны уметь «в алгоритмы и стурктуры данных». Если нет — то нет.

                                                                                                    Вот только почему-то у разработчиков в других областях эта банальщина не вызывает отторжения, а фронтэндеры — воспринимают эту банальную истину «в штыки».
                                                                                                      0
                                                                                                      Как раз этот вариант и невозможен. Бизнес очень-очень часто хочет «быстро и качественно» (и обычно, хотя и не всегда, даже готов за это платить). Но получает всегда «быстро и плохо».

                                                                                                      О нет. Этот вариант очень даже возможен в огромном количестве случаев, просто бизнес часто очень плохо представляет, насколько дорого это всё выйдет. Ну и да, конечно же, вещи с некоторого уровня сложности и выше имеют свою цену не в деньгах или не только в деньгах. Не всё параллелится, не всё делается с первого раза, да и всегда есть досадная загвоздка в виде невозможности нарушить законы физики, даже если залить это всё деньгами.

                                                                                                      «Не говно» будет кому-то нужно через десять лет. Про говно все забудут.

                                                                                                      А если еще точнее — некоторое отдельное «не говно» будет кому-то нужно и через десять лет. Множество другого, не менее хорошего «не говна» всё равно не будет нужно. Нужность через N лет не определяется качественностью, качественность тут — всего лишь одно из необходимых, но не достаточных условий.

                                                                                                      ЗЫ: Ну и да, я согласен, что ветка комментов себя исчерпала — я еще где-то выше сказал, что комментировать вот это вот «производительность будет очень редко упираться в структуры данных или алгоритмы» я считаю излишним; это ж просто глупость написана. Многие места в UI упираются в производительности в юзера, но никакой даже очень примитивный UI никогда полностью не упирается в производительность юзера (вторая сторона, сам код, тоже как бы должен отрабатывать). На счётах тоже считают со скоростью юзера, но если счёты у вас заржавеют, то проблема будет не на стороне юзера.
                                                                                            +1
                                                                                            Проведите эксперимент: сделайте страницу с десятью тысячами картинок (вот просто картинок, без CSS и прочего), откройте её и попробуйте пролистать. Возможно для вас это будет откровением и удивлением, но её можно будет прекрасно просматривать в то время, как ваши десять тысяч картинок будут «медленно и печально» грузиться через GPRS (по крайней мере в Chrome).

                                                                                            Проводили такой эксперемент… Не прекрасно там ничего, и картинок там было меньше десяти тысяч, и комп был нормальный, на нём видео обычно рендерят, и браузеры разные были, и человек, писавший это является ярым противником js, и было это год назад… Пока оно всё грузилось, а оно реально долго грузилось, потому что фото были хорошие, наваристые, страницу прокручивать было просто невозможно. И фоточек там была наверное тысяча. Как ни странно, но JQ + lazy load решили все проблемы разом, потому что не надо было эти самые картинки грузить и пытаться их отрисовывать кусками, уже пришедшими с сервера.

                                                                                              –1
                                                                                              Возможно. Спорить не буду. В любом случае грузить гигабайт данных, когда об этом не просят — попросту некрасиво. Но вопрос-то был о другом: необходим ли для отзывчивости этой страницы «виртуальный скроллинг» или достаточно грамотного кодинга? Ответ: грамотного кодинга — достаточно. Но его нет. В этом беда.
                                                                                              0

                                                                                              Однажды проводил похожий эксперимент. В тот раз я попытался понять, почему же тормозит Хабр на страницах с кучей комментариев. Я нажал "Ответить", открыл инструменты разработчика, и начал снимать с поля ввода все подозрительные обработчики событий.


                                                                                              Так вот — когда я снял все, тормоза не исчезли. Дальнейшее исследование показало, что тормозит сам браузер: при вводе любого символа он считал, что размеры textarea могли измениться, и бросался делать всему дереву DOM повторный layout и render.


                                                                                              Ну и чем тут могли помочь алгоритмы, "правильная" работа с HTML и прочее? Да ни чем, единственный способ предотвратить тормоза без переписывания браузера — просто не показывать столько комментариев на странице одновременно...

                                                                                                +1
                                                                                                Ну и чем тут могли помочь алгоритмы,

                                                                                                Ещё как могли. Только не вам, а разработчикам браузера. Меня, например, откровенно коробит, что моя современная машина с кучей ядер, гигагерц и гигабайт тормозит на такой ерундовой задаче, как рендеринг пары тысяч абзацев. Почему двадцать с лишним лет назад Pentium-233 не тормозил при наборе документа в полторы сотни страниц со встроенной графикой в Word'е, и ему для этой задачи хватало аж нескольких мегабайт, а современный браузер уваливается, и жрет сотни мегабайт или даже гигабайты? Ах, да, ещё и сам Word при этом занимал метров 30, и разрабатывался даже меньшей командой, чем современные браузеры.
                                                                                        0
                                                                                        У меня вот в проекте есть места, на которых скорость начала сдавать за счёт сильного увеличения количества элементов, которые надо получить с бэка, а потом отрисовать. Я уверен, что можно получить некоторый прирост за счёт структуры данных. Но. В некоторых случаях, по итогам анализа удалось сократить время ожидания за счёт сжатия данных на бэке. В некоторых случаях удалось оптимизировать скорость работы за счёт перевода пагинации с фронта на бэк, грузя за раз N элементов. Селект с поиском, в котором отрисовывались N элементов, тоже начал тупить, когда N подросло с пары сотен до нескольких тысяч — и проблема прекрасно решилась выносом автокомплита на бэк. Это всё — реальные куски работающей системы, периодические проблемы которые возникают в работе. И решаются они в каждом конкретном случае — разными способами, наиболее подходящими в данном случае. Бывает, конечно, что и на бэке перестаёт хватать скорости обработки данных. Например, у меня в одном пет проекте прототип на php работал несколько минут над хорошей такой кучей взаимно перелинкованных объектов, которые надо было обойти по несколько раз вложенными циклами. Структура данных для коллекций в php одна — называется массивом, а по факту является хэш-словарём. И что там оптимизировать? Возможно, я бы смог переписать алгоритмы и добиться ускорения в два-три раза… Но я ускорил этот кусок кода в сотни раз, просто переписав его на Go.

                                                                                        И да, признаюсь, я не знаю как составить самостоятельно связанный список. Пока ни разу не понадобились такие навыки, понадобятся — пойду и прочитаю как это делается.
                                                                                        0
                                                                                        Не будем забывать что в js "настоящего" связного списка нет, он будет делатся через объект(который хеш таблица).

                                                                                        Начиная с V8 небольшие объекты — больше не хеш-таблицы, а записи (благодаря скрытым классам). А теперь уже все основные движки так умеют.

                                                                                      +4

                                                                                      Список — самая простая рекурсивная структура данных, и на нем удобно учиться мыслить формально рекурсивно.


                                                                                      И, кстати, список — это вполне формально в некотором смысле самая простая структура данных, так как это свободная монада. Но это уже совсем другая история.

                                                                                        –1
                                                                                        уточните, кандидат на должность по какому языку?

                                                                                        Python


                                                                                        Например, зачем мне на python или javascript знать как организовывать связанные списки(за исключением саморазвития и расширения кругозора)?

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


                                                                                        Во-вторых, иногда и на высоком уровне приходится использовать базовые структуры данных. Реальная продуктовая задачка: для подготовки данных необходимо применить цепочку преобразований. Элемент a заменить элементом b, элемент b элементом c, элемент h элементом g и т.д. Для каждого элемента цепочка преобразований образует односвязный список. А цепочки эти комбинируются из различных источников и, чтобы исключить ошибку, перед применением необходимо проверить их на валидность – удостовериться, что в них нет циклов. А если есть, то либо целиком откинуть такую цепочку, либо поднять информативную ошибку.


                                                                                        Ни одна стандартная структура данных Python здесь не поможет, библиотек для такой фигни никто не станет писать. Но, понимая структуру данных и зная алгоритм, можно за 5 минут накидать его в несколько строк.


                                                                                        И это простейший пример. Гораздо чаще возникают деревья и графы.

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

                                                                                          Цепочка преобразований скорей всего будет записана через таблицу замены. Проверка на исключение циклов — это к алгоритмам, а не к структурам данных.
                                                                                          Графы и деревья в условиях скриптовых языков точно так же будут записаны через структуры Hash\Map. И это точно не является типичной задачей для фронтенда\веба.

                                                                                          Вопросы на структуры данных и алгоритмы в современных реалиях строго под специфику разрабатываемого продукта.
                                                                                            +1
                                                                                            Как тут поможет односвязный список? Вам придётся его эмулировать на имеющихся стандартных типах, что даст только оверхэд на эмуляцию.

                                                                                            Можно эмулировать, можно и не эмулировать.


                                                                                            @dataclass(frozen=True)
                                                                                            class Node:
                                                                                                next: 'Node'
                                                                                                value: T

                                                                                            Проверка на исключение циклов — это к алгоритмам, а не к структурам данных.

                                                                                            Алгоритмы и структуры данных настолько тесно связаны, что говорить о них отдельно совершенно не имеет смысла.


                                                                                            Графы и деревья в условиях скриптовых языков точно так же будут записаны через структуры Hash\Map.

                                                                                            Ну почему же? Я вот так всегда деревья записываю:


                                                                                            @dataclass(frozen=True)
                                                                                            class Node:
                                                                                                left_child: 'Node'
                                                                                                right_child: 'Node'
                                                                                                value: T

                                                                                            это точно не является типичной задачей для фронтенда\веба.

                                                                                            Человек спросил про Python / JavaScript, а не про фронтенд. В статье тоже ничего конкретно про фронтенд. Мы же с вами не фронтендщиков обсуждаем, а программирование в целом. И в программировании довольно часто появляются задачи, связанные с графами и деревьями. В backend и data science особенно.

                                                                                              –1
                                                                                              … а еще можно через массив\список\кортеж, и тогда ссылки — это индексы в нем.
                                                                                                –1
                                                                                                Всё таки сильно зависит от области работы. В моём backend за 7 лет ещё ни разу не было необходимости вручную ворочить списками\деревьями. Там где есть хоть какие то объёмы данных, в дело вступают базы данных (тут скорее задачка, правильно выбрать индексы).

                                                                                                Могу ошибаться, но кажется системщики, сетевеки, разработчики драйвером, криптографы и прочая братия тоже не слишком часто сталкиваются с необходимостью реализовать структуры данных вроде деревьев\списков, а вот других специфичных особенностей там будет навалом.
                                                                                                  0
                                                                                                  Да нет, сталкиваемся довольно часто. На самом деле, в ядре уже есть примитивы для одно- и дву- связных списков, rbtree и других чудес алгоритмики. Но примитивы довольно таки тонкие, поэтому все равно надо хотя бы представлять как оно там внутри устроено.
                                                                                                    +2
                                                                                                    Всё таки сильно зависит от области работы.

                                                                                                    Пожалуй.


                                                                                                    Три примера из моей области:


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


                                                                                                    2) Для поиска похожих фильмов удобно использовать граф, где рёбрами будут метаданные и скоры из различных моделей. На таком графе затем запускается процедура оптимизации, считающая степень похожести.


                                                                                                    3) Ансамбли деревьев решений – мощные алгоритмы машинного обучения, но скорость предсказаний у них оставляет желать лучшего. Поэтому мы пишем компилятор таких деревьев в нативный код. Для этого, естественно, в памяти необходимо построить некое абстрактное представление таких деревьев, которое затем может быть оптимизировано и скомпилировано.

                                                                                                      +1

                                                                                                      Распределенные системы и криптография. Задачи с деревьями, хитрыми структурами данных вроде crdt, фильтров Блума часты, если не повседневны.
                                                                                                      Однако, я не считаю, что даже в эту область обязательно проверять знания вроде написания своих списков. Пришедший кандидат может оказаться полезен во множестве других задач.

                                                                                              0
                                                                                              И тут такой момент если вы таких кандидатов отсеиваете, то откуда знание в чем они разбираются и что умеют?
                                                                                                +1

                                                                                                После собеседования даём тестовое и потом смотрим корреляцию результатов и присланного кода.


                                                                                                Честные эксперименты проводить, конечно же, очень дорого.

                                                                                                  0

                                                                                                  Думаю такой подход даёт максимум информации без затрат денег. Просто предположил что вы используете только вопросы для фильтра.

                                                                                                0
                                                                                                Не уверен, что понял правильно, не знаю языка, но выглядит, как одна и та же проверка внутри цикла. x же не меняется? Действительно, сферическая неэффективность в вакууме
                                                                                                  0

                                                                                                  Ну я опечатался, там y in xs должно быть.

                                                                                                  0
                                                                                                  Какое бурное обсуждение односвязного списка. Что обсуждать и какие алгоритмы связанные с ним? Элемент такого списка имеет способ получить следующий, если он не последний. А что с полученным элементом делать, к односвязным спискам никакого отношения не имеетю
                                                                                                  +6

                                                                                                  А еще эта задача внезапно становится интересной в случае программирования на Rust.

                                                                                                    0

                                                                                                    А что там в Rust?


                                                                                                    Я как ближайший по наркомании аналог беру хаскель — так там обычная свёртка слева с аккумулятором, ровно n действий (в отличие от наивного reverse (x:xs) = reverse xs ++ [x] за n²).

                                                                                                      +3

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

                                                                                                        0

                                                                                                        А, хм. Интересно, да. Надо попробовать написать на идрисе с линейными типами.

                                                                                                          0
                                                                                                          Скорее всего это тот самый случай, когда надо писать «небезопасно»
                                                                                                            0

                                                                                                            unsafe не отключает borrow checker. Хотя… если использовать «сырые» указатели, то может быть и можно что-то замутить, но тогда уж проще этот список на старой доброй сишечке написать :)

                                                                                                          +5

                                                                                                          А в Rust если хочется написать односвязный список лучше сразу перестать хотеть

                                                                                                        +5
                                                                                                        Хм, кстати интересный вопрос: а много ли программистов, скажем от миддлов и выше, которые не знают как развернуть связный список?
                                                                                                        Кому не сложно: если вы не знаете, на уровне алгоритма/псевдокода как это сделать, расскажите, на каком языке вы пишете, какими проектами занимаетесь? Ну или, предположим у вас есть знакомый, который не знает как развернуть список, расскажите о нем.
                                                                                                          +4
                                                                                                          Спутникостроение, роботостроение, всякая низко(и очень низко) уровневая дичъ. Очень давно не проходил собеседование, обычно зовут меня, а я ленив чтобы сам искать. Не знаю даже смогу ли.
                                                                                                          Но точно спрошу, что простите вы хотите со списком сделать? После чего видимо буду забрит как безперспективный дед =)
                                                                                                            0
                                                                                                            Интересный случай у вас. Но, да, наверное, с таким ответом откажут
                                                                                                              +5
                                                                                                              Но при этом это не имеет никакого отношения к квалификации и к знанию Си и структур данных. Всего лишь к знанию терминологии собеседованй. Мне пришлось погуглить чтобы понять что вы об изменить направление связей односвязного списка.

                                                                                                              Связный список в общем случае не надо разворачивать. Связный список можно развернуть в массив, если считать «развернуть» синонимом «распаковать» а не «повернуть». А возможно речь вообще о Развёрнутых связных списках.

                                                                                                              Если же исходить из задачи поменять направление — то логичный ответ — зачем? Если мне зачем-то нужно развернуть односвязный список — то я наверняка что-то делаю неправильно.

                                                                                                              Вообще это отдельная история — терминология собеседований. У вас есть best practices и есть их названия. И если ты не знаешь названия — считается что ты не используешь практику, а если знаешь — то используешь. Что имеет весьма отдаленное отношение к реальности.
                                                                                                                0
                                                                                                                Окей, возможно, терминология сбивает. Но, предположим вам бы предложили задачу в ясной формулировке, типа:
                                                                                                                преобразовать список
                                                                                                                a->b->… ->d->null
                                                                                                                в
                                                                                                                d->… ->b->a->null
                                                                                                                , ответили бы на уточняющие вопросы по формулировки. При этом вы бы были мотивированы пройти это собеседование. Вы бы смогли придумать алгоритм/написать псевдокод?
                                                                                                                  0
                                                                                                                  Да конечно, я тоже уверен что любой мидл должен быть в состоянии эту задачу решить не задумываясь. Да и любой джун если он планирует писать на чем-то типа C/C++

                                                                                                                  Конечно извиняюсь что ответил на заданный вопрос, а не на подразумеваемый, хотя подразумеваемый и был очевиден, но так просто захотелось сказать, что ответ может быть «не смогу» не только из за квалификации.
                                                                                                                    0
                                                                                                                    я бы предложил использовать двунаправленный список и не париться :-D
                                                                                                                    но вот подумав минуту, я чтото не придумал быстрого и при этом безопасного алгоритма. Единственно что приходит в голову — использовать стэк, заполнив его адресами элементов и потом сформировать новый список.
                                                                                                                      0
                                                                                                                      но вот подумав минуту, я чтото не придумал быстрого и при этом безопасного алгоритма.
                                                                                                                      Что значит «безопасного» в данном случае???
                                                                                                                        0
                                                                                                                        ну можно использовать рекурсию и попасть на Stack Overflow)
                                                                                                                        +1
                                                                                                                        Ок, не проблема. Дополнительное ограничение (типичная штука для таких задачек): памяти у вас на это нет. Вот есть у вас список в 3Гб и больше нет ни ОЗУ, ни адресного пространства в товарных количествах.
                                                                                                                          –2
                                                                                                                          ну ок, если у нас есть практическая задача, где приходится разворачивать список, то я бы изначально использовал двунаправленный список) это было бы быстрее, а +4 байта на элемент — не так и много) если же 4 байта на элемент — много, т.е. элементы маленькие, значит опять архитектурный косяк — надо было изначально использовать массивы либо динамический массив динамических массивов, если конечное количество данных непредсказуемо)
                                                                                                                          т.е. задача разворота однонаправленного списка — изначально из разряда сферического коня в ваккуме. Хотя нет, для времен, когда данных было мало, памяти 512 кб, а максимальный размер сегмента памяти 64 кб, идея со списками была неплоха)
                                                                                                                            +1
                                                                                                                            Если есть память на пару указателей, задача тривиальна — запоминаешь указатель на предыдущий и следующий элемент и меняешь их местами. Тут даже спрашивать написать код необязательно, достаточно на доске нарисовать список из трёх элементов и проиллюстрировать что происходит на каждом шаге цикла.
                                                                                                                              +2
                                                                                                                              я бы изначально использовал двунаправленный список) это было бы быстрее
                                                                                                                              Нет, не было бы. Скорость будет примерно равная, либо в пользу односвязного если упрется в кеш.
                                                                                                                    +2
                                                                                                                    О_о нешто же такой длинный ответ было написать быстрее, чем в течение нескольких секунд быстро представить в голове хотя бы пару принципиальных ответов?
                                                                                                                    +2
                                                                                                                    Ох ты ж. Когда то, во время учебы ворочал этими списками без проблем. Потом использовал в своих домашних поделках иногда, причем, больше «из любви к искусству» чем из-за необходимости. Но фразу «развернуть связный список» пришлось гуглить, т.к. зачем такое может понадобиться не представляю. Потому как звучит из разряда «как же я цифры буквами напишу».
                                                                                                                      0
                                                                                                                      А в какой области вы работаете, если не секрет?
                                                                                                                        0
                                                                                                                        Работал в области продаж компьютерной техники (была такая сеть Polaris), в области строительства (обработка и визуализация инфы со всяких датчиков в зоне ведения работ — графики, 2D, 3D), в области логистики, сейчас работаю над проектом федерального уровня (заказчик системы — государство).
                                                                                                                        Ну и на всякий случай, чтобы «два раза не вставать», образование — «прикладная математика».
                                                                                                                        0
                                                                                                                        зачем такое может понадобиться не представляю

                                                                                                                        Ну самое простое — чисто функциональная очередь, например, с амортизированными константными вставками и удалениями.

                                                                                                                          0
                                                                                                                          вот один раз было надо написать такое, плюс чтобы одновременно было несколько писателей (и чтобы при этом не лочить всю очередь).
                                                                                                                          Но действительно, нечасто и в весьма низкоуровневом коде…
                                                                                                                        +5
                                                                                                                        Хм, кстати интересный вопрос: а много ли программистов, скажем от миддлов и выше, которые не знают как развернуть связный список?

                                                                                                                        В СНГ процентов 99%.
                                                                                                                          0
                                                                                                                          В СНГ процентов 99%.

                                                                                                                          Ну, выглядит как серьезное преувеличение.
                                                                                                                            +5
                                                                                                                            Отбросьте Яндекс и может еще пару компаний. В остальных без подготовки развернет список только случайный человек. Просто потому, что этого не спрашивают на собеседованиях, это не нужно в работе.
                                                                                                                              0

                                                                                                                              То есть это не нужно спрашивать?

                                                                                                                                0
                                                                                                                                Я такого не говорил. Я как раз за алгоритмические вопросы, структуры данных и задачи на доске на собеседованиях.
                                                                                                                                  +3
                                                                                                                                  Скользкий конечно момент нужно ли спрашивать то, что не будет нужно от кандидата. От того в каждом посте про алгоритмы сплошной холивар. Спор ли это на тему плоских или конусообразных кто знает.
                                                                                                                                • <