Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Sort colors in .Filter in a stable way, even with duplicate names #25

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

aligator
Copy link

@aligator aligator commented Dec 2, 2024

Maybe fixes #24

My idea is to add a deterministic sort by the color if the names are the same.
On my first tests it seems that

	sort.Slice(c, func(i, j int) bool {
		if c[i].Name == c[j].Name {
			return ToHex(c[i].Color) < ToHex(c[j].Color)
		}
		di := smetrics.WagnerFischer(strings.ToLower(c[i].Name), s, 1, 1, 2)
		dj := smetrics.WagnerFischer(strings.ToLower(c[j].Name), s, 1, 1, 2)
		return di < dj
	})

is enough to make it stable,
However maybe it is even more guaranteed if I use .SliceStable instead. So I used that.

I tried to write a test for this, but it is quite hard to reproduce this error in a test, because when I create a simple loop calling the filter multiple times, I always get the same result for each round.

However when writing a simple program logging the output and executing this several times I get always different outputs. (50/50)
With the new code I always get the same output.

But for that its harder to write in a test.

And furthermore I noticed a very interesting / strange behavior with Go while I tried to write a test:

When I run the old code with this it fails. because the expected order is always the wrong way around.

Even when I switch the expected order it still fails. Because of some weird optimization, the actual order is exactly the opposite now^^
But I am not sure if that is reproducible on your end, because it also may have something to do with how the CPU execution branches work, Go compiler optimization or smth. like that? ...

However with the new code it always succeeds.

func TestFilterStability(t *testing.T) {
	//expectedOrder := []string{"#66d9ef", "#66d900"}
	expectedOrder := []string{"#66d900", "#66d9ef"}

	rounds := 2000
	for i := 0; i < rounds; i++ {

		p := Palette{}
		c := Colors{
			{"Duplicate", Hex("#66d900"), ""},
			{"Extra White", Hex("#F8F8F2"), ""},
			{"Caviar", Hex("#272822"), ""},
			{"Caviar Dark", Hex("#141411"), ""},
			{"Blue Beyond", Hex("#89BDFF"), ""},
			{"Urbane Bronze", Hex("#595959"), ""},
			{"Duplicate", Hex("#66d9ef"), ""},
			{"Tricorn Black", Hex("#383830"), ""},
			{"Soothing White", Hex("#E6E6E6"), ""},
			{"Ice Plant", Hex("#FD5FF1"), ""},
		}
		p.AddColors(c)

		cc := p.Filter("Duplicate")
		if ToHex(cc[0].Color) != expectedOrder[0] || ToHex(cc[1].Color) != expectedOrder[1] {
			t.Errorf("Expected %v, got %v", expectedOrder, []string{ToHex(cc[0].Color), ToHex(cc[1].Color)})
		}
	}
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Duplicates in Wikipedia lead to random colors
1 participant