Función garantizada para no devolver nunca el mismo valor dos veces [cerrado]

23

Esta es una pregunta que me hicieron en una entrevista de trabajo, y no puedo encontrar la respuesta que estaban buscando, así que espero que alguien aquí tenga algunas ideas. El objetivo es escribir una función que garantice que nunca devolverá el mismo valor dos veces. Suponga que varias máquinas tienen acceso a esta función simultáneamente.

Mi idea era asignar a cada máquina una identificación única y pasar ese valor a la función de generador de valor único:

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

Esto evitaría las consecuencias de las condiciones de carrera, ya que incluso si dos o más procesos leen el mismo valor i, cada valor de retorno está etiquetado como una combinación única de identificación de proceso e identificación de máquina. Sin embargo, a mi entrevistador no le gustó esta respuesta porque poner otra máquina en línea implica asignarle una identificación.

Entonces, ¿alguien puede pensar en otra forma de resolver esto que no implique configurar cada máquina para que tenga una identificación única? Me gustaría tener una respuesta en caso de que esta pregunta vuelva a surgir. Gracias.

arrendajo
fuente
31
Garantizado en el sentido estricto de la palabra? Quiero decir, incluso los Guías comenzarán a repetirse en algún momento. Puede que ya no vivamos, pero garantiza ... Y, por cierto, una identificación de proceso está lejos de ser única .
JensG
77
@CodesInChaos: esa es una suposición bastante terrible, dado que en algunos sistemas operativos es trivial cambiar su dirección mac.
Telastyn
77
"Suponga que varias máquinas tienen acceso a esta función simultáneamente". Honestamente, esto podría significar "el código se ejecuta en cada máquina de forma individual, sin comunicación entre las máquinas" o "hay una máquina central / base de datos central donde la función se proporciona para las otras máquinas, disponibles a través de la red ". Deberías comenzar a aclarar esto primero.
Doc Brown
28
¿Fue una pregunta capciosa? Por ejemplo, una función que contiene un bucle infinito nunca devolverá el mismo valor dos veces ..
Brendan
8
Quizás estaban buscando un programador que haga preguntas sobre requisitos dudosos, en lugar de hacer suposiciones y correr con él :)
theMayer

Respuestas:

60

No se preocupe, simplemente arroje un contador simple (seguro) detrás de algún punto final de comunicación (WCF, servicio web, lo que sea):

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

Sí, eventualmente se desbordará. Sí, no maneja reinicios. Sí, no es al azar. Sí, alguien podría ejecutar esto en varios servidores.

Esto es lo más simple que satisface los requisitos prácticos. Luego, permítales que sean los que sigan con esos problemas (para asegurarse de que entiendan las limitaciones, ¿ realmente creen que necesita más de 2 ^ 64 identificadores), para que pueda preguntar qué compensaciones están bien. ¿Necesita sobrevivir a los reinicios? ¿Qué pasa con la falla del disco duro? ¿Qué hay de la guerra nuclear? ¿Tiene que ser al azar? ¿Qué tan aleatorio?

Telastyn
fuente
77
Esta es una buena respuesta, porque el entrevistador nunca hace preguntas para obtener una respuesta directa. Quieren que responda donde puede justificar sus decisiones. Si comprende el dominio, casi cualquier respuesta será adecuada si puede justificarlo.
77
¿Cómo se supone que esto funciona si el código se ejecuta en diferentes máquinas (obviamente en diferentes procesos)? Cada proceso tendrá una copia diferente de x. Y creo que sin una explicación sobre el tipo de mecanismo de enclavamiento que tienes en mente, esta respuesta es bastante vaga.
Doc Brown
77
@DocBrown "al que acceden varias máquinas simultáneamente" parece implicar que varias máquinas acceden a una única función en un solo servidor. De lo contrario, debería estar redactado "Varias máquinas ejecutarán una copia de esta función al mismo tiempo"
Falco
3
@LightnessRacesinOrbit: supongo que esto debe ser C #, y la System.Threading.Interlockedclase, que proporciona incrementos atómicos. Pero también podría leer esto como una especie de pseudocódigo.
Doc Brown
3
Si yo fuera la persona que preguntara, estaría muy descontento con esta propuesta. Comenzar a implementar algo sin siquiera saber cuáles son los requisitos es una gran señal de alerta. Espero que preguntes.
JensG
25

Si me hicieran esa pregunta, y dejaran en claro que tiene que ser única en los reinicios y en diferentes máquinas, les asignaría una función que invoca el mecanismo estándar para crear un nuevo GUID, sea lo que sea que esté en El lenguaje utilizado.

Mason Wheeler
fuente
El problema con los GUID v4 es que es muy probable que sean únicos, no garantizados como únicos. No es un gran problema en la práctica, pero no satisface los requisitos si el entrevistador los toma literalmente.
CodesInChaos
En particular, si el mecanismo GUID estándar no cumple con los requisitos del entrevistador, descubra las diferencias en los requisitos entre el entrevistador y un usuario común de GUID. Un entrevistador sensato que hace este tipo de preguntas ("¿cómo haces <alguna cosa estándar generalmente conocida, tal vez con una ligera variación de los requisitos habituales>") debería esperar respuestas muy diferentes de los candidatos que conocen el estado del arte para GUID y candidatos que están inventando algo desde cero.
Steve Jessop
Esta es probablemente la respuesta más simple, suponiendo requisitos flexibles.
theMayer
99
+1 porque este es básicamente el problema que resuelven las guías. Producir un Guid duplicado, sin importar su formato, es la lotería más difícil del planeta. Aparentemente, muchas personas no tienen sentido de la improbabilidad exponencial de las colisiones.
Usr
3
Ah, y si ofrece la respuesta "utilizar una función estándar" a cualquiera de estas preguntas, espere una pregunta de seguimiento "¿y cómo se implementa la función estándar?". A lo que bien podría responder "No lo sé, pero definitivamente lo buscaría en lugar de tratar de inventar algo", que es una respuesta completamente precisa que no logra mantener la suspensión de la incredulidad esperada en las condiciones de la entrevista, que habías nunca hace nada importante sin investigar primero ;-)
Steve Jessop
22

El entrevistador dijo que el método se llamará simultáneamente, no en paralelo; simplemente regrese la fecha / hora a tantos decimales como pueda.

¿Por qué todos piensan demasiado en esto? Estarás muerto mucho tiempo antes de que se gaste cualquier finitud y no tengas la posibilidad de una colisión.

Si le preocupa que regrese al mismo tiempo, agregue un retraso por la menor cantidad de tiempo medible.

Si le preocupa retrasar el reloj para el horario de verano (experimentar 1 vez dos veces), agregue una constante a la hora la segunda vez que lo experimente.

brian
fuente
12
O simplemente devuelva la hora UTC independientemente de la zona horaria de los solicitantes. Como UTC no está localizado, no se verá afectado por los cambios de horario de verano.
Mauro
1
System.currentTimeNanos () :-)
Falco
1
A menos que devuelva la fecha y la hora en un formato legible para humanos, su valor no debería tener ninguna información de zona horaria dentro de todos modos.
Lightness compite con Monica el
12
La menor cantidad de tiempo aún producirá colisiones si se llama con frecuencia / concurrentemente. También producirá colisiones debido a la deriva de sincronización del reloj, la manipulación maliciosa del reloj y, si no tiene cuidado, el horario de verano.
Telastyn
1
Muy creativo, al menos. Confiar en un reloj que se va a ajustar de vez en cuando todavía no es una gran idea, en mi humilde opinión. El desplazamiento no lo salvará de colisiones.
JensG
15

En primer lugar, querrá hacerle dos preguntas al entrevistador.


Pregunta 1.

si el entrevistador espera que se usen una o más "máquinas centrales" para asignar algunos números únicos o bloques de números únicos.


Pregunta 2.

Si el entrevistador espera un mecanismo para la detección de colisión, o si acepta el riesgo calculado de una posibilidad minúscula de colisión sin detectarlos explícitamente.

También existe el enfoque de defensa en profundidad, en el que uno incorpora alguna parte de la identificación de usuario en la aleatoriedad (por lo tanto, no completamente al azar). Por lo tanto, se reduce la posibilidad de que el mismo usuario encuentre una colisión dentro del contenido creado por ese mismo usuario.


Hay una pregunta implícita 3, ...

Pero es uno que tendrá que evaluar sin preguntar, porque es extremadamente descortés preguntarle a su entrevistador.

Si el entrevistador asume el conocimiento de probabilidad, riesgo y algunas técnicas simples empleadas en sistemas criptográficos y de seguridad de la información.

El primer tipo de conocimiento asegura que no está tratando de convencer a una persona no científica para que acepte un concepto científico que no aceptará.

El segundo tipo de conocimiento asegura que se aborden las preocupaciones que se suman a la mera probabilidad. En otras palabras, cómo defenderse de los "asaltantes" que desean romper intencionalmente su esquema de aleatorización, manipulando las máquinas o sus hosts virtuales para forzar a dos máquinas a generar el mismo valor.


Por qué preguntar.

La razón es que si el entrevistador lo espera de una forma u otra, tratar de responder con el enfoque opuesto nunca hará feliz al entrevistador.

La razón más profunda es que a algunas personas no les gusta la idea de decir, una 1.0e-20posibilidad de fracasar. (Intentaré no despertar argumentos filosóficos o religiosos aquí).


En primer lugar, el "espacio de nombres" de los números aleatorios se convierte en una jerarquía, con cierto número de bits asignados a una fuente de aleatorización, y el otro número de bits asignados a otras formas, etc.

El enfoque centralizado se basa en alguna autoridad central para asignar de forma exclusiva el primer nivel de bits. Luego, las otras máquinas pueden llenar el resto de los bits.

Existen varios enfoques descentralizados:

  • Simplemente genere números aleatorios tan bien como sea posible y acepte la posibilidad prácticamente nula de fallar justificada por los cálculos.
  • Utilice medios criptográficos para generar valores aleatorios a partir de una fuente determinista, digamos, valores incrementales.
rwong
fuente
Creo que esta es la mejor respuesta. Los otros son soluciones sin requisitos.
Jack Aidley
Observando su tercera pregunta: parece que la competencia es una suposición segura, o al menos irrelevante. Si una empresa no proporcionó un entrevistador competente, probablemente habrá fallas más grandes en el proceso de selección. Si lo hicieron, entonces él / ella apreciará las preguntas.
theMayer
1
¿Por qué no podría abordarse la "pregunta 3" preguntando algo como: "¿Necesitamos una singularidad realmente garantizada o simplemente una muy, muy baja probabilidad de colisiones?" y, "¿Qué tan seguro debe ser esto? ¿Debemos suponer que un atacante intentará romper el mecanismo? ¿Qué tipo de ataques nos preocupan?" Las respuestas a esas preguntas deben aclarar si el autor de la pregunta comprende estos problemas y qué espera.
jpmc26
12

Entonces, teniendo en cuenta que esta es una pregunta de entrevista y no un escenario real de la vida real, creo que el enfoque correcto (y probablemente lo que el entrevistador está buscando) es hacer una pregunta aclaratoria o escribir "No puede ser hecho "y seguir adelante. Este es el por qué.

Lo que pide el entrevistador:

Escriba una función que garantice que nunca devolverá el mismo valor dos veces. Suponga que varias máquinas tienen acceso a esta función simultáneamente.

Lo que necesita el entrevistador:

¿Este candidato evalúa efectivamente los requisitos y busca aportes adicionales cuando es necesario?

Nunca asumas.

Cuando a un ingeniero se le entrega un requisito (a través de una SOW o una Especificación o algún otro documento de requisitos), algunos son evidentes y otros no son del todo claros. Este es un ejemplo perfecto de esto último. Como han mostrado las respuestas anteriores, no hay forma de responder a este requisito sin hacer varias suposiciones importantes, ya sea (a) en cuanto a la naturaleza de la pregunta o (b) en cuanto a la naturaleza del sistema, porque el requisito no puede cumplirse tal como está escrito (es imposible).

La mayoría de las respuestas hacen un intento u otro para resolver el problema a través de una serie de suposiciones. Uno recomienda específicamente hacerlo rápidamente y dejar que el cliente se preocupe si está mal.

Este es realmente un mal enfoque. Como cliente, si doy un requisito poco claro, y el ingeniero se va y me crea una solución que no funciona, me enojaría que se pusieran a trabajar y gastaran mi dinero sin molestarse en preguntarme primero. Ese tipo de toma de decisiones arrogante demuestra una falta de trabajo en equipo, incapacidad para pensar críticamente y falta de juicio. Puede conducir a cualquier tipo de consecuencias negativas, incluida la pérdida de vidas en un sistema crítico de seguridad.

¿Por qué hacer la pregunta?

El punto si este ejercicio es que es costoso y lleva mucho tiempo construir con requisitos ambiguos. En el caso del OP, se le ha asignado una tarea imposible. Su primera acción debería ser pedir una aclaración: ¿qué se requiere? ¿Qué grado de singularidad se necesita? ¿Qué sucede si un valor no es único? La respuesta a estas preguntas podría ser la diferencia entre varias semanas y unos minutos. En el mundo real, uno de los mayores factores de costo en los sistemas complejos (incluidos muchos sistemas de software) son los requisitos poco claros y poco conocidos. Esto conduce a errores costosos y que consumen mucho tiempo, rediseños, frustración de clientes y equipos, y una cobertura mediática vergonzosa si el proyecto es lo suficientemente grande.

¿Qué sucede cuando asumes?

Dado mi experiencia en la industria aeroespacial, y debido a la naturaleza altamente visible de las fallas aeroespaciales, me gusta presentar ejemplos de este dominio para ilustrar puntos importantes. Examinemos un par de misiones fallidas de Marte: Mars Climate Orbiter y Mars Polar Lander. Ambas misiones fallaron debido a problemas de software, porque los ingenieros hicieron suposiciones inválidas debido, en parte, a requisitos poco claros y mal comunicados.

Mars Climate Orbiter : este caso generalmente se cita como lo que sucede cuando la NASA intenta convertir el inglés a unidades métricas. Sin embargo, esa es una representación demasiado simplista y pobre de lo que realmente ocurrió. Es cierto que hubo un problema de conversión, pero se debió a requisitos mal comunicados en la fase de diseño y a un esquema de verificación / validación incorrecto. Además, cuando dos ingenieros diferentes notaron el problema porque era obvio a partir de los datos de la trayectoria de vuelo, no plantearon el problema al nivel adecuado porque asumieron que era un error de transmisión. Si el equipo de operaciones de la misión hubiera tenido conocimiento del problema, habría tiempo suficiente para corregirlo y salvar la misión. En este caso, había una condición lógica imposible que no se reconoció por lo que era, lo que condujo a un costoso fracaso de la misión.

Marte Polar Lander- este caso es un poco menos conocido, pero posiblemente más vergonzoso debido a su proximidad temporal a la falla del Mars Climate Orbiter. En esta misión, el software controlaba el descenso asistido por el propulsor del cohete hacia la superficie marciana. En un punto a 40 metros sobre la superficie, las patas del módulo de aterrizaje se desplegaron en preparación para aterrizar. También había un sensor en las piernas que detectaba movimiento (para indicar cuándo habían impactado) para indicarle al software que apague el motor. La mejor suposición de la NASA sobre lo que sucedió (porque hay múltiples fallas posibles y datos incompletos) es que las vibraciones aleatorias en las piernas debido a su despliegue simultáneo y dispararon incorrectamente el mecanismo de apagado a 40 metros de la superficie, lo que provocó el choque y la destrucción de los $ 110 M nave espacial. Esta posibilidad se planteó en el desarrollo, pero nunca fue abordado. En última instancia, el equipo de software hizo suposiciones inválidas sobre cómo este código debía ejecutarse (una de esas suposiciones es que una señal espuria sería demasiado corta para ser detectada, a pesar de las pruebas que muestran lo contrario), y esas suposiciones nunca fueron cuestionadas hasta después el hecho.

consideraciones adicionales

Entrevistar y evaluar a las personas es un asunto complicado. Hay varias dimensiones de un candidato que un entrevistador puede desear explorar, pero una de las más importantes es la capacidad de un individuo para pensar críticamente. Por una variedad de razones, una de las cuales es que el pensamiento crítico está mal definido, nos resulta muy difícil evaluar las habilidades de pensamiento crítico.

Como instructor de ingeniería, una de mis formas favoritas de evaluar la capacidad de un estudiante para pensar críticamente era hacer una pregunta algo ambigua. Los estudiantes más agudos captarían la premisa defectuosa de la pregunta, la notarían y responderían dada la premisa o rechazarían responder por completo. Por lo general, haría una pregunta similar a la siguiente:

Recoges un dibujo de tu pila de trabajo. El dibujo contiene una variedad de rótulos diferentes, pero los puntos más importantes apuntan a una superficie horizontal y dice "Perfectamente plano". La superficie es de 5 "de ancho por 16" de largo, y la parte está hecha de aluminio. ¿Cómo mecanizará la pieza para crear esta función?

(Por cierto, te sorprendería la frecuencia con la que aparece una especificación tan pobre en el lugar de trabajo).

Espero que los estudiantes reconozcan que no es posible crear una característica perfecta y que lo declararán en su respuesta. Por lo general, otorgaría un punto de bonificación si dicen que volverán al diseñador y pedirán una aclaración antes de hacer la parte. Si un estudiante procede a decirme cómo van a lograr una planaridad de .001 o algún otro valor inventado, otorgo cero puntos. Esto me ayuda a decirles a mis alumnos que necesitan pensar en el panorama general.

Línea de fondo

Si estoy entrevistando a un ingeniero (o una profesión similar), estoy buscando a alguien que pueda pensar críticamente y cuestionar lo que se le ha puesto delante. Quiero a alguien que haga la pregunta "¿Tiene sentido?" .

No tiene sentido pedir una parte perfectamente plana, porque no existe tal cosa como perfecta. No tiene sentido pedir una función que nunca devuelva un valor duplicado, porque es imposible hacer tal garantía. En la programación, a menudo escuchamos la frase "basura adentro, basura afuera". Si le entregan basura por requisitos, es su responsabilidad ética detenerse y hacer cualquier pregunta que lo ayude a obtener la verdadera intención. Si estoy entrevistando a un candidato y le doy un requisito poco claro, esperaré preguntas de aclaración.

theMayer
fuente
5

Garantizar la unicidad es difícil porque las computadoras no tienen variables infinitamente grandes. Ninguna máquina de Turing del mundo real puede.

A mi modo de ver, hay dos problemas aquí, y ambos tienen soluciones bien establecidas.

  • Concurrencia. Varias máquinas pueden necesitar un valor al mismo tiempo. Afortunadamente, las CPU modernas tienen simultaneidad incorporada y algunos idiomas brindan facilidades para desarrolladores para aprovechar esto.
  • Unicidad. Aunque es imposible singularidad de garantía, podemos tener arbitrariamente grandes variables que pueden contener valores tan grandes que un sistema en el mundo real tendría un muy difícil momento de agotar todos los valores únicos

Aquí está mi solución en 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 es un tipo entero de tamaño arbitrario. Puede crecer para mantener valores que son bastante grandes, incluso si no son infinitos. El bloqueo garantiza la concurrencia, por lo que el mismo valor no puede ser devuelto dos veces por dos solicitudes simultáneas atendidas por subprocesos separados.

ChaosPandion
fuente
Creo que la suposición de que el código solo se usará durante menos de quinientos años es una suposición válida. Si simplemente devuelve valores crecientes en el almacenamiento de 64 bits, estará bien durante bastante tiempo. A 1 llamada por nosotros, en 584555 años.
Mooing Duck
1
Al menos en Java, eso es 2 ^ 63 valores (la mitad de ese tiempo). Aún más tiempo que la raza humana probablemente existirá dada nuestra tendencia a matarse unos a otros. De todos modos, tomé un enfoque más teórico. Siendo realistas, 64 (o 63) bits deberían ser suficientes.
1
@Snowman: ¡¿QUÉ ?! Su solución solo es válida por 250K años?!?!? PRÓXIMO CANDIDATO !!!!!! :-)
Bob Jarvis - Restablece a Monica el
0

Expondría la función a través de un puerto en el servidor; Para llamar a la función, la máquina solicitante solicita una conexión y se le concede una, al tiempo que se le asigna un código de identificación (número secuencial para simplificar). Cada vez que se envía un mensaje al puerto solicitando el valor único, el valor se genera concatenando el hash MD5 de la fecha y hora actual con el hash MD5 del código de identificación.

Si quieren una solución más a prueba de balas, tendrían que especificar sus requisitos reales en lugar de ser tan vagos sobre las cosas.

thespratty
fuente
-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;
}

De la manera anterior, podemos asegurarnos de que el valor de retorno sea diferente incluso si se reinicia o incluso si se llama simultáneamente desde diferentes máquinas.

techExplorer
fuente
Los programadores tratan sobre preguntas conceptuales y se espera que las respuestas expliquen las cosas. Lanzar volcados de código en lugar de una explicación es como copiar código del IDE a la pizarra: puede parecer familiar e incluso a veces comprensible, pero se siente extraño ... simplemente extraño. Whiteboard no tiene compilador
mosquito
Gracias mosquito por señalarlo, nos ocuparemos de explicar la solución de la próxima vez
techExplorer