Proposed improvement : performance of #atRandom: in class Bag

[bstjean]

Whenever using Bag instances with a LARGE number of objects (like millions), #atRandom becomes less and less useable since it almost crawls to a halt. The problem resides in the fact that the Bag class inherits #atRandom: (which is called by #atRandom) from Collection and the current implementation of Collection>>#atRandom: uses #do: to iterate over EVERY item (virtual) of the bag. A faster method would be to use the occurrences of every object in the bag to iterate only over the keys in the dictionary instead of iterating over all the "virtual" items contained in the bag.

I have included a fix (see attached file).

Here are some example timings to show the performance difference:

Tests WITHOUT #atRandom: override!

Very good case : evaluated #atRandom 200 times in 17.27 seconds for 3000000 elements!
Average case : evaluated #atRandom 200 times in 193.38 seconds for 3000000 elements!
Worst case : evaluated #atRandom 200 times in 283.19 seconds for 3000000 elements!

Tests WITHOUT #atRandom: override!

Very good case : evaluated #atRandom 200 times in 16.26 seconds for 3000000 elements!
Average case : evaluated #atRandom 200 times in 185.52 seconds for 3000000 elements!
Worst case : evaluated #atRandom 200 times in 295.37 seconds for 3000000 elements!

---

Tests WITH #atRandom: override!

Very good case : evaluated #atRandom 200 times in 12.76 seconds for 3000000 elements!
Average case : evaluated #atRandom 200 times in 37.89 seconds for 3000000 elements!
Worst case : evaluated #atRandom 200 times in 44.79 seconds for 3000000 elements!

Tests WITH #atRandom: override!

Very good case : evaluated #atRandom 200 times in 12.61 seconds for 3000000 elements!
Average case : evaluated #atRandom 200 times in 37.93 seconds for 3000000 elements!
Worst case : evaluated #atRandom 200 times in 44.73 seconds for 3000000 elements!
Bag-atRandom.zip

[welcome]

Thanks for opening your first issue! Please check the CONTRIBUTING documents for some tips about which information should be provided. You can find information of how to do a Pull Request here: https://github.com/pharo-project/pharo/wiki/Contribute-a-fix-to-Pharo

GitHub

pharo-project/pharo

Pharo is a dynamic reflective pure object-oriented language supporting live programming inspired by Smalltalk. - pharo-project/pharo

[svenvc]

Why do you make it so hard to look at what you propose ? A zip file of a single method ?

Anyway, this is what you are proposing:

Bag>>#atRandom: aGenerator
	"Answer a random element of the receiver. Uses aGenerator which
    should be kept by the user in a variable and used every time. Use
    this instead of #atRandom for better uniformity of random numbers because 
	only you use the generator. Causes an error if self has no elements."
	| rand index |

	self emptyCheck.
	rand := aGenerator nextInt: self size.
	index := 0.
	self doWithOccurrences: [:key :count | 	index := index + count.
														rand <= index ifTrue: [^key]].
	^ self errorEmptyCollection! !

I don't think this would be correct: says a bag contains 1000 times 1 and 10 times 2. Your approach would return 1 and 2 with each a 50% change, which does not seem to be correct since 1 occurs 100 times more frequently, and should thus be picked 100 more at random.

[bstjean]

Nope.  You missed it. You can verify this by yourself using this: | bag results | bag := Bag new. results := Bag new. 1000 timesRepeat: [ bag add: 1]. 100 timesRepeat: [ bag add: 2]. 100000 timesRepeat: [ results add: bag atRandom ]. results inspect.

On 2019-12-18 05:55, Sven Van Caekenberghe wrote: Why do you make it so hard to look at what you propose ? A zip file of a single method ? Anyway, this is what you are proposing: |Bag>>#atRandom: aGenerator "Answer a random element of the receiver. Uses aGenerator which     should be kept by the user in a variable and used every time. Use     this instead of #atRandom for better uniformity of random numbers because only you use the generator. Causes an error if self has no elements." | rand index | self emptyCheck. rand := aGenerator nextInt: self size. index := 0. self doWithOccurrences: [:key :count | index := index + count. rand <= index ifTrue: [^key]]. ^ self errorEmptyCollection! ! | I don't think this would be correct: says a bag contains 1000 times 1 and 10 times 2. Your approach would return 1 and 2 with each a 50% change, which does not seem to be correct since 1 occurs 100 times more frequently, and should thus be picked 100 more at random. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#5392?email_source=notifications&email_token=AEFVQ7YPHZSPJJVTEMLIDKLQZH6TPA5CNFSM4J4HLVYKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEHFXPGI#issuecomment-566982553>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEFVQ754LQK4VW3TWARG7P3QZH6TPANCNFSM4J4HLVYA>.

-- ----------------- Benoît St-Jean Yahoo! Messenger: bstjean Twitter: @BenLeChialeux Pinterest: benoitstjean Instagram: Chef_Benito IRC: lamneth GitHub: bstjean Blogue: endormitoire.wordpress.com "A standpoint is an intellectual horizon of radius zero". (A. Einstein)

[bstjean]

Oups!  Made a typo! Check it with this: | bag results | bag := Bag new. results := Bag new. 1000 timesRepeat: [ bag add: 1]. 10 timesRepeat: [ bag add: 2]. 1000 timesRepeat: [ results add: bag atRandom ]. results inspect.

On 2019-12-18 05:55, Sven Van Caekenberghe wrote: Why do you make it so hard to look at what you propose ? A zip file of a single method ? Anyway, this is what you are proposing: |Bag>>#atRandom: aGenerator "Answer a random element of the receiver. Uses aGenerator which     should be kept by the user in a variable and used every time. Use     this instead of #atRandom for better uniformity of random numbers because only you use the generator. Causes an error if self has no elements." | rand index | self emptyCheck. rand := aGenerator nextInt: self size. index := 0. self doWithOccurrences: [:key :count | index := index + count. rand <= index ifTrue: [^key]]. ^ self errorEmptyCollection! ! | I don't think this would be correct: says a bag contains 1000 times 1 and 10 times 2. Your approach would return 1 and 2 with each a 50% change, which does not seem to be correct since 1 occurs 100 times more frequently, and should thus be picked 100 more at random. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#5392?email_source=notifications&email_token=AEFVQ7YPHZSPJJVTEMLIDKLQZH6TPA5CNFSM4J4HLVYKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEHFXPGI#issuecomment-566982553>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEFVQ754LQK4VW3TWARG7P3QZH6TPANCNFSM4J4HLVYA>.

-- ----------------- Benoît St-Jean Yahoo! Messenger: bstjean Twitter: @BenLeChialeux Pinterest: benoitstjean Instagram: Chef_Benito IRC: lamneth GitHub: bstjean Blogue: endormitoire.wordpress.com "A standpoint is an intellectual horizon of radius zero". (A. Einstein)

[svenvc]

OK, now I see. I was thrown off by the weird formatting ;-)

The final expression is not needed, since you started with an emptyCheck.

Reformatted then:

Bag>>#atRandom: aGenerator
	"Answer a random element of the receiver. Uses aGenerator which
	should be kept by the user in a variable and used every time. Use
	this instead of #atRandom for better uniformity of random numbers because 
	only you use the generator. Causes an error if self has no elements."

	| rand index |
	self emptyCheck.
	rand := aGenerator nextInt: self size.
	index := 0.
	self doWithOccurrences: [ :key :count | 
		index := index + count.
		rand <= index ifTrue: [ ^ key ] ]

Still, we need a PR as well. And maybe a specific test unless this is already covered by other tests.

[bstjean]

True! I just picked the original and changed the #do: loop to use #doWithOccurrences: ! To really see a difference, you'd need a big bag (1M+ works really fine) to notice the significant improvement! And it would be difficult to create a test to compare a method that exists to a method that is no longer there. Anyone got suggestions besides compiling and removing code on the fly ?

[svenvc]

I did not mean testing the performance, that is too hard.
I meant testing the correctness of your change (for example the fact that the loop always answers and does not fall through), to make sure your improvement does not break anything unforeseen.

[svenvc]

#5445