Комментарии 28
Статьи рассчитаны на разработчиков, которые уже знакомы с дженериками, работали с массивами/множествами/словарями, разбираются в отличиях классов от структур и делают вид, что понимают рекурсию.
неа, основные непонятки с этим странным SWIFT и употреблением weak или с утверждением
копирование необходимо если сильных ссылок больше одной
и почему вы пытаетесь копировать если надо после каждого действия со списком и думаете что там будет O(1)?
и почему сразу двойной связный список
и вообще почему вы представляете в обьектном виде, а не связный список из индексов (int) на обычный массив…
По поводу необходимости копирования: если на первый контейнер нашего списка ссылается кто-то еще (копии нашей структуры), то нам необходимо создать новый экземпляр списка и работать с ним иначе изменения нашего списка отразятся на всех его копиях. Контейнеры же ссылочный тип.
Сразу двойной связанный список, потому что мы здесь не в игрушки играемся! Простых примеров в интернете полно.
На самом деле у меня к реализации есть замечание:
Меня смутил WeakReference а ровном месте. То есть протокол принуждаем людей сразуже использовать weak ссылку, а не просто получить первый элемент — что обычно и хочется.
Все это ради Copy-on-write?.. ну а я сделаю вот так: let node = list.first.node то есть решение еще и не назовешь надежным. А потом так: let node = list.first.node.next и поведение резко изменится.
Но давайте учить людей правильно — внешний интерфейс всегда важнее технических проблем. А в данном случае техническая проблема решается легко, да и делает использование надежней:
struct LinkedList<T> {
private class Reference { }
private var ref = Reference()
...
}И вот этой переменной уже можно пользоваться, для получения количества копий именно структуры. При изменении смотрим количество ссылок, и если больше одной, то делаем тоже самое + пересоздаем переменную (дабы каждый раз не копировать).
P.S. ну и я закрываю глаза, на тот факт, что никто не мешает получить node и поиграться таким образом, что весь лист будет сломан — у Node то нет полей доступа, аля private(set)
P.P.S. не знаю почему, но ваша статья меня привлекла — рассказано в самом деле хорошо. Да и LinkedList я тоже люблю — на нем много какие особенности языка всплывают.
Может быть посоветуете как можно элегантно закрыть доступ к модификации содержимого контейнеров, но так чтобы внутри класса LinkedList логика не изменилась? Всем классом сидим голову ломаем и никаких результатов.
К сожалению это решение в данном случае наиболее предпочтительное — не пораждает лишних абстракций.
Но можно сделать протокол который бы имел только getter-ы, и отдавать не экземпляр уже класса, а экземпляр этого протокола во всех методах.
Плюсы первого решения: Не пораждает лишних абстракций, нельзя обойти.
Минусы первого решения: Все в одном файле.
Плюсы второго решения: Можно разделить на файлы.
Минусы второго решения: Лишняя абстракция, легко обходится оператором as.
Таковы реалии swift и иногда не хватает дружественных классов из С++. В данном случае хранить эти объекты в одном файле ничего критично не имеет, но иногда это усложняет чтение кода, но поделить нельзя — так как хочешь закрыть реализацию.
P.S. Есть третье решение — выделить все в отдельный модуль/проект. Тогда у свойств может быть модификатор доступа: public internal(set) и все проблемы уходят.
" var value: T { get }"
то получившийся протокол мы как тип использовать не сможем. Не параметром передать ни рекурсивно сослаться.
Диванные эксперты без пруфов утверждают, что реализовывать необходимо через inderect enum, забывая про его value-type природу. Даже если чудом реализовать через inderect enum, то мы получаем сложность О(n) на любые операции добавления/удаления элемента в список. Класс-контейнер даёт нам O(1) практически на все операции, если нет необходимости копировать структуру.
Начал писать код в комментарии, и вспомнил что да на самом деле использовать Node как протокол не получится.
Про indirect enum: https://www.hackingwithswift.com/example-code/language/what-are-indirect-enums.
Реализовать так можно (отбросим вопросы про удобство использования в сторону), и оно будет работать.
Но:
- Само по себе работать с этим сложнее, в силу необходимости работать в обратном порядке.
- Двухсвязный список не реализуем в такой концепции.
- (value-type) Замена элемента в середине списка не возможно за O(1). И дело не в копировании даже. Список уже сформирован — когда меняется центральный элемент, список не меняется сам по себе — меняется всего один элемент. Для замены элемента нужно ручками снова пройти все элементы и обновить их.
Простой пример:
var node2 = node.next!
var node3 = node.next!.next!
var node4 = node.next!.next!.next!
node2 = LinkedListItem.linkNode(value: -1, next: node4)
var currentNode = node
// ЦиклВ этом примере -1 не будет выведен.
Итог понятен — LinkedList через indirect enum (или struct), не будет являются LinkedList ибо не имеет его преимуществ. С тем же успехом (и даже лучше) можно просто все запихнуть в массив.
1. Почему Avito и Yandex? Я ничего против них не имею, но полно и других.
2. Когда я собеседовался в Yandex на iOS, то меня почему-то спрашивали именно те вопросы которые попали в категорию «так себе перспективы»
3. Почему вдруг эти вопросы плохие? Мне на собеседованиях один кандидат из 20 способен не только сказать заученную фразу, но и на практике доказать, что он понимает её… остальные не способны без компилятора сказать, что напишет код из 5 простых строчек и как поведение меняется в зависимости от типа.
Про Solid промолчу — не люблю этот вопрос, и не обращаю внимание если человек не знает что это, но когда люди говорят, что знаю… см начало пункта.
А ну и замечание по коду — писать ‘guard a != b else’ это кощунство над людьми которые будут читать — два отрицания за место обычного: ‘if a==b’.
P.S. с тем что знание алгоритмов полезно я соглашусь. Правда стоит начать с более важных вещей, например что такое словарь, массив, множество — сложность операций, как реализовано в iOS. Вроде бы этим пользуются каждый день, но как устроено мало кто знает.
- Я ждал вопроса «почему яндекс?!». Выбор пал на эти компании, потому что они известны своими «сложными» и долгими отборочными этапами. Разговоры о престижности и тд это все очень субъективно.
- «Так себе перспективы» это не всегда о компании в целом. Даже в яндексе найдутся команды, где работать скучно и платят меньше.
- То-то и оно! Если у Вас в сторе 20 проектов, 5 лет опыта работы над проектами с многомиллионной аудиторией, а у Вас спрашивают вопросы для отсева полных новичков, то тут два варианта. Первый — вам не верят, второй — вас собеседуют по вопросам из интернета.
- Про if и guard это все субъективная вкусовщина.
3) Ну… я лично бы не верил. Я даже себе на собеседовании бы не верил :).
И встречал людей с N проектами N лет опыта, но которые не понимаю разницы между этими всеми вещями, даже на базовом уровне.
Хотя меня тоже бы расстроили подобные вопросы на собеседовании, но только если не было бы развития вопроса в глубь. Например вопрос "отличие reference type от value type" — хороший. На него ответит junior и senior по разному, и сломаются они на разных стадиях развития этого вопроса. Ибо к нему потом сверху идут weak/unowned/strong, захват, замыкания, аналоги в obj-c. Короче тема хорошо развивается, и если человек на самом деле крут, то доходит до разговора — а как это внутри устроено.
4) Ну в общем счете да, и я даже не настаиваю как писать. Но люди так пишут до тех пор пока не ошибутся в этом условии по несколько раз, хотя кто-то продолжает так писать.
guard let читается легко и это его назначение — разворот области видимости, а guard без let имеет по факту отрицание в себе, и если условие с отрицанием, да еще и не одно условие, то начинаются серьезные проблемы.
В прочем если отстранится от swift то guard без let по стилю мышления похож на assert.
Не знаю как кто, но я еще не видел людей которые бы assert-ы всегда писали с первого раза верно — в них часто условие при написании инвертят, и позже исправляют.
Хотя разговор в этом плане похож на табы vs пробелы :) Так как есть человек с самого первого дня пишет на swift с guard, то ему будет одинаково легко читать как guard так и if.
Такой код становится не очевидным и менее читабельным, но если ты сам на проекте, можно писать хоть ногой. Например, через switch.
А где же тесты?
На самом деле соглашусь с утверждением, про двусторонний список. Но тут оно оправдано — removeLast не удалось бы реализовать за O(1) без двухстороннего списка, и при таком способе реализации.
Сразу добавлю к другой части вашего комментария, так-как по теме:
и вообще почему вы представляете в обьектном виде, а не связный список из индексов (int) на обычный массив…
Думаю в силу того, что реализуется "связный список", у которого одно из преимуществ "структурная гибкость" (взял из вики). Что на практике всегда выражалось тем, что можно выделить память под все свои элементы почти всегда, в отличии от массива на который памяти не будет в силу фрагментации.
А вот почему не нужно его всегда копировать, при попытке изменить содержимое, если есть несколько ссылок на список не совсем понятно. Да возможно компилятор языка это делает чуть умнее, и учитывает некоторые другие особенности (не буду утверждать — ни разу не смотрел какие оптимизации там есть на этот счет). Но автор не влазил в работу компилятора, и реализовал вариант, который работает согласно принципу copy-on-write, хоть и было кривенько реализовано.
Возможно некоторые аспекты в статье на самом деле не аргументированы, но думаю автору который говорит про "школу" можно такое простить… Яб даже сказал, я удивлен, что в школе учат swift, в прочем как и любой другой язык...
P.S. Про сложность — если учитывать copy-on-write, и тот факт, что память надо иногда перевыделять, то у apple во всей документации описание сложности не верное. Ведь даже добавление элемента в конец массива, не всегда O(1) — иногда надо сделать realloc, что требует некоторого времени. Иногда realloc требует O(N), если вдруг память идущая дальше уже занята.
Структуры данных с примерами на языке Swift. Часть первая: связаный список