Функция гарантированно никогда не возвращает одно и то же значение дважды [закрыто]

23

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

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

var i = 0;
function uniq(process_id, machine_id) {
   return (i += 1).toString() + machine_id + "-" + process_id;
}

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

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

сойка
источник
31
Гарантируется в строгом смысле этого слова? Я имею в виду, что даже Гиды в какой-то момент начнут повторяться. Мы можем больше не жить, но гарантируем .. И, кстати, идентификатор процесса далеко не уникален .
JensG
7
@CodesInChaos - это довольно ужасное предположение, учитывая, что в некоторых операционных системах тривиально изменить ваш mac-адрес.
Теластин
7
«Предположим, что эта функция будет доступна нескольким машинам одновременно» - честно говоря, это может означать «код выполняется на каждой машине индивидуально, без связи между машинами», или «существует центральная машина / центральная база данных, где функция предоставляется для других машин, доступных по сети ". Вы должны начать разъяснять это в первую очередь.
Док Браун,
28
Это был вопрос с подвохом? Например, функция, содержащая бесконечный цикл, никогда не будет возвращать одно и то же значение дважды ..
Брендан,
8
Возможно, они искали программиста, который задает вопросы о сомнительных требованиях, а не делает предположения и работает с ним :)
theMayer

Ответы:

60

Не думайте, просто бросьте простой (потокобезопасный) счетчик за какой-то конечной точкой связи (WCF, веб-сервис, что угодно):

   long x = long.MinValue;
   public long ID(){
       return Interlocked.Increment(ref x);
   }

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

Это самая простая вещь, которая удовлетворяет практическим требованиям. Затем пусть они будут теми, кто следит за этими проблемами (чтобы убедиться, что они понимают ограничения, действительно ли они думают, что вам нужно больше 2 ^ 64 идентификаторов), чтобы вы могли тогда спросить о том, какие компромиссы в порядке. Нужно ли пережить перезагрузки? Как насчет сбоя жесткого диска? А как насчет ядерной войны? Это должно быть случайным? Как случайно?

Telastyn
источник
7
Это хороший ответ, потому что интервьюер никогда не задает вопросы, чтобы получить прямой ответ. Они хотят, чтобы вы дали ответ, где вы можете обосновать свои решения. Если вы понимаете предметную область, подойдет почти любой ответ, если вы сможете его обосновать.
7
Как это должно работать, если код работает на разных машинах (очевидно, в разных процессах)? Каждый процесс будет иметь свою копию x. И я думаю, что без объяснения того, какой механизм блокировки вы имеете в виду, этот ответ довольно расплывчатый.
Док Браун,
7
@DocBrown "доступ к нескольким машинам одновременно", по-видимому, подразумевает, что несколько машин получают доступ к одной функции на одном сервере. В противном случае следует сформулировать следующее: «Несколько машин будут одновременно запускать копию этой функции»
Falco
3
@LightnessRacesinOrbit: Я предполагаю, что это C # и System.Threading.Interlockedкласс, который обеспечивает атомарные приращения. Но вы также можете прочитать это как некий псевдокод.
Док Браун
3
Если бы я был человеком, спрашивающим, я был бы очень недоволен этим предложением. Начало реализации чего-либо, даже не зная, каковы требования, это большой красный флаг. Я ожидаю, что вы спросите.
JensG
25

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

Мейсон Уилер
источник
Проблема с v4 GUID состоит в том, что они очень вероятно уникальны, а не гарантированно уникальны. Не большая проблема на практике, но не удовлетворяет требованиям, если интервьюер воспринимает их буквально.
CodesInChaos
В частности, если стандартный механизм GUID не соответствует требованиям интервьюера, выявите различия в требованиях между интервьюером и обычным пользователем GUID. Разумный интервьюер задает этот вид вопроса ( «Как поживает <некоторые вообще известную стандартной вещь , возможно , с небольшим изменением от обычных требований>») следует ожидать очень разные видов ответа от кандидатов , которые знают о состоянии искусства для GUID и кандидатов, которые что-то изобретают с нуля.
Стив Джессоп
Это, вероятно, самый простой ответ, предполагающий гибкие требования.
Май
9
+1, потому что это в основном проблема, которую решают гиды. Создание дубликата Guid, независимо от его формата, является самой сложной лотереей на планете. Видимо, многие люди не понимают экспоненциальной вероятности столкновений.
USR
3
Да, и если вы предложите ответ «использовать стандартную функцию» на любой такой вопрос, ожидайте дополнительного вопроса «а как реализована стандартная функция?». На что вы могли бы очень хорошо ответить «Я не знаю, но я определенно посмотрю бы это, а не пытался что-то придумать», что является совершенно точным ответом, который совершенно не в состоянии поддерживать ожидаемую приостановку неверия в условиях интервью, что ты когда- нибудь сделаешь что-то важное, не исследуя это сначала ;-)
Стив Джессоп
22

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

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

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

Если вас беспокоит перевод часов на летнее время (1 раз в два раза), добавьте константу ко времени во второй раз.

Брайан
источник
12
Или просто вернуть время UTC независимо от часового пояса запрашивающих. Поскольку UTC не локализовано, изменения DST не влияют на него.
Мауро
1
System.currentTimeNanos () :-)
Falco
1
Если вы не возвращаете дату и время в удобочитаемом формате, ваше значение в любом случае не должно содержать никакой информации о часовом поясе.
Легкость гонки с Моникой
12
Наименьшее количество времени все еще будет вызывать коллизии, если вызываться достаточно часто / одновременно. Это также приведет к коллизиям из-за дрейфа синхронизации часов, злонамеренного манипулирования часами и, если вы не будете осторожны - летнего времени.
Теластин,
1
Очень креативно, по крайней мере. ИМХО, полагаться на часы, которые будут время от времени настраиваться, - все еще не такая уж хорошая идея. Смещение не спасет вас от столкновений.
JensG
15

Во-первых, вы захотите задать интервьюеру два вопроса.


Вопрос 1.

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


Вопрос 2.

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

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


Есть неявный вопрос 3, ...

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

Предполагает ли интервьюер знание вероятности, риска и некоторых простых методов, используемых в криптографических системах и системах защиты информации.

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

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


Зачем спрашивать.

Причина в том, что, если интервьюер ожидает, что так или иначе, попытка ответить с противоположным подходом никогда не сделает интервьюера счастливым.

Более глубокая причина заключается в том, что некоторым людям не нравится идея сказать, 1.0e-20шанс потерпеть неудачу. (Я постараюсь не вызывать здесь философских или религиозных аргументов.)


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

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

Есть несколько децентрализованных подходов:

  • Просто генерируйте случайные числа настолько хорошо, насколько это возможно, и принимайте практически нулевой шанс на неудачу, оправданный расчетами.
  • Используйте криптографические средства генерации случайных значений из детерминированного источника, скажем, приращения значений.
rwong
источник
Я думаю, что это лучший ответ. Другие решения без требований.
Джек Эйдли,
Подчеркнем ваш третий вопрос - кажется, что компетентность является безопасным предположением или, по крайней мере, неуместным. Если компания не предоставила компетентного интервьюера, вероятно, будут существенные недостатки в процессе отбора. Если они сделали, то он / она оценит вопросы.
The Mayer
1
Почему нельзя ответить на «вопрос 3», задавая что-то вроде: «Нужна ли нам действительно гарантированная уникальность или просто очень, очень низкая вероятность столкновений?» и «Насколько безопасным это должно быть? Нужно ли нам предполагать, что злоумышленник попытается сломать механизм? Какие виды атак нас беспокоят?» Ответы на эти вопросы должны уточнить, понимает ли спрашивающий эти проблемы и что они ожидают.
jpmc26
12

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

Что спрашивает интервьюер:

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

Что нужно интервьюеру:

Эффективно ли этот кандидат оценивает требования и ищет дополнительный вклад в случае необходимости?

Никогда не принимай.

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

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

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

Зачем задавать вопрос?

Дело в том, что это упражнение является дорогостоящим и трудоемким, чтобы построить с неоднозначными требованиями. В случае с ОП вам дали невыполнимую задачу. Ваше первое действие должно заключаться в том, чтобы попросить разъяснений - что требуется? Какая степень уникальности нужна? Что происходит, если значение не является уникальным? Ответом на эти вопросы может быть разница между несколькими неделями и несколькими минутами. В реальном мире одним из главных факторов, определяющих стоимость сложных систем (включая многие программные системы), являются неясные и плохо понятые требования. Это приводит к дорогостоящим и трудоемким ошибкам, перепроектированию, разочарованию клиентов и команды, а также затрудняет освещение в СМИ, если проект достаточно большой.

Что происходит, когда вы предполагаете?

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

Mars Climate Orbiter - этот случай обычно упоминается как случай, когда НАСА пытается преобразовать английский в метрические единицы. Однако это слишком упрощенное и плохое представление о том, что действительно произошло. Правда, была проблема преобразования, но это было связано с плохо сообщенными требованиями на этапе проектирования и неправильной схемой верификации / валидации. Кроме того, когда два разных инженера заметили проблему, потому что это было очевидно из данных траектории полета, они не подняли проблему до надлежащего уровня, потому что они предположили, что это была ошибка передачи. Если бы оперативная группа миссии была проинформирована об этой проблеме, было бы достаточно времени, чтобы исправить ее и сохранить миссию. В этом случае существовало невозможное логическое условие, которое не было признано таким, каким оно было, что приводило к дорогостоящему провалу миссии.

Марс Полярный Ландер- этот случай немного менее известен, но, возможно, более смущает из-за его временной близости к отказу Марс-климатического орбитального аппарата. В этой миссии программное обеспечение контролировало спуск ракеты с помощью двигателя на поверхность Марса. В точке 40 метров над поверхностью ноги посадочного аппарата развернуты в процессе подготовки к приземлению. Был также датчик на ногах, который обнаружил движение (чтобы сигнализировать, когда они пострадали), чтобы сказать программное обеспечение, чтобы выключить двигатель. Наилучшим предположением НАСА относительно того, что произошло (поскольку существует множество возможных отказов и неполных данных), является то, что случайные вибрации в опорах из-за их одновременного развертывания и неправильного запуска механизма отключения на 40 м над поверхностью приводят к аварии и разрушению 110 долл. США. М космический корабль. Эта возможность была поднята в разработке, но никогда не был адресован. В конечном счете, команда разработчиков сделала неверные предположения о том, как должен выполняться этот код (одно из таких предположений состоит в том, что ложный сигнал будет слишком коротким, чтобы его можно было принять, несмотря на тесты, показывающие обратное), и эти предположения никогда не подвергались сомнению до тех пор, пока факт.

Дополнительные соображения

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

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

Вы берете рисунок из своей стопки работ. Чертеж содержит множество различных выносок, но наиболее важные указывают на горизонтальную поверхность и говорят «Совершенно плоско». Поверхность 5 "в ширину и 16" в длину, а часть изготовлена ​​из алюминия. Как вы будете обрабатывать деталь для создания этой функции?

(Кстати, вы были бы шокированы тем, как часто на рабочем месте появляются такие плохие спецификации.)

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

Нижняя граница

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

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

theMayer
источник
5

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

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

  • Параллелизм. Несколько машин могут нуждаться в значении одновременно. К счастью, современные процессоры имеют встроенный параллелизм, и некоторые языки предоставляют удобные средства для разработчиков, чтобы воспользоваться этим.
  • Уникальность. Хотя невозможно гарантировать уникальность, мы можем иметь произвольно большие переменные, которые могут содержать значения настолько большие, что реальной системе будет очень трудно исчерпать все уникальные значения

Вот мое решение на Java:

public class Foo {
  private static BigInteger value = BigInteger.ZERO;
  private static final Lock lock = new ReentrantLock();

  public static BigInteger nextValue() {
    try {
      lock.lock();
      value = value.add(BigInteger.ONE);
      return value;
    }
    finally {
      lock.unlock();
    }
  }
}

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

ChaosPandion
источник
Я думаю, что предположение о том, что код будет использоваться менее пятисот лет, является допустимым предположением. Если вы просто возвращаете увеличивающиеся значения в 64-битном хранилище, у вас достаточно времени. По 1 звонку за нас, в 584555 лет.
Mooing Duck
1
По крайней мере, в Java это 2 ^ 63 значения (так что вдвое меньше). Еще дольше, чем будет существовать человеческая раса, учитывая нашу тенденцию убивать друг друга. Несмотря на это, я выбрал более теоретический подход. Реально, 64 (или 63) бит должно быть достаточно.
1
@ Снеговик: ЧТО?!? Ваше решение действительно только в течение 250 тысяч лет?!?!? СЛЕДУЮЩИЙ КАНДИДАТ !!!!!! :-)
Боб Джарвис - Восстановить Монику
0

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

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

thespratty
источник
-1
string uniq(string machine_id) 
{
   static long u = long.MinValue;
   Interlocked.Increment(ref u);

   //Time stamp with millisecond precison
   string timestamp = DateTime.UtcNow.ToString("yyyy-MM-dd HH:mm:ss.fff",
                                            CultureInfo.InvariantCulture);

   return machine_id + "-" + timestamp + "-" + u;
}

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

techExplorer
источник
Программисты о концептуальных вопросах, и ответы должны объяснить вещи. Создание дампов кода вместо объяснения похоже на копирование кода из IDE на доску: это может показаться знакомым и даже иногда понятным, но это кажется странным ... просто странным. У доски нет компилятора
gnat
Спасибо, комнат, за то, что указал на это, постараюсь объяснить решение в следующий раз
techExplorer