Created
April 5, 2019 04:40
-
-
Save jxxcarlson/2b028fe107e0668d30a15b560d7ce3c3 to your computer and use it in GitHub Desktop.
Schelling's model
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
For the Schelling model, there is one file of interest, https://github.com/jxxcarlson/schelling/blob/master/src/Schelling.elm. | |
The main data structures are Cell, an opaque type, and Array Cell. | |
I use 1D arrays, but process them as if they were 2D arrays using | |
the functions | |
location :(Int, Int) -> Int | |
location (row, col) = | |
nRows * row + col | |
matrixIndex : Int -> (Int, Int) | |
matrixIndex n = | |
(n // nCols, modBy nCols n) | |
Seems retro, but actually works well for this problem. I don't | |
know if it has bad performance implications. | |
The main function is | |
updateCells : List (Int, Int) -> Array Cell -> Array Cell | |
updateCells tupleList cellArray = | |
List.foldl updateCell cellArray tupleLis | |
The functon of the tupleList : List (Int, Int) to (a) determine the order in which | |
cells are updated and (b) to furnish a random number which is used | |
in the update process for the given cell. In practie, (via Main.elm), | |
the tupleList is a list or pairs where the projection to the first | |
coordinate is a random permutation of the list 0, 1, ... (N^2 - 1), | |
where the array is NxN. The projection to the second coordinate is a | |
list of random integers. | |
The function upDateCells is just a driver for | |
updateCell : (Int, Int) -> Array Cell -> Array Cell | |
updateCell (idx, rand) cellArray = | |
let | |
(row, col) = matrixIndex idx | |
updatedCell = updateEmotionalStateOfCellAtIndex (row, col) cellArray | |
in | |
if emotionalState updatedCell == Unsatisfied then | |
swapWithUnoccupiedCell rand updatedCell cellArray | |
else | |
replace updatedCell cellArray | |
While the app works just fine for 40x40 arrays with 500 ms delay between updates, | |
I would like for it perform as well as possible. In general, I am interested | |
in places where the code can be improved. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Here is the relevant part of the old data structure:
I changed it to this:
Then the index function is
Of course one now has to be VERY careful about how cells are updated. If they are not "moved", all is OK. In this project, the only way cells move is by swapping two cells. So we run all changes through this function,
which swaps the indices when the cells are swapped. Then cells always
carry a valid index.
With Evan's amazing compiler, it took exactly one hour to conceive and implement
all the changes. The result (using the benchmark program) is a 47% decrease in
in execution time. This carries over the app. I had reduced the update interval
from 500 ms to 250 ms. But it was somewhat jerky. I've reduced the update
interval to 50ms and it is still very smooth. This is better than can be explained
by the above.