Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Xanthir
My HERO!!!
Posts: 5292
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Thu Feb 15, 2018 1:05 am UTC

Yeah, a dict just connects keys to values. Values can be anything, keys are anything "hashable" (strings, numbers, tuples of those, and some other things).

An array is basically just a dict that only accept integer keys, and only in a certain range - it just connects the numbers 0, 1, 2, etc to values.

You just use different syntax to define/refer to them. Previous posts already went into detail about what sort of dict you'd want to use - probably with keys that are 3-tuples for the coordinates, like `{(0,0,0): 0, (0,0,1): 0, ...}`; I won't repeat the previous posts here. To get/set them you can still use the `a[foo]` syntax, but it'll look like `a[0,0,1] = 2` (set the key (0,0,1) to the value 2), instead of your current drilling down into a multidimensional array like `a[0][0][1] = 2` (look up the value at index 0, then the value at index 0 of the subarray, then the value at index 1 of the sub-subarray, and set it to 2).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Flumble
Yes Man
Posts: 1998
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Thu Feb 15, 2018 2:45 am UTC

Assuming that cells are either alive or dead, I'd go with sets. Sets are simple things that hold a bunch of items. For example, a set in which each item is the coordinate of a live cell. So the question "is the cell at (x,y,z) alive or dead?" becomes "does the coordinate (x,y,z) exist in the set of alive cells or not?". And birthing/killing cells becomes a matter of adding/deleting coordinates to/from the set.

The example below also adds some functional programming to the mix leading to only a few (>5) lines of code:

Code: Select all

# in haskell typology: getNeighbours :: Coordinate -> Set Coordinate
def getNeighbours(coordinate):
    (x,y,z) = coordinate # python 3 doesn't allow deconstructing a tuple in the parameter definition, so it needs its own line
    return frozenset({(x+dx,y+dy,z+dz) for dx in [-1,0,1] for dy in [-1,0,1] for dz in [-1,0,1] if not dx == dy == dz == 0}) # butifel
    # also, if you want a wrapping field or dead boundaries or whatever, this is the place to go

# in haskell typology: evolveState :: Set Coordinate -> Set Coordinate
def evolveState(oldAlive):
    newAlive = set() # starting with a blank slate (practice may show that copying the old state and adding/deleting some elements performs better)
    activeCells = oldAlive.union(*map(getNeighbours, oldAlive)) # such ugly notation to take the union of a couple of sets (also simply assuming that all live cells and their neighbours may change; this may be optimized)

    for cell in activeCells:
        aliveNeighbours = sum(1 for neighbour in getNeighbours(cell) if neighbour in oldAlive)
        if aliveNeighbours == 5 or (cell in oldAlive and 1 < aliveNeighbours < 8): # copied a rule from the blogosphere
            newAlive.add(cell) # I would've gone for `newAlive = newAlive.union({cell})` if it weren't both less readable and significantly slower because python won't realize that it can reuse the set instead of making a modified copy

    return frozenset(newAlive) # just pretend it was a frozen set all along

def __main__():
    alive = someInitialLiveCells # like `frozenset({(-1, 0, 0), (0, -1, 0), (0, 0, 0), (0, 1, 0), (1, -1, 0), (1, 1, 0)})`

    for generation in range(1, 1001):
        alive = evolveState(alive)
        somehowShowThisState(generation, alive) # like... I dunno, I avoid graphics libraries, and 3D data doesn't translate to text output nicely

It becomes more readable if you remove the comments, except for the oldAlive.union(*map(getNeighbours, oldAlive)), which is alive ∪ { N | N ∈ getNeighbours(A), A ∈ alive } or "grab all the alive cells and all their surrounding cells".
I have no idea about the performance of this thing, though I expect something of an O(n²) time per iteration because of the way the active cells are decided.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1420
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Coding: Fleeting Thoughts

Postby Xenomortis » Tue Mar 27, 2018 12:30 pm UTC

*Spends a few days writing code at work*

Code: Select all

me@work:project$ sloccount src
...
Total Physical Source Lines of Code (SLOC) = 700
Development Effort Estimate, Person-Years (Person-Months) = 0.14 (1.65)
...
Total Estimated Cost to Develop = $18,578

So where's my cut of that $18k?
Image

Tub
Posts: 381
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Mar 27, 2018 1:09 pm UTC

There's extensive documentation about the calculation and interpretation of those values. I bet you haven't produced a single UML diagram, barely did any testing, and there's zero documentation, so your 700 loc aren't finished yet.

Sloccount is also highly inaccurate in small projects. Writing the first 700 lines for a new project is cheap (In java, you can write 700 loc just by clicking "create new empty project"!). On the other hand, try getting 700 lines of code commited to the linux kernel, see if you can do it in less than 1.65 months.


Then again, $18k sounds much better, so run with it. Apparently I've been producing 2 man-years worth of code in half a man-year, so I'm going to ask for a 300% raise tomorrow.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11078
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Tue Mar 27, 2018 1:21 pm UTC

Lines of code have negative value. Every line of code added to our code base is a liability that will cost us money every year until the code base goes under.

Negative lines of code, now that is quality stuff.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1420
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Coding: Fleeting Thoughts

Postby Xenomortis » Tue Mar 27, 2018 1:58 pm UTC

Tub wrote:There's extensive documentation about the calculation and interpretation of those values. I bet you haven't produced a single UML diagram, barely did any testing, and there's zero documentation, so your 700 loc aren't finished yet.

To be fair, it has had zero testing.
And basically no error handling.
Also ANSI C.

Yakk wrote:Lines of code have negative value. Every line of code added to our code base is a liability that will cost us money every year until the code base goes under.

Negative lines of code, now that is quality stuff.

There's probably more than one git repo at work where my "Lines Added minus Lines Deleted" statistic is negative.
Image

User avatar
raudorn
Posts: 353
Joined: Mon Jun 13, 2011 11:59 am UTC

Re: Coding: Fleeting Thoughts

Postby raudorn » Wed Apr 04, 2018 4:00 pm UTC

Ciber wrote:Lately I have been working on force directed graph layouts. Currently trying to port (is that the right word here?) my naive implementation to numpy because with the 400 node, 900 link test graph I'm using it takes several seconds per iteration.

Uhm, I may be a bit late to the party here, but are you still working on this? I'm asking because I just came out of the end-of-semester slog and both force directed graph layouts and general spatial data structures are still fresh in my mind.

Basically, the best approaches I know boil down to desperately avoiding O(N²) runtime and bring it down to O(N*log(N)). Also cutting the number of iterations down can help, but that usually grows slower than the cost of each iteration anyway.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Fleeting Thoughts

Postby You, sir, name? » Fri Apr 13, 2018 7:23 pm UTC

I'm between stuff to do at work, so I've been reading papers about Haskell and implementing the ideas as haskell:y as possible in Java.

Works... surprisingly well once you find a middle road between Java's clunkiness and Haskell's weirdness. But now I have a expressive powerful monadic parser library cooking based on Hutton & Meijer's paper. Took some head scratching before I figured out how to express chainl1 and chainr1, but in the end the were pretty clean too.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3391
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Coding: Fleeting Thoughts

Postby Soupspoon » Fri Apr 13, 2018 10:35 pm UTC

I was browsing a computing magazine in the supermarket, the other day (wondering whether to buy it for a couple the whatever-you-call-clickbait-when-it's-on-a-magazine-cover items) and one thing that (subsequent to the original interest) caught my eye was a suggestion to try Ada, as a strong-typed overloadable language that people might prefer to Haskell.

I have to say, Ada was the most tortuous of the strongly-typed languages that I've 'learnt'. It looks like the IDE surrounding the suggested Ada compiler does solve a lot of the issues I had with the (probably) emacs-editing I did, back in the day, but I still have bad memories of its awkwardness, compared to my experience around the same time with Forth, LISP, Fortran and even COBOL. Heck, I'd even prefer to write my missile-flight controller modules1 in Redcode, if I could make it sufficiently Imp-proof!

Anyway, just thought I'd open the vent, slightly, on this long internal simmering disquiet. It quite possibly was the reason I was driven to particularly like Perl, and I'll leave it up to you whether this was ultimately a very good consequence (for me and/or the world at large) or a very bad one (ditto). The Ada of 2018 may even be worth a new try, I suppose, although I've probably forgotten more about it than I ever learnt in the first place (as the post-'80s implemention doubtless was revised and contemperaneously restyled several times to address problems such as I might have identified for myself) so I might effectively be starting from scratch again.


1 The alleged historic reasoning behind its belligerent awkwardness to use. Though I personally think someone didn't like female programmers, and so wanted to blacken Countess Lovelace's name, rather than insult Grace Hopper.

gd1
Posts: 160
Joined: Wed Nov 14, 2012 5:42 am UTC

Re: Coding: Fleeting Thoughts

Postby gd1 » Sun Jul 29, 2018 10:37 am UTC

Dungeon siege 1

[t:template,n:spell_sky_turret_lightning]
{
category_name = "magic";
doc = "spell sky turret lightning";
specializes = base_spell_good;
[aspect]
{
gold_value = 206;
}
[attack]
{
damage_max = 0;
damage_min = 0;
}
[common]
{
description = "Expels a split of lightning at the Target.";
screen_name = "Turret Lightning";
}
[gui]
{
active_icon = b_gui_ig_i_ic_sp_038;
inventory_icon = b_gui_ig_i_ic_sp_038_inv;
}
[magic]
{
attack_damage_modifier_max = ((#magic+1)*3.17+5)*(1+((1/(#magic+8))+.041));
attack_damage_modifier_min = ((#magic+1)*3.17+5)*(1-((1/(#magic+8))+.041));
cast_range = 54;
cast_reload_delay = 0.01;
effect_duration = 500000;
mana_cost = 1;
mana_cost_modifier = (#magic*0)+1;
max_level = 27000;
required_level = 90;
requires_line_of_sight = false;
speed_bias = 1;
target_type_flags = tt_conscious_enemy | tt_unconscious_enemy | tt_breakable;
usage_context_flags = uc_offensive;
cast_sub_animation = 0;
}
[spell_turret]
{
initial_delay = 0.01;
lightning_dur = 0.01;
shot_rate = 0.01;
effect_script = gom_turret_lightning;
charge_effect = gom_turret_lightning_charge;
}
}

Not even remotely fun, but fun to think about.
There is no emotion more useless in life than hate.

Tub
Posts: 381
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Jul 31, 2018 11:43 am UTC

Has anyone found a valid use case for a WeakMap in JavaScript?

It's supposed to prevent memory leaks, by allowing you to attach data to objects without leaking the data. The example for a key is often a DOM element, because those tend to disappear every now and then.

Code: Select all

let wm = new WeakMap();
let e = document.getElementById('foo');
wm.set(e, {
  private_data: 1
})

There. The private data can be reclaimed by the GC when the element disappears, so there's no memory leak.

But there wasn't any memory leak in the legacy variant, either:

Code: Select all

const KEY = '_private_data';
let e = document.getElementById('foo');
e[KEY] = {
  private_data: 1
}

No leak, though the additional property may mess up for...in loops or something; it's not properly hidden. But another ES6 feature does fix that:

Code: Select all

const KEY = Symbol('private data');


So.. why would I use a WeakMap to associate data with an object when I can use a Symbol?


Considering that a WeakMap has no size and is not iterable, I don't see any other use than associating data to an object. It's intentionally impossible to use a weakmap to detect when an object was garbage collected.

User avatar
Xanthir
My HERO!!!
Posts: 5292
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Tue Jul 31, 2018 4:30 pm UTC

Note that you *can* retrieve all the Symbols attached to an object; they're not "hidden" in any way whatsoever, they're just guaranteed to never collide with anything else unless you specifically use the same Symbol object. So if you really do have some private data to associate, you can't attach it with a Symbol.

That said, *most* of the time using a Symbol or a WeakMap is just a choice of how you want to interact with the data; whether it makes more sense to think of it as a property of the object or as data collected into a map.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tub
Posts: 381
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Jul 31, 2018 5:39 pm UTC

I'm aware, but being collision-free and non-enumerable is enough to prevent accidental bugs when multiple separate modules mess with the same object.

You can access or change private members in Java with the reflection API, but we still consider them private. You can mangle symbol properties in JavaScript using getOwnPropertySymbols(), but unless someone hands you the symbol as part of an API contract, you have no idea what the associated data means, and you know you shouldn't access it. That's private enough for me.

I suppose WeakMap has its uses if you use Object.freeze() a lot, or if you want to delete associated data from all objects (just delete the WeakMap). It's just that I have seen zero use cases where it would prevent memory leaks as advertised. It certainly won't help me prevent the memory leaks I'm facing right now.

Tub
Posts: 381
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Jul 31, 2018 8:57 pm UTC

I've done some benchmarks.

Code: Select all

const LOOPS = 10000000;
const ITERATIONS = 10;

(function() {
   const PROP = '_private_data';
   let o = {};
   bench('prop-single',
      function() {
         o[PROP] = {
            a: 1,
            b: 1
         };
      },
      function() {
         let p = o[PROP];
         let sum = p.a + p.b;
         p.a = p.b;
         p.b = sum;
      }
   );
   console.log(o[PROP].a);
})();

(function() {
   const PROP_A = '_private_data_a';
   const PROP_B = '_private_data_b';
   let o = {};
   bench('prop-multi',
      function() {
         o[PROP_A] = 1;
         o[PROP_B] = 1;
      },
      function() {
         let sum = o[PROP_A] + o[PROP_B];
         o[PROP_A] = o[PROP_B];
         o[PROP_B] = sum;
      }
   );
   console.log(o[PROP_A]);
})();


(function() {
   const PROP = Symbol();
   let o = {};
   bench('symbol-single',
      function() {
         o[PROP] = {
            a: 1,
            b: 1
         };
      },
      function() {
         let p = o[PROP];
         let sum = p.a + p.b;
         p.a = p.b;
         p.b = sum;
      }
   );
   console.log(o[PROP].a);
})();

(function() {
   const PROP_A = Symbol();
   const PROP_B = Symbol();
   let o = {};
   bench('symbol-multi',
      function() {
         o[PROP_A] = 1;
         o[PROP_B] = 1;
      },
      function() {
         let sum = o[PROP_A] + o[PROP_B];
         o[PROP_A] = o[PROP_B];
         o[PROP_B] = sum;
      }
   );
   console.log(o[PROP_A]);
})();


(function() {
   let wm = new WeakMap();
   let o = {};
   bench('weakmap-single',
      function() {
         wm.set(o, {
            a: 1,
            b: 1
         });
      },
      function() {
         let p = wm.get(o);
         let sum = p.a + p.b;
         p.a = p.b;
         p.b = sum;
      }
   );
   console.log(wm.get(o).a);
})();

(function() {
   let wm_a = new WeakMap();
   let wm_b = new WeakMap();
   let o = {};
   bench('weakmap-multi',
      function() {
         wm_a.set(o, 1);
         wm_b.set(o, 1);
      },
      function() {
         let sum = wm_a.get(o) + wm_b.get(o);
         wm_a.set(o, wm_b.get(o));
         wm_b.set(o, sum);
      }
   );
   console.log(wm_a.get(o));
})();

function bench(name, init, func) {
   let times = [];
   let t = Date.now();
   for (let i = 0; i < ITERATIONS; i++) {
      init();
      for (let l = 0; l < LOOPS; l++) {
         func();
      }
      let t2 = Date.now();
      times.push(t2 - t);
      t = t2;
   }
   let avg = times.reduce((a, e) => a + e) / times.length;
   console.log(name, times, avg);
}


Code: Select all

prop-single [ 115, 114, 101, 100, 101, 100, 101, 101, 101, 100 ] 103.4
prop-multi [ 332, 309, 290, 293, 292, 294, 292, 293, 284, 293 ] 297.2
symbol-single [ 232, 227, 226, 226, 226, 226, 227, 227, 226, 225 ] 226.8
symbol-multi [ 253, 239, 241, 240, 264, 251, 241, 240, 240, 248 ] 245.7
weakmap-single [ 464, 460, 469, 467, 465, 459, 457, 457, 457, 456 ] 461.1
weakmap-multi [ 4180, 4278, 3888, 3791, 3743, 3762, 3700, 3697, 3856, 3701 ] 3859.6


I'm not sure why the first one is faster, but the WeakMap variants are slowest in all engines I've tested (those numbers are nodejs v10.5)


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 11 guests