Kam to reikia?

Nevisada pakanka, kad elementas būtų parinktas pasinaudojant vien tik atsitiktinių skaičių generatorium, kurio rezultatas yra tolygiai pasiskirstęs (”normalinis pasiskirstymas”) duotame intervale. Minėtu būdu dirba Winamp’as: aktyvavus “Shuffle”, kiekvienai dainai grojaraštyje yra vienoda tikimybė būti išrinktai. Bet kas jei grojaraštyje yra dainų, kurias mes labai mėgstame, ir tokių, kurias klausome tik dėl įvairumo? Tokiu atveju, kiekvienai dainai (bendru atveju - elementui) turime priskirti svorį - t.y. koeficientą, kuris padidina parinkimo tikimybę. Multimedia programos šį svorį pavadintų “dainos reitingu” ar panašiai.

Algoritmas

Tarkime turime tik dvi dainas - A ir B. Norime, kad A dauna būtų grojama dvigubai dažniau nei B. B priskiriame svorį 1, o A - 2. Dabar, generuojame atsitiktininį skaičių ne iš intervalo [1..elementų_suma] o iš intervalo [1..svorių_suma]. Sugeneravę skaičių, dainą išskaičiuojame taip:

1. SUMA = 0
2. ištraukiame elementą[i], i=[1..elementų_suma]
3. jeigu (sugeneruotas_skaičius>SUMA) AND (sugeneruotas_skaičius<=SUMA+i_elemento_svoris) tai radome reikiamą elementą
4. priešingu atveju SUMA=SUMA+i_elemento_svoris
5. ištraukiame sekantį elementą - GOTO “2.”

Patikrinę visus tris atvejus matome, kad A daina bus grojama jeigu sugeneruotas skaičius lygus arba 1 arba 2, o daina B - tik kai sugeneruotas skaičius yra 3.

Realizavimas - pirmas būdas

Sakykime, kad dainų pavadinimai saugomi MS SQL 2000 DBVS. Su svorių sumos skaičiavimu problemos nebūtų:

SELECT SUM(svoris) AS svoriu_suma FROM dainos

Bet kas, jei bazėje yra 1.000.000 įrašų, ir dar iškrito 900.000-asis? Reiškia, programa turės apdoroti 900.000 elementų… Dėl to būtų netikslinga šį darbą pavesti vartotojo programai. Atsitiktinio elemento parinkimas turi įvykti pačioje DBVS, o gražinamas turi būti tik parinktas elementas. Tam galime sukurti pvz.. Stored Procedure:

1. gauname svorių sumą
2. generuojame skaičių iš intervalo [1..svorių_suma]
3. vykdome anksčiau aprašytą algoritmą.

Realizavimas - antras būdas

Pirmą būdą galime bandyti optimizuoti. Pakeisime kodą taip, kad parinkimas vyktų iš dviejų dalių: pirma - mes nuspresime, su kokiu elementas turi būti parinktas; antra - pažymime (SELECT) visus elementus kurie turi tą svorį, ir tiesiai naudodami atsitiktinių skaičių generatorių išrenkame iš jų bet kurį elementą. Štai galutinis kodo variantas:

CREATE VIEW svoriai
AS
SELECT svoris, count(ID) AS kiekis, svoris*count(ID) AS sandauga
FROM gabalai
GROUP BY svoris
GO
DECLARE @suma int
SELECT @suma = sum(sandauga) FROM svoriai
 
-- === BEGIN reikia sugeneruoti atsitiktini skaiciu is intervalo [1..@suma]
DECLARE @atsitiktinis float
DECLARE @target int
SET @atsitiktinis = RAND(
(DATEPART(mm, GETDATE()) * 100000 ) +
(DATEPART(ss, GETDATE()) * 1000 ) +
DATEPART(ms, GETDATE()) )
SET @target = ROUND((@suma-1) * @atsitiktinis, 0)+1
-- PRINT @target
-- === END reikia sugeneruoti atsitiktini skaiciu is intervalo [1..@suma]
 
DECLARE svoriu_kursorius CURSOR
FOR
SELECT svoris, sandauga FROM svoriai
DECLARE @svoris sysname
DECLARE @sandauga sysname
DECLARE @kiek int
SET @kiek = 0
OPEN svoriu_kursorius
FETCH NEXT FROM svoriu_kursorius INTO @svoris, @sandauga
WHILE @@fetch_status = 0
BEGIN
IF (@target > @kiek) AND (@target <= @kiek + @sandauga)
BEGIN
BREAK
END
SET @kiek = @kiek + @sandauga
FETCH NEXT FROM svoriu_kursorius INTO @svoris, @sandauga
END
CLOSE svoriu_kursorius
-- PRINT 'parinktas svoris yra: '+CONVERT(VARCHAR(20), @svoris)
DEALLOCATE svoriu_kursorius
 
DECLARE @kiekis int
SELECT @kiekis = kiekis FROM svoriai WHERE svoris = @svoris
-- PRINT 'ju kiekis yra: '+CONVERT(VARCHAR(20), @kiekis)
 
DROP VIEW svoriai
 
-- === BEGIN reikia sugeneruoti atsitiktini skaiciu is intervalo [1..@kiekis]
DECLARE @kelintas int
SET @atsitiktinis = RAND(
(DATEPART(mm, GETDATE()) * 100000 ) +
(DATEPART(ss, GETDATE()) * 1000 ) +
DATEPART(ms, GETDATE()) )
SET @kelintas = ROUND((@kiekis-1) * @atsitiktinis, 0)+1
-- PRINT @kelintas
-- === END reikia sugeneruoti atsitiktini skaiciu is intervalo [1..@kiekis]
-- ---------
-- Pastaba: virtualios lentelės "svoriai" kūrimą reikėtų iškelti atskirai, o ne kurti ir šalinti kiekvieną kartą.
-- ---------

Dabar beliko pažymėti visas dainas kurių svoris yra @svoris ir gražinti įrašą, kurio eilės numeris yra @kelintas. Ant MySQL šitą galima būtų įvykdyti viena užklausa (pastaba: čia @kelintas reikia sumažinti vienetu, nes jis turi būti iš intervalo [0..kiekis-1] o ne [1..kiekis]):

SELECT * FROM gabalai WHERE svoris=@svoris LIMIT 1 OFFSET @kelintas

Ant MS SQL Server turbūt reikės vėl kurti kursorių.

Panašūs straipsniai

• Skaldyk ir valdyk! (21)
• Savaitgalio skaitiniai #32 (0)
• Savaitgalio skaitiniai #27 (0)
• Limituojam MySQL duombazės dydį su… pačiu MySQL (3)

Žymėti: kaip.tik.ten | del.icio.us | topix.lt | žynios.lt