Skip to content
This repository has been archived by the owner on Dec 16, 2021. It is now read-only.

Change definition of frequencies in Game of Life to be O(N log N) #17

Open
NicMcPhee opened this issue Dec 18, 2019 · 0 comments
Open

Comments

@NicMcPhee
Copy link
Member

The current approach to frequencies in the Game of Life project is O(N^2), so it starts to bog down when there are a lot of cells, especially when they're scattered around the world so there's little overlap.

An alternative is to sort the list of cells using posn< and then write a recursive helper function that marches down the list, counting the size of groups. The sorting is then O(N log N) and processing the sorted list is O(N). This does, in fact, considerably speed up the process, and the system seems to run smoothly even with pretty large numbers of cells.

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

No branches or pull requests

1 participant