[RUBY]Arrays op een efficiente manier vergelijken

[van.der.schulting]

Hoihoi,

Ik heb het volgende programmeerprobleem in Ruby.
Ik heb een lijst met nummers. In een loop pak ik elke keer een nummer. Elk nummer moet een keer 'gepakt' zijn, voordat een nummber opnieuw gepakt kan worden.
Een nummer uit de lijst pakken kan op twee manieren.
- random
- gewogen (het ene nummer heeft een grotere kans geretourneerd te worden dan het andere nummer). Bijvoorbeeld nummerA heeft gewicht 1, nummberB gewicht 3 etc.

Ik zat eraan te denken dat het me het simpelste leek om een gewogen nummer het aantal keer van het gewicht in de lijst te zetten. Dus bij gewicht 1, 1x in de lijst; gewicht 2, 2x in de lijst, etc.

Nu los ik het probleem als volgt op:
Ik heb twee lijsten (arrays):
- een array met alle nummers (all_numbers);
- een array met de nummers die ik al een keer gehad heb (already_seen);

Ik doorloop de volgende stappen:
1. Ik bepaal welke nummers ik nog niet gehad heb als volgt:

code:

all_numbers - already_seen = not_seen

2. Uit de nieuwe array pak ik een nieuw nummer, dit geef ik weer en voeg ik toe aan de array already_seen.

Maar volgens mij moet dit sneller en efficienter kunnen met behulp van een handig algoritme.
Ik heb bijvoorbeeld gehoord dat Google dit probleem oplost, niet door de twee arrays met elkaar te vergelijken, maar door van beide arrays een hash te maken en dat met elkaar te vergelijken... Masar hoe dat precies werkt, geen idee...

Heeft iemand een idee hoe ik mijn probleem efficienter kan aanpakken? Is hiervoor misschien een heel efficient algoritme?

[ Voor 15% gewijzigd door van.der.schulting op 21-03-2014 13:44 ]

[Bigs]

Het maken van extra arrays is in Ruby erg kostbaar. Ik zou het simpel houden en als volgt aanpakken:

code:

a = [1,2,3,4,5]     # => [1, 2, 3, 4, 5]
a.delete(rand(a.length))     # => 4
a     # => [1, 2, 3, 5]

[ Voor 4% gewijzigd door Bigs op 21-03-2014 10:06 ]

[Keeper]

Wat je precies wilt is een beetje vaag, dus mogelijk kan je het gewoon heel simpel oplossen door eerst de elementen in de array random te sorteren en er dan gewoon doorheen te loopen?

code:

a = [1, 2, 3, 4, 5]
a.shuffle.each{|i| puts i}

[Bigs]

Keeper schreef op vrijdag 21 maart 2014 @ 11:26:
Wat je precies wilt is een beetje vaag, dus mogelijk kan je het gewoon heel simpel oplossen door eerst de elementen in de array random te sorteren en er dan gewoon doorheen te loopen?

code:

a = [1, 2, 3, 4, 5]
a.shuffle.each{|i| puts i}

Ohja dat is natuurlijk nog beter

[van.der.schulting]

Je hebt gelijk, ik heb het onvolledig uitgelegd.

Een nummer uit de lijst pakken kan op twee manieren.
- random
- gewogen (het ene nummer heeft een grotere kans geretourneerd te worden dan het andere nummer). Bijvoorbeeld nummerA heeft gewicht 1, nummberB gewicht 3 etc.

Ik zat eraan te denken dat het me het simpelste leek om een gewogen nummer het aantal keer van het gewicht in de lijst te zetten. Dus bij gewicht 1, 1x; gewicht 2, 2x, etc.

Doordat nummers gewogen kunnen is shuffelen dus helaas niet mogelijk. Het kan wel, maar dan zou ik bij een gewogen nummer alsnog de hele array moeten doorlopen om het nummer eruit te halen.

[Bigs]

In dat geval heb je wel iets aan de antwoorden in deze StackOverflow vraag (eerste resultaat op Google):

Weighted random selection from array.

Iets te veel voor mij om hier samen te vatten.

[ Voor 5% gewijzigd door Bigs op 21-03-2014 13:51 ]

[drm]

Maar volgens mij moet dit sneller en efficienter kunnen met behulp van een handig algoritme.

Waarom denk je dat?

[Soultaker]

Wat je dus wil is een manier om een random permutatie van een lijst waarden te maken, waarbij de waarde op elke positie willekeurig, maar naar gewicht (in plaats van uniform verdeeld) bepaald wordt. Aan de eis: “elk nummer moet een keer 'gepakt' zijn, voordat een nummer opnieuw gepakt kan worden” kun je voldoen door simpelweg een permutatie helemaal af te lopen voordat je een nieuwe genereert.

Het genereren van een gewogen willekeurige permutatie kan volgens mij in O(N log N) tijd, door de lijst van waarden in tweeën te splitsen, elke lijst afzonderlijk (gewogen) te husselen, en vervolgens de gehusselde lijsten probabilistisch samen te voegen.

Geïmplementeerd in Python ziet dat er zo uit:

Python:

import collections
import random

WeightedValue = collections.namedtuple('WeightedValue', ['value','weight'])

def weighted_random_merge(list1, list2):
        pos1, weight1 = 0, sum(elem.weight for elem in list1)
        pos2, weight2 = 0, sum(elem.weight for elem in list2)
        merged = [ ]
        while pos1 < len(list1) and pos2 < len(list2):
                if random.uniform(-weight1, +weight2) < 0:
                        merged.append(list1[pos1])
                        weight1 -= list1[pos1].weight
                        pos1 += 1
                else:
                        merged.append(list2[pos2])
                        weight2 -= list2[pos2].weight
                        pos2 += 1
        return merged + list1[pos1:] + list2[pos2:]

def weighted_random_permutation(list):
        if len(list) < 2:
                return list
        return weighted_random_merge(
                weighted_random_permutation(list[:len(list)//2]),
                weighted_random_permutation(list[len(list)//2:]) )

# Simpele test:
list = [ WeightedValue(1, weight=7),
         WeightedValue(2, weight=1),
         WeightedValue(3, weight=1),
         WeightedValue(4, weight=1),
         WeightedValue(5, weight=3.5) ]
for _ in range(100):
        print([elem.value for elem in weighted_random_permutation(list)])

... dit lijkt wel te doen wat je wil (hoewel ik het niet uitgebreid geverifieerd heb). Je kunt dit algoritme zelf wel porten naar Ruby, neem ik aan.

Dit algoritme kost O(N log N) tijd voor het husselen van N elementen; dat is beter dan de O(N²) van je huidige algoritme. (Eventueel zou je 'm ook nog iteratief in plaats van recursief kunnen implementeren, á la iteratieve merge sort.)