Addition of weighted selection to custom providers by SamuelNeceda · Pull Request #1414 · datafaker-net/datafaker

SamuelNeceda · 2024-10-30T21:04:04Z

As for the Issue, I have implemented the capability for weighted selection with custom providers.

#1314

what-the-diff · 2024-10-30T21:04:31Z

PR Summary

Implementation of a New Function
The code now includes a new method called weightedArrayElement that is placed inside RandomService.java. This added function allows for selecting an item from a list of maps, but the odds of any specific item being selected can be uneven or "weighted".
Introduction of Input Checks
The newly implemented weightedArrayElement function has also been hardened against faults by adding validation that checks the input data. If the input is not provided, is left empty, or has weights that are zero or less, it will now throw exceptions and prevent further operations.
Addition of Test Cases
To ensure that the new weightedArrayElement function performs correctly, the RandomServiceTest.java class has been updated with multiple tests. These tests confirm the function's performance with different scenarios, including the use of a single or multiple elements, inputs that are null or empty, and situations with zero or negative weights.
Introduction of New Utility Class for Testing
Developers now have a TestConstants.java utility class at their disposal, facilitating easier testing. This class houses various constants, which not only enhance the readability of the tests but also makes their maintenance much easier.
Defining Constants for Testing
The newly created TestConstants.java contains a set of newly defined constants including WEIGHT_KEY, VALUE_KEY, and various element weights. These constants are to ensure consistency across tests and improve the ease-of-use and readability of the testing process.

kingthorin

What happens in the case of an empty or non-double weight?

(I haven't pulled the code and tried).

I'd also suggest creating a test YAML file and testing as you see users actually using it. (Which can likely be re-used for documentation later)

SamuelNeceda · 2024-10-31T21:58:41Z

@kingthorin , great catch on the edge cases for weights! I’ve implemented a solution that should address the necessary scenarios.

Additionally, in this file, I demonstrated the weighted selection with a custom hardcoded provider.

Currently, I’m working on implementing weighted selection using a custom provider that loads data from a YAML file. I’ve created the file, but I’m facing challenges loading the data to apply the weighted selection. Following the logic from the ant() method, it looks like the key changes might be needed in AbstractProvider and FakeValueService classes, but I'm unsure how to proceed. Could you please provide any recommendations?

codecov · 2024-10-31T22:13:06Z

Codecov Report

Attention: Patch coverage is 82.35294% with 6 lines in your changes missing coverage. Please review.

Project coverage is 92.20%. Comparing base (0f50bbe) to head (8d0de4a).

Files with missing lines	Patch %	Lines
...main/java/net/datafaker/service/RandomService.java	82.35%	3 Missing and 3 partials ⚠️

Additional details and impacted files

@@             Coverage Diff              @@
##               main    #1414      +/-   ##
============================================
- Coverage     92.22%   92.20%   -0.03%     
- Complexity     3165     3182      +17     
============================================
  Files           320      320              
  Lines          6173     6207      +34     
  Branches        592      596       +4     
============================================
+ Hits           5693     5723      +30     
- Misses          335      336       +1     
- Partials        145      148       +3

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

Oops still draft

snuyanzin · 2024-10-31T22:31:48Z

src/main/java/net/datafaker/service/RandomService.java

+    private double calculateTotalWeight(List<Map<String, Object>> items) {
+        return items.stream()
+            .mapToDouble(item -> (Double) item.get(WEIGHT_KEY))
+            .sum();
+    }


How will it work if

there are N weights each of them is Double.MAX_VALUE - 1 or something like that, are we protected against overflow?

what if there are custom fields with same name however with different meaning in same provider and even number type? Will there at least any warning appear or how should user be warned about this (without hours of debugging)

I appreciate your insight regarding potential overflow. While weights are typically not expected to be extremely large, I've implemented an iterative approach to ensure that adding each weight is checked against Double.MAX_VALUE. This helps prevent overflow in cases where unusually large weights might occur.

I believe that values should be unique when performing weighted selection. Therefore, while weights can be the same, duplicates in the value parameter trigger an exception that informs the user of the specific duplicate value. This approach seems appropriate to ensure the integrity of the selection process.

While weights are typically not expected to be extremely large,

if we are talking about project in open source which is used then any input should be expected if it passes all existing validation

Sure, I got your point. I provided the guard for overflow.

snuyanzin · 2024-10-31T22:45:13Z

src/main/java/net/datafaker/service/RandomService.java

+        for (Map<String, Object> item : items) {
+            currentWeight += (Double) item.get(WEIGHT_KEY);
+            if (randomValue < currentWeight) {
+                return (T) item.get(VALUE_KEY);
+            }
+        }


is there a reason to do this on each iteration?
IIUC data in file is persistent then we could sort them once including all unboxing things (not sure if need them...) only once and have something like array of doubles
then just use something like adopted binary search

or did I miss anything here?

Thank you for the suggestion. I implemented the proposed optimization of sorting and preprocessing the cumulative weights once, which improved the efficiency.

src/test/java/net/datafaker/utils/TestConstants.java

snuyanzin · 2024-11-01T17:08:30Z

src/main/java/net/datafaker/service/RandomService.java

+    private double[] cumulativeWeights;
+    private Object[] values;
+


Definitively it should be outside of this class
Otherwise it will slow down all other not weight related cases

There should be a weight provider dedicated interface/class instead this very generic

i guess same for methods otherwise we are in situation that we have functionality in generic class which doesn't support 100% of existing providers
at the same time for each instance we add more memory footprint

I've moved all the logic for the weight selector to the WeightedRandomSelector class. Currently, I’ve placed it in the service package, as it seems to fit best there, though I believe you initially suggested putting it in the providers package?

Additionally, based on the issue description, WeightedRandomSelector appears intended mainly for custom providers. At this point, no provider has data in the format required for this functionality. Should I register it only to be used with custom providers, or do you have a different solution in mind?

snuyanzin · 2024-11-01T17:16:30Z

src/main/java/net/datafaker/service/RandomService.java

+
+    private void assertUniqueValues(Map<String, Object> item, Set<Object> values) {
+        Object value = item.get(VALUE_KEY);
+        if (!values.add(value)) {


Another problem Set for objects
this is a very error prone to assume that for very object there are suitable equals/hashcode

Do you have some suggestions on how to refactor it?

snuyanzin · 2024-11-01T17:16:56Z

src/main/java/net/datafaker/service/RandomService.java

+        if (item == null || item.isEmpty()) {
+            throw new IllegalArgumentException("Item cannot be null or empty");
+        }
+        if (!item.containsKey(WEIGHT_KEY) || !item.containsKey(VALUE_KEY)) {


same here about equals/hashcode

Sorry, but I might not get this. I am checking if each item contains weight and value keys defined as strings. If for some reason they do not, I am directly throwing an exception.

… FakeValuesService.java

SamuelNeceda · 2024-11-17T21:26:14Z

@kingthorin @snuyanzin
I have removed all changes from the mentioned classes, ensuring that the WeightedRandomSelector can now be instantiated independently.

Additionally, I have updated the documentation and examples to emphasize that weighted random selection is still in the Proof of Concept (POC) stage.

I believe these changes address your concerns, and the PR is now ready for merging. Any future suggestions for improvements will be considered and addressed in subsequent Issues, ...

SamuelNeceda · 2024-11-19T20:23:38Z

@snuyanzin , would you be so kind and have a look at the PR please. I am awaiting your approve so it can be merged.

snuyanzin · 2024-11-24T12:22:08Z

docs/documentation/custom-providers.md

+            List<Map<String, Object>> insects = List.of(
+                Map.of("value", "Driver ant", "weight", 6.0),
+                Map.of("value", "Fire ant", "weight", 3.0),
+                Map.of("value", "Harvester ant", "weight", 1.0)
+            );


It would be better to follow same way as existing example and place all the example data in constant like above rather than generating it for each method invocation

snuyanzin · 2024-11-24T12:23:15Z

docs/documentation/custom-providers.md

+                Map.of("value", "Harvester ant", "weight", 1.0)
+            );
+
+            WeightedRandomSelector selector = new WeightedRandomSelector(new Random());


Also I guess we don't need to create a new selector per getter invocation and can reuse it

snuyanzin · 2024-11-24T12:32:19Z

src/main/java/net/datafaker/service/WeightedRandomSelector.java

+        if (!(weightObj instanceof Double weight)) {
+            throw new IllegalArgumentException("Weight must be a non-null Double");
+        }
+        if (weight <= 0 || Double.isNaN(weight) || Double.isInfinite(weight)) {


out of curiosity: why do we consider weight = 0 as an error?
IMHO it might be a valid way to turn off this value while the total must be positive

My thought was that a weight of 0 implies that the corresponding item cannot be selected. Since WeightedRandomSelector is designed to assign probabilities proportional to weights, including a weight of 0 would lead to unnecessary processing for an element that cannot be selected. But I refactored the code to enable also 0 weight, allowing weights of 0 to be a legitimate way to "turn off" certain elements while still keeping them in the configuration

snuyanzin · 2024-11-24T12:44:10Z

src/test/java/net/datafaker/service/WeightedRandomSelectorTest.java

+    @ParameterizedTest
+    @MethodSource("weightedRandomSelectorProvider")
+    void testWeightedArrayElement_withZeroWeight(WeightedRandomSelector weightedRandomSelector) {
+        List<Map<String, Object>> items = List.of(
+            Map.of(VALUE_KEY, ELEMENT_1, WEIGHT_KEY, ZERO_WEIGHT),
+            Map.of(VALUE_KEY, ELEMENT_2, WEIGHT_KEY, ELEMENT_2_WEIGHT)
+        );
+
+        assertThatThrownBy(() -> weightedRandomSelector.select(items))
+            .isInstanceOf(IllegalArgumentException.class)
+            .hasMessage("Weight must be a positive number and cannot be NaN or infinite");
+    }
+
+    @ParameterizedTest
+    @MethodSource("weightedRandomSelectorProvider")
+    void testWeightedArrayElement_withNegativeWeight(WeightedRandomSelector weightedRandomSelector) {
+        List<Map<String, Object>> items = List.of(
+            Map.of(VALUE_KEY, ELEMENT_1, WEIGHT_KEY, NEGATIVE_WEIGHT),
+            Map.of(VALUE_KEY, ELEMENT_2, WEIGHT_KEY, ELEMENT_2_WEIGHT)
+        );
+
+        assertThatThrownBy(() -> weightedRandomSelector.select(items))
+            .isInstanceOf(IllegalArgumentException.class)
+            .hasMessage("Weight must be a positive number and cannot be NaN or infinite");
+    }
+
+    @ParameterizedTest
+    @MethodSource("weightedRandomSelectorProvider")
+    void testWeightedArrayElement_withInfiniteWeight(WeightedRandomSelector weightedRandomSelector) {
+        List<Map<String, Object>> items = List.of(
+            Map.of(VALUE_KEY, ELEMENT_1, WEIGHT_KEY, Double.POSITIVE_INFINITY),
+            Map.of(VALUE_KEY, ELEMENT_2, WEIGHT_KEY, ELEMENT_2_WEIGHT)
+        );
+
+        assertThatThrownBy(() -> weightedRandomSelector.select(items))
+            .isInstanceOf(IllegalArgumentException.class)
+            .hasMessage("Weight must be a positive number and cannot be NaN or infinite");
+    }


It looks like all these tests (my be some more) could be replaced with one parameterized test
since we have input of key/value sequence, exception and error message

Good point, I refactored a whole test class to use a parameterized tests.

…datafaker into weighted_selection

snuyanzin · 2024-11-24T14:36:20Z

I think this version is much closer to be merged, I left some comments

SamuelNeceda · 2024-11-24T14:39:05Z

Thanks for the comments @snuyanzin , I have already addressed them.

snuyanzin · 2024-11-24T14:39:48Z

src/test/java/net/datafaker/service/WeightedRandomSelectorTest.java

+     */
+    @ParameterizedTest
+    @MethodSource("exceptionCasesProvider")
+    void testWeightedArrayElement_exceptions(List<Map<String, Object>> items, String expectedMessage) {


Can you rearrange a bit methods within this class
in a way: methods with different test annotations first
all other methods after that

tests were rearranged

snuyanzin · 2024-11-24T14:40:41Z

src/test/java/net/datafaker/service/WeightedRandomSelectorTest.java

+     */
+    @ParameterizedTest
+    @MethodSource("exceptionCasesProvider")
+    void testWeightedArrayElement_exceptions(List<Map<String, Object>> items, String expectedMessage) {


Suggested change

void testWeightedArrayElement_exceptions(List<Map<String, Object>> items, String expectedMessage) {

void testWeightedArrayElementExceptions(List<Map<String, Object>> items, String expectedMessage) {

or another way

Suggested change

void testWeightedArrayElement_exceptions(List<Map<String, Object>> items, String expectedMessage) {

void testWeightedArrayElementFailureCase(List<Map<String, Object>> items, String expectedMessage) {

lets's do not mix different notations

snuyanzin · 2024-11-24T15:16:20Z

src/main/java/net/datafaker/service/WeightedRandomSelector.java

+     *                                  - any values in the list are not unique or null,
+     *                                  - the sum of weights exceeds Double.MAX_VALUE.
+     */
+    public <T> T select(List<Map<String, Object>> items) {


Suggested change

public <T> T select(List<Map<String, Object>> items) {

public static <T> T select(List<Map<String, Object>> items) {

this seems not addressed yet
not sure if we need it public

By the current design, the method public T select(List<Map<String, Object>> items) cannot be static because it relies on the random field of the WeightedRandomSelector record, which is an instance field.
If the goal is to make the method static, I will need to explicitly pass the Random object to the method.
From my point of view, the current implementation is correct.

SamuelNeceda added 5 commits October 21, 2024 22:16

initial progress

4a70b22

unit tests added

ccd7051

refactor to map

5d14afe

Update RandomServiceTest.java

90e99e7

Merge branch 'main' into weighted_selection

a76280a

kingthorin reviewed Oct 30, 2024

View reviewed changes

SamuelNeceda added 3 commits October 31, 2024 20:31

enhance handling for edge cases

2525cad

Merge branch 'main' into weighted_selection

10856e6

hardcoded custom data provider

8d0de4a

kingthorin previously approved these changes Oct 31, 2024

View reviewed changes

snuyanzin reviewed Oct 31, 2024

View reviewed changes

increase tests coverage

754af80

kingthorin reviewed Oct 31, 2024

View reviewed changes

src/test/java/net/datafaker/utils/TestConstants.java Outdated Show resolved Hide resolved

SamuelNeceda added 4 commits November 1, 2024 12:39

reference test constants directly in the test class

8499822

check for duplicates & overflow prevention

ea4c662

improve efficiency

0a0c726

Merge branch 'main' into weighted_selection

012b483

snuyanzin reviewed Nov 1, 2024

View reviewed changes

SamuelNeceda added 4 commits November 1, 2024 18:46

update java doc

4ea7223

separate logic to WeightedRandomSelector

0d3b828

register provider & add documentation

49efe88

Merge branch 'main' into weighted_selection

353a4a5

SamuelNeceda changed the title ~~[Draft] Addition of weighted selection to custom providers.~~ Addition of weighted selection to custom providers Nov 3, 2024

SamuelNeceda added 6 commits November 17, 2024 19:23

Merge branch 'main' into weighted_selection

1074120

remove implementation from BaseFaker.java, ProviderRegistration.java,…

5f7f43c

… FakeValuesService.java

pr review changes

c65938d

update doc

60299a4

Update FakeValuesService.java

9a06e2d

Update UniqueTest.java

a70472b

bodiam mentioned this pull request Nov 18, 2024

#1412 fix concurrency issue in CopyOnWriteMap #1419

Merged

Merge branch 'main' into weighted_selection

1b04d0a

asolntsev added this to the 2.4.3 milestone Nov 19, 2024

asolntsev linked an issue Nov 19, 2024 that may be closed by this pull request

Add weighted selection #1314

Closed

asolntsev added the enhancement New feature or request label Nov 19, 2024

snuyanzin reviewed Nov 24, 2024

View reviewed changes

SamuelNeceda added 4 commits November 24, 2024 13:35

Merge branch 'main' into weighted_selection

1be2de5

Update pom_update.yml

8112e46

Merge branch 'weighted_selection' of https://github.com/SamuelNeceda/…

0a92ca5

…datafaker into weighted_selection

pr review

3f58c88

snuyanzin reviewed Nov 24, 2024

View reviewed changes

tests refactored

2712e8b

snuyanzin reviewed Nov 24, 2024

View reviewed changes

snuyanzin approved these changes Nov 24, 2024

View reviewed changes

kingthorin approved these changes Nov 24, 2024

View reviewed changes

kingthorin merged commit 59eebb9 into datafaker-net:main Nov 24, 2024

	void testWeightedArrayElement_exceptions(List<Map<String, Object>> items, String expectedMessage) {
	void testWeightedArrayElementExceptions(List<Map<String, Object>> items, String expectedMessage) {

	void testWeightedArrayElement_exceptions(List<Map<String, Object>> items, String expectedMessage) {
	void testWeightedArrayElementFailureCase(List<Map<String, Object>> items, String expectedMessage) {

	public <T> T select(List<Map<String, Object>> items) {
	public static <T> T select(List<Map<String, Object>> items) {

Conversation

SamuelNeceda commented Oct 30, 2024 • edited by kingthorin Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

what-the-diff bot commented Oct 30, 2024

PR Summary

Uh oh!

kingthorin left a comment

Choose a reason for hiding this comment

Uh oh!

SamuelNeceda commented Oct 31, 2024

Uh oh!

codecov bot commented Oct 31, 2024

Codecov Report

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

snuyanzin Nov 1, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SamuelNeceda commented Nov 17, 2024

Uh oh!

SamuelNeceda commented Nov 19, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

snuyanzin commented Nov 24, 2024

Uh oh!

SamuelNeceda commented Nov 24, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

snuyanzin Nov 24, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

SamuelNeceda commented Oct 30, 2024 •

edited by kingthorin

Loading

snuyanzin Nov 1, 2024 •

edited

Loading

SamuelNeceda commented Nov 19, 2024 •

edited

Loading

snuyanzin Nov 24, 2024 •

edited

Loading