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: 5281
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: 1990
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: 1412
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: 373
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: 11077
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: 1412
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: 351
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: 3086
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.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests