Funkcja nigdy nie zwraca dwukrotnie tej samej wartości [zamknięte]

To pytanie zadano mi na rozmowie o pracę i nie mogę znaleźć odpowiedzi, której szukali, więc mam nadzieję, że ktoś tutaj może mieć jakieś pomysły. Celem jest napisanie funkcji, która gwarantuje, że nigdy nie zwróci dwukrotnie tej samej wartości. Załóżmy, że ta funkcja będzie dostępna dla wielu komputerów jednocześnie.

Moim pomysłem było przypisanie każdej maszynie unikalnego identyfikatora i przekazanie tej wartości do funkcji generatora unikalnych wartości:

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

Pozwoliłoby to uniknąć wypadków spowodowanych warunkami wyścigu, ponieważ nawet jeśli dwa lub więcej procesów odczytuje tę samą wartość i, każda zwracana wartość jest oznaczana unikalną kombinacją identyfikatora procesu i identyfikatora maszyny. Jednak mojemu ankieterowi nie spodobała się ta odpowiedź, ponieważ przejście do innej maszyny online wymaga przypisania jej identyfikatora.

Czy ktoś może pomyśleć o innym sposobie rozwiązania tego problemu, który nie wymaga skonfigurowania każdego komputera, aby miał unikalny identyfikator? Chciałbym uzyskać odpowiedź na wypadek, gdyby to pytanie znów się pojawiło. Dzięki.

Nie bądź fantazyjny, wystarczy rzucić prosty (bezpieczny w wątkach) licznik za punktem końcowym komunikacji (WCF, usługa sieciowa, cokolwiek):

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

Tak, w końcu się przepełni. Tak, nie obsługuje restartów. Tak, to nie jest przypadkowe. Tak, ktoś może uruchomić to na wielu serwerach.

Jest to najprostsza rzecz, która spełnia praktyczne wymagania. Następnie pozwól im być tymi, którzy zajmą się tymi problemami (aby upewnić się, że rozumieją ograniczenia, czy naprawdę uważają, że potrzebujesz więcej niż 2 ^ 64 identyfikatorów), abyś mógł następnie zapytać, jakie kompromisy są w porządku. Czy musi przetrwać ponowne uruchomienie? Co z awarią dysku twardego? Co z wojną nuklearną? Czy to musi być losowe? Jak losowo

Gdybym zadał to pytanie i wyjaśnili, że musi być unikalny w przypadku restartów i różnych komputerów, dałbym im funkcję, która wywołuje standardowy mechanizm tworzenia nowego identyfikatora GUID, niezależnie od tego, co się dzieje używany język.

Ankieter powiedział, że metoda będzie wywoływana jednocześnie, a nie równolegle; po prostu przywróć datę / godzinę do jak największej liczby miejsc po przecinku.

Dlaczego wszyscy to przesadnie myślą? Będziesz martwy długo, zanim skończy się jakaś skończoność i nie masz szansy na kolizję.

Jeśli martwisz się, że powróci on w tym samym czasie, dodaj opóźnienie dla najmniejszej ilości mierzalnego czasu.

Jeśli martwisz się o ustawienie zegara na czas letni (dwukrotnie 1 raz), dodaj stałą do czasu za drugim razem.

Po pierwsze, będziesz chciał zadać ankieterowi dwa pytania.

Pytanie 1.

czy ankieter oczekuje, że jedna lub więcej „centralnych maszyn” zostanie wykorzystanych do przypisania niektórych unikalnych numerów lub bloków niepowtarzalnych numerów.

Pytanie 2.

Czy ankieter oczekuje mechanizmu wykrywania kolizji, czy zamiast tego akceptuje obliczone ryzyko niewielkiej szansy na kolizję bez wyraźnego ich wykrycia.

Istnieje również podejście polegające na dogłębnej obronie, w którym włącza się część losowości ID użytkownika (a więc nie do końca losowa). Dlatego prawdopodobieństwo, że ten sam użytkownik napotka kolizję w treści utworzonej przez tego samego użytkownika, jest zmniejszone.

Istnieje ukryte pytanie 3, ...

Ale musisz to ocenić sam, nie pytając, ponieważ bardzo nieuprzejmie jest zapytać swojego ankietera.

Czy ankieter zakłada wiedzę o prawdopodobieństwie, ryzyku i kilku prostych technikach stosowanych w systemach kryptograficznych i zabezpieczających informacje.

Pierwszy rodzaj wiedzy gwarantuje, że nie próbujesz przekonać osoby niebędącej naukowcem do zaakceptowania koncepcji naukowej, której nie zaakceptuje.

Drugi rodzaj wiedzy gwarantuje, że rozwiążesz problemy, które są nie tylko prawdopodobieństwem. Innymi słowy, jak się bronić przed „napastnikami”, którzy chcą celowo złamać twój schemat losowy, manipulując maszyną (maszynami) lub ich wirtualnymi hostami, aby zmusić dwie maszyny do wygenerowania tej samej wartości.

Po co pytać.

Powodem jest to, że jeśli ankieter spodziewa się tego w ten czy inny sposób, próba odpowiedzi z odwrotnym podejściem nigdy go nie uszczęśliwi.

Głębszy powód jest taki, że niektórym ludziom nie podoba się pomysł powiedzenia „ 1.0e-20szansa na porażkę”. (Postaram się nie wywoływać tutaj argumentów filozoficznych lub religijnych).

Przede wszystkim „przestrzeń nazw” liczb losowych jest przekształcana w hierarchię, z pewną liczbą bitów przydzieloną do jednego źródła losowości, a drugą liczbę bitów przypisaną do innych sposobów itp.

Podejście scentralizowane opiera się na centralnym autorytecie w celu jednoznacznego przypisania pierwszego poziomu bitów. Następnie inne maszyny mogą wypełnić resztę bitów.

Istnieje kilka podejść zdecentralizowanych:

• Po prostu wygeneruj liczby losowe tak dobre, jak to tylko możliwe, i zaakceptuj praktycznie zerową szansę na niepowodzenie uzasadnioną obliczeniami.
• Użyj kryptograficznych metod generowania losowych wartości ze źródła deterministycznego, powiedzmy, wartości przyrostowych.

Pamiętając o tym, że jest to pytanie do rozmowy kwalifikacyjnej, a nie rzeczywisty scenariusz, uważam, że właściwym podejściem (i prawdopodobnie tego, czego szuka ankieter) jest postawienie pytania wyjaśniającego lub napisanie: „Nie może być gotowe ”i przejść dalej. Dlatego.

O co pyta ankieter:

Napisz funkcję, która gwarantuje, że nigdy nie zwróci dwukrotnie tej samej wartości. Załóżmy, że ta funkcja będzie dostępna dla wielu komputerów jednocześnie.

Czego potrzebuje ankieter:

Czy ten kandydat skutecznie ocenia wymagania i w razie potrzeby szuka dodatkowych informacji?

Nigdy nie zakładaj.

Kiedy inżynier otrzymuje wymagania (poprzez SOW lub specyfikację lub inny dokument wymagań), niektóre są oczywiste, a inne zupełnie niejasne. To doskonały przykład tego ostatniego. Jak pokazały poprzednie odpowiedzi, nie ma sposobu, aby odpowiedzieć na to wymaganie bez przyjęcia kilku głównych założeń (a) co do charakteru pytania lub (b) co do charakteru systemu, ponieważ wymaganie to nie może być spełnione jak napisano (jest to niemożliwe).

Większość odpowiedzi podejmuje próbę rozwiązania problemu za pomocą szeregu założeń. Jeden szczególnie zaleca, aby zrobić to szybko i pozwolić klientowi się tym martwić, jeśli jest to źle.

To naprawdę złe podejście. Jako klient, jeśli podam niejasne wymagania, a inżynier odejdzie i zbuduje mi rozwiązanie, które nie działa, będę zmartwiony, że poszli do pracy i wydali moje pieniądze, nie zawracając sobie głowy pytaniem mnie najpierw. Tego rodzaju nonszalanckie podejmowanie decyzji świadczy o braku pracy zespołowej, niezdolności do krytycznego myślenia i złej ocenie sytuacji. Może to prowadzić do wszelkiego rodzaju negatywnych konsekwencji, w tym utraty życia w systemie o krytycznym znaczeniu dla bezpieczeństwa.

Po co zadawać pytanie?

Chodzi o to, że ćwiczenie to jest kosztowne i czasochłonne w budowaniu według niejednoznacznych wymagań. W przypadku PO otrzymałeś niemożliwe zadanie. Twoim pierwszym działaniem powinno być poproszenie o wyjaśnienie - czego potrzeba? Jaki stopień wyjątkowości jest potrzebny? Co się stanie, jeśli wartość nie jest unikalna? Odpowiedzią na te pytania może być różnica między kilkoma tygodniami a kilkoma minutami. W prawdziwym świecie jednym z największych czynników napędzających koszty w złożonych systemach (w tym w wielu systemach oprogramowania) są niejasne i źle zrozumiane wymagania. Prowadzi to do kosztownych i czasochłonnych błędów, przeprojektowywania, frustracji klientów i zespołu oraz żenujących relacji z mediów, jeśli projekt jest wystarczająco duży.

Co się dzieje, kiedy zakładasz?

Biorąc pod uwagę moje doświadczenie w branży lotniczej i kosmicznej oraz ze względu na bardzo widoczny charakter awarii lotniczych, chciałbym przytoczyć przykłady z tej dziedziny, aby zilustrować ważne punkty. Przeanalizujmy parę nieudanych misji Marsa - Mars Climate Orbiter i Mars Polar Lander. Obie misje zakończyły się niepowodzeniem z powodu problemów z oprogramowaniem - ponieważ inżynierowie przyjęli nieprawidłowe założenia, częściowo z powodu niejasnych i źle zakomunikowanych wymagań.

Mars Climate Orbiter - ten przypadek jest zwykle cytowany jako to, co dzieje się, gdy NASA próbuje przekonwertować język angielski na jednostki metryczne. Jest to jednak zbyt uproszczone i słabe przedstawienie tego, co naprawdę się wydarzyło. To prawda, że ​​wystąpił problem z konwersją, ale wynikał on z nieprawidłowo zakomunikowanych wymagań na etapie projektowania i niewłaściwego schematu weryfikacji / weryfikacji. Ponadto, gdy dwóch różnych inżynierów zauważyło problem, ponieważ było to oczywiste na podstawie danych trajektorii lotu, nie podnieśli problemu do właściwego poziomu, ponieważ przyjęli, że to błąd transmisji. Gdyby zespół operacyjny misji został poinformowany o problemie, byłby odpowiedni czas, aby go naprawić i uratować misję. W tym przypadku istniał niemożliwy warunek logiczny, który nie został rozpoznany, co doprowadziło do kosztownego niepowodzenia misji.

Mars Polar Lander- ten przypadek jest nieco mniej znany, ale być może bardziej krępujący ze względu na jego czasową bliskość do awarii Mars Orbitera. W tej misji oprogramowanie kontrolowało wspomagane pędem opuszczanie rakiety na powierzchnię Marsa. W punkcie 40 metrów nad powierzchnią nogi lądownika rozłożyły się w ramach przygotowań do lądowania. Na nogach znajdował się także czujnik wykrywający ruch (sygnalizujący uderzenie) informujący oprogramowanie o wyłączeniu silnika. Najlepszym przypuszczeniem NASA co do tego, co się stało (ponieważ istnieje wiele możliwych awarii i niekompletnych danych) jest to, że przypadkowe wibracje w nogach z powodu ich jednoczesnego rozmieszczenia i nieprawidłowo uruchomiły mechanizm wyłączający 40 m nad powierzchnią, powodując awarię i zniszczenie 110 USD Statek kosmiczny M. Możliwość ta została podniesiona podczas opracowywania, ale nigdy nie został skierowany. Ostatecznie zespół programowy dokonał nieprawidłowych założeń dotyczących tego, jak ten kod musi działać (jednym z takich założeń jest to, że fałszywy sygnał byłby zbyt krótki, aby go wykryć, pomimo testów wykazujących inaczej), i te założenia zostały zakwestionowane dopiero po fakt.

Dodatkowe uwagi

Wywiady i ocena ludzi to trudna sprawa. Kandydat może zbadać kilka wymiarów kandydata, ale jednym z najważniejszych jest umiejętność krytycznego myślenia danej osoby. Z różnych powodów, między innymi dlatego, że krytyczne myślenie jest źle zdefiniowane, bardzo trudno jest nam ocenić umiejętności krytycznego myślenia.

Jako instruktor inżynierii jednym z moich ulubionych sposobów oceny zdolności studenta do krytycznego myślenia było zadanie nieco dwuznacznego pytania. Ostrzejsi uczniowie wychwyciliby błędne przesłanie pytania, odnotowali je i albo odpowiedzieli na to przesłanie, albo odmówili odpowiedzi. Zazwyczaj zadałbym pytanie podobne do następującego:

Odbierasz rysunek ze stosu pracy. Rysunek zawiera wiele różnych objaśnień, ale najważniejsze punkty wskazują na poziomą powierzchnię i mówią „Idealnie płaski”. Powierzchnia ma szerokość 5 na 16 cali, a część wykonana jest z aluminium. Jak obrobisz część, aby utworzyć tę funkcję?

(Nawiasem mówiąc, byłbyś zszokowany tym, jak często taka słaba specyfikacja pojawia się w miejscu pracy).

Oczekuję, że uczniowie uznają, że nie można stworzyć idealnej funkcji i podadzą to w swojej odpowiedzi. Zazwyczaj przyznawałbym punkt bonusowy, jeśli powiedzą, że wrócą do projektanta i poproszą o wyjaśnienie przed wykonaniem części. Jeśli uczeń powie mi, w jaki sposób osiągnie płaskość 0,001 lub jakąś inną wymyśloną wartość, przyznam zero punktów. To pomaga mi wskazać moim uczniom, że muszą myśleć o szerszym obrazie.

Dolna linia

Jeśli przeprowadzam wywiad z inżynierem (lub podobnym zawodem), szukam kogoś, kto może myśleć krytycznie i kwestionować to, co zostało przed nim postawione. Chcę kogoś, kto zadaje pytanie „Czy to ma sens?” .

Nie ma sensu prosić o idealnie płaską część, ponieważ nie ma czegoś takiego jak idealny. Nie ma sensu prosić o funkcję, która nigdy nie zwraca zduplikowanej wartości, ponieważ nie można uzyskać takiej gwarancji. W programowaniu często słyszymy zwrot „śmieci, śmieci”. Jeśli otrzymujesz śmieci w celu spełnienia wymagań, Twoim etycznym obowiązkiem jest zatrzymać się i zadać pytanie, które pomoże ci wywołać prawdziwy zamiar. Jeśli przeprowadzam wywiad z kandydatem i stawiam mu niejasny wymóg, spodziewam się pytań wyjaśniających.

Zagwarantowanie niepowtarzalności jest trudne, ponieważ komputery nie mają nieskończenie dużych zmiennych. Żadna prawdziwa maszyna Turinga tego nie potrafi.

Moim zdaniem są tutaj dwa problemy i oba mają dobrze ugruntowane rozwiązania.

• Konkurencja. Wiele komputerów może potrzebować wartości w tym samym czasie. Na szczęście nowoczesne procesory mają wbudowaną współbieżność, a niektóre języki zapewniają udogodnienia przyjazne dla programistów, aby z nich skorzystać.
• Wyjątkowość. Chociaż niemożliwe jest zagwarantowanie wyjątkowości, możemy mieć dowolnie duże zmienne, które mogą przechowywać wartości tak duże, że rzeczywisty system miałby bardzo trudny czas wyczerpując wszystkie unikalne wartości

Oto moje rozwiązanie w Javie:

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 jest liczbą całkowitą o dowolnym rozmiarze. Może rosnąć, aby utrzymać wartości, które są dość duże, nawet jeśli nie są nieskończone. Blokada zapewnia współbieżność, więc tej samej wartości nie można zwrócić dwukrotnie przez dwa jednoczesne żądania obsługiwane przez osobne wątki.

Odsłoniłbym funkcję za pośrednictwem portu na serwerze; w celu wywołania funkcji, maszyna żądająca żąda połączenia i zostaje mu przyznana, przy jednoczesnym przydzieleniu kodu identyfikacyjnego (dla uproszczenia numer kolejny). Za każdym razem, gdy wiadomość wysyłana jest do portu z żądaniem unikalnej wartości, wartość jest generowana przez połączenie skrótu MD5 bieżącej daty i godziny z skrótem MD5 kodu identyfikacyjnego.

Jeśli chcą bardziej kuloodpornego rozwiązania, będą musieli określić swoje rzeczywiste wymagania, a nie będą niejasne.

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

W powyższy sposób możemy upewnić się, że zwracana wartość jest inna, nawet jeśli są restartowane lub nawet jeśli są wywoływane jednocześnie z różnych maszyn.