[NotABigFan]

Dzisiaj w szabas to dam coś prostszego niby zadanie z Facebooka ale tak naprawdę stare jak świat. Może ktoś nie znał ( ͡° ͜ʖ ͡°)

Mając dany strumień elementów zbyt wielki aby przechowywać go w pamięci, wybierz losowy element ze strumienia z jednakowym prawdopodobieństwem dla wszystkich elementów ze strumienia.

#dailycodingproblem #programowanie

[Saly]

@NotABigFan: nie rozumiem, nie możemy poprostu wylosować pozycji dowolnego elementu?

[NotABigFan]

@Saly: nie wiesz ile elementów ma strumień i nie możesz zapamiętywać przeczytanych do tej pory elementów

[Saly]

@NotABigFan: to moze tak: czytam elementy pojedynczo, każdemu przypisuję losową liczbę, ten który wylosuje największą wygrywa

[NotABigFan]

@Saly: ok ale jaką losową liczbę? ( ͡° ͜ʖ ͡°)

[S.....s]

@NotABigFan: pewnie coś w stylu, że pierwszy element bierzemy na 100%, drugi na 50%, trzeci 1/3, itd

[Saly]

@NotABigFan: dowolną w zależności od potrzeb. Jak wylosuję liczbę na 1024 bajtach to pokryję wielokrotnie liczbę atomów w wszechswiecie. Jeżeli będę miał kolizję tzn dla kolejnego elementu mam dotychczasowego maxa to mogę trzymać te elementy w liscie, a na koniec mogę wybrać z tej listy losowy element

[Saly]

@NotABigFan:

max = 0
l = []

for e

[NotABigFan]

@SuppressWarnings: no, jakby kogoś to interesowało to jest cała rodzina takich algorytmów: https://en.wikipedia.org/wiki/Reservoir_sampling

[NotABigFan]

@Saly: Dam plusika ale nie wiem czy to jest poprawne, instynktownie czuję, że jest tam coś śliskiego (・へ・)

[S.....s]

@Saly: @NotABigFan: wydaje mi się, że też jest ok