Здравствуйте, avpavlov, Вы писали:
L>>Если не сложно, ответь на вопрос как он был изначально задан.
A>Словарь — это алгоритм. Я отвечал уже на этот вопрос. Ты собираешься меня переспросить про каждую известную тебе имплементацию словаря?
Вопрос был немного другим:
реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?
Если не сложно, ответь именно про "Dictionary из .Net".
L>>Ага. А если из тебя все внутренности вырезать, то через пару минут ты не останешься. Выходит ты — это селезенка.
A>Это как раз твоя мысль. Если следовать моей мысли, то человека человеком делает не селезёнка и другие органы, а то, как они взаимодействуют друг с другом.
Человека человеком делает как селезенка, так и взаимодействие оной со всем остальным. А "структура данных" — это как внутренняя организация данных, так и алгоритмы роаботы с ними.
Здравствуйте, avpavlov, Вы писали:
A>Теперь моя очередь попросить тебя сделать то, что было запрошено изначально
A>
A>Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Ты ошибаешься в определении понятия "структуры данных". В чем твоя ошибка тебе уже сказали. Как найти информацию тебе тоже сказали.
Извини, но дальше — сам.
L>>Ты ошибаешься в определении понятия "структуры данных". В чем твоя ошибка тебе уже сказали. Как найти информацию тебе тоже сказали.
A>Я тебе привёл другое определение, но ты его проигнорировал, как менее удобное для тебя
ты его просто некорректно трактовал.
например, возьми то же бинарное дерево. если для тебя это просто способ организации данных в памяти, то никто мне не помешает вставить в произвольное место дерева данные, которые там быть не должны, а то и вовсе зациклить его. следовательно, без правильного кода, работающего с этим деревом, дерево не будет выполнять своей функции быстрого поиска. эти два понятия (организация данных и способ работы с ними) просто неотъемлемы.
в этом ключе и надо трактовать "структура данных", о чем я писал.
Здравствуйте, avpavlov, Вы писали:
L>>Если не сложно, ответь именно про "Dictionary из .Net".
A>Отвечаю в последний раз — это алгоритм.
Неужели? Ну значит мне снова наврали, пойду выпью чаю с горя.
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).
L>Неужели? Ну значит мне снова наврали, пойду выпью чаю с горя.
L>
L>In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).
Ллойд, а ты забавный, ей богу. Пинал меня "ответь про .Нет, ответь про .Нет" и как только я ответил про .Нет, сразу перевёл тему в другую плоскость. Если ты намеренно съузил тему до словаря из .Нет, я тебя прошу приводить цитаты из МСДН, иначе ты просто демагог.
L> эти два понятия (организация данных и способ работы с ними) просто неотъемлемы. L>в этом ключе и надо трактовать "структура данных", о чем я писал.
А я считаю, что есть смысл проводить между ними черту, о чем тоже писал. Потому что если эту черту не провести, то возникает двусмысленность, из-за невозможности точно сказать, о чём в конкретный момент времени идёт речь — "о способе хранения" или "о способе хранения и манипулировании".
L>>Неужели? Ну значит мне снова наврали, пойду выпью чаю с горя.
L>>
L>>In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).
A>Ллойд, а ты забавный, ей богу. Пинал меня "ответь про .Нет, ответь про .Нет" и как только я ответил про .Нет, сразу перевёл тему в другую плоскость.
Да нет, плоскость все та же самая. Dictionary из .Net-а — частный случай хэш-таблицы.
A>Если ты намеренно съузил тему до словаря из .Нет, я тебя прошу приводить цитаты из МСДН,
Не сузил, а спустил на землю. Занимаясь философией можно много до чего договориться, а вот раельность отрезвляет.
A>иначе ты просто демагог.
Первый признак демагога — обвинение собеседника в демагогии.
Здравствуйте, avpavlov, Вы писали:
L>> эти два понятия (организация данных и способ работы с ними) просто неотъемлемы. L>>в этом ключе и надо трактовать "структура данных", о чем я писал.
A>А я считаю, что есть смысл проводить между ними черту, о чем тоже писал. Потому что если эту черту не провести, то возникает двусмысленность, из-за невозможности точно сказать, о чём в конкретный момент времени идёт речь — "о способе хранения" или "о способе хранения и манипулировании".
Я так не считаю. "Структура данных" — устоявшийся термин и тракторать его по-своему нежелательно.
Здравствуйте, abc1234573, Вы писали:
A>На собеседованиях часто спрашивают что такое deadlock. Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами. A>На практике это обычно решается изменением архитектуры. Как можно устранить проблему либо при использовании дополнительных алгоритмов, либо особенностей языка, библиотек, операционной системы.
Deadlock, т.е. взаимная блокировка — чисто архитектурная проблема и решать её нужно на уровне архитектуры. Основной алгоритм — определение неделимых частей кода — транзакций. Для классического примера с википедии при первом же обнаружении deadlock'а следовало бы убрать независимый захват ресурсов A и B, и добавить захват ресурсов A + B. Возможен другой подход: если в какой то части кода захвачено монопольно более одного ресурса, то процесс захвата и освобождения должен производиться по принципу FILO, т.е. в том же случае с вики "второй процесс" должен ждать освобождения A, даже если B свободен.
Погуглил, и таки-да, появилось ощущение, что много кто взаимозаменяет понятия "неблокирующий алгоритм" и "неблокирующая структура данных", что лично мне представляется грустным.
...
Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Изначально уже ясно, что самоцель достаточно странная. Алгоритм-структура...
Но по теме:
Словарь (ассоциативный массив) — это абстрактный тип данных (АТД, abstract data type). Стэк — АТД, хотя он же и структура данных. Их пруд пруди.
Эти самые АТД, определяют операции над собой (что логично, собственно как и все типы данных определяют операции над собой).
Таким образом эти операции иногда просто называют интерфейсом.
Хэш-таблица — это структура данных реализующая интерфейс словаря. Ничего не мешает эти же данные хранить в обычном списке выставив наружу IDictionary, ну разве что только скорость.
Таким образом структура данных определяет способ упаковки данных и методы работы над ними (алгоритмы обработки этих данных, их сложность).
Но алгоритм, в прошлом предложении — стоит не забывать, что это в том числе и жесткий контракт, особенно если вести речь о неблокирующих структурах данных. Речь изначально и шла, что невозможно отделить эти методы от самой структуры данных. Поэтому само по себе понятие неблокирующий алгоритм не особо имеет смысл, в данном контексте. Ещё примеров — пожалуйста — XOR linked list — врядли получение предыдущего/следующего элемента вне этой структуры имеет смысл. И точно так же эти методы не применимы к классическому дву-связному связному списку.
On 16.08.2011 18:21, abc1234573 wrote:
> На собеседованиях часто спрашивают что такое deadlock. Затем может следовать > вопрос а как его можно устранить, при этом желательно привести несколько > примеров устранения различными способами.
Устранить -- это разрешить ситуацию дедлока в конкретном случае, или сделать
так, чтобы её не возникало никогда в системе ?
> На практике это обычно решается изменением архитектуры. Как можно устранить
Здравствуйте, avpavlov, Вы писали:
L>>Если не сложно, ответь именно про "Dictionary из .Net".
A>Отвечаю в последний раз — это алгоритм.
Это не алгоритм и не структура данных. Это (абстрактный) тип данных. Применительно к Dictionary структурой данных будут его внутренние поля в которых находятся ключи и значения, а алгоритмами — набор операций, которые можно осуществлять над словарем (добавление значение, поиск значения, перечисление значений и ключей).
Здравствуйте, MasterZiv, Вы писали:
MZ>On 16.08.2011 18:21, abc1234573 wrote:
>> На собеседованиях часто спрашивают что такое deadlock. Затем может следовать >> вопрос а как его можно устранить, при этом желательно привести несколько >> примеров устранения различными способами.
MZ>Устранить -- это разрешить ситуацию дедлока в конкретном случае, или сделать MZ>так, чтобы её не возникало никогда в системе ?
в конкретном случае сделать так чтобы участок кода вызывающий дедлок либо его не вызывал либо дополнительно обрабатывался чтобы исключиь такую ситуацию
>> На практике это обычно решается изменением архитектуры. Как можно устранить
MZ>Да не только.
вот как раз интересно как это сделать без изменения архитектуры
Здравствуйте, abc1234573, Вы писали:
A>На собеседованиях часто спрашивают что такое deadlock.
Обычно это расшифровывается как бесконечное ожидание на объекте синхронизации, который больше нельзя переключить в свободное состояние.
A>Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами.
Примеров уйма, от забыл освободить, до нарушения порядка захвата-освобождения (cross deadlock). При этом один из двух мютексов с лекгостью фейла может быть системным.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
On 17.08.2011 15:51, abc1234573 wrote:
> MZ>Устранить -- это разрешить ситуацию дедлока в конкретном случае, или сделать > MZ>так, чтобы её не возникало никогда в системе ? > > в конкретном случае сделать так чтобы участок кода вызывающий дедлок либо его не > вызывал либо дополнительно обрабатывался чтобы исключиь такую ситуацию > >> > На практике это обычно решается изменением архитектуры. Как можно устранить > > MZ>Да не только. > > вот как раз интересно как это сделать без изменения архитектуры
Ну что такое "изменение архитектуры" не очень понятно, ну да ладно.
принципиально есть следующие способы разрешения дедлоков:
-- отказ от многопользовательской и/или многозадачной работы
-- сериализация доступа к блокам кода, в которых возникает дедлок (в общем-то
можно сказать локальный отказ от многозадачности в рамках куска кода).
-- установка общего глобального в приложении порядка захвата синхронизирующих
объектов.
Это из средств предотвращения дедлоков.
А средства выхода из ситуации дедлока пожалуй только два:
-- таймауты (дешёвый)
-- анализ графа зависимостей локов для выявления циклов. (дорогой).
