Am un array. Suma elementelor e 1. Dau cu zarul si obtin intre 0.0 si 1.0. Care element e mai apropiat de valoare zarului?

La prima vedere a parut o problema simpla. Am gasit o functie care calculeaza indexul elementului ptr. valoarea cea mai apropiata:

func closest_index(arr,num):
	var closest_index=0
	var curr=arr[0]
	for i in range(len(arr)):
		var val=arr[i]
		if abs(num-val) < abs (num - curr):
			closest_index=i
			curr=val
	return closest_index

eg. Daca am [0.1,0.4,0.5] si numarul este 0.15 imi da 0.1 (si index 0).

Ruland insa aceasta simulare de mai multe ori (1000+) distributia valorilor este neasteptata.
Ce vreau eu e ca 0.1 sa apara in aprox. 0.1 (10%) din cazuri, 0.4 in 0.4 din cazuri si 0.5 in 0.5 din cazuri.
In realitate insa valorile sunt altfel:

Problema se amplifica cand diferenta dintre elemente este mare:


WTF?

Am mai incercat cateva functii dar tot am avut discrepante majore.
Cine poate sa ma ajute cu o idee?

1 Like

Stai ca nu e chiar asa, adica nu o sa ai 99% potrivite pentru 0.99 in arrayul tau.
Gandeste-o asa: ai un interval pe care l-ai impartit in 3 segmente. Primul este in jurul lui 0.15, al doilea in jurul lui 0.4, samd. Asta inseamna ca prima plaja de valori este de la 0 la 0.27 (mijlocul intre 0.15 si 0.40), al doilea de la 0.27 la 0.45 (mijlocul intre 0.4 si 0.5), iar ultimul intre 0.45 si 1. Acum dai cu zarul si probabilitatea sa pice intr-unul din segmente e proportionala cu lungimea lor.

5 Likes

Aha, makes sense. :slight_smile:
Cum crezi ca as putea sa determin o valoare in asa fel incat sa apara in functie de valoare?

Exemplu: ptr. un array [0.1, 0.4,0.5] si un numar random intre 0 si 1 sa aleg o valoare in asa fel incat ptr. 1000+ iteratii 0.1 sa fie ales in 10% din cazuri, 0.4 in 40% din cazuri, 0.5 in 50% din cazuri?

Ai 3 intervale acolo, [0…0,1), [0,1…0,5), [0,5…1]. Intervalele incep de unde se termina anteriorul si au lungimi date in array-ul tau. 0,1+0,4 da intervalul #2. Etc. odata ce ai intervalele e un simplu if in bucla:
If random < interval[i] return true; else i++;

Cred ca testul este putin mai complicat. Ar trebui sa arate cam asa:

def draw_from_dist(arr, num):
    cum_sum = 0
    c_idx = 0
    for i in range(len(arr)):
        cum_sum += arr[i]
        if num < cum_sum:
            return c_idx
        c_idx += 1
    raise Error("This shouldn't happen! Panic!")

Ce pare ca vrei sa faci e sa generezi un numar aleator din intervalul 0...len(arr) si fiecare element i sa fie extras cu probabiltate arr[i].

Exista o metoda de a face acest lucru cu ajutorul unui generator uniform in intervalul [0, 1] cu care presupun ca l-ai scos pe num ca mai sus. O metoda mai generala este inverse method. E multa matematica pe acolo, dar in principiu trebuie sa calculezi inversa unei functii - codul de mai sus face asta babeste.

Daca vrei sa faci asta de multe (multe) ori, are sens sa calculezi un array de forma carr[0] = arr[0], carr[i] = arr[i] + carr[i-1] si sa faci o cautare binara in ea.

2 Likes

@alexjorj Multumesc Alex, explicatia ta a clarificat problema.

Eu am pornit de la premiza ca elementele array-ului reprezinta indexul intervalelor pe lungimea segmentului.

De fapt elementele array-ului reprezinta length-ul fiecarui interval.
Folosim aceste lengths ptr. a calcula indexul intervalelor pe lungimea segmentului.

Am adaugat si un info_grafic care sa explice ptr. cei ce intalnesc o problema similara:

Am implementat si codul si acum rezulatele sunt asa cum ma asteptam:

Si codul, impartit in 2 functii ptr. a evita calculatul indexul segmentelor de mai multe ori:

func get_arr_elem_interval_indexes(arr):
	# arr elems are just segment lengths (0.1 lengtt + 0.4 length + 0.5 length=1 length)
	# now let's calc segment intervals (0.1 -firs interval index, 0.5 - second interval index, 1 final interval index)
	# note how from 0 to 0.1 - 0.1 length, from 0.1 to 0.5 - 0.4 length, from 0.5 to 1 - 0.5 length
	var interval_indexes=[]
	var start_index=0
	for i in arr:
		var interval_index=start_index+i
		interval_indexes.append(interval_index)
		start_index=interval_index
	return interval_indexes


# given an array [0.1,0.5,1] anda num 0.15
# it will return the index of elem for which num is smaller.
# in this case it will return index 1 since 0.15 is maller than 0.5
# pass a sorted array for tis to work properly
# Usually you pass teh result from get_arr_elem_interval_indexes
func get_smallest_index_for_sorted_arr(arr,num):
	for i in range(len(arr)):
		if num<arr[i]:
			return i
	return -1

Este folosit in felul urmator:

	        var arr=[0.1,0.4,0.5]
		var chance=Utils.rand_float(0,1)
		var interval_indexes=Utils.get_arr_elem_interval_indexes(arr)
		var closest_index=Utils.get_smallest_index_for_sorted_arr(interval_indexes,chance)
2 Likes

Hey @horia141 ! Implementarea ta e mai concisa si cred ca e posibil sa fie mai performanta in anumite cazuri cand e chemata de putine ori(de vreme ce calculeaza si sum-ul la fiecare iteratie dar nu continua sa itereze daca a gasit index-ul potrivit).

Implementarea mea calculeaza o singura data toate sumele. Apoi foloseste array-u rezultat doar ptr. a verifica index-ul corect.

Thanks! :slight_smile: