On 6 July 2013 02:54, Felix Gallo <span dir="ltr"><<a href="mailto:felixgallo@gmail.com" target="_blank">felixgallo@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<br><div dir="ltr">In my continuing quest to learn erlang, I'm trying to implement a 1000x1000 grid into which items may be placed or removed, with perhaps a millon items in placement at once, spread fairly evenly across the grid.  No grid cell will hold more than a thousand things.  In the future, this grid may be shared across multiple processes, but for now I'm content to just try to get it working for one.<div>



<br></div><div>In the mutable world, you might structure it as a hashtable of hashes, or hashtable of sets etc., and use the coordinate tuple {x,y} as a key into the hash table, then mutate the list.  addtocell(Coordinate, Value) and removefromcell(Coordinate, Value) are very small, easy, and extremely fast (sub-second for a million iterations of addtocell()).</div>



<div><br></div><div>In erlang world, the naive approach of attempting to use a list of lists (and then a list of sets), and lists:keytake() worked for small grid dimensions (10x10) but ran for several minutes before I killed it when I moved up in grid size and tried to insert a million things, with no indication when it would ever finish.</div>



<div><br></div><div>The slightly less naive approach of using ets worked for larger grid dimensions, but was also highly nonperformant (60s for a million iterations of addtocell()).</div><div><br></div></div></blockquote>

<div><br>If I use the cell-id (Row-index, Col-index) as the key for each row in an ETS table, I am able to insert a million cells in about 1.25 seconds. The timing is the same whether the ets table is of type set or bag. Have I misunderstood your problem?<br>

<br>16> grid:init_grid(set).       <br><0.81.0><br>17> grid:add_cells(1000, 1000).<br>1252287<br>18> ets:info(grid, size).      <br>1000000<br>19> <br>19> grid ! stop.               <br>stop<br>20> <br>

20> <br>20> grid:init_grid(bag).       <br><0.86.0><br>21> grid:add_cells(1000, 1000).<br>1248606<br>22> grid:add_cells(1000, 1000).<br>1247905<br>23> grid:add_cells(1000, 1000).<br>1345457<br>24> ets:info(grid, size).      <br>

3000000<br><br>%%------------------------ grid.erl --------------------<br>-module(grid).<br>-compile(export_all).<br><br>init_grid(Type) -><br>    proc_lib:spawn(?MODULE, grid_owner, [Type]).<br><br>grid_owner(Type) -><br>

    ets:new(grid, [named_table, public, Type]),<br>    register(grid, self()),<br>    receive<br>        stop -><br>            ok<br>    end.<br><br>add_cells(Num_rows, Num_cols) -><br>    Start = now(),<br>    add_to_cell(Num_rows, Num_cols),<br>

    End = now(),<br>    timer:now_diff(End, Start).<br><br>add_to_cell(0, _) -><br>    ok;<br>add_to_cell(Row_num, Num_cols) -><br>    add_to_row(Row_num, Num_cols),<br>    add_to_cell(Row_num - 1, Num_cols).<br><br>

add_to_row(_, 0) -><br>    ok;<br>add_to_row(Row_num, Col_num) -><br>    ets:insert(grid, {{Row_num, Col_num}, os:timestamp()}),<br>    add_to_row(Row_num, Col_num - 1).<br><br></div></div>