Здравствуйте, Undying, Вы писали:
U>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>Ты, видимо, ничего не понял, либо я плохо объяснил. То, что элементы лежат в массиве не значит, что их порядок совпадает с порядком следования в массиве. Это полноценный список со всеми его плюсами и минусами.
U>А в чем тогда смысл использования? Как я понимаю, список может оказаться наилучшим решением, когда производительность вставок в середину важна, а скорость прохода по коллекции нет. Вроде и полилинии, и проводники, и контуры полигонов намного чаще обходятся, чем изменяются. Минусом же является и производительность и усложнение кода — рекурсию сложнее читать чем циклы. Соответственно непонятно в чем выгода от использования списков для решения этих задач.
Почему именно список?
Списки я использую для хранения отношения "многие ко многим". Проводники состоят из сегментов, полигоны — из вершин (или сегментов, зависит от задачи) и т.д.
Количество элементов часто меняется — сегменты могут подразбиваться, объединяться, переходить из одного проводника в другой.
А как ты верно заметил, главный (+) списка — возможность быстрой вставки в середину, достаточно поправить значение поля Next.
Для добавления нового элемента не надо сдвигать все элементы массива, достаточно новый элемент добавить в конец и настроить ссылки на него. Это при условии, что свободных ячеек нет. Если они есть, то достаточно вынуть индекс вакантной позиции из одного списка и вставить в другой.
При всем этом редактировании необходимо сохранить идентификаторы сегментов, поэтому хранение в традиционном массиве непригодно — добавление элемента в середину потянет перестраивание связей между объектами.
Хранение каждого объекта независимо, как в учебнике (Объект "полигон", внутри массив вершин) неприменимо, т.к. во-первых дорого, а во-вторых необходимо, чтобы была однозначная идентификация объекта и связь его с коллекцией с минимальными накладными расходами.
Теперь о моих структурах.
Их придумал не я, в gamedev'е они применяются со времен DOS. Правда в литературе что-то подобное я встречал только в книжке Ульмана 80-х годов.
Достоинства: все данные лежат плотно и обычно целиком попадают в кеш процессора. Т.е. прыгать по такому списку получается быстрее, чем по "традиционному". Накладные расходы на выделение памяти сокращаются. Бинарная сериализация выполняется моментально, т.к. записывается не каждый элемент по отдельности, а весь массив за один вызов.
Если требуется для каждого элемента списка построить временные данные, то с традиционным списком возникают проблемы — как связать элемент списка с данными. В моем списке это решается элементарно — строится массив с размером, разным числу элементов списка. Получается отношение 1:1 без всяких хешей.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, gandjustas, Вы писали:
G>>>99% смогут написать разворот списка имея компьютер и час времени. Обход дерева — 4 часа, ни раз не писав обходы до этого.
PD>>Я, конечно, извиняюсь, но о каком дереве речь идет ? Если об обычном двоичном дереве, то 4 часа — гм... Примерно по строчке в час получается.
G>Ключевое выделено.
Тогда уж добавь — "никогда не слышавший про деревья". Как можно хоть что-то знать про деревья и не знать про самый простой алгоритм в дереве — не понимаю.
А если он и впрямь о них никогда не слышал — так учиться надо. Впрочем, изучение темы двоичных деревьев с нуля и до способов обхода едва ли и в этом случае потребует 4 часов. Максимум час.
Здравствуйте, Undying, Вы писали: U>Дерево это другая структура данных.
Да тоже самое. Только листьев больше чем 1.
U>Не понял. Зачем для того, чтобы понимать, что многократное сложение при последующем делении может привести к переполнению, знать что "умножение в двоичной системе счисления считается через цикл и сдвиг"? Первое со вторым вообще не связано.
Потому, что нет в компьютере десятичных чисел.
Если относится к этому поверхностно, не вникая можно очень долго решать тривиальные проблемы.
U>Производительность работника в первую очередь снижает решение простых задач сложными методами. Например, применением рекурсии там где можно обойтись циклами. И по хорошему именно умение работника решать задачи просто надо проверять на собеседовании. Вы же пытаетесь проверять обратное — умеет ли работник видеть в мухе слона.
Переворот списка — это вообще не сложно. Тут нет ни мух ни слонов.
Есть основы, которые нужно знать.
Принципиально как вы будете хранить в одном элементе хеш-таблицы несколько значений?
С помощью массива? И постоянно его ресайзить?
Это не то, что оптимизация, это способ, самый распространенный.
Здравствуйте, Undying, Вы писали:
U>Здравствуйте, -n1l-, Вы писали:
N>>Св хештаблице напрямую.
U>В реализациях хештаблиц, да, список используется. Но и там задача переворота списка абсурдна.
Вовсе нет.
И вы видимо буквально все воспринимаете.
Здравствуйте, -n1l-, Вы писали:
N>Да тоже самое. Только листьев больше чем 1.
Не то же самое. Т.к. переворот дерева представить очень сложно.
N>Потому, что нет в компьютере десятичных чисел. N>Если относится к этому поверхностно, не вникая можно очень долго решать тривиальные проблемы.
Все равно не понял. Как десятичность/двоичность представления числа влияет на возможность/невозможность переполнения?
N>Переворот списка — это вообще не сложно. Тут нет ни мух ни слонов. N>Есть основы, которые нужно знать.
Зачем знать? Придумать самому при необходимости, да, это полезный навык. Знание экзотики бесполезный.
Здравствуйте, -n1l-, Вы писали:
N>Принципиально как вы будете хранить в одном элементе хеш-таблицы несколько значений?
Считаем позицию на основе вторичного хэша, если и она занята, то считаем третичный хэш и т.д.
N>С помощью массива? И постоянно его ресайзить?
Зачем постоянно ресайзить массив?
N>Это не то, что оптимизация, это способ, самый распространенный.
Это именно оптимизация. Т.е. без списка код хеш таблицы будет проще, хоть и несколько проиграет в производительности и памяти. Но т.к. хэш таблицы это стандартные структуры данных, то все оптимизации в коде их реализации уже сделаны.
Здравствуйте, Vzhyk, Вы писали:
I>> 1. вообще не работал со списковыми структурами (может всю жизнь матрицы умножал) V>Прикольно и показательно для местного форума: матрицы здесь не умножают.
Вообще то умножают. Один из умножателей даже отметился в этом треде.
Здравствуйте, Undying, Вы писали:
U>Здравствуйте, -n1l-, Вы писали:
N>>Да тоже самое. Только листьев больше чем 1.
U>Не то же самое. Т.к. переворот дерева представить очень сложно.
Да что вы на этом перевороте зациклились? Список, что только переворотом одним отличается от других струкутур данных?
U>Все равно не понял. Как десятичность/двоичность представления числа влияет на возможность/невозможность переполнения?
Ооо....
U>Зачем знать? Придумать самому при необходимости, да, это полезный навык. Знание экзотики бесполезный.
Что придумать самому? Наложение маски, адресную арифметику, базовые алгоритмы?
Что экзотичного в обходе списка по средствам ссылок?
Типичное незнание указателей приводит например вот к такому коду:
List<Objects> objects = new List<Objects>();
List<Objects> objects = repository.getObjectList().ToList();
И таких ляпов полно. Хорошо еще, что ляпы, так ведь бывают же и ошибки.
public static void MyMethod(List<int> list)
{
list = Enumerable.Range(0,100).ToList();
}
Потом начинается долгая отладка, вопли и неожиданные открытия.
Тратится уйма времени в итоге, на всякую хрень.
Здравствуйте, herethere, Вы писали:
H>Вот это я вам и повторяю — независимо от ваших глупых собеседований, всё равно вы не можете достоверно сказать, что наняли лучшего программиста. Зато рассуждений о списках — целая простыня! Тогда какой смысл во всех этих хитродуманных задачах? Отсеять ламеров? Так это вы должны уметь уже по CV и первым трём предложениям.
У тебя какая то неправильная дифференциация — или лучший или ламеры. Если предположить, что все люди именно такие, то у тебя все правильно — по CV и первым трём предложениям. Дальше останутся лучшие
H>Я же сказал — это СЛОЖНО, это психология (а я всего лишь прогер). Так что типичный отсев можно свести к отбору наиболее опытных (5+ лет разработки коммерческих систем) и "рассуждательных беседах" типа "как вы подступитесь к задаче такой-то". Думаю, никакие ваши смешные указатели не заменят умения видеть и описывать глобальные проблемы.
Есть мнение, что хорошие программисты свободно владеют инструментом — ЯП.
H>Вот задача, например, написать "торговую систему" для международной корпорации — за 5 минут можно выяснить на каком уровне думает собеседник и может ли он предвидеть подводные камни. А что можно увидеть, "оборачивая список"??
Я уже ответил достаточно подробно на этот вопрос.
I>>Умение взять в себя в руки очень важно. Умение работать в критической ситуации так же очень важно.
H>Та... это вы "Матрицу" пересмотрели — не должно быть у программиста таких авралов.
А они бывают. Это особенность конкретного бизнеса. В некоторых областях все спокойно. В некоторых время от времени случаются авраалы. В некоторых, как геймдев, авраал это естественное состояние.
>И даже если они есть, решаются они не написанием вычурного алгоритма, а тупо либо фиксеньем проблемы (если нашлась), либо врéменными подпорками.
Подразумевается, что авраал есть, но проблема может и найтись ? Сказки какие то. Я не знаю, что такое "фиксеньем проблемы". Вот обход xml определенного вида и генерация по ём некоторых данных сгодится ?
Здравствуйте, Undying, Вы писали: U>Считаем позицию на основе вторичного хэша, если и она занята, то считаем третичный хэш и т.д.
Слишком медленно. Плюс нужно иметь в кармане свободное место.
U>Зачем постоянно ресайзить массив?
Потому, что он не динамический.
U>Это именно оптимизация.
Это именно способ.
Здравствуйте, gandjustas, Вы писали:
I>>Задача на граф или дерево слишком сложная, что бы давать её на собеседовании. G>Да ну? А как тогда проверить что кандидат таки умеет работать с графами? Это ведь нужно в первую очередь.
Ну да. Если человек умеет кодить, то он сумеет закодить любой алгоритм. При этом знания алгоритмов проверяется несколько другим способом.
G>>>99% смогут написать разворот списка имея компьютер и час времени. Обход дерева — 4 часа, ни раз не писав обходы до этого. I>>Это заблуждение. G>Что именно?
'99% смогут написать разворот списка имея компьютер и час времени.'
'Обход дерева — 4 часа, ни раз не писав обходы до этого.'
Если человек не писал ни одного обхода, это примерно студент 1го курса университета или по скилам приравненый к такому студенту.
Пудозреваю, если искать скажем лисперов, хаскелистов и прочих функциональщиков, то результат будет все 100%
I>>>>Если не понимает указатели-ссылки, то на каком основании он называется программистом ? G>>>Указатели далеко не везде есть. Более того, сейчас больше языков, где указателей нет. I>>"указатели-ссылки" — нет указателей, значит есть ссылки. В приведеной задаче про реверс списка указатель ничем от ссылки не отличается, там не нужна адрсная арифметика и тд и тд. G>А что нужно понимать в ссылках? Что после a=b; Object.ReferenceEquals(a,b)==true?
Например присваивание ссылки это совсем не то же самое, что присваивание значения.
G>А причем тут разворот списка? Тебя уже сильно в сторону унесло. А ты даже близко не подошел к обоснованию полезности этой задачи.
Здравствуйте, herethere, Вы писали:
H>Вот именно — паттерны "получились сами", их применили, потому что они были нужны. Сейчас всё ровно наоборот — бегает куча "списиалистов", которые знают шаблоны и так и ждёшь от них "хелловорлд" на 20 экранов — "а ларчик просто открывался".
А еще трава была зеленее, люди знали способ превращения травы в ТРАВУ, а так же владели секретом бессмертия, но унесли его в могилу.
I>>Если человек мало чем интересуется, то как правило, он всякие паттерны вряд ли будет знать.
H>А что в знании ваших паттернов такого важного?? Я же специально дал вначале пример винды — вы что, прочли и так ничего и не поняли? Тогда какой смысл "всем интересоваться" как любопытный дельфин?
Любознательность очень важное свойства любого профессионала. Знание паттернов не сводится к перечислению названий и сведений вроде "разница между прокси и адаптером".
I>>Как он будет общаться с коллегами по цеху — не ясно.
H>Да как веками это делали — на родном языке. Только вот из моего опыта я даже и не вспомню, хоть раз была ли у меня потребность разжёвывать "а вот тут я при помощи паттерна "фасад"..." — как правило, нормальному программисту объясняешь всё "в квадратиках", остальное он легко допирает сам.
Каменный век.
I>> Как минимум, паттерны нужо знать, ибо почти во всех источниках используется этот язык паттернов.
H>гыг Ну если только читать книги со словом "паттерны" — да, без них никуда! А так, в нормальной литературе, я не встречаю этого шарлатанства.
Приведи пяток примеров этой нормальной литературы. Если нечего сказать — ничего не говори.
Здравствуйте, Undying, Вы писали:
N>>Св хештаблице напрямую.
U>В реализациях хештаблиц, да, список используется. Но и там задача переворота списка абсурдна.
На собеседованиях нет смысла давать стандартные задачи. От программиста в первую очередь требуется умение решать новые задачи.
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
I>>>Задача на граф или дерево слишком сложная, что бы давать её на собеседовании. G>>Да ну? А как тогда проверить что кандидат таки умеет работать с графами? Это ведь нужно в первую очередь.
I>Ну да. Если человек умеет кодить, то он сумеет закодить любой алгоритм. При этом знания алгоритмов проверяется несколько другим способом.
С чего ты взял что человек, не умеющий написать на бумаге разворот списка на собеседовании не умеет кодить?
G>>>>99% смогут написать разворот списка имея компьютер и час времени. Обход дерева — 4 часа, ни раз не писав обходы до этого. I>>>Это заблуждение. G>>Что именно?
I>'99% смогут написать разворот списка имея компьютер и час времени.' I>'Обход дерева — 4 часа, ни раз не писав обходы до этого.'
I>Если человек не писал ни одного обхода, это примерно студент 1го курса университета или по скилам приравненый к такому студенту.
И? Все равно он может с помощью гугла написать код на нужном языке за полдня.
Если не умеет гуглить, то ему в ИТ вообще нельзя.
Здравствуйте, gandjustas, Вы писали:
G>>>Если у тебя в работе постоянно используется топосорт, то спрашивай на собеседовании НС>>Зачем? Мне не нужно знание топосорта, я его уже написал, я просто тебе реальный пример привел. Мне нужно, чтобы человек умел в голове оперировать ссылками. G>не понял, в чем реальность? Нужная сортировка гуглится максимум за час. Зачем спрашивать на собеседовании то, что не используется?
На сортировке отлично проверяются алгоритмические скилы. Если ты гуглишь сортировки, то сильно вряд ли ты в курсе, что есть сортировки за линейное время или близкое к нему.
А еще у каждой сортировки целая куча разных особенностей, таких, как лучший и худший случаи.
И часто очень важно обосновать правильный выбор. Есть случаи, когда можно и нужно использовать быструю сортировку, а есть случаи, когда ни в коем случае этого нельзя делать.
Кроме того, если нужно будет модифицировать алгоритм, то гугл не скажет тебе, как изменяется вычислительная сложность.
Вообще сортировка это практически дедушка всех алгоритмов, если специалист по алгоритмам здесь плавает, то дальше его можно и не спрашивать.
G>Задаем вопрос про value и reference типы в .NET. G>На этом вопросе 20% отваливаются.
А задача навроде реверса отфильтровывает примерно 80% и вот с остальными имеет смысл толковать про более важные вещи.
Здравствуйте, Pavel Dvorkin, Вы писали:
G>>99% смогут написать разворот списка имея компьютер и час времени. Обход дерева — 4 часа, ни раз не писав обходы до этого.
PD>Я, конечно, извиняюсь, но о каком дереве речь идет ? Если об обычном двоичном дереве, то 4 часа — гм... Примерно по строчке в час получается.
Ну вот такие у него и работают — в час по чайной ложке выдают.
Здравствуйте, gandjustas, Вы писали:
G>>>Тебе лично сколько раз приходилось писать разворот списка в настоящем проекте? G>>>Вот мне ровно 0. Думаю подавляющему большинству посетителей форума — также. V>>Да причем тут это? Есть большая толпа что хочет крутую зарплату. Ка прикажешь их отсеивать? По сути для работы пофиг кого брать. G>Давайте задачу близкую к реальной работе.
G>Мы берем SharePoint программистов, просим написать SharePoint код. Буквально 7 строк, но куча тонкостей, 30% на нем и отсеивается.
Опаньки ! Практически аналог реверса для SharePoint — программиста.
Ты похоже делаешь выводы по своему частному случаю. Баззворд SharePoint в вакансии сам по себе фильтрует неплохо и на собеседования новички практически не приходят.
Тогда какой смысл во всех этих хитродуманных задачах? Отсеять ламеров? Так это вы должны уметь уже по CV и первым трём предложениям.
