| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

Nobody gives a shit; Lepton Decay Irregularity; An Easier Way; Julia's BinDeps (aka How To Install Cairo); Good Example Of Good Police Work (And Anonymity Being Hard); Best Santiago Burgers; Also; Michael Emmerich (Vibrator Translator) Interview (Japanese Books); Clarice Lispector (Brazillian Writer); Books On Evolution; Looks like Ara (Modular Phone) is dead; Index - Translations From Chile; More Emotion in Chilean Wines; Week 7; Aeon Magazine (Science-ish); QM, Deutsch, Constructor Theory; Interesting Talk Transcripts; Interesting Suggestion Of Election Fraud; "Hard" Books; Articles or Papers on depolarizing the US; Textbook for "QM as complex probabilities"; SFO Get Libor Trader (14 years); Why Are There Still So Many Jobs?; Navier Stokes Incomplete; More on Benford; FBI Claimed Vandalism; Architectural Tessellation; Also: Go, Blake's 7; Delusions of Gender (book); Crypto AG DID work with NSA / GCHQ; UNUMS (Universal Number Format); MOOCs (Massive Open Online Courses); Interesting Looking Game; Euler's Theorem for Polynomials; Weeks 3-6; Reddit Comment; Differential Cryptanalysis For Dummies; Japanese Graphic Design; Books To Be Re-Read; And Today I Learned Bugs Need Clear Examples; Factoring a 67 bit prime in your head; Islamic Geometric Art; Useful Julia Backtraces from Tasks; Nothing, however, is lost with less discomfort than that which, when lost, cannot be missed; Article on Didion; Cost of Living by City; British Slavery; Derrida on Metaphor; African SciFi; Traits in Julia; Alternative Japanese Lit; Pulic Key as Address (Snow); Why Information Grows; The Blindness Of The Chilean Elite; Some Victoriagate Links; This Is Why I Left StackOverflow; New TLS Implementation; Maths for Physicists; How I Am 8; 1000 Word Philosophy; Cyberpunk Reading List; Detailed Discussion of Message Dispatch in ParserCombinator Library for Julia; FizzBuzz in Julia w Dependent Types; kokko - Design Shop in Osaka; Summary of Greece, Currently; LLVM and GPUs; See Also; Schoolgirl Groyps (Maths); Japanese Lit; Another Example - Modular Arithmetic; Music from United; Python 2 and 3 compatible alternative.; Read Agatha Christie for the Plot; A Constructive Look at TempleOS; Music Thread w Many Recommendations; Fixed Version; A Useful Julia Macro To Define Equality And Hash; k3b cdrom access, OpenSuse 13.1; Week 2; From outside, the UK looks less than stellar; Huge Fonts in VirtualBox; Keen - Complex Emergencies; The Fallen of World War II; Some Spanish Fiction; Calling C From Fortran 95; Bjork DJ Set; Z3 Example With Python; Week 1; Useful Guide To Starting With IJulia; UK Election + Media; Review: Reinventing Organizations; Inline Assembly With Julia / LLVM; Against the definition of types; Dumb Crypto Paper; The Search For Quasi-Periodicity...; Is There An Alternative To Processing?; CARDIAC (CARDboard Illustrative Aid to Computation); The Bolivian Case Against Chile At The Hague; Clear, Cogent Economic Arguments For Immigration; A Program To Say If I Am Working; Decent Cards For Ill People

© 2006-2015 Andrew Cooke (site) / post authors (content).

Reduced Range Sudoku Solver

From: "andrew cooke" <andrew@...>

Date: Sun, 27 May 2007 09:37:38 -0400 (CLT)

As noted in the previous threads -
http://www.acooke.org/cute/CommunityS0.html
http://www.acooke.org/cute/ParallelSu0.html - this still doesn't converge
(in a reasonable amount of time).  However, for those that are interested
the code is now much cleaner and includes "range narrowing" as suggested
by Jonathan Sillito.


-module(light).

-export([start/0, starting/3]).

-define(CELL_TIMEOUT_MIN, 1).
-define(CELL_TIMEOUT_MAX, 10).
-define(DISPLAY_COUNT, 100).
-define(CONTROL_TIMEOUT, 10000).
-define(RANGE, lists:seq(1, 9)).
-define(GREEDINESS, 0.9).
-define(INTEREST, 1).

-record(cell, {locn, comp, cmty, rnge=?RANGE}).

solve(Puzzle, File) ->
    {ok, Log} = file:open(File, [write]),
    Cells = [{X, Y} || Y <- ?RANGE, X <- ?RANGE],
    application:start(sasl),     % debug info for failed processes
    register(ctrl, self()),
    [new_cell(Puzzle, Cell, Log) || Cell <- Cells],
    broadcast(Cells, start),
    ok = wait_to_complete(Cells, Log, now(), 0, 0, 0, 0),
    broadcast(Cells, sleep),
    Result = result(Cells),
    broadcast(Cells, stop),
    Result.

broadcast(Cells, Message) ->
    io:fwrite("broadcast ~p~n", [Message]),
    [address(Cell) ! Message || Cell <- Cells].

address(Locn) ->
    list_to_atom(lists:flatten(io_lib:format("~p", [Locn]))).

new_cell(Puzzle, Locn, Log) ->
    {Value, Weight} = initialise(Puzzle, Locn),
    io:fwrite(Log, "~p.~n", [{Locn, Value, Weight}]),
    Community = community(Locn),
    Cell = #cell{locn = Locn,
                 comp = competitors(Locn, Community),
                 cmty = Community},
    register(address(Locn),
             proc_lib:spawn(light, starting, [Cell, Value, Weight])).

initialise(Puzzle, Locn) ->
    case gb_trees:is_defined(Locn, Puzzle) of
        true -> {gb_trees:get(Locn, Puzzle), certain};
        false -> {unknown(Locn, Puzzle), 0}
    end.

unknown(Locn, Puzzle) ->
    Known = [gb_trees:get(L, Puzzle) ||
                L <- community(Locn), gb_trees:is_defined(L, Puzzle)],
    Rest = lists:subtract(?RANGE, Known),
    Index = 1 + length([L || L <- community(Locn), L < Locn,
                             not gb_trees:is_defined(L, Puzzle)]),
    lists:nth(Index, Rest).

community({X,Y}) ->
    CornerX = 3 * ((X - 1) div 3),
    CornerY = 3 * ((Y - 1) div 3),
    lists:usort([{XX, YY} || XX <- [CornerX + P || P <- [1, 2, 3]],
                             YY <- [CornerY + Q || Q <- [1, 2, 3]],
                             {XX, YY} /= {X, Y}]).

competitors({X, Y}, Community) ->
    [{XX, Y} || XX <- ?RANGE,
                XX /= X, not contains(Community, {XX,Y})]
        ++ [{X, YY} || YY <- ?RANGE,
                       YY /= Y, not contains(Community, {X,YY})].

contains([], _Value) -> false;
contains([Value|_Tail], Value) -> true;
contains([_Value|Tail], Value) -> contains(Tail, Value).

init_random(Cell) ->
    {X, Y} = Cell#cell.locn,
    {_, _, T} = now(),
    random:seed(X, Y, T).

random_pause() ->
    ?CELL_TIMEOUT_MIN
        + trunc(random:uniform() * (?CELL_TIMEOUT_MAX - ?CELL_TIMEOUT_MIN)).


% states

starting(Cell, Value, Weight) ->
    report_state(Cell, starting),
    init_random(Cell),
    receive
        start -> direct(fun searching/3, Cell, Value, Weight)
    end.

sleeping(Cell, Value, Weight) ->
    report_state(Cell, sleeping),
    receive
        stop -> ok;
        {swap, _} = Swap ->
            reject_swap(fun sleeping/3, Cell, Value, Weight, Swap);
        {assert, _} = Assert ->
            reject_assert(fun sleeping/3, Cell, Value, Weight, Assert);
        report ->
            report(fun sleeping/3, Cell, Value, Weight);
        status ->
            status(fun sleeping/3, Cell, Value, Weight)
    end.

searching(Cell, Value, Weight) ->
    report_state(Cell, searching),
    receive
        sleep ->
            direct(fun sleeping/3, Cell, Value, Weight);
        report ->
            report(fun searching/3, Cell, Value, Weight);
        status ->
            status(fun searching/3, Cell, Value, Weight);

        % if we are certain, and our competitor is in conflict, deny them.
        {assert, {_From, Value, _Test}} = Assert when Weight == certain ->
            deny_assert(fun searching/3, Cell, Value, Weight, Assert);
        % if our competitor is certain reduce the available range and change
        {assert, {_From, Value, certain}} = Assert ->
            accept_assert(reduce_range(Cell, Value), Value, Weight, Assert);
        % decide on weights, but add flexibility
        {assert, {_From, Value, Test}} = Assert ->
            case you_win_anyway(Weight, Test) of
                true ->
                    accept_assert(Cell, Value, Weight, Assert);
                false ->
                    deny_assert(fun searching/3, Cell, Value, Weight, Assert)
            end;
        % consistent, so increase our weight
        {assert, {_From, Other, _Test}} = Assert when Value =/= Other ->
            accept_assert(Cell, Value, earn(Weight), Assert);

        % refuse to swap if our value is certain
        {swap, _} = Swap when Weight == certain ->
            reject_swap(fun searching/3, Cell, Value, Weight, Swap);
        % otherwise, accept the swap if weights ok, or flexible
        {swap, {_From, New, YourWeight, Range}} = Swap ->
            case do_swap(Cell, Value, Weight, New, YourWeight, Range) of
                true ->
                    accept_swap(Cell, Value, Swap);
                false ->
                    reject_swap(fun searching/3, Cell, Value, Weight, Swap)
            end;

        % discard responses to an assert interrupted by swap
        reject_assert ->
            direct(fun searching/3, Cell, Value, Weight);
        {accept_assert, _} ->
            direct(fun searching/3, Cell, Value, Weight);
        {deny_assert, _} ->
            direct(fun searching/3, Cell, Value, Weight);

        % fail on other
        Message ->
            erlang:error("Unexpected message", [Message])
    after
        random_pause() ->
            assert(Cell, Value, Weight)
    end.

swapping(Cell, Old, Weight) ->
    report_state(Cell, swapping),
    receive
        report ->
            report(fun swapping/3, Cell, Old, Weight);
        status ->
            status(fun swapping/3, Cell, Old, Weight);
        {assert, _} = Assert ->
            reject_assert(fun swapping/3, Cell, Old, Weight, Assert);
        {accept_swap, New} ->
            new_value(Cell, Old, New);
        {swap, _} = Swap ->
            reject_swap(fun swapping/3, Cell, Old, Weight, Swap);
        % this used to restart a new swap, but the system would lock after
        % around 1 million exchanges.  instead, to avoid deadlock (all
        % trying to swap, we leave to a later assertion.
        reject_swap ->
            direct(fun searching/3, Cell, Old, Weight);
        % discard responses to an assert interrupted by swap
        reject_assert ->
            direct(fun swapping/3, Cell, Old, Weight);
        {accept_assert, _} ->
            direct(fun swapping/3, Cell, Old, Weight);
        {deny_assert, _} ->
            direct(fun swapping/3, Cell, Old, Weight);
        % this would be dangerous if not for the fact that sleep
        % cannot return to searching.
        sleep ->
            direct(fun sleeping/3, Cell, Old, Weight);
        Message ->
            erlang:error("Unexpected message", [Message])
    end.

asserting(Cell, Value, Weight) ->
    report_state(Cell, asserting),
    receive
        % refuse to swap if our value is certain
        {swap, _} = Swap when Weight == certain ->
            reject_swap(fun asserting/3, Cell, Value, Weight, Swap);
        % swap takes priority over assertion
        {swap, {_From, New, YourWeight, Range}} = Swap ->
            case do_swap(Cell, Value, Weight, New, YourWeight, Range) of
                true ->
                    accept_swap(Cell, Value, Swap);
                false ->
                    reject_swap(fun asserting/3, Cell, Value, Weight, Swap)
            end;
        sleep ->
            direct(fun sleeping/3, Cell, Value, Weight);
        report ->
            report(fun asserting/3, Cell, Value, Weight);
        status ->
            status(fun asserting/3, Cell, Value, Weight);
        reject_assert ->
            direct(fun searching/3, Cell, Value, Weight);
        % have to change value by swapping with someone else
        {deny_assert, Value} ->
            swap(Cell, Value, Weight);
        % ...but not if they were denying some old value
        {deny_assert, Other} when Other =/= Value ->
            direct(fun asserting/3, Cell, Value, Weight);
        % yield increases weight if it matches our value
        {accept_assert, Value}->
            direct(fun searching/3, Cell, Value, earn(Weight));
        % ..but otherwise discard and keep waiting
        {accept_assert, Other} when Other =/= Value->
            direct(fun asserting/3, Cell, Value, Weight);
        {assert, _} = Assert ->
            reject_assert(fun asserting/3, Cell, Value, Weight, Assert);
        Message ->
            erlang:error("Unexpected message", [Message])
    end.

do_swap(Cell, Old, MyWeight, New, YourWeight, Range) ->
    contains(Range, Old) and
        contains(Cell#cell.rnge, New) and
        you_win_anyway(MyWeight, YourWeight).

you_win_anyway(MyWeight, YourWeight) when YourWeight > MyWeight -> true;
you_win_anyway(_MyWeight, _YourWeight) -> random:uniform() > ?GREEDINESS.


% transitions

direct(Next, Cell, Value, Weight) -> Next(Cell, Value, Weight).

report(Next, Cell, Value, Weight) ->
    ctrl ! {result, {Value, Weight}},
    Next(Cell, Value, Weight).

status(Next, Cell, Value, Weight) ->
    error_logger:info_msg("~p = ~p (~p)",
                          [Cell#cell.locn, Value, Weight]),
    Next(Cell, Value, Weight).

% reject is when we're otherwise busy
reject_assert(Next, Cell, Value, Weight, {assert, {From, _Other, _Test}}) ->
    From ! reject_assert,
    Next(Cell, Value, Weight).

% deny is when it's wrong (distinction important to sender)
deny_assert(Next, Cell, Value, Weight, {assert, {From, Value, _Test}}) ->
    From ! {deny_assert, Value},
    Next(Cell, Value, Weight).

% second clause when values don't match
accept_assert(Cell, Value, Weight, {assert, {From, Value, _Test}}) ->
    From ! {accept_assert, Value},
    swap(Cell, Value, Weight);
accept_assert(Cell, Value, Weight, {assert, {From, Other, _Test}}) ->
    From ! {accept_assert, Other},
    searching(Cell, Value, Weight).

accept_swap(Cell, Old, {swap, {From, New, _Weight, _Range}}) ->
    debug("~p accept swap from ~p~n", [Cell#cell.locn, From]),
    ctrl ! {new_value, {Cell#cell.locn, Old, New}},
    From ! {accept_swap, Old},
    new_value(Cell, Old, New).

reject_swap(Next, Cell, Value, Weight,
            {swap, {From, _Other, _Weight, _Range}}) ->
    debug("~p no swap to ~p~n", [Cell#cell.locn, From]),
    ctrl ! {conflict, Cell#cell.locn},
    From ! reject_swap,
    Next(Cell, Value, Weight).

new_value(Cell, Old, New) ->
    debug("~p ~p -> ~p~n", [Cell#cell.locn, Old, New]),
    searching(Cell, New, 0).

swap(Cell, Value, Weight) ->
    Partner = random_neighbour(Cell),
    debug("~p swap ~p with ~p?~n", [Cell#cell.locn, Value, Partner]),
    Partner ! {swap, {self(), Value, Weight, Cell#cell.rnge}},
    swapping(Cell, Value, Weight).

assert(Cell, Value, Weight) ->
    Competitor = random_competitor(Cell),
    debug("~p assert ~p to ~p~n", [Cell#cell.locn, Value, Competitor]),
    Competitor ! {assert, {self(), Value, Weight}},
    asserting(Cell, Value, Weight).


% weight increases when a cell's value is confirmed by other cells.
% the aim is to encourage the growth of a set of mutually consistent
% values.
earn(certain) -> certain;
earn(Weight) -> Weight + ?INTEREST.

% sometimes we can exclude a value from those open to us.
reduce_range(Cell, Value) ->
    Cell#cell{rnge = [V || V <- Cell#cell.rnge, V =/= Value]}.

random_competitor(Cell) ->
    address(lists:nth(random:uniform(length(Cell#cell.comp)),
                      Cell#cell.comp)).

random_neighbour(Cell) ->
    address(lists:nth(random:uniform(length(Cell#cell.cmty)),
                      Cell#cell.cmty)).

report_state(Cell, State) ->
    debug("~p -> ~p~n", [Cell#cell.locn, State]).

debug(_Format, _Values) ->
%    io:fwrite(Format, Values).
    ok.

% shutdown and reporting

wait_to_complete(Cells, Log, Start, Swap, Cycles, ?DISPLAY_COUNT,
CycleFail) ->
    NewCycles = Cycles + 1,
    Attempts = NewCycles * ?DISPLAY_COUNT,
    % broadcast(Cells, status),
    {_Values, Puzzle} = result(Cells),
    TotalSuccess = 100 * Swap / Attempts,
    CycleSuccess = 100 * (?DISPLAY_COUNT - CycleFail) / ?DISPLAY_COUNT,
    Secs = trunc(timer:now_diff(now(), Start) / 1000000),
    error_logger:info_msg("~nreport ~p after ~ps "
                          "(greediness: ~4.2f; interest: ~p)~n"
                          "total of ~p swaps in ~p attempts~n"
                          "average swap success rate: ~4.1f%~n"
                          "success rate in last ~p attempts: ~4.1f%~n"
                          "~n~s~n(snapshot is not instantaneous)~n~n",
                          [NewCycles, Secs,
                           ?GREEDINESS, ?INTEREST,
                           Swap, Attempts,
                           TotalSuccess,
                           ?DISPLAY_COUNT, CycleSuccess,
                           ascii(Puzzle)]),
    wait_for_tick(Cells, Log, Start, Swap, NewCycles, 0, 0);
wait_to_complete(Cells, Log, Start, Swap, Cycles, CycleTotal, CycleFail) ->
    wait_for_tick(Cells, Log, Start, Swap, Cycles, CycleTotal, CycleFail).

wait_for_tick(Cells, Log, Start, Swap, Cycles, CycleTotal, CycleFail) ->
    receive
        {new_value, {Locn, _Old, New}} ->
            io:fwrite(Log, "~p.~n", [{Locn, New}]),
            wait_to_complete(Cells, Log, Start, Swap + 1,
                             Cycles, CycleTotal + 1, CycleFail);
        {conflict, _Locn} ->
            wait_to_complete(Cells, Log, Start, Swap,
                             Cycles, CycleTotal + 1, CycleFail + 1)
    after
        ?CONTROL_TIMEOUT ->
            file:close(Log),
            ok
    end.

result(Cells) ->
    io:fwrite("collecting result~n"),
    Values = [],
    Puzzle = gb_trees:empty(),
    collect_reports(Values, Puzzle, Cells).

collect_reports(Values, Puzzle, []) -> {Values, Puzzle};
collect_reports(Values, Puzzle, [Cell|Cells]) ->
    address(Cell) ! report,
    receive
        {result, {Value, Weight}} ->
            collect_reports([{Cell, Value, Weight}|Values],
                            gb_trees:insert(Cell, Value, Puzzle), Cells)
    end.


% formatting

value(Puzzle, Locn) -> integer_to_list(gb_trees:get(Locn, Puzzle)).

values(N, Puzzle, X, Y) ->
    lists:flatten([value(Puzzle, {XX,Y}) || XX <- lists:seq(X, X + N - 1)]).

line(Puzzle, Y) ->
    util:join_with([values(3, Puzzle, X, Y) || X <- [1, 4, 7]], " ").

lines(N, Puzzle, Y) ->
    util:join_with([line(Puzzle, YY) || YY <- lists:seq(Y, Y + N - 1)],
                   "\n") ++ "\n".

ascii(Puzzle) ->
    util:join_with([lines(3, Puzzle, Y) || Y <- [1, 4, 7]],
                   lists:duplicate(11, $\ ) ++ "\n").


% format used at http://norvig.com/sudoku.html
norvig(List, File) ->
    Cells = [{X, Y} || Y <- ?RANGE, X <- ?RANGE],
    Clean = [L || L <- List,
                  (L == $.) or ((L >= $0) and (L =< $9))],
    Puzzle = lists:foldl(fun set_known/2, gb_trees:empty(),
                         lists:zip(Clean, Cells)),
    solve(Puzzle, File).

set_known({N, _Locn}, Puzzle) when (N < $1) or (N > $9) -> Puzzle;
set_known({CharValue, Locn}, Puzzle) ->
    gb_trees:insert(Locn, list_to_integer([CharValue]), Puzzle).

start() ->
    {_R, P} = norvig("4.. ... 8.5"
                     ".3. ... ..."
                     "... 7.. ..."
                     ".2. ... .6."
                     "... .8. 4.."
                     "... .1. ..."
                     "... 6.3 .7."
                     "5.. 2.. ..."
                     "1.4 ... ...", "light.txt"),
    io:fwrite("~s", [ascii(P)]).

% c(light), {R,P} = light:norvig(), io:fwrite("~s", [light:ascii(P)]).

% lessons learned
% - tag messages
% - use {tag, payload} to allow easy matching
% - keep clear priority in protocol
% - match failures
% - avoid insisting on a response (tight loops)

Typical Report

From: "andrew cooke" <andrew@...>

Date: Sun, 27 May 2007 09:41:07 -0400 (CLT)

=INFO REPORT==== 27-May-2007::09:40:52 ===

report 1283 after 888s (greediness: 0.90; interest: 1)
total of 12246 swaps in 128300 attempts
average swap success rate:  9.5%
success rate in last 100 attempts: 10.0%

497 126 835
631 895 742
258 734 916

829 457 163
316 982 457
745 316 298

982 643 571
573 291 684
164 578 329

(snapshot is not instantaneous)

Hot Damn Fuck Me Backwards Woot!

From: "andrew cooke" <andrew@...>

Date: Sun, 27 May 2007 12:34:47 -0400 (CLT)

It just converged!

=INFO REPORT==== 27-May-2007::11:37:25 ===

report 9327 after 7880s (greediness: 0.90; interest: 1)
total of 86858 swaps in 932700 attempts
average swap success rate:  9.3%
success rate in last 100 attempts:  2.0%

417 369 825
632 158 947
958 724 316

825 437 168
791 586 432
346 912 759

289 643 571
573 291 684
164 875 293

(snapshot is not instantaneous)

broadcast sleep
collecting result
broadcast stop
417 369 825
632 158 947
958 724 316

825 437 169
791 586 432
346 912 758

289 643 571
573 291 684
164 875 293

Ahem.  Excuse the language.

Andrew

Aborted Output with Greediness=0.5

From: "andrew cooke" <andrew@...>

Date: Sun, 27 May 2007 18:07:16 -0400 (CLT)

Going to try 0.99 instead.  Already longer in time and may more swaps than
0.9.


report 59282 after 16456s (greediness: 0.50; interest: 1)
total of 1209866 swaps in 5928200 attempts
average swap success rate: 20.4%
success rate in last 100 attempts: 29.0%

472 169 835
831 825 796
956 734 124

825 497 563
691 382 412
743 516 789

289 643 571
573 291 648
164 875 392

(snapshot is not instantaneous)

Andrew

Greediness 0.75

From: "andrew cooke" <andrew@...>

Date: Sun, 27 May 2007 22:04:10 -0400 (CLT)

Killed at:

report 35899 after 13594s (greediness: 0.75; interest: 1)
total of 522184 swaps in 3589900 attempts
average swap success rate: 14.5%
success rate in last 100 attempts: 15.0%

467 921 835
239 468 217
815 735 946

928 974 163
371 386 452
645 512 798

982 643 971
573 291 684
164 857 523

(snapshot is not instantaneous)

Andrew

Convergence with Greediness 0.95

From: "andrew cooke" <andrew@...>

Date: Mon, 28 May 2007 06:22:10 -0400 (CLT)

This was running longer than the 0.5 and 0.75 cases, so doesn't say much
(and that's ignoring the small number stats...).  Still, it's nice to have
another convergence.

report 14263 after 22069s (greediness: 0.95; interest: 1)
total of 83859 swaps in 1426300 attempts
average swap success rate:  5.9%
success rate in last 100 attempts:  2.0%

417 369 825
238 158 947
956 724 316

825 437 169
791 586 432
346 912 758

289 643 571
573 291 684
164 875 293

(snapshot is not instantaneous)

broadcast sleep
collecting result
broadcast stop
417 369 825
632 158 947
958 724 316

825 437 169
791 586 432
346 912 758

289 643 571
573 291 684
164 875 293

Timing Data

From: "andrew cooke" <andrew@...>

Date: Mon, 4 Jun 2007 06:32:18 -0400 (CLT)

Here are some results for different values of the Greediness.  I've seen
convergence from 0.81 to 0.95.  There's a lot of scatter but the minimum
time seems to be around 0.87.  Note that some "no convergence" are for
very short times and there's very little testing of small (less than 0.8)
values.


[not converged]
report 32827 after 73477s (greediness: 0.99; interest: 1)
total of 98289 swaps in 3282700 attempts
average swap success rate:  3.0%
success rate in last 100 attempts:  9.0%

[not converged]
report 38185 after 71706s (greediness: 0.97; interest: 1)
total of 172440 swaps in 3818500 attempts
average swap success rate:  4.5%
success rate in last 100 attempts:  7.0%

[converged]
report 14263 after 22069s (greediness: 0.95; interest: 1)
total of 83859 swaps in 1426300 attempts
average swap success rate:  5.9%
success rate in last 100 attempts:  2.0%

[converged]
report 77110 after 90562s (greediness: 0.93; interest: 1)
total of 591911 swaps in 7711000 attempts
average swap success rate:  7.7%
success rate in last 100 attempts: 15.0%

[converged]
report 47199 after 49666s (greediness: 0.91; interest: 1)
total of 380760 swaps in 4719900 attempts
average swap success rate:  8.1%
success rate in last 100 attempts: 10.0%

[converged]
report 9327 after 7880s (greediness: 0.90; interest: 1)
total of 86858 swaps in 932700 attempts
average swap success rate:  9.3%
success rate in last 100 attempts:  2.0%

[converged]
report 32218 after 25576s (greediness: 0.89; interest: 1)
total of 307132 swaps in 3221800 attempts
average swap success rate:  9.5%
success rate in last 100 attempts:  9.0%

[converged]
report 24497 after 16786s (greediness: 0.87; interest: 1)
total of 256732 swaps in 2449700 attempts
average swap success rate: 10.5%
success rate in last 100 attempts: 12.0%

[not converged]
report 56168 after 32334s (greediness: 0.85; interest: 1)
total of 640289 swaps in 5616800 attempts
average swap success rate: 11.4%
success rate in last 100 attempts:  6.0%

[converged]
report 37874 after 19319s (greediness: 0.83; interest: 1)
total of 451522 swaps in 3787400 attempts
average swap success rate: 11.9%
success rate in last 100 attempts: 13.0%

[converged]
report 124689 after 58531s (greediness: 0.81; interest: 1)
total of 1587776 swaps in 12468900 attempts
average swap success rate: 12.7%
success rate in last 100 attempts: 15.0%

[not converged]
report 226865 after 100423s (greediness: 0.80; interest: 1)
total of 2952758 swaps in 22686500 attempts
average swap success rate: 13.0%
success rate in last 100 attempts:  9.0%

[not converged]
report 35899 after 13594s (greediness: 0.75; interest: 1)
total of 522184 swaps in 3589900 attempts
average swap success rate: 14.5%
success rate in last 100 attempts: 15.0%

[not converged]
report 59282 after 16456s (greediness: 0.50; interest: 1)
total of 1209866 swaps in 5928200 attempts
average swap success rate: 20.4%
success rate in last 100 attempts: 29.0%

Andrew

Comment on this post